How I recovered your private key or why small keys are bad

In the following blogpost I will explain why it is a bad idea to use small RSA keys. To make things look and feel real, I will demonstrate all steps needed to factorize and recover a private key.

What is RSA?

RSA is an asymmetric public-key cryptosystem named after its inventors Rivest, Shamir & Adleman. Two keys are required to succesfully encrypt and decrypt a message. A keypair consists of the following keys:

Private key: The recipient needs this key to decrypt the message and it should be kept private.
Public key: The sender needs this key to send an encrypted message to the recipient and it can be public.

Let's have a short look on how the RSA key generation works:

Find two distinct prime numbers p and q: E.g. p=61 and q=53
Calculate the modulus n=p*q: n=61*53=3233
Calculate phi(n)=(p-1)*(q-1): phi(3233)=(61-1)*(53-1)=60*52=3120
Find a number e which is coprime to phi(n) and 1 < e < phi(n) holds. A trick is to choose e prime and check that e does not divide phi(n). e=17
Compute the modular multiplicative inverse d of e (mod phi(n)): d=2753

Now we have all numbers to form the keys:

The public key is (n=3233, e=17)
The private key is (n=3233, d=2753)

En-/decrypting a message m is simple:

Encryption: c(m) = m ^ e mod n
Decryption: m(c) = c ^ d mod n

Using OpenSSL

Now that we know the theory behind RSA we can use OpenSSL to do the work for us.

Let's create a private key:

$> openssl genrsa 128 > my.key
Generating RSA private key, 128 bit long modulus
..+++++++++++++++++++++++++++
..+++++++++++++++++++++++++++
e is 65537 (0x10001)

Note: This is only a 128 bit key. Use this only for demo/educational purposes!

The genrsa command does all the steps 1-5 (and maybe a bit more). Note that the modulus (n) is 128 bit long. That usually means that the primes p & q are half the size, because n = p*q.

You can get some information about the private key with the rsa command:

$> openssl rsa -inform PEM -text -noout < my.key 
Private-Key: (128 bit)
modulus:
    00:c8:08:21:20:63:7e:86:2a:79:fb:67:1f:04:ea:
    a2:65
publicExponent: 65537 (0x10001)
privateExponent:
    7f:ab:98:a1:18:7f:b7:d7:20:f1:87:86:c5:da:0e:
    3d
prime1: 17546182527694491887 (0xf380900b976550ef)
prime2: 15153598738517072363 (0xd24c65c3f61e19eb)
exponent1: 13725148347990572143 (0xbe7985b41b847c6f)
exponent2: 1796132795227133041 (0x18ed2542ccf15471)
coefficient: 17063613649022129323 (0xecce2234f67894ab)

However, the private key is our secret and we need the public key to encrypt a message. Extract the public key with the -pubout switch:

$> openssl rsa -pubout -in my.key > my.pub 
writing RSA key

$> openssl rsa -inform PEM -text -noout -pubin < my.pub 
Public-Key: (128 bit)
Modulus:
    00:c8:08:21:20:63:7e:86:2a:79:fb:67:1f:04:ea:
    a2:65
Exponent: 65537 (0x10001)

$> cat my.pub 
-----BEGIN PUBLIC KEY-----
MCwwDQYJKoZIhvcNAQEBBQADGwAwGAIRAMgIISBjfoYqeftnHwTqomUCAwEAAQ==
-----END PUBLIC KEY-----

As you can see, our public key contains only the modulus n and the exponent e. The file my.pub is the public key in PEM format.

Let's encrypt a message using our public key. OpenSSL's rsautl helps with that:

$> echo -n "Hi" |openssl rsautl -encrypt -inkey my.key > message

$> cat message 
¨á²áåÔÈä³F
           É6                
$> cat message | hexdump 
0000000 e1a8 947f e1b2 e514 c8d4 b3e4 0c46 36c9
0000010

Note: This only works for messages which are smaller than the modulus. Usually the message is encrypted with a symmetric key which is in turn encrypted with RSA.

As you can see, we encrypted our message "Hi" and the result is gibberish. Only the recipient can decrypt it using his private key.

Recovering the private key

As said above, the sender needs the recipient's public key to encrypt a message. Unfortunately, one can factorize the modulus n into two primes p*q if n is too small (usually < 1048). Thus an adversary can recover the private key and decrypt the message.

I have chosen a pretty small key of 192 bits above. Let's assume we are the adversary and are interested in recovering the contents of the message. We only have the public key, because it was uploaded to a keyserver, and the encrypted message:

Modulus:
    00:c8:08:21:20:63:7e:86:2a:79:fb:67:1f:04:ea:
    a2:65
Exponent: 65537 (0x10001)

The modulus n is 0x00c8082120637e862a79fb671f04eaa265 (simply remove the colons). The most time consuming part is to find two prime numbers p' & q' so that n=p'*q'.
We can use a tool like Yafu or a site like factordb.com:

