Crack unsafe RSA Encryption

I had to decrypt a weak RSA encrypted message. Why weak? Because a (only) 268-bit key was used for encryption. So RSA is not bad, but please use a suitable key size.

For this blog post it's not important, why RSA is secure and works, it's just a tutorial how to calculate a private key if it get's lost (will just work for unsecure keys indeed) or to demonstrate that small key sizes are unsecure. If you want to know how RSA works, take a look at one of the million blog posts out there. First we need to gather some information like modulo $n$ and the exponent $e$. These values can be extracted out of the public key file. The following command can be used case of an *.pem file:

~/D/tuna ❯❯❯ openssl asn1parse -in public_key1.pem
    0:d=0  hl=3 l= 148 cons: SEQUENCE          
    3:d=1  hl=3 l= 140 prim: INTEGER           :042F37B80F922E5D16DDC79420233A40C5DFE2863C3A3D4E0C4D414D8C7DEDDA2058AB27638CA7CD3B787980D7569DE2DC283BFBCF0D2D80AD4C3BB39213186C1202801310FD6362600783D30A7F7EE3389DDBA1BD8FE9FA0A09ECF9D0B6A60FCE8E414424808C4FB0346097D31567215639D58A37721701C3EF34007B5543DA0ED195BE22221CC38426641B
  146:d=1  hl=2 l=   3 prim: INTEGER           :010001

The second Integer is the modulo and the last int is the exponent. To get the corresponding decimal values we have to convert the hex-values. This can be done with python like this:

print(int("042F37B80F922E5D16DDC79420233A40C5DFE2863C3A3D4E0C4D414D8C7DEDDA2058AB27638CA7CD3B787980D7569DE2DC283BFBCF0D2D80AD4C3BB39213186C1202801310FD6362600783D30A7F7EE3389DDBA1BD8FE9FA0A09ECF9D0B6A60FCE8E414424808C4FB0346097D31567215639D58A37721701C3EF34007B5543DA0ED195BE22221CC38426641B", 16))

#result
232805337824709187758567614345164369640905196906161190117399914999084869280501377034146427509821310414018646093699105528219624749717431457106237039734270204290594088884317268823351960048222904591377231999511261693392492917096983385403575193640490238594096249866899523020243255292818672149033458690078581352942476216908273781672014930971

Now we have to find the factors $(p,q)$ of the modulus $n$. These can be calculated, but this is not easy so I will look them up ;).

A good factor database of can be found here: http://www.factordb.com

C Version

I used this c program to calculate the private key. You will need openssl-dev and provide -lssl -lcrypto as compiler flags. After compilation, call the generated binary and provide your $q$ and $p$ as arguments. Finally pipe your output to some file - Viola!

gcc private-from-pq.c -o gen -lssl -lcrypto
./gen <your_p> <your_q> > private.key

To decrypt messages you can use the follwoing command:

openssl rsautl -in encrypted_message.bin -inkey private.key -decrypt -hexdump

Python version

It's also possible to generate the keys (or directly encrypt the message) using python, just by using the awesome pycrypto package.

from fractions import gcd
from Crypto.PublicKey import RSA

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

n = 232805337824709187758567614345164369640905196906161190117399914999084869280501377034146427509821310414018646093699105528219624749717431457106237039734270204290594088884317268823351960048222904591377231999511261693392492917096983385403575193640490238594096249866899523020243255292818672149033458690078581352942476216908273781672014930971L
e= 65537L
secret_message = open('../Downloads/message.bin', "rb").read()

## http://www.factordb.com was used to get factors 
q = 99999989L
p = 2328053634332991654214758107075035474662954181986571919696910316650983524413201455793624412396898467799017918828962126468030158980491802425160637165012790194312862263258021646615900728231309151357778969350799245521841936573582856948150016232906688005676643123099738771173697382034898745329196573112408855894398910552962898642639L

phi = (p-1)*(q-1)
gcd, x, y = egcd(e, phi)

assert gcd == 1 # should be 1 = they have to be coprime
d = x % phi

private_key = RSA.construct((n, e, d))
print private_key.decrypt(secret_message)

f = open('private_key.pem','w')
f.write(private_key.exportKey('PEM'))
f.close()

Links