forked from p4-team/ctf
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathexploit.py
128 lines (105 loc) · 2.45 KB
/
exploit.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
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
from random import randrange
import fractions, math, binascii
def get_primes(n):
numbers = set(range(n, 1, -1))
primes = []
while numbers:
p = numbers.pop()
primes.append(p)
numbers.difference_update(set(range(p*2, n+1, p)))
return primes
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def miller_rabin(n, k):
r, s = 0, n - 1
while s % 2 == 0:
r += 1
s //= 2
for _ in range(k):
a = randrange(2, n - 1)
x = pow(a, s, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
### main #################
primes = get_primes(443)
primes.sort()
del primes[0]
#print primes
pi = 1;
for x in primes:
pi *= x
print "pi=%X" % pi # pi~2**600
n=int(open("publickey").read().split("\n")[0][2:],16)
e=0x10001
# n=p*q
# n=(2**400 * pi)**2 * (kp*kq) + (2**400 * pi)*(tp*kq+tq*kp) + tp*tq
base=pi*(2**400) # Around 2**1000
C=n%base
nn=n
nn/=base
B=nn%base
nn/=base
A=nn
print "BASE:", hex(base)
print "A :", hex(A)
print "B :", hex(B)
print "C :", hex(C)
k=[]
for i in range(1, 2**12):
kx = i + 2**12 + 2**13 + 2**14 + 2**15 + 2**16 + 2**17 + 2**18 + 2**19
if A%kx==0:
k.append(kx)
print k
t=[0,0]
# At this point, we have to find t[], knowing that: // (0-p), (1-q)
# C=t[0]*t[1]
# B=t[0]*k[1]+t[1]*k[0]
# We know everything besides t's, so we have two equations with two unknowns
def isqrt(n):
x = n
y = (x + 1) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
a=k[0]
b=-B
c=k[1]*C
# This quadratic equation gives t[1]
delta=b*b-4*a*c
sdelta=isqrt(delta)
print "DELTA :", hex(delta)
print "SQRT DELTA :", hex(sdelta)
print "SQRT DELTA ** 2:", hex(sdelta*sdelta)
print (sdelta*sdelta)==delta
t[1]=(-b+sdelta)/2/a
print t[1]*2*a==sdelta-b
t[0]=C/t[1]
print t[0]*k[1]+t[1]*k[0]==B
print t[0]*t[1]==C
p=k[0]*pi*2**400+t[0]
q=k[1]*pi*2**400+t[1]
d = modinv(e, (p-1)*(q-1))
print "d=%X" % d
c=int(open("ciphertext").read(), 16)
# c - ciphertext
m2 = pow(c, d, n) # This will be equal to m. It's a proof that this stuff works.
print hex(m2)
print binascii.unhexlify(hex(m2)[2:-1])