## Thursday, December 27, 2012

### RSA parameters in PEM file...

If you've ever read anything about how RSA works you most probably know that RSA is based on arithmetic modulo some large integer. First, let N be a product of two, very large, primes p and q. N is n-bit number, those days minimally 1024 bits, and thus p and q are half that size, so that after multiplication we get required number of bits. Next, there are two numbers e and d that satisfy relation $eq = 1\ mod\ \phi(N)$, where $\phi(N)=(p-1)(q-1)$. $(N, e)$ is encryption key - or what's frequently referred to as a public key, while $(N,d)$ is decryption key, or a private key. The question now is: Given a PEM file with private key, how to find out those parameters for a specific public/private keys? In this post I'll show three ways to do it. The first two are using tools that are a standard part of OpenSSL/GnuTLS libraries. The third one is using Python.

OpenSSL/GnuTLS

Those two, especially OpenSSL, are very popular and complex cryptograhpic libraries. Both of them come with a very capable command line tools. In the case of OpenSSL the there is a single binary, openssl, that performs its function depending on the second argument. In this post, I'll use arguments rsa and genrsa that manipulate and generate, respectively, RSA keys. GnuTLS, on the other hand, has a several tools, of which we'll use certtool.

Now, first thing is to create RSA public/private key. You can do this using the following commands:
openssl genrsa -out key.pem 512
or, if you use GnuTLS, then:
certtool --generate-privkey --bits 512 --outfile key.pem
In both cases the generated RSA modulus (N) will have 512 bits, and the keys will be written into output file key.pem. You should note few things here:
1. The output file contains both private and public keys!
2. We didn't encrypt output file, which is recommended to do.
3. 512 bits these days is a way insecure. Use minimally 1024 bits.
Ok, now we can request information about this RSA keys. Again, you can do that using openssl in the following way:
openssl rsa -in key.pem -noout -text
or, using GnuTLS:
certtool -k --infile key.pem
In both cases you'll receive the following output (GnuTLS is a bit more verbose):
Private-Key: (512 bit)
modulus:
00:ba:b6:78:3b:1c:15:f1:d9:e3:48:16:5e:e7:8e:
6e:ef:b2:b5:cd:ee:38:e9:f8:6d:64:c9:ea:95:ae:
87:13:5a:23:8b:2f:0b:e8:bb:c6:f8:c6:c4:ee:64:
3c:d4:97:bd:a3
publicExponent: 65537 (0x10001)
privateExponent:
39:6b:07:ca:55:b6:c1:eb:59:a3:bf:8d:6b:f4:63:
36:d3:5f:fb:ff:76:63:f7:3d:86:51:bc:77:2e:56:
8d:4b:87:73:e0:53:bd:17:e8:4a:e8:df:f5:86:14:
65:60:f2:4f:03:02:3b:e9:23:c6:d3:ce:b3:1d:e9:
13:1a:0f:b1
prime1:
00:d6:b1:f9:53:8c:56:96:79:c0:bd:68:6c:b9:07:
e7:9c:70:de:f5:61:ed:bb:51:12:1d:24:37:0f:cc:
bf:8a:95
prime2:
00:de:a2:52:be:a1:a4:eb:d7:48:24:95:c5:2c:05:
bd:5f:7f:74:d5:12:bd:7c:5f:f1:8e:45:a2:50:26:
ec:d1:57
exponent1:
66:61:30:58:1b:10:1f:69:a7:f3:aa:9c:4e:0f:ea:
ee:bb:14:57:47:7f:aa:57:9a:9f:b2:e9:5e:eb:70:
5b:91
exponent2:
22:2d:8f:40:5e:b6:5f:d2:5b:eb:e9:e6:2c:1c:f1:
10:df
coefficient:
22:9c:f3:1f:85:68:a3:36:ab:07:87:ed:a4:c0:e5:
ef:13:a8:28:02:55:35:c1:76:96:86:97:58:08:90:
6e:70
In this output we see parameters N (modulus), e (publicExponent), d (privateExponent), p (prime1), and q (prime2). Also, what's written in there are values d mod (p-1) (exponent1),  d mod (q-1) (exponent2) and q-1 mod p (coefficient).

The interesting thing to note is the value of publicExponent, it is 65537. Namely, the size of public exponent isn't so important and by having such a low value it is relatively easy to encrypt messages (rising to this exponent requires 17 multiplications). This is very frequent value for encryption key, i.e. public exponent. privateExponent, on the other hand, has to be large and random, so that it isn't easy to guess.

Python

The recommended library to use to manipulate RSA keys is m2crypto which is a wrapper to OpenSSL library. There are many other libraries, of course, and you can find an older comparison here. Unfortunately, I was unable to find downloadable version on the Internet.

Anyway, to be able to manipulate RSA keys you have to import RSA module from M2Crypto, i.e.:
from M2Crypto import RSA
Then, to load RSA private/public key from a file use the following line:
You can also generate new RSA private key as follows:
rsa=RSA.gen_key(512, 65537)
In this case you are generating private key based on public key 65537 (we saw that this is very frequently used public key) and we require 512 bit modulus. You can find out modulus length using Python's len() function, i.e.:
>>> len(rsa)
512
To obtain N, you can inquire attribute n of the object holding RSA key, i.e.:
>>> rsa.n
To obtain pair (e,d), or public key, you can use the following method:
>>> RSA.pub()
Alternatively, you can find out only e in the following way:
>>> rsa.e
As far as I could see, there is no way to find other parameters besides N, e and bit length.