Cracking 768bit RSA Encryption

0x00 Introduction

This post is going to be demonstrating a 768 bit RSA crack when all you have is the file you want to decrypt, and the public key. RSA isnt all that hard to crack given the correct circumstances, however this wont be the case all the time so you may be in need of a lot of processing power.

A brief info on RSA encryption and public/private keys... in public-key cryptography the keys are signed with a key algorithm and in this case it is RSA which is an asymmetric algorthim and this uses integer factorization as the basis of the cryptographic method, as you will find out later. 


0x01 RSA public/private key generation

In RSA, the private key is generated (d,p,q), the public key is generated (e,n):

• p = randomly chosen prime
• q = randomly chosen prime 
• n = modulus for public and private keys(n=pq) 
• f(n)=(p-1)(q-1) :: f(n) counts the number of positive integers less than or equal to n that are relatively prime to n
• e = exponent (chosen as 1 < e < f(n) && greatest common divisor of (e, f(n)) = 1... so e and f(n) are coprime) this is the public key exponent
• d = e^-1(mod f(n)) or (de) = 1 mod f(n)  --- this is the private key exponent

So now you know the Math-o-Crypto:
We have a file which has been encrypted and all we have is the public key below which is available to anyone. We can however, deduce the private key from the public key, if the circumstances are correct. 

0x03 Math-o-crypto practical 

root@vm:~/Desktop/RSAcrack/# cat publickey.pem
-----BEGIN PUBLIC KEY----- MGQwDQYJKoZIhvcNAQEBBQADUwAwUAJJAMLLsk/b+SO2Emjj8Ro4lt5FdLO6WHMM vWUpOIZOIiPu63BKF8/QjRa0aJGmFHR1mTnG5Jqv5/JZVUjHTB1/uNJM0VyyO0zQ owIDAQAB
-----END PUBLIC KEY-----

