# Wiener's attack against RSA (small values of d)

Wiener has proved that the attacker may efficiently find d when:

d < (N**0.25)/3

```# `cat wiener_attack.py`
#!/usr/bin/python

from sympy.solvers import solve
from sympy import Symbol

def partial_quotiens(x, y):
pq = []
while x != 1:
pq.append(x / y)
a = y
b = x % y
x = a
y = b
#print pq
return pq

def rational(pq):
i = len(pq) - 1
num = pq[i]
denom = 1
while i > 0:
i -= 1
a = (pq[i] * num) + denom
b = num
num = a
denom = b
#print (num, denom)
return (num, denom)

def convergents(pq):
c = []
for i in range(1, len(pq)):
c.append(rational(pq[0:i]))
#print c
return c

def phiN(e, d, k):
return ((e * d) - 1) / k

# e = 17993
# n = 90581
# wiener_attack(e, n) --> p =  239, q =  379

n = 0x02aeb637f6152afd4fb3a2dd165aec9d5b45e70d2b82e78a353f7a1751859d196f56cb6d11700195f1069a73d9e5710950b814229ab4c5549383c2c87e0cd97f904748a1302400dc76b42591da17dabaf946aaaf1640f1327af16be45b8830603947a9c3309ca4d6cc9f1a2bcfdacf285fbc2f730e515ae1d93591ccd98f5c4674ec4a5859264700f700a4f4dcf7c3c35bbc579f6ebf80da33c6c11f68655092bbe670d5225b8e571d596fe426db59a6a05aaf77b3917448b2cfbcb3bd647b46772b13133fc68ffabcb3752372b949a3704b8596df4a44f085393ee2bf80f8f393719ed94ab348852f6a5e0c493efa32da5bf601063a033beaf73ba47d8205db

pq = partial_quotiens(e, n)
c = convergents(pq)
x = Symbol('x')
for (k, d) in c:
if k != 0:
y = n - phiN(e, d, k) + 1
roots = solve(x**2 - y*x + n, x)
if len(roots) == 2:
p = roots[0]
q = roots[1]
if p * q == n:
print 'p = ', p
print 'q = ', q
break
# `./wiener_attack.py`
p =  12001304129015480165432875074437607933493850611499879464845243350215176144760883615322622081442653872645865326992384034722586201972392183010813439352778246403016897976571514715418700569567613729681273931557848857971070286176848136118602099586101089743239644367344468295964691411425416652519752140536869089101
q =  28216117316929874067495888027767527011360661622486842768414059951572932145196930641365509243766454218518793508840136548374994021850853203018205749779390383366761851772055038753940967432004901699256177783249460134792699230632136386268348434203012426963129659057781488950062703849444443906614331812260961682887```

Reference

http://en.wikipedia.org/wiki/Wiener's_attack

1 comment:

Blogger said...

If you want your ex-girlfriend or ex-boyfriend to come crawling back to you on their knees (even if they're dating somebody else now) you got to watch this video
right away...

(VIDEO) Win your ex back with TEXT messages?