### # 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