Skip to content

Instantly share code, notes, and snippets.

@Cyxo
Last active May 23, 2020 15:22
Show Gist options
  • Save Cyxo/b68f66905d2f155d16ea71d9135fd4ad to your computer and use it in GitHub Desktop.
Save Cyxo/b68f66905d2f155d16ea71d9135fd4ad to your computer and use it in GitHub Desktop.
A Python3 script to generate a PEM private key file from p, q and e. Adapted from the Python2 code here: https://0day.work/how-i-recovered-your-private-key-or-why-small-keys-are-bad/
#!/usr/bin/python3
import pyasn1.codec.der.encoder
import pyasn1.type.univ
import base64
def recover_key(p, q, e, output_file):
"""Recoveres a RSA private key from:
p: Prime p
q: Prime q
e: Public exponent
output_file: File to write PEM-encoded private key to"""
# SRC: https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
def egcd(a, b):
x,y, u,v = 0,1, 1,0
while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y
def modinv(a, m):
gcd, x, y = egcd(a, m)
if gcd != 1:
return None # modular inverse does not exist
else:
return x % m
# SRC: http://crypto.stackexchange.com/questions/25498/how-to-create-a-pem-file-for-storing-an-rsa-key/25499#25499
def pempriv(n, e, d, p, q, dP, dQ, qInv):
template = '-----BEGIN RSA PRIVATE KEY-----\n{}-----END RSA PRIVATE KEY-----\n'
seq = pyasn1.type.univ.Sequence()
i = 0
for x in [0, n, e, d, p, q, dP, dQ, qInv]:
seq.setComponentByPosition(i, pyasn1.type.univ.Integer(x))
i += 1
der = pyasn1.codec.der.encoder.encode(seq)
return template.format(base64.encodebytes(der).decode('ascii'))
n = p * q
phi = (p -1)*(q-1)
d = modinv(e, phi)
dp = modinv(e,(p-1))
dq = modinv(e,(q-1))
qi = modinv(q,p)
key = pempriv(n, e, d, p, q, dp, dq, qi)
f = open(output_file,"w")
f.write(key)
f.close()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment