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
| import gmpy2
import time
def continuedFra(x, y):
cF = []
while y:
cF += [x / y]
x, y = y, x % y
return cF
def Simplify(ctnf):
numerator = 0
denominator = 1
for x in ctnf[::-1]:
numerator, denominator = denominator, x * denominator + numerator
return (numerator, denominator)
def calculateFrac(x, y):
cF = continuedFra(x, y)
cF = map(Simplify, (cF[0:i] for i in xrange(1, len(cF))))
return cF
def solve_pq(a, b, c):
par = gmpy2.isqrt(b * b - 4 * a * c)
return (-b + par) / (2 * a), (-b - par) / (2 * a)
def wienerAttack(e, n):
for (d, k) in calculateFrac(e, n):
if k == 0: continue
if (e * d - 1) % k != 0: continue
phi = (e * d - 1) / k
p, q = solve_pq(1, n - phi + 1, n)
if p * q == n:
return abs(int(p)), abs(int(q))
print 'not find!'
time.clock()
n = 86966590627372918010571457840724456774194080910694231109811773050866217415975647358784246153710824794652840306389428729923771431340699346354646708396564203957270393882105042714920060055401541794748437242707186192941546185666953574082803056612193004258064074902605834799171191314001030749992715155125694272289
e = 46867417013414476511855705167486515292101865210840925173161828985833867821644239088991107524584028941183216735115986313719966458608881689802377181633111389920813814350964315420422257050287517851213109465823444767895817372377616723406116946259672358254060231210263961445286931270444042869857616609048537240249
c = 37625098109081701774571613785279343908814425141123915351527903477451570893536663171806089364574293449414561630485312247061686191366669404389142347972565020570877175992098033759403318443705791866939363061966538210758611679849037990315161035649389943256526167843576617469134413191950908582922902210791377220066
p, q = wienerAttack(e, n)
print '[+]Found!'
print ' [-]p =',p
print ' [-]q =',q
print ' [-]n =',p*q
d = gmpy2.invert(e,(p-1)*(q-1))
print ' [-]d =', d
print ' [-]m is:' + '{:x}'.format(pow(c,d,n)).decode('hex')
print '\n[!]Timer:', round(time.clock(),2), 's'
print '[!]All Done!'
|
