持续更新中~

1
from hashlib import md5
2
from Crypto.Cipher import AES
3
from Crypto.Util.Padding import unpad
4

5
k = bytes.fromhex("54686973497341555331323435363638")
6
IV = bytes.fromhex("496E697469616C697A6174696F6E2056")
7
c = bytes.fromhex("ae4ff1ccc900eb0ba99857c297cf0b73")
8
cipher = AES.new(k, AES.MODE_CBC, IV)
9
pt = unpad(cipher.decrypt(c), 16)
10
print("flag{" + md5(pt).hexdigest() + "}")
11
# flag{3f234da2fe6e8c189048e522b18fefed}

1
#!/usr/bin/python3.10
2
def Sn(i):
3
    s = ''
4
    while i != 0:
5
        digit = i & 0xff
6
        i >>= 8
7
        s += chr(digit)
8
    return s
9

10

11
def In(s):
12
    val = 0
13
    for i in range(len(s)):
14
        digit = ord(s[len(s) - i - 1])
15
        val <<= 8
16
        val |= digit
17
    return val
18

19

20
def egcd(a, b):
21
    if a == 0:
22
        return b, 0, 1
23
    else:
24
        g, y, x = egcd(b % a, a)
25
        return g, x - (b // a) * y, y
26

27

28
def add(a, b, p):
29
    if b == -1:
30
        return a
31
    if a == -1:
32
        return b
33
    x1, y1 = a
34
    x2, y2 = b
35
    x3 = ((x1 * x2 - x1 * y2 - x2 * y1 + 2 * y1 * y2) * mod_inv(x1 + x2 - y1 - y2 - 1, p)) % p
36
    y3 = ((y1 * y2) * mod_inv(x1 + x2 - y1 - y2 - 1, p)) % p
37
    return x3, y3
38

39

40
def double_add(a, p):
41
    return add(a, a, p)
42

43

44
def mod_inv(a, p):
45
    a %= p
46
    g, x, y = egcd(a, p)
47
    if g != 1:
48
        raise Exception('No inverse exists for %d mod %d' % (a, p))
49
    else:
50
        return x % p
51

52

53
def mod_mul(m, g, p):
54
    r = -1
55
    while m != 0:
56
        if m & 1:
57
            r = add(r, g, p)
58
        m >>= 1
59
        g = double_add(g, p)
60
    return r
61

62

63
def encrypt(message, key):
64
    return message ^ key
65

66

67
p = ...
68

69
g = (..., ...)
70

71
A = (..., ...)
72

73
B = (..., ...)
74

75
if __name__ == "__main__":
76
    from secret import aliceSecret, bobSecret, flag
77

78
    assert A == mod_mul(aliceSecret, g, p)
79
    assert B == mod_mul(bobSecret, g, p)
80

81
    aliceMS = mod_mul(aliceSecret, B, p)
82
    bobMS = mod_mul(bobSecret, A, p)
83
    assert aliceMS == bobMS
84
    masterSecret = aliceMS[0] * aliceMS[1]
85

86
    length = len(flag)
87
    encrypted_message = encrypt(In(flag), masterSecret)
88

89
    print("length = %d, encrypted_message = %d" % (length, encrypted_message))
90

91
# length = 62, encrypted_message = ...

1
# SageMath 10.7
2
from Crypto.Util.number import long_to_bytes
3

4
def map_v(point):
5
    x, y = R(point[0]), R(point[1])
6
    return (x - y - 1) / (x - y)
7

8
def map_w(point):
9
    x, y = R(point[0]), R(point[1])
10
    return y / (x - y)
11

12
p = ...
13
g = (..., ...)
14
A = (..., ...)
15
B = (..., ...)
16
encrypted_message = ...
17
R = Integers(p)
18
vg = map_v(g)
19
va = map_v(A)
20
vb = map_v(B)
21
wb = map_w(B)
22
alice_secret = discrete_log(va, vg)
23
vs = vb ** alice_secret
24
ws = wb ** alice_secret
25
Us = 1 / (1 - vs)
26
ys = ws * Us
27
xs = Us + ys
28
master_secret = int(xs) * int(ys)
29
decrypted_int = encrypted_message ^^ master_secret
30
print(long_to_bytes(decrypted_int).decode()[::-1])
31
# flag{Who_has_the_computer_organization_principle_in_the_exam?}

1
import libnum
2
from flag import *
3

4
m1 = libnum.s2n(flag[:21])
5
m2 = libnum.s2n(flag[21:])
6
p = libnum.generate_prime(1024)
7
q = libnum.generate_prime(1024)
8
e = 0x10001
9
n = p * q
10
h1 = pow(2025 * p + 2024 * q, 7717, n)
11
h2 = pow(2024 * p + 2025 * q, 8859, n)
12
c1 = pow(m1, e, n)
13
c2 = pow(m2, e, n)
14

15

16
print("h1=", h1)
17
print("h2=", h2)
18
print("n=", n)
19
print("c=", (c1 + c2))
20
print("leak=", (c1 * 2 - c2))
21
#output
22
# h1 = ...
23
# h2 = ...
24
# n = ...
25
# c = ...
26
# leak = ...

1
from gmpy2 import gcd, invert
2
from Crypto.Util.number import long_to_bytes
3

4
h1 = ...
5
h2 = ...
6
n = ...
7
c = ...
8
leak = ...
9
e, e1, e2 = 0x10001, 7717, 8859
10
c1 = (c + leak) // 3
11
c2 = (2 * c - leak) // 3
12
p = gcd(pow(2025, e1 * e2, n) * pow(h1, e2, n) - pow(2024, e1 * e2, n) * pow(h2, e1, n), n)
13
q = n // p
14
assert p * q == n
15
phi = (p - 1) * (q - 1)
16
d = invert(e, phi)
17
m1 = pow(c1, d, n)
18
m2 = pow(c2, d, n)
19
flag = long_to_bytes(m1) + long_to_bytes(m2)
20
print(flag.decode())
21
# flag{fc08e137-5be9-4677-a1f5-4e640223df0e}

1
from Crypto.Util.number import *
2
from secret import FLAG
3
p = getPrime(128)
4
step = len(FLAG) // 3
5
lcg = [bytes_to_long(FLAG[:step]), bytes_to_long(FLAG[step:2*step]), bytes_to_long(FLAG[2*step:])]
6
a = getPrime(80)
7
b = getPrime(80)
8
c = getPrime(80)
9
a = 678292774844628690689951
10
b = 799218428050845578943269
11
c = 871991670671866736323531
12
p = 226554022535584634512578046463759712133
13

14
for _ in range(10):
15
    new_state = (a*lcg[0] + b*lcg[1] + c*lcg[2]) % p
16
    lcg = lcg[1:] + [new_state]
17
    #print(lcg)
18
print(lcg)
19
print(a, b, c, p)

1
from Crypto.Util.number import long_to_bytes, inverse
2

3
lcg = [531812496965714475754459274425954913, 573493247306997567791036597408132959, 531874692922906583591521900672740733]
4
flag = long_to_bytes(lcg[0]) + long_to_bytes(lcg[1]) + long_to_bytes(lcg[2])
5
print(flag.decode())
6
# flag{try_to_transform_it_into_formulaic_form}
7
a = 678292774844628690689951
8
b = 799218428050845578943269
9
c = 871991670671866736323531
10
p = 226554022535584634512578046463759712133
11
a_inv = inverse(a, p)
12
for _ in range(10):
13
    new_state = (lcg[2] - lcg[1] * c - lcg[0] * b) * a_inv % p
14
    lcg = [new_state] + lcg[:-1]
15
print(long_to_bytes(lcg[0]), long_to_bytes(lcg[1]), long_to_bytes(lcg[2]))
16
# b'\x1a\xcapQ|\x12\x8fRD\xcd\xbcT;\x05~\x8c' b')X^;\xdd\x08\x1bv3"\xfe\x91<\xaf\x01U' b'\x896@\xcey\x87\xc7\xbc\xa0ox\xce\t\xc2?`'

1
from Crypto.Util.number import *
2
from secret import flag
3
# 生成1024位的大素数p和q
4
p = getPrime(1024)
5
q = getPrime(1024)
6

7
# 计算RSA模数n
8
n = p * q
9

10
d=getPrime(521)
11
e = inverse(d,(p-1)*(q-1))
12
flag_int = bytes_to_long(flag())
13
c = pow(flag_int, e, n)
14
# 生成提示信息1：p的高位部分（右移224位）
15
hint1 = p >> (1024-224)
16

17
# 生成提示信息2：q的高位部分（右移224位）
18
hint2 = q >> (1024-224)
19
print(f"n = {n}")
20
print(f"e = {e}")
21
print(f"c = {c}")
22
print(f"hint1 = {hint1}")
23
print(f"hint2 = {hint2}")
24
'''
25
n = ...
26
e = ...
27
c = ...
28
hint1 = ...  # p高位
29
hint2 = ...  # q高位
30
'''

1
# SageMath 10.7
2
from __future__ import print_function
3
import time
4

5
############################################
6
# Config
7
##########################################
8

9
"""
10
Setting debug to true will display more informations
11
about the lattice, the bounds, the vectors...
12
"""
13
debug = True
14

15
"""
16
Setting strict to true will stop the algorithm (and
17
return (-1, -1)) if we don't have a correct
18
upperbound on the determinant. Note that this
19
doesn't necesseraly mean that no solutions
20
will be found since the theoretical upperbound is
21
usualy far away from actual results. That is why
22
you should probably use `strict = False`
23
"""
24
strict = False
25

26
"""
27
This is experimental, but has provided remarkable results
28
so far. It tries to reduce the lattice as much as it can
29
while keeping its efficiency. I see no reason not to use
30
this option, but if things don't work, you should try
31
disabling it
32
"""
33
helpful_only = True
34
dimension_min = 7 # stop removing if lattice reaches that dimension
35

36
############################################
37
# Functions
38
##########################################
39

40
# display stats on helpful vectors
41
def helpful_vectors(BB, modulus):
42
    nothelpful = 0
43
    for ii in range(BB.dimensions()[0]):
44
        if BB[ii,ii] >= modulus:
45
            nothelpful += 1
46

47
    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
48

49
# display matrix picture with 0 and X
50
def matrix_overview(BB, bound):
51
    for ii in range(BB.dimensions()[0]):
52
        a = ('%02d ' % ii)
53
        for jj in range(BB.dimensions()[1]):
54
            a += '0' if BB[ii,jj] == 0 else 'X'
55
            if BB.dimensions()[0] < 60:
56
                a += ' '
57
        if BB[ii, ii] >= bound:
58
            a += '~'
59
        print(a)
60

61
# tries to remove unhelpful vectors
62
# we start at current = n-1 (last vector)
63
def remove_unhelpful(BB, monomials, bound, current):
64
    # end of our recursive function
65
    if current == -1 or BB.dimensions()[0] <= dimension_min:
66
        return BB
67

68
    # we start by checking from the end
69
    for ii in range(current, -1, -1):
70
        # if it is unhelpful:
71
        if BB[ii, ii] >= bound:
72
            affected_vectors = 0
73
            affected_vector_index = 0
74
            # let's check if it affects other vectors
75
            for jj in range(ii + 1, BB.dimensions()[0]):
76
                # if another vector is affected:
77
                # we increase the count
78
                if BB[jj, ii] != 0:
79
                    affected_vectors += 1
80
                    affected_vector_index = jj
81

82
            # level:0
83
            # if no other vectors end up affected
84
            # we remove it
85
            if affected_vectors == 0:
86
                print("* removing unhelpful vector", ii)
87
                BB = BB.delete_columns([ii])
88
                BB = BB.delete_rows([ii])
89
                monomials.pop(ii)
90
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
91
                return BB
92

93
            # level:1
94
            # if just one was affected we check
95
            # if it is affecting someone else
96
            elif affected_vectors == 1:
97
                affected_deeper = True
98
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
99
                    # if it is affecting even one vector
100
                    # we give up on this one
101
                    if BB[kk, affected_vector_index] != 0:
102
                        affected_deeper = False
103
                # remove both it if no other vector was affected and
104
                # this helpful vector is not helpful enough
105
                # compared to our unhelpful one
106
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
107
                    print("* removing unhelpful vectors", ii, "and", affected_vector_index)
108
                    BB = BB.delete_columns([affected_vector_index, ii])
109
                    BB = BB.delete_rows([affected_vector_index, ii])
110
                    monomials.pop(affected_vector_index)
111
                    monomials.pop(ii)
112
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
113
                    return BB
114
    # nothing happened
115
    return BB
116

117
"""
118
Returns:
119
* 0,0   if it fails
120
* -1,-1 if `strict=true`, and determinant doesn't bound
121
* x0,y0 the solutions of `pol`
122
"""
123
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
124
    """
125
    Boneh and Durfee revisited by Herrmann and May
126

127
    finds a solution if:
128
    * d < N^delta
129
    * |x| < e^delta
130
    * |y| < e^0.5
131
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
132
    """
133

134
    # substitution (Herrman and May)
135
    PR.<u, x, y> = PolynomialRing(ZZ)
136
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
137
    polZ = Q(pol).lift()
138

139
    UU = XX*YY + 1
140

141
    # x-shifts
142
    gg = []
143
    for kk in range(mm + 1):
144
        for ii in range(mm - kk + 1):
145
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
146
            gg.append(xshift)
147
    gg.sort()
148

149
    # x-shifts list of monomials
150
    monomials = []
151
    for polynomial in gg:
152
        for monomial in polynomial.monomials():
153
            if monomial not in monomials:
154
                monomials.append(monomial)
155
    monomials.sort()
156

157
    # y-shifts (selected by Herrman and May)
158
    for jj in range(1, tt + 1):
159
        for kk in range(floor(mm/tt) * jj, mm + 1):
160
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
161
            yshift = Q(yshift).lift()
162
            gg.append(yshift) # substitution
163

164
    # y-shifts list of monomials
165
    for jj in range(1, tt + 1):
166
        for kk in range(floor(mm/tt) * jj, mm + 1):
167
            monomials.append(u^kk * y^jj)
168

169
    # construct lattice B
170
    nn = len(monomials)
171
    BB = Matrix(ZZ, nn)
172
    for ii in range(nn):
173
        BB[ii, 0] = gg[ii](0, 0, 0)
174
        for jj in range(1, ii + 1):
175
            if monomials[jj] in gg[ii].monomials():
176
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
177

178
    # Prototype to reduce the lattice
179
    if helpful_only:
180
        # automatically remove
181
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
182
        # reset dimension
183
        nn = BB.dimensions()[0]
184
        if nn == 0:
185
            print("failure")
186
            return 0,0
187

188
    # check if vectors are helpful
189
    if debug:
190
        helpful_vectors(BB, modulus^mm)
191

192
    # check if determinant is correctly bounded
193
    det = BB.det()
194
    bound = modulus^(mm*nn)
195
    if det >= bound:
196
        print("We do not have det < bound. Solutions might not be found.")
197
        print("Try with highers m and t.")
198
        if debug:
199
            diff = (log(det) - log(bound)) / log(2)
200
            print("size det(L) - size e^(m*n) = ", floor(diff))
201
        if strict:
202
            return -1, -1
203
    else:
204
        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
205

206
    # display the lattice basis
207
    if debug:
208
        matrix_overview(BB, modulus^mm)
209

210
    # LLL
211
    if debug:
212
        print("optimizing basis of the lattice via LLL, this can take a long time")
213

214
    BB = BB.LLL()
215

216
    if debug:
217
        print("LLL is done!")
218

219
    # transform vector i & j -> polynomials 1 & 2
220
    if debug:
221
        print("looking for independent vectors in the lattice")
222
    found_polynomials = False
223

224
    for pol1_idx in range(nn - 1):
225
        for pol2_idx in range(pol1_idx + 1, nn):
226
            # for i and j, create the two polynomials
227
            PR.<w,z> = PolynomialRing(ZZ)
228
            pol1 = pol2 = 0
229
            for jj in range(nn):
230
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
231
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
232

233
            # resultant
234
            PR.<q> = PolynomialRing(ZZ)
235
            rr = pol1.resultant(pol2)
236

237
            # are these good polynomials?
238
            if rr.is_zero() or rr.monomials() == [1]:
239
                continue
240
            else:
241
                print("found them, using vectors", pol1_idx, "and", pol2_idx)
242
                found_polynomials = True
243
                break
244
        if found_polynomials:
245
            break
246

247
    if not found_polynomials:
248
        print("no independant vectors could be found. This should very rarely happen...")
249
        return 0, 0
250

251
    rr = rr(q, q)
252

253
    # solutions
254
    soly = rr.roots()
255

256
    if len(soly) == 0:
257
        print("Your prediction (delta) is too small")
258
        return 0, 0
259

260
    soly = soly[0][0]
261
    ss = pol1(q, soly)
262
    solx = ss.roots()[0][0]
263

264
    #
265
    return solx, soly
266
def example():
267
    ############################################
268
    # Problem to solve (edit the following values)
269
    ##########################################
270

271
    # the modulus
272
    N = ...
273

274
    # the public exponent
275
    e = ...
276

277
    # ciphertext
278
    c = ...
279

280
    ############################################
281
    # The hypothesis on the private exponent
282
    ##########################################
283
    # d is ~521-bit in the generation code
284
    # N is ~2048-bit, so delta around 521/2048 ~= 0.254
285
    # Keep < 0.292
286
    delta = 0.26
287

288
    ############################################
289
    # Lattice parameters
290
    ##########################################
291
    # Try slightly larger m than the toy example
292
    m = 5
293
    t = int((1-2*delta) * m)  # optimization from Herrmann and May
294

295
    # bounds
296
    X = 2*floor(N^delta)
297
    Y = floor(N^(1/2))
298

299
    ############################################
300
    # Don't touch anything below
301
    ##########################################
302

303
    # Problem put in equation
304
    P.<x,y> = PolynomialRing(ZZ)
305
    A = int((N+1)/2)
306
    pol = 1 + x * (A + y)
307

308
    # Checking bounds
309
    if debug:
310
        print("=== checking values ===")
311
        print("* delta:", delta)
312
        print("* delta < 0.292", delta < 0.292)
313
        print("* size of e:", int(log(e)/log(2)))
314
        print("* size of N:", int(log(N)/log(2)))
315
        print("* m:", m, ", t:", t)
316

317
    # boneh_durfee
318
    if debug:
319
        print("=== running algorithm ===")
320
        start_time = time.time()
321

322
    solx, soly = boneh_durfee(pol, e, m, t, X, Y)
323

324
    # found a solution?
325
    if solx > 0:
326
        print("=== solution found ===")
327

328
        d = int(pol(solx, soly) / e)
329
        print("private key found:", d)
330

331
        # decrypt
332
        m_int = pow(int(c), int(d), int(N))
333
        try:
334
            from Crypto.Util.number import long_to_bytes
335
            print(long_to_bytes(m_int).decode())
336
        except Exception:
337
            # fallback if pycryptodome not available in your Sage env
338
            print("m_int =", m_int)
339

340
    else:
341
        print("=== no solution was found ===")
342

343
    if debug:
344
        print(("=== %s seconds ===" % (time.time() - start_time)))
345

346
example()
347
# flag{please-put-this-one-in-sagamath}