root@vm:~/Desktop/RSAcrack/# cat file2crack.bin
0000000: 7bca 100e 286c 9a4b e34f 7b19 7be1 04f2  {...(l.K.O{.{...
0000010: 5c0d bc11 2c15 e818 17af 8e38 53a2 47a8  \...,......8S.G.
0000020: 0cb4 c671 c5b6 bf6c 880b 503f 2957 7c84  ...q...l..P?)W|.
0000030: 7f48 0e39 f1ee 0796 c2de f426 a3b6 c4e0  .H.9.......&....
0000040: f708 29fa 4519 9040                      ..).E..@

We have our public and file that we want to decrypt... 
First step is to extract  public key modulus and public key exponent (n, e):

root@vm:~/Desktop/RSAcrack/# pkcs1-conv publickey.pem | xxd
0000000: 2831 303a 7075 626c 6963 2d6b 6579 2839  (10:public-key(9
0000010: 3a72 7361 2d70 6b63 7331 2831 3a6e 3733  :rsa-pkcs1(1:n73
0000020: 3a00 c2cb b24f dbf9 23b6 1268 e3f1 1a38  :....O..#..h...8
0000030: 96de 4574 b3ba 5873 0cbd 6529 3886 4e22  ..Et..Xs..e)8.N"
0000040: 23ee eb70 4a17 cfd0 8d16 b468 91a6 1474  #..pJ......h...t
0000050: 7599 39c6 e49a afe7 f259 5548 c74c 1d7f  u.9......YUH.L..
0000060: b8d2 4cd1 5cb2 3b4c d0a3 2928 313a 6533  ..L.\.;L..)(1:e3
0000070: 3a01 0001 2929 29                        :...)))  


(I like to use pkcs1-conv from the nettle-bin package to do this step though it can be done with other methods)

From this information n can be obtained from bytes 0x21 - 0x69

I know this because after the header with "(1:n73", after the final character 0x3a, begins the modulus, it ends before the signature 0000060: ... 29 28 31 3a 65 33 3a ...

n = 0xc2cbb24fdbf923b61268e3f11a3896de4574b3ba58730cbd652938864e2223ee eb704a17cfd08d16b46891a61474759939c6e49aafe7f2595548c74c1d7fb8d24cd1 5cb23b4cd0a3

e = 0x010001 (from bytes 0x71-0x73)

These now need to be turned into integers so load up python or whatever you want:
root@vm:~/Desktop/RSAcrack/# python
>>> int("0xc2cbb24fdbf923b61268e3f11a3896de4574b3ba58730cbd652938864e2223ee eb704a17cfd08d16b46891a61474759939c6e49aafe7f2595548c74c1d7fb8d24cd1 5cb23b4cd0a3", 16)

188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059L

>>> int("0x10001", 16)
65537

n = 188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059L
e = 65537

Now this is where the luck or processing power will come in... we need to find the factors (p,q) from the modulus (n) integer. The first place to look is a factor database which have already been generated so go to factordb.com and enter your modulus:

http://www.factordb.com/

 I happen to have two factors returned so save these and now these are your p and q parameters, if you dont happen to find factors already on the web you will have to try and generate them yourselves, and this is what makes RSA harder to crack as more bits are used in generation

so now:

p =  398075086424064937397125500550386491199064362342526708406385189575946388957261768583317
q =  472772146107435302536223071973048224632914695302097116459852171130520711256363590397527

Everything we need apart from the private key exponent (d) which we can hopefully deduce from the information currently owned(p, q, n, e).
There is a python script which can generate RSA algorithms given the correct parameters, so run this through rsatool.py -p -q -n -e

(https://raw.github.com/ius/rsatool/master/rsatool.py)

root@vm:~/Desktop/RSAcrack/# python rsatool.py -p 398075086424064937397125500550386491199064362342526708406385189575946388957261768583317 -q 472772146107435302536223071973048224632914695302097116459852171130520711256363590397527 -n 188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059 -e 65537
Using (p, q) to initialise RSA instance

n =
c2cbb24fdbf923b61268e3f11a3896de4574b3ba58730cbd652938864e2223eeeb704a17cfd08d16
b46891a61474759939c6e49aafe7f2595548c74c1d7fb8d24cd15cb23b4cd0a3

e = 65537 (0x10001)

d =
32030e42c69d4e77de7e2397b13dba2e52f2c57a205f5973fed6f87632f53cf8886609ff63fa114e
2b5df1db6249f8eaf0bf5fa26ad5b8e48b7fab050d32fc574b446e22d08ba7b1

p =
cce95457f127c49546e57841029ac6af70604c64e8281018acbb538233bb57f37a6e6895

q =
f35cb825f003396f11f149a59a0fe73db43162cb305b8ebfeda5ca840be24c536b6aae57
We now have been given d which is the private key exponent which has been generated via: d = e^-1(mod f(n))

All you need now is a short python script which I found on the net which uses all the paramaters you have found to decrypt the original file and you have cracked 768 bit RSA

RSAcrack.py:
#!/usr/bin/python
from sys import*;from string import*;a=argv;[s,p,q]=filter(lambda x:x[:1]!=
'-',a);d='-d'in a;e,n=atol(p,16),atol(q,16);l=(len(q)+1)/2;o,inb=l-d,l-1+d
while s:s=stdin.read(inb);s and map(stdout.write,map(lambda i,b=pow(reduce(
lambda x,y:(x<<8L)+y,map(ord,s)),e,n):chr(b>>8*i&255),range(o-1,-1,-1))) 

Usage : cat file | python rsacrack.py -d [private key exponent] [public key modulus]

Ill run this command and pipe it to Strings as it is strings Im after:

root@vm:~/Desktop/RSAcrack/# cat file2crack.bin | python RSAimplement.py -d 32030e42c69d4e77de7e2397b13dba2e52f2c57a205f5973fed6f87632f53cf8886609ff63fa114e2b5df1db6249f8eaf0bf5fa26ad5b8e48b7fab050d32fc574b446e22d08ba7b1 C2CBB24FDBF923B61268E3F11A3896DE4574B3BA58730CBD652938864E2223EEEB704A17CFD08D16B46891A61474759939C6E49AAFE7F2595548C74C1D7FB8D24CD15CB23B4CD0A3 | strings
Ae"h
up2l6DnaIhZgxA
 
And there you have it, the decrypted message was:
Ae"h
up2l6DnaIhZgxA


----------------------------------------------------------------

Any questions feel free to comment below!
Hope this was of help to some of you who dont already know it!

~m0x39