Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A script to find the common factor between two related RSA public keys and regenerate the unknown private keys
from Crypto.PublicKey import RSA
import gmpy
#Switch to python2 in the code doesn't work on python3. Simple change the input to raw_input
n1 = long(input("Insert first pub key (n1): "))
n2 = long(input("Insert second pub key (n2): "))
#Replicate the values of n1 and n2 before carrying out GCD operation
num1=long(n1)
num2=long(n2)
#Find the GCD on num1 and num2 with the loop
while(num2 != 0):
# swap using temp variable
temp = num2
num2 = num1 % num2
num1 = temp
#When gcd is found, it is saved as p
p = long(num1)
print("GCD (p) = ", p)
#Mathematical operation to find q1 and q2
q1=n1//p
q2=n2//p
print("q1= ", q1)
print("q2= ", q2)
#Credit to Cosu https://gist.github.com/cosu/4058678
#Start regenerating the private key
#tup (tuple) - A tuple of long integers, with at least 2 and no more than 6 items. The items come in the following order:
#RSA modulus (n).
#Public exponent (e).
#Private exponent (d)
#First factor of n (p).
#Second factor of n (q)
#RSA keys mostly use exponent 65537
e = long(65537)
phi1 = (p - 1) * (q1 - 1)
phi2 = (p - 1) * (q2 - 1)
d1 = long(gmpy.invert(e, phi1))
d2 = long(gmpy.invert(e, phi2))
tup1 = (n1 ,e, d1, p, q1 )
tup2 = (n2 ,e, d2, p, q2 )
key1 = RSA.construct(tup1)
key2 = RSA.construct(tup2)
#The private keys are saved as key1.pem and key2.pem
#The public keys are saved as public1.pem and public2.pem
f = open("key1.pem","w+")
g = open("public1.pem","w+")
h = open("key2.pem","w+")
i = open("public2.pem","w+")
f.write(key1.exportKey('PEM'))
g.write(key1.publickey().exportKey())
h.write(key2.exportKey('PEM'))
i.write(key2.publickey().exportKey())
#Output keys to console
print ("##########################################\n##########################################")
print ("Private key for N1 is saved as key1.pem")
print ("Public key for N1 is saved as public1.pem")
print ("##########################################\n##########################################")
print ("Private key for N2 is saved as key2.pem")
print ("Public key for N2 is saved as public2.pem")
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.