# 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:

1. Find two distinct prime numbers `p` and `q`: E.g. `p=61` and `q=53`
2. Calculate the modulus `n=p*q`: `n=61*53=3233`
3. Calculate `phi(n)=(p-1)*(q-1)`: `phi(3233)=(61-1)*(53-1)=60*52=3120`
4. 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`
5. 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-----
-----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.

-=-