Skip to content

Instantly share code, notes, and snippets.

@maojui

maojui/wiener_attack.py

Last active Nov 22, 2020
Embed
What would you like to do?
Wiener Attack
import sys
from sympy.solvers import solve
from sympy import Symbol
# This is comes from https://github.com/sourcekris/RsaCtfTool/blob/master/wiener_attack.py
# A reimplementation of pablocelayes rsa-wiener-attack
# https://github.com/pablocelayes/rsa-wiener-attack/
class WienerAttack(object):
def __init__(self, n, e):
self.d = None
self.p = None
self.q = None
sys.setrecursionlimit(100000)
frac = self.rational_to_contfrac(e, n)
self.convergents = self.convergents_from_contfrac(frac)
self.solve(n,e)
def rational_to_contfrac (self, x, y):
a = x//y
if a * y == x:
return [a]
else:
pquotients = self.rational_to_contfrac(y, x - a * y)
pquotients.insert(0, a)
return pquotients
def convergents_from_contfrac(self, frac):
convs = []
for i in range(len(frac)):
convs.append(self.contfrac_to_rational(frac[0:i]))
return convs
def contfrac_to_rational (self, frac):
if len(frac) == 0:
return (0,1)
elif len(frac) == 1:
return (frac[0], 1)
else:
remainder = frac[1:len(frac)]
(num, denom) = self.contfrac_to_rational(remainder)
return (frac[0] * num + denom, num)
def is_perfect_square(self, n):
h = n & 0xF;
if h > 9:
return -1
if ( h != 2 and h != 3 and h != 5 and h != 6 and h != 7 and h != 8 ):
t = self.isqrt(n)
if t*t == n:
return t
else:
return -1
return -1
def isqrt(self, n):
if n == 0:
return 0
a, b = divmod(n.bit_length(), 2)
x = 2**(a+b)
while True:
y = (x + n//x)//2
if y >= x:
return x
x = y
def solve(self,n,e):
for (k,d) in self.convergents:
if k!=0 and (e*d-1)%k == 0:
phi = (e*d-1)//k
s = n - phi + 1
discr = s*s - 4*n
if(discr>=0):
t = self.is_perfect_square(discr)
if t!=-1 and (s+t)%2==0:
self.d = d
print("find d:", self.d)
x = Symbol('x')
roots = solve(x**2 - s*x + n, x)
if len(roots) == 2:
self.p = roots[0]
self.q = roots[1]
break
def wiener(N,e):
"""
If the encryption exponent is too small or too large.
Let N=pq, q<p<2q, d < (1/3) * N**(1/4)
usage : wiener(N,exponent)
return : p, q
link : https://en.wikipedia.org/wiki/Wiener's_attack
"""
wa = WienerAttack(N,e)
if wa.p == None :
print("Wiener Attack Fail.")
return None
return int(wa.p), int(wa.q)
if __name__ == "__main__":
n = 0x92411fa0c93c1b27f89e436d8c4698bcf554938396803a5b62bd10c9bfcbf85a483bd87bb2d6a8dc00c32d8a7caf30d8899d90cb8f5838cae95f7ff5358847db1244006c140edfcc36adbdcaa16cd27432b4d50d2348b5c15c209364d7914ef50425e4c3da07612cc34e9b93b98d394b43f3eb0a5a806c70f06697b6189606eb9707104a7b6ff059011bac957e2aae9ec406a4ff8f8062400d2312a207a9e018f4b4e961c943dfc410a26828d2e88b24e4100162228a5bbf0824cf2f1c8e7b915efa385efeb505a9746e5d19967766618007ddf0d99525e9a41997217484d64c6a879d762098b9807bee46a219be76941b9ff31465463981e230eecec69691d1
e = 0x6f6b385dd0f06043c20a7d8e5920802265e1baab9d692e7c20b69391cc5635dbcaae59726ec5882f168b3a292bd52c976533d3ad498b7f561c3dc01a76597e47cfe60614f247551b3dbe200e2196eaa001a1d183886eeacddfe82d80b38aea24de1a337177683ed802942827ce4d28e20efef92f38f1b1a18c66f9b45f5148cceabfd736de8ac4a49e63a8d35a83b664f9f3b00f822b6f11ff13257ee6e0c00ca5c98e661ea594a9e66f2bd56b33d9a13f5c997e67a37fcf9a0c7f04d119fe1ba261127357e64a4b069aefed3049c1c1fe4f964fd078b88bedd064abea385cfebd65e563f93c12d34eb6426e8aa321033cfd8fe8855b9e74d07fe4f9d70de46f
print(wiener(n,e))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.