/
solve.py
53 lines (40 loc) · 1003 Bytes
/
solve.py
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
# coding:utf-8
from __future__ import print_function
from Crypto.Util.number import inverse, long_to_bytes
import Crypto.PublicKey.RSA as RSA
def sqrt(x):
lb = 0
ub = x
while (ub - lb) > 1:
mb = (ub + lb) / 2
if mb * mb > x:
ub = mb
else:
lb = mb
return lb
with open("key1", "r") as f:
n1 = int(f.readline())
with open("key2", "r") as f:
n2 = int(f.readline())
b = (n2 - n1 - 4)
assert b % 2 == 0
b = b / 2
c = n1
D_tmp = b * b - 4 * c
D = sqrt(D_tmp)
assert D_tmp == D * D
tmp = b + D
assert tmp % 2 == 0
p, q = (b + D) / 2, (b - D) / 2
assert p * q == n1 # 因数分解できちゃった
# あとはやるだけ
e = long(65537)
d1 = inverse(e, (p-1)*(q-1))
d2 = inverse(e, (p+1)*(q+1))
rsa1 = RSA.construct((n1, e, d1))
rsa2 = RSA.construct((n2, e, d2))
with open("encrypted", "rb") as f:
enc = int(f.read().strip("\n"))
tmp = rsa2.decrypt(enc)
flag = rsa1.decrypt(tmp)
print(long_to_bytes(flag).split("\0")[0])