Skip to content

Instantly share code, notes, and snippets.

@AntonKueltz
Created April 1, 2017 03:02
Show Gist options
  • Save AntonKueltz/73c28f5a2ceb5f37a3db471068a36a68 to your computer and use it in GitHub Desktop.
Save AntonKueltz/73c28f5a2ceb5f37a3db471068a36a68 to your computer and use it in GitHub Desktop.
Factor an RSA modulus given the public and private key
def factor(n, e, d):
"""http://crypto.stackexchange.com/a/25910/17884
n - modulus
e - public exponent
d - private exponent
returns - (p, q) such that n = p*q
"""
from fractions import gcd
from random import randint
while True:
z = randint(2, n - 2)
k, x = 0, e * d - 1
while not x & 1:
k += 1
x /= 2
t = pow(z, x, n)
if t == 1 or t == (n-1):
continue
bad_z = False
for _ in range(k):
u = pow(t, 2, n)
if u == -1 % n:
bad_z = True
break
if u == 1:
p = gcd(n, t-1)
q = gcd(n, t+1)
assert n == p * q
return p, q
else:
t = u
if bad_z:
continue
@HaoPham23
Copy link

HaoPham23 commented Mar 10, 2023

In case x is big, I think we should replace x /= 2 by x >>= 1

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment