I'm writing a program that will calulate the private key for a weak RSA public key. I am wondering how I would go about determining the values for p and q from the value n. Here is the Python code so far:
from Crypto.PublicKey import RSA #PyCryptoDome
import .math as cm # My own module
with open(public_keyfile, 'rb') as key: # Public Keyfile Is in PEM format
public_key = RSA.import_key(key)
n = public_key.n # N value of the public_key
e = public_key.e # E value of the public_key
p, q = get_factors_of(n) # This I don't know how to do, though there is a question that might help [see bottom]
t = cm.lcm(p-1, q-1) # Get the lowest common multiple of q and q
d = cm.mod_inverse(e, t) # Get d, the modular inverse of e % t
private_key = RSA.construct((n, e, d, p, q) # Construct the RSA private_key
The .math module referenced above:
from math import gcd
def mod_inverse(a, b):
a = a % b
for x in range(1, b):
if (a * x) % b == 1:
return x
return 1
def lcm(x, y):
return x * y // gcd(x, y)
What I need to do appears to be referenced here but this code is in Java.
If anyone knows how to get p and q from n with python, help would be appreciated.
Many thanks, Legorooj.
After lots of googling, and pdf reading, I found an algorithm that works. Here is a python implementation:
import math
def get_factors_of(num):
poss_p = math.floor(math.sqrt(num))
if poss_p % 2 == 0: # Only checks odd numbers, it reduces time by orders of magnitude
poss_p += 1
while poss_p < num:
if num % poss_p == 0:
return poss_p
poss_p += 2
This algorithm effectively finds the P/Q factors of a small RSA key. (I have tested it against a 64-bit PEM public key)