第二届长城杯

known_phi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
from Crypto.Util.number import getPrime, bytes_to_long, inverse, long_to_bytes
from Crypto.PublicKey import DSA
from hashlib import sha256
import random
from secret import flag

def gen(a):
    p = getPrime(a) 
    q = getPrime(a)
    r = getPrime(a)
    x = getPrime(a)
    n = p*q*r*x
    phi = (p-1)*(q-1)*(r-1)*(x-1)

    return n, phi, [p, q, r, x]

def sign(m, k, x, p, q, g):
    hm = bytes_to_long(sha256(m).digest())
    r = pow(g, k, p) % q
    s = (hm + x*r) * inverse(k, q) % q

    return r,s

e = 65537
a = 256
x = bytes_to_long(flag)
# print(x)

n, phi, n_factors = gen(a)
n_factors = sorted(n_factors)
print(f'n = {n}')
print(f'phi = {phi}')
m1 = long_to_bytes(n_factors[0] + n_factors[3])
m2 = long_to_bytes(n_factors[1] + n_factors[2])
# print(f'm1 = {m1}')
# print(f'm2 = {m2}')

key = DSA.generate(int(2048))
q = key.q
p = key.p
g = key.g
assert q > x
k = random.randint(1, q-1)
r1, s1 = sign(m1, k, x, p, q, g)
r2, s2 = sign(m2, k, x, p, q, g)
# print(f'k = {k}')
print(f'q = {q}')
print(f's1 = {s1}')
print(f'r1 = {r1}')
print(f's1 = {s1}')
print(f'r2 = {r2}')
print(f's2 = {s2}')

'''
n = 104228256293611313959676852310116852553951496121352860038971098657350022997841589403091722735802150153734050783858816709247647536393314564077002364012463220999962114186339228164032217361145009468516448617173972835797623658266515762201804936729547278758839604969469770650218191574897316410254695420895895051693
phi = 104228256293611313959676852310116852553951496121352860038971098657350022997837434645707418205268240995284026522165519145773852565112344453740579163420312890001524537570675468046604347184376661743552799809753709321949095844960227307733389258381950812717245522599433727311919405966404418872873961877021696812800
q = 24513014442114004234202354110477737650785387286781126308169912007819
s1 = 764450933738974696530033347966845551587903750431946039815672438603
r1 = 8881880595434882344509893789458546908449907797285477983407324325035
s1 = 764450933738974696530033347966845551587903750431946039815672438603
r2 = 8881880595434882344509893789458546908449907797285477983407324325035#r1==r2
s2 = 22099482232399385060035569388467035727015978742301259782677969649659
'''

个人认为题目分为两部分，第一部分通过n和phi分解n，第二部分则是DSA。

分解n找到了相应的论文和代码（3-540-36492-7_25.pdf (springer.com)）

DSA部分比较简单，是私钥k复用问题，有如下式子
$$
\begin{cases}
s_1=(hm_1+x*r_1)k^{-1}\quad mod\ q\\
s_2=(hm_2+x*r_2)k^{-1}\quad mod\ q
\end{cases}
$$
两式相乘有
$$
s_1*(hm_2+x*r_2)k^{-1}≡s_2*(hm_1+x*r_1)k^{-1}\quad mod\ q
$$
化简
$$
x≡(hm_1*s_2-hm_2*s_1)*(r_2*s_1-r_1*s_2)^{-1}\quad mod\ q
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.PublicKey import DSA
from hashlib import sha256
from gmpy2 import is_prime, invert
from math import gcd
from random import randrange

