Regenerating an RSA private key with Python


Warren GuyWarren Guy
14 October 2014

This is an exercise in regenerating an RSA private key while possessing only the public key. You might also find this useful if you happen to know all of the parameters of a private key (modulus, public exponent, and either the private exponent or prime factors), and want to reconstruct a key from them (skip to the end). This covers only the practical steps required without detailed explanation.

The example used here is a 256-bit RSA key, which can be factored on my laptop in less than three minutes. You won't (I hope) find any 256-bit RSA keys in the real world, however you could likely factor a 512-bit key (which sadly do exist in the wild) with modern hardware in a matter of days.

Gather required parameters

Given an arbitrary 256-bit public key in PEM format:

-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhANOs+tITdaEjOm7ClFLWmWco9m4sDymx
LuttBGjekQvZAgMBAAE=
-----END PUBLIC KEY-----

we can extract the modulus n and public exponent e with PyCrypto's RSA module (which we'll be using throughout the process):

>>> from Crypto.PublicKey import RSA
>>>
>>> pub = RSA.importKey("""-----BEGIN PUBLIC KEY-----
... MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhANOs+tITdaEjOm7ClFLWmWco9m4sDymx
... LuttBGjekQvZAgMBAAE=
... -----END PUBLIC KEY-----""")
>>>
>>> n = long(pub.n))
>>> e = long(pub.e))
>>>
>>> print n
95743639846435911282201623368817149970231530745600716013851051418596093791193
>>> print e
65537

Now we need to find our primes p and q (if you don't have them). The msieve program (not Python) is sufficient for solving for our 256-bit (77 digit integer) modulus.

$ ./msieve -v 95743639846435911282201623368817149970231530745600716013851051418596093791193

<verbose output removed for conciseness>

prp39 factor: 295067566530689955169650537538641733517
prp39 factor: 324480392650940924672294142667097877629
elapsed time 00:02:32
$ 

We now have our primes p and q:

  • 295067566530689955169650537538641733517; and
  • 324480392650940924672294142667097877629

We now need to derive the private exponent d. We can use gmpy for this:

>>> import gmpy
>>> 
>>> p = 295067566530689955169650537538641733517
>>> q = 324480392650940924672294142667097877629
>>> 
>>> d = long(gmpy.invert(e,(p-1)*(q-1)))
>>> 
>>> print d
7383437688388041802649602583365150616391030425600226685189771052318916795489

So we now have also have private exponent d and therefore enough information to completely reconstruct the private key.

Generating the private key

Using PyCrypto's RSA.construct function:.

>>> key = RSA.construct((n,e,d))
>>> 
>>> print key.exportKey()
-----BEGIN RSA PRIVATE KEY-----
MIGqAgEAAiEA06z60hN1oSM6bsKUUtaZZyj2biwPKbEu620EaN6RC9kCAwEAAQIg
EFLgrN6vTZPn5669vX2rKrN+O/1McYVSsX4cHx063GECEQD0HKaEXpRA57HuM9ut
p6x9AhEA3fvyOif7XTjMPzbO+LAnjQIRAJrjXuiYVjsEiApbDyUVQcUCEEHHUrPg
/R9WoU9qElKnAFECED96Z+Qs253ZrapyKxWcwyg=
-----END RSA PRIVATE KEY-----
>>> 
>>> print key.publickey().exportKey()
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhANOs+tITdaEjOm7ClFLWmWco9m4sDymx
LuttBGjekQvZAgMBAAE=
-----END PUBLIC KEY-----

We now have the RSA private key corresponding exactly with our original public key,.

Confirmation

>>> message = 'hack the planet'
>>> signature = key.sign(message,'')
>>> pub.verify(message,signature)
True
>>> secret = pub.encrypt(message,'')
>>> print key.decrypt(secret)
hack the planet

TAGS: SysAdmin, Cryptography, Security, PyCrypto, gmpy, Python, Public Key Cryptography, RSA

Next post: Detecting Tor users in nginx on Linux
Previous post: Global DNS Tester Update

Related posts:


View all posts