$> yafu "factor(0x00c8082120637e862a79fb671f04eaa265)"
fac: factoring 265887809417461548369618742468095418981
[..snip..]
Total factoring time = 0.3822 seconds
***factors found***
P20 = 17546182527694491887
P20 = 15153598738517072363

Okay, cool. It took us 0.4 seconds to find the prime factors of our modulus:

p'=17546182527694491887
q'=15153598738517072363

The rest is some math again. Let's use python for it:

$> python2
>>> e = 0x010001
>>> n = 0x00c8082120637e862a79fb671f04eaa265
>>> p = 17546182527694491887
>>> q = 15153598738517072363

Now we basically have to do step 3 and 5 to recover d. We calculate phi(n) first:

>>> phi = (p -1)*(q-1)

After that we can use the extended euclidean algorithm to calculate the modular inverse:

>>> def egcd(a, b):
...     if a == 0:
...         return (b, 0, 1)
...     else:
...         g, y, x = egcd(b % a, a)
...         return (g, x - (b // a) * y, 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
... 
>>> d = modinv(e,phi)
>>> d
169702933917069733210018512109397741117L
>>> hex(d)
'0x7fab98a1187fb7d720f18786c5da0e3dL'

If you take a close look at the hex value of d you will notice that this is the same as our private key:

privateExponent:
    7f:ab:98:a1:18:7f:b7:d7:20:f1:87:86:c5:da:0e:
    3d

YAY, we successfully recovered the private key.

Now we could decrypt the message manually, but I prefer to create a private key file and use OpenSSL. It does not use d for decryption, but three more variables to be more efficient.

>>> dp = modinv(e,(p-1))
>>> dq = modinv(e,(q-1))
>>> qi = modinv(q,p)

Now we can use a snippet from crypto.stackexchange.com to create the PEM-encoded private key. You may need to install python2-pyasn1 on your system.

>>> import pyasn1.codec.der.encoder
>>> import pyasn1.type.univ
>>> import base64
>>> 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()
...     for x in [0, n, e, d, p, q, dP, dQ, qInv]:
...         seq.setComponentByPosition(len(seq), pyasn1.type.univ.Integer(x))
...     der = pyasn1.codec.der.encoder.encode(seq)
...     return template.format(base64.encodestring(der).decode('ascii'))
... 
>>> key = pempriv(n,e,d,p,q,dp,dq,qi)
>>> key
'-----BEGIN RSA PRIVATE KEY-----\nMGMCAQACEQDICCEgY36GKnn7Zx8E6qJlAgMBAAECEH+rmKEYf7fXIPGHhsXaDj0CCQDzgJALl2VQ\n7wIJANJMZcP2HhnrAgkAvnmFtBuEfG8CCBjtJULM8VRxAgkA7M4iNPZ4lKs=\n-----END RSA PRIVATE KEY-----\n'
>>> f = open("recovered.key","w")
>>> f.write(key)
>>> f.close()

Done!
Let's see what OpenSSL says about our recovered key:

$> openssl rsa -inform PEM -text -noout < recovered.key  
Private-Key: (128 bit)
modulus:
    00:c8:08:21:20:63:7e:86:2a:79:fb:67:1f:04:ea:
    a2:65
publicExponent: 65537 (0x10001)
privateExponent:
    7f:ab:98:a1:18:7f:b7:d7:20:f1:87:86:c5:da:0e:
    3d
prime1: 17546182527694491887 (0xf380900b976550ef)
prime2: 15153598738517072363 (0xd24c65c3f61e19eb)
exponent1: 13725148347990572143 (0xbe7985b41b847c6f)
exponent2: 1796132795227133041 (0x18ed2542ccf15471)
coefficient: 17063613649022129323 (0xecce2234f67894ab)

Note: The values exponent1 / exponent2 might differ, but that does not matter.

The last step is to decrypt the message with our recovered key:

$> cat message  |openssl rsautl -decrypt -inkey recovered.key 
Hi

YAY, we did it! :)

Conclusion

I hope you learned that using asymmetric cryptosystems is cool, but using them with small keys is not.
Keys up to 300 bits can be factored within an hour on personal computers. There's even an RSA factoring challenge and the largest factored modulus is 768 bit long. This is a real problem, because people used such small ssh keys on GitHub. Sometimes too small keys can lead to serious security issues.

It's recommended to use keys with at least 2048 bits. There is almost no performance loss, even on smartphones.

Code

Here's the full python code:

#!/usr/bin/python2
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()
	    for x in [0, n, e, d, p, q, dP, dQ, qInv]:
	        seq.setComponentByPosition(len(seq), pyasn1.type.univ.Integer(x))
	    der = pyasn1.codec.der.encoder.encode(seq)
	    return template.format(base64.encodestring(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()

Update 13.11.2016:
Use correct formulas for dp, dq, qi.

-=-

Sebastian Neef - 0day.work

What is RSA?

Using OpenSSL

Recovering the private key

Conclusion

Code