SCTF 2024 Crypto

Signin

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
from sage.all import *
from Crypto.Util.number import *
from hashlib import md5

class RSA():
    def __init__(self, nbits):
        self.nbits = nbits
        self.p, self.q = self.getPrimes()
        self.n = self.p*self.q
        self.Gift = self.Gift()
        self.priv, self.pub = self.keyGen()
        
    
    def getPrimes(self):
        nbits = self.nbits
        p = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        q = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        while p == q:
            q = random_prime(2^(nbits-1),lbound=2^(nbits-2))
        return p,q
    
    def Gift(self):
        p,q = self.p, self.q
        return (p^2 + p + 1)*(q^2 + q + 1)
    
    def keyGen(self):
        nbits = self.nbits
        while True:
            d = randint(2^(nbits//4),2^(nbits//2))
            if gcd(d,self.Gift) != 1:
                d = randint(2^(nbits//4),2^(nbits//2))
            e = pow(d,-1,self.phi)
            return (self.p,self.q,self.n,e,d),(self.n,e)
    

RRR = RSA(512)

bp = long_to_bytes(int(RRR.p))
FLAG = 'SCTF{'+md5(bp).hexdigest()+'}'


print(f'N = {RRR.n}')
print(f'e = {RRR.pub[1]}')

'''
N = 32261421478213846055712670966502489204755328170115455046538351164751104619671102517649635534043658087736634695616391757439732095084483689790126957681118278054587893972547230081514687941476504846573346232349396528794022902849402462140720882761797608629678538971832857107919821058604542569600500431547986211951
e = 334450817132213889699916301332076676907807495738301743367532551341259554597455532787632746522806063413194057583998858669641413549469205803510032623432057274574904024415310727712701532706683404590321555542304471243731711502894688623443411522742837178384157350652336133957839779184278283984964616921311020965540513988059163842300284809747927188585982778365798558959611785248767075169464495691092816641600277394649073668575637386621433598176627864284154484501969887686377152288296838258930293614942020655916701799531971307171423974651394156780269830631029915305188230547099840604668445612429756706738202411074392821840
'''

$e$ 的数量级大概是 $N$ 的两倍，直接连分数分解 $e$ 和 $N^2$ 就可以得到 $k$ 和 $d$ ，然后解方程得到 $p$ 和 $q$

Whisper

Two public key certificates were monitored. And Mr. Dual intercepted a ciphertext. Just when he was in the rough, a Careless Whisper told that the length of a key parameter is carelessly set to 345 bits.

题目给了两个pem文件，解析出来两个 $e$ 是相同的，通过上文的题目描述可以知道有一个关键参数是345位，可能是 $\phi(N)$ ，还有一个人名 Dual 提示了一下，直接套板子

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
from sage.all import *
import itertools

# display matrix picture with 0 and X
def matrix_overview(BB):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += ' ' if BB[ii, jj] == 0 else 'X'
            if BB.dimensions()[0] < 60:
                a += ' '
        print(a)

def dual_rsa_liqiang_et_al(e, n1, n2, delta, mm, tt):
    '''
    Attack to Dual RSA: Liqiang et al.'s attack implementation
    '''

    N = (n1 + n2) // 2
    A = ZZ(floor(N^0.5))

    _XX = ZZ(floor(N^delta))
    _YY = ZZ(floor(N^0.5))
    _ZZ = ZZ(floor(N^(delta - 1./4)))
    _UU = _XX * _YY + 1

    # Find a "good" basis satisfying d = a1 * l'11 + a2 * l'21
    M = Matrix(ZZ, [[A, e], [0, n1]])
    B = M.LLL()
    l11, l12 = B[0]
    l21, l22 = B[1]
    l_11 = ZZ(l11 / A)
    l_21 = ZZ(l21 / A)

    modulo = e * l_21
    F = Zmod(modulo)

    PR = PolynomialRing(F, 'u, x, y, z')
    u, x, y, z = PR.gens()

    PK = PolynomialRing(ZZ, 'uk, xk, yk, zk')
    uk, xk, yk, zk = PK.gens()

    # For transform xy to u-1 (unravelled linearlization)
    PQ = PK.quo(xk*yk+1-uk)

    f = PK(x*(n2 + y) - e*l_11*z + 1)
    fbar = PQ(f).lift()

    # Polynomial construction
    gijk = {}
    for k in range(0, mm + 1):
        for i in range(0, mm - k + 1):
            for j in range(0, mm - k - i + 1):
                gijk[i, j, k] = PQ(xk^i * zk^j * PK(fbar) ^ k * modulo^(mm-k)).lift()

    hjkl = {}
    for j in range(1, tt + 1):
        for k in range(floor(mm / tt) * j, mm + 1):
            for l in range(0, k + 1):
                hjkl[j, k, l] = PQ(yk^j * zk^(k-l) * PK(fbar) ^ l * modulo^(mm-l)).lift()

    monomials = []
    for k in gijk.keys():
        monomials += gijk[k].monomials()
    for k in hjkl.keys():
        monomials += hjkl[k].monomials()

    monomials = sorted(set(monomials))[::-1]
    assert len(monomials) == len(gijk) + len(hjkl)  # square matrix?
    dim = len(monomials)

    # Create lattice from polynomial g_{ijk} and h_{jkl}
    M = Matrix(ZZ, dim)
    row = 0
    for k in gijk.keys():
        for i, monomial in enumerate(monomials):
            M[row, i] = gijk[k].monomial_coefficient(monomial) * monomial.subs(uk=_UU, xk=_XX, yk=_YY, zk=_ZZ)
        row += 1
    for k in hjkl.keys():
        for i, monomial in enumerate(monomials):
            M[row, i] = hjkl[k].monomial_coefficient(monomial) * monomial.subs(uk=_UU, xk=_XX, yk=_YY, zk=_ZZ)
        row += 1

    matrix_overview(M)
    print('=' * 128)

    # LLL
    B = M.LLL()

    matrix_overview(B)

    # Construct polynomials from reduced lattices
    H = [(i, 0) for i in range(dim)]
    H = dict(H)
    for j in range(dim):
        for i in range(dim):
            H[i] += PK((monomials[j] * B[i, j]) / monomials[j].subs(uk=_UU, xk=_XX, yk=_YY, zk=_ZZ))
    H = list(H.values())

    PQ = PolynomialRing(QQ, 'uq, xq, yq, zq')
    uq, xq, yq, zq = PQ.gens()

    # Inversion of unraveled linearization
    for i in range(dim):
        H[i] = PQ(H[i].subs(uk=xk*yk+1))

    # Calculate Groebner basis for solve system of equations
    I = Ideal(*H[1:20])
    g = I.groebner_basis('giac')[::-1]
    mon = list(map(lambda t: t.monomials(), g))

    PX = PolynomialRing(ZZ, 'xs')
    xs = PX.gen()

    x_pol = y_pol = z_pol = None

    for i in range(len(g)):
        if mon[i] == [xq, 1]:
            print(g[i] / g[i].lc())
            x_pol = g[i] / g[i].lc()
        elif mon[i] == [yq, 1]:
            print(g[i] / g[i].lc())
            y_pol = g[i] / g[i].lc()
        elif mon[i] == [zq, 1]:
            print(g[i] / g[i].lc())
            z_pol = g[i] / g[i].lc()

    if x_pol is None or y_pol is None or z_pol is None:
        print('[-] Failed: we cannot get a solution...')
        return

    x0 = x_pol.subs(xq=xs).roots()[0][0]
    y0 = y_pol.subs(yq=xs).roots()[0][0]
    z0 = z_pol.subs(zq=xs).roots()[0][0]

    # solution check
    assert f(x0 * y0 + 1, x0, y0, z0) % modulo == 0

    a0 = z0
    a1 = (x0 * (n2 + y0) + 1 - e * l_11 * z0) / (e * l_21)

    d = a0 * l_11 + a1 * l_21
    return d

if __name__ == '__main__':
    delta = 0.334
    mm = 4
    tt = 2

    n1 = int("1b 5d 4f e0 aa 67 82 e2 75 d4 ce 12 a6 d5 75 62 ef bb e7 db 6f 52 77 25 5b 89 17 29 bf a2 a1 8d 3e db 49 84 3d 79 89 a3 7b 95 16 be 2d f8 ca 93 90 58 e6 5f 64 b5 fb 20 71 be a4 f5 f8 d1 39 28 95 b3 2b f0 37 7d 99 f4 f7 99 79 12 5e 5d b0 1c db 50 80 a1 c2 d6 65 c9 ac 31 b5 82 30 25 49 9c 95 13 27 7b ae 5e 7a 84 6c d2 71 c4 39 6e 2b a2 19 02 0e 58 a9 05 5c b1 8a 28 d3 6a 00 bf 71 7b ".replace(" ",""),16)
    e = int("07 9f 5c cc 66 57 67 b4 a2 57 e5 c1 ff 56 e9 80 3d f2 e5 65 03 02 da ad 42 01 05 fe 67 24 47 74 3b d3 f0 be a1 c4 6a 49 87 93 2e 9a 88 6c a8 7a 7a fd 77 96 ab f1 e5 62 9c 49 86 fe 4f 22 e8 9c dc e7 ab b0 66 24 46 51 46 a2 e2 b6 ca 9a b3 19 6c ea b7 46 79 74 c1 dc 45 60 8a 20 04 11 b2 91 fd af 99 f7 d8 0d ce 4d b3 56 6f 4a 9e 2e 57 4c 62 24 cd 07 d8 06 38 d2 8f 78 20 bc f4 b4 91 43".replace(" ",""),16)
    n2 = int("07 1c 32 4e 87 69 49 31 87 c1 5f 72 d5 cc 69 57 29 b4 84 88 ee 3f bd 01 db 00 d5 c4 78 f0 8c 7c f3 20 93 ba 61 74 50 51 d3 e9 d1 69 52 3a a9 14 38 18 1f 47 67 9a ff 5e dd 22 95 0f 74 a1 eb 14 43 32 0a aa 5d 97 f5 c1 e8 1b 5e f9 a3 e6 9b a6 69 ab c4 c6 c4 b4 05 f5 08 8a 60 3a 74 f9 bc ef 88 82 3b 45 23 57 41 14 c8 10 60 08 38 72 81 96 f8 e5 e0 d4 ae ee ea b7 9d d8 68 3a 72 f3 c0 17 ".replace(" ",""),16)
    c = bytes_to_long(open("ciphertext.txt",'rb').read())

    d = dual_rsa_liqiang_et_al(e, n1, n2, delta, mm, tt)
    print(f"d = {d}")
    m1 = pow(c,int(d),n1)
    m2 = pow(c,int(d),n2)
    flag1 = long_to_bytes(m1)
    flag2 = long_to_bytes(m2)
    
    print(flag1 + flag2)

不完全阻塞干扰

抽象文件，要手动提取参数，提取出来是 $p$ 和 $q$ 的高位，二元coppersmith

LinearARTs

复现
#复现
SCTF 2024 Crypto
http://example.com/2025/01/23/SCTF 2024 Crypto/
作者
John Doe
发布于
2025年1月23日
更新于
2025年1月23日
许可协议