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
| from math import isqrt
def long_to_bytes(n):
return n.to_bytes((n.bit_length() + 7) // 8, 'big')
def continued_fraction(n, d, max_terms=10000):
cf = []
while d != 0 and len(cf) < max_terms:
q = n // d
cf.append(q)
n, d = d, n - q * d
return cf
def convergents(cf):
h0, k0 = 0, 1
h1, k1 = 1, 0
convs = []
for a in cf:
h2 = a * h1 + h0
k2 = a * k1 + k0
convs.append((h2, k2))
h0, k0 = h1, k1
h1, k1 = h2, k2
return convs
N = 0x8b8da624b8b91c867977a89dbb49fd32f85bcf72baf4692cd02b6d2a46f7118f5f8f6d91a9d07dc6860cd4a00c246aa39dd63768c004afce09d1e2e3bfee5061d1585e9369f4b0c39d084abc19bd35fa9fab69e275e15709d189a8a18fcc462b659de4095fc6506fcea7394edebd88167d64f118494f1c3d414ad0a5a9c9f7156c5cb69a3dbce3345c7bf6742c2937d38023a66ee6a4536450b84e73ae86ff2f4a416c768ad3fe8567ea0edfeec0c219c9a94f5f4050a4e8cd08baa3e075db2ad9c18d6adb9aa5f77dd009fdcba6abf2deb7116ae8feea922779df85c6480aeac6ce9531cb72254769d70dee68013ea7fe8031c7c9f71b157f8dbbbb81989199
e = 0x8b27ebda101c0cb89f5a802d12f5a23516e654ba48745f57207560dbab41281fc4a7a4ea4f38104faab0a75cedc820dab4d23000bcca448f591abb27c5993fadaf0b5f46e320826fc32bf3d35e3958e7f5b8d8e02918b39d3c02ea80fd704e164b043fd8530b7d76b1c8a4e5dec12edf59ef495d17e907a8d1e9e6171ee1c64e4ba69b0b4b96e129fed9e3f92f4562b7e0f86567b9e39c9690ccfc1527d65eddbd739f8c3f0f78f9ff3660a0f3a77e9e0128b6fd78472e80bfa05b66612a8bcbe81384d7e5cf0f1e241f11bed1ad77054beb71547657feff53696115f3cc41d8d6741a2137bcc42b334157df7bc29a5cc4684145b8bd4b0b61917a3fdb800ebf
c = 0x19de1ed091b280112cb718bdd4c52d6b923a51dbb3ebc3f50d5e89ef02eecee0141661b6a00e2b459dcfe8da027878808c3f8f67626dccbc29bc4a0ed06f11957be4d98c2ca0085d03731a69a336b51c45cc35f72cec75c6f50adfbe3e8d552e2d59c6cd78fa6b0bc52139f3a7db7d7902c392a7dab01a7bf8708657145d83947a5a4a708a6aff33c4ca851339ee24f52a732ae0e7d19e7db6e406dab9bc5d00b805ec6510ea38190ef0aec200d4827a24b38425abe937a28d486eb5f035ac25b518208369cd03278736870527ad9f974e882eaae6fe2b9e64e2e15b7ffd97a52a3c196e3804343241d390f09d8b4944c2961909d7922291e6c03a7ad6e6713e
cf = continued_fraction(e, N)
convs = convergents(cf)
for i, (h, k) in enumerate(convs):
if k == 0 or h == 0:
continue
if (e * k - 1) % h != 0:
continue
phi = (e * k - 1) // h
if phi <= 0 or phi >= N:
continue
s = N - phi + 1
D = s*s - 4*N
if D < 0:
continue
root = isqrt(D)
if root * root != D:
continue
p = (s + root) // 2
q = (s - root) // 2
if p * q == N:
d = k
m = pow(c, d, N)
flag = long_to_bytes(m)
print(flag.decode())
Break
|
CaesarCerydra
Lagrange