def factorize_multi_prime(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method works for a modulus consisting of any number of primes, but is considerably be slower than factorize.
    More information: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3)
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors
    """
    prime_factors = set()
    factors = [N]
    while len(factors) > 0:
        # Element to factorize.
        N = factors[0]

        w = randrange(2, N - 1)
        i = 1
        while phi % (2 ** i) == 0:
            sqrt_1 = pow(w, phi // (2 ** i), N)
            if sqrt_1 > 1 and sqrt_1 != N - 1:
                # We can remove the element to factorize now, because we have a factorization.
                factors = factors[1:]

                p = gcd(N, sqrt_1 + 1)
                q = N // p

                if is_prime(p):
                    prime_factors.add(p)
                elif p > 1:
                    factors.append(p)

                if is_prime(q):
                    prime_factors.add(q)
                elif q > 1:
                    factors.append(q)

                # Continue in the outer loop
                break

            i += 1

    return list(prime_factors)

n = 104228256293611313959676852310116852553951496121352860038971098657350022997841589403091722735802150153734050783858816709247647536393314564077002364012463220999962114186339228164032217361145009468516448617173972835797623658266515762201804936729547278758839604969469770650218191574897316410254695420895895051693
phi = 104228256293611313959676852310116852553951496121352860038971098657350022997837434645707418205268240995284026522165519145773852565112344453740579163420312890001524537570675468046604347184376661743552799809753709321949095844960227307733389258381950812717245522599433727311919405966404418872873961877021696812800
q = 24513014442114004234202354110477737650785387286781126308169912007819
s1 = 764450933738974696530033347966845551587903750431946039815672438603
r1 = 8881880595434882344509893789458546908449907797285477983407324325035
r2 = 8881880595434882344509893789458546908449907797285477983407324325035 #r1==r2
s2 = 22099482232399385060035569388467035727015978742301259782677969649659

n_factors = factorize_multi_prime(n,phi)
n_factors = sorted(n_factors)
m1 = long_to_bytes(n_factors[0] + n_factors[3])
m2 = long_to_bytes(n_factors[1] + n_factors[2])
hm1 = bytes_to_long(sha256(m1).digest())
hm2 = bytes_to_long(sha256(m2).digest())

tmp = (hm1*s2 - hm2*s1)
inv = invert(r2*s1-r1*s2, q)
x = inv*tmp%q
print(long_to_bytes(x))

RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
from Crypto.Util.number import bytes_to_long, getPrime, isPrime
import win32gui,PIL,numpy,operator,pymouse
from Crypto.Random import random
from random import getrandbits
from sympy.ntheory.residue_ntheory import nthroot_mod
from sympy import nextprime
from secret import flag

def get_primes(m):
    p = getPrime(Bits)
    pl = p & int('f'*(m//4), 16)#p&(2**(200)-1)
    q = (getrandbits(Bits - m) << m)^^pl#rand+p的低200bit
    while not isPrime(q):
        q = (getrandbits(Bits - m) << m)^^pl
    return (p, q)

def get_key(p, q, delta, beta, Bits):
    phi = (p - 1) * (q - 1)
    d1 = getPrime(floor(2 * Bits * delta))
    e1 = inverse_mod(d1, phi)
    d2 = nextprime(d1 ^^ getrandbits(floor(2 * Bits * beta)))
    e2 = inverse_mod(d2, phi)
    d3 = getPrime(floor(2 * Bits * delta))
    e3 = inverse_mod(d3, phi)
    return (e1, e2, e3, d1, d2, d3)

    
if __name__ == '__main__':
    Bits = 1024 
    alpha = 0.098
    delta = 0.536
    beta = delta
    gamma = 1
    m = floor(2 * alpha * Bits)#200bit<n^(1/4)

    p, q = get_primes(m)
    n = p * q
    assert n % 2^3 == 1
    u0 = nthroot_mod(n, 2, 2^m, all_roots=False)
    v0 = (2*u0 + ((n - u0^2) * inverse_mod(u0, 2^(2*m)) % 2^(2*m)))
    e1, e2, e3, d1, d2, d3 = get_key(p, q, delta, beta, Bits)

    flag = bytes_to_long(flag)
    c = pow(flag, e3, n)
    l0 = d1 - d2

    print(f'N = {hex(n)}')
    print(f'e1 = {hex(e1)}')
    print(f'e2 = {hex(e2)}')
    print(f'e3 = {hex(e3)}')
    print(f'c = {hex(c)}')
    print(f'v0 = {hex(v0)}')
    print(f'l0 = {hex(l0)}')

# N = 0x62c048bc886075bffb9ad01255786dd8ef2480ba510f13689c1e84ffaaf21dfb5695a4d83f4ba22093bdd75bfc8f5979185d29724ecccf045e1857b1b2a4757dd82dc44318c054c9fce9bc451e6beecb97bbda6562420fc8c295521c5455443413f90403cf1af6271fb6d2d54378b86ced18ae6844a877890ea853a215880a09c68c517a75c1183c067b706ce630f3f0913591f7354cfa60c8f6b7ab2f15e466a1ea6e8034417a5fc3c11b8ba746596c22c734b09257e9a6fb18358738d416eda0ba0e7b028dd2d550b1e018b180916ac25f47910657a5db2410946c0593b7e23ed1659a811083f363ad4eb65642091a040befbd643089bbee376634d2394d11
# e1 = 0x124241a12ea2be53f9b9b1fd92e10d089cfa32aa07e6c2cace848aaa6c73ff06d4c6c92b7d1f29160b2eef95a5f580915d3f15c0ea23975cbadfe8347a10daab2bd0827d7e909b329ec53c5eb306f0a5125b3817e7ea0c15b2317a46c36c4f34fc626dadc6c769bcc7be18ddf7954fae8dde3fd4ce3c5146c019bdb0d9552af1dc9ef7186e06b1d59e763fb05c7cd21fbb3f509fee52d4e24921ebfa76bb8302ea6760e92606e440907cc1c110946af53900904e84dbc309fcef15ea060c667070e5e0310891606df151609ff609bcc6125c6043c35119b25df78b4d5ca61ab6492753cc5e5b32e044fce0aeb0442464f36298add254e9fb6505fa4cddae1cf7
# e2 = 0x17b3937cec3ca5fdddad8db29c6dc4efae1408bf5b4aa2ff602112c50f302e9698c79c7ab79fef0210c621dcc218d91d358b7f93a978c4e3f2b982794697c4797cef89189d1464ed1c767bf72433092922352885f8e355952c558ad2c9ade58a19375ddc5dcf3f9fa28c68a5cff158734d94224b85f77bd939133f39ab7884ece61d9fb3496373008827c2ae694dfe7da08eee348ef99c3a6737a4b088b62978cf209ef3d1140a30d42872615b94378108266e3d344caf51b497a585a4b5ef8619cc46959bad9b89f59f36175fbf9b64363443f3f7743896c72a198decedf89c518fa07b1d401d0359578a4926b7d67de86232ee24751f17dafbc749c0783b33
# e3 = 0x5647c4490bda9e7e497651551600572c5ef4e2d889b9b1ba0e9a493660497e10877e975c01da9aebae5e3ba9aad976a1a783b39191e8fd799689dfa26b069264d60543602d514ac412ac75d827d67c78ad544bda633f0fa69fb5bbc37e0f6b95714576ff53bae3f7f991d143a4b1e841730d5d580d4effeb8fb02e8b3c3c9a1f1899d2eb411ce37f16d30cfa1f7af7322be4f42f5d012f484a1181fa4aa0b5f420a472030a5c08c80bff76ab82ef5768bfd495abcdc5f22aae1891561322dfb28ff63c4e467411c8b73c11d64b05f411e2a1de0c7754c6a62d1f72cded9e2592ccc21be3fce4ea6f083a617a246fd3fe464ef2487adbfabfb628c882ea991675
# c = 0x45f2ee650d622d1e0f0e2e2e861001e9866c541f9f1dd2ec1dec18194f8b7224914916ecd68bbc74b28a000d2664e671586aed63b54c0928a939caf28d39eeba03c0ce3afcf2cdc5805e8e2792d76e88545aa4dee11078ba1e2e5b56ee23d58e443d7aff180d4e7463ae66ea8e96e0c8d4e1443e7664b99599af14e591e28cf2f833bd30b44b89c396b5fc1ee81ea3f7bc08dab426b1871eb66829c81d57e2ebf5c7a3e9c593ce496f0b0c4237906b019ae75ca551d6b0b1adfe64958c2ead6c39e517eb75eaf4b4d72402bea40f043cf0a80317aa2f1a996c727e195e15f903c0cac618f668af1015ee479d1c7b1c1b370fd4a5a76f5bf295e6bd7d0f4ae56f
# v0 = 0x2c77a013f2595a90c4e10a53a0f863d02b361c7407dad7d59db7c98df427da00c8d8627dbaef9557279ca31227cdb402d2d2
# l0 = 0x3dbabf6ea5b801221c283bd234f04264d292c8f3048c8b59c21e003cda983a3a41e4392c6ea77a706631de60d261f2b367027e037d37fda5a13a8e01b2c6c0f48a3112315cffe7420a50a3ebada09aba61f8e6da793654a467b9f780c20c5085012e064ab9205c076073b4fb4895e01d0d568fd5c30159879180093855d39d5548a1389a94f57c680c

有等式如下
$$
\begin{cases}
e_1*d_1 ≡ 1\quad mod\ phi\\
e_2*d_2 ≡ 1\quad mod\ phi\\
d_1-d_2=l_0
\end{cases}
$$
化简有
$$
e_1*e_2*l_0 ≡ (e_2-e_1)\quad mod\ phi\quad ==>\quad k*phi=e_1*e_2*l_0 - (e_2 - e_1)
$$
在模为k*phi的域上，有
$$
e_3*d_3’≡1\quad mod\ (k*phi)\
$$
根据RSA的加解密公式推导有
$$
\begin{align}
c &≡ m^{e_3} \\
==>c^{d_3’} &≡ m^{e_3*d_3’}\\
&≡ m^{1+k_1*k*phi}\\
&≡ m^{1+K*phi}\\
&= m \quad mod\ (N)
\end{align}
$$

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import long_to_bytes, inverse

N = 0x62c048bc886075bffb9ad01255786dd8ef2480ba510f13689c1e84ffaaf21dfb5695a4d83f4ba22093bdd75bfc8f5979185d29724ecccf045e1857b1b2a4757dd82dc44318c054c9fce9bc451e6beecb97bbda6562420fc8c295521c5455443413f90403cf1af6271fb6d2d54378b86ced18ae6844a877890ea853a215880a09c68c517a75c1183c067b706ce630f3f0913591f7354cfa60c8f6b7ab2f15e466a1ea6e8034417a5fc3c11b8ba746596c22c734b09257e9a6fb18358738d416eda0ba0e7b028dd2d550b1e018b180916ac25f47910657a5db2410946c0593b7e23ed1659a811083f363ad4eb65642091a040befbd643089bbee376634d2394d11
e1 = 0x124241a12ea2be53f9b9b1fd92e10d089cfa32aa07e6c2cace848aaa6c73ff06d4c6c92b7d1f29160b2eef95a5f580915d3f15c0ea23975cbadfe8347a10daab2bd0827d7e909b329ec53c5eb306f0a5125b3817e7ea0c15b2317a46c36c4f34fc626dadc6c769bcc7be18ddf7954fae8dde3fd4ce3c5146c019bdb0d9552af1dc9ef7186e06b1d59e763fb05c7cd21fbb3f509fee52d4e24921ebfa76bb8302ea6760e92606e440907cc1c110946af53900904e84dbc309fcef15ea060c667070e5e0310891606df151609ff609bcc6125c6043c35119b25df78b4d5ca61ab6492753cc5e5b32e044fce0aeb0442464f36298add254e9fb6505fa4cddae1cf7
e2 = 0x17b3937cec3ca5fdddad8db29c6dc4efae1408bf5b4aa2ff602112c50f302e9698c79c7ab79fef0210c621dcc218d91d358b7f93a978c4e3f2b982794697c4797cef89189d1464ed1c767bf72433092922352885f8e355952c558ad2c9ade58a19375ddc5dcf3f9fa28c68a5cff158734d94224b85f77bd939133f39ab7884ece61d9fb3496373008827c2ae694dfe7da08eee348ef99c3a6737a4b088b62978cf209ef3d1140a30d42872615b94378108266e3d344caf51b497a585a4b5ef8619cc46959bad9b89f59f36175fbf9b64363443f3f7743896c72a198decedf89c518fa07b1d401d0359578a4926b7d67de86232ee24751f17dafbc749c0783b33
e3 = 0x5647c4490bda9e7e497651551600572c5ef4e2d889b9b1ba0e9a493660497e10877e975c01da9aebae5e3ba9aad976a1a783b39191e8fd799689dfa26b069264d60543602d514ac412ac75d827d67c78ad544bda633f0fa69fb5bbc37e0f6b95714576ff53bae3f7f991d143a4b1e841730d5d580d4effeb8fb02e8b3c3c9a1f1899d2eb411ce37f16d30cfa1f7af7322be4f42f5d012f484a1181fa4aa0b5f420a472030a5c08c80bff76ab82ef5768bfd495abcdc5f22aae1891561322dfb28ff63c4e467411c8b73c11d64b05f411e2a1de0c7754c6a62d1f72cded9e2592ccc21be3fce4ea6f083a617a246fd3fe464ef2487adbfabfb628c882ea991675
c = 0x45f2ee650d622d1e0f0e2e2e861001e9866c541f9f1dd2ec1dec18194f8b7224914916ecd68bbc74b28a000d2664e671586aed63b54c0928a939caf28d39eeba03c0ce3afcf2cdc5805e8e2792d76e88545aa4dee11078ba1e2e5b56ee23d58e443d7aff180d4e7463ae66ea8e96e0c8d4e1443e7664b99599af14e591e28cf2f833bd30b44b89c396b5fc1ee81ea3f7bc08dab426b1871eb66829c81d57e2ebf5c7a3e9c593ce496f0b0c4237906b019ae75ca551d6b0b1adfe64958c2ead6c39e517eb75eaf4b4d72402bea40f043cf0a80317aa2f1a996c727e195e15f903c0cac618f668af1015ee479d1c7b1c1b370fd4a5a76f5bf295e6bd7d0f4ae56f
v0 = 0x2c77a013f2595a90c4e10a53a0f863d02b361c7407dad7d59db7c98df427da00c8d8627dbaef9557279ca31227cdb402d2d2
l0 = 0x3dbabf6ea5b801221c283bd234f04264d292c8f3048c8b59c21e003cda983a3a41e4392c6ea77a706631de60d261f2b367027e037d37fda5a13a8e01b2c6c0f48a3112315cffe7420a50a3ebada09aba61f8e6da793654a467b9f780c20c5085012e064ab9205c076073b4fb4895e01d0d568fd5c30159879180093855d39d5548a1389a94f57c680c

kphi = e1*e2*l0 - (e2 - e1)
d3 = inverse(e3, kphi)
m = pow(c, d3, N)
print(long_to_bytes(m))
Crypto
#RSA
第二届长城杯
http://example.com/2022/09/12/CTF/第二届长城杯/
作者
gla2xy
发布于
2022年9月12日
许可协议