Playing with RSA and python

Intro

In a challenge, I was confronted with RSA. Usual stuff, which means you have to break a key, and decipher data. This blogpost is just a cookbook of what I used. This is not how to break a RSA key, this is more how you use RSA with python in order to have better understanding of what you can do with python.

A bit of theory, at first

A public key is composed of 2 numbers: n and e
A private key is composed of 2 numbers: n and d

With a private key, you decipher messages, with public key you cipher messages.

n is the results of two prime number, p and q.
e is a coprime of 'n', which means the GCD of n and e is 1.
d is choosen as d*e % (p-1)(q-1)=1

Confused? Read the excellent paper here: http://pajhome.org.uk/crypt/rsa/rsa.html

Creating RSA keys manually

Let's choose some numbers in order to create an RSA key:

• p=47 (prime)
• q=13 (prime)
• n=p*q=611
• m=(p-1)*(q-1)=552
• e=5 because PGCD(552,5)=1
• d=221 because (1+2×552)÷5=221 which is not a decimal number.
• (still confused? read again Paj's paper)

Go, python, go:

Let's follow the documentation:
https://www.dlitz.net/software/pycrypto/api/current/Crypto.PublicKey.RSA.RSAImplementation-class.html#construct

We can create an RSA key with our numbers, encrypt data with public key and decrypt data with private key:
$ ipython
In [1]: from Crypto.PublicKey import *
In [2]: key=RSA.construct((611L,5L,221L,47L,13L))
In [3]: key.publickey().encrypt('Z','x')[0]
Out[3]: '\x01\xe0'
In [4]: key.decrypt('\x01\xe0')
Out[4]: 'Z'

Notes:

• The encrypted message here is really short, it must be shorter than the key.
• The second parameter of encrypt() function is mandatory, but is useless, put whatever you want.
• key represent the private key. If you want the public key, you have to specify it with key.publickey().

And of course, you can import/export keys in PEM/DER format:
http://stackoverflow.com/questions/3504955/using-rsa-in-python

Ok, and when you have only the public key?

That's (not so) easy. Let's replay with our really weak key:
$ ipython
In [1]: from Crypto.PublicKey import *
In [2]: pubkey=RSA.construct((611L,5L))
In [3]: pubkey.has_private()
Out[3]: False
In [4]: pubkey.e
Out[4]: 5L
In [5]: pubkey.n
Out[5]: 611L

You can print out the 'n' parameter and try to find the prime numbers.. Once done, just verify the 'e' parameter and find the 'd' param. Next, build the private key, and key.decrypt() everything.

611 = 47*13  (that's the hard part when n is big)
m=46*12
e=5
for i in range(1,25):
    if (((1.0+i*m)/e) % 1)==0:
        print (1+i*m)/e
        break

221  which is the 'd' parameter

And you have everything to create a private key.

And with openssl?

$ ipython
In [1]: from Crypto.PublicKey import *
In [2]: key=RSA.construct((611L,5L,221L,47L,13L))
In [3]: print key.exportKey()
-----BEGIN RSA PRIVATE KEY-----
MB0CAQACAgJjAgEFAgIA3QIBLwIBDQIBJQIBBQIBHQ==
-----END RSA PRIVATE KEY-----

Copy paste the key in a file called privkey.pem, and:
mitsurugi@mitsu:~$ printf '\x01\xe0' | openssl rsautl -decrypt -inkey privkey.pem -raw
Z