Cracking RSA

Cracking RSA

Recently Crown Sterling gave a demo of cracking a 256-bit RSA key. Unfortunately this size of key is hardly a major challenge in the industry, as these keys can be broken with limited computing resources. In practice we use a 2,048 bit modulus (and created by two 1,024 bit prime numbers), and which is considerably more difficult to crack. In fact you would need all the computing power — and all the electrical power — on the planet, and much more, to crack a single 2048 bit key.

So what’s the strength of RSA? Well, it’s related to the factorization of a modulus N into its prime number factors (p and q). If we can find p and q, we can crack the cipher.

So let’s try:

c=607778777406675887172756406181993732, and

N = 764721720347891218098402268606191971.

First we factorize N into its prime number factors. As we are using 60-bit prime numbers (which gives a 120-bit modulus), it is fairly easy to factorize:

It will take a few seconds to generate, but it will give the factors of:

p = 954354002755510667
q = 801297755486859913

Once we have these, we calculate PHI:

PHI=(p-1) (q-1)

Now we can determine the decryption key with:

d = e^{-1} (mod PHI)

Then we crack with:

Msg = c^d (mod N)

A sample run is [here]:

Cipher:  607778777406675887172756406181993732
p:  954354002755510667
q:  801297755486859913
=== Calc ===
d= 487033582336704937347300968187062897
n= 764721720347891218098402268606191971
Decrypt: kiwi

And there you go, we have found the fruit (“kiwi”). If we can factorize the modulus, RSA is cracked. Unfortunately quantum computers can easily factorize the modulus.

So here are some challenges for you:

• Can you find the animal? N=1171846932127658054303826252418828087 [factor], cipher=854921192940138883343456605232835549
• Can you find the city in England? N=826382916071823972711332001902568877 [factor], cipher=511617430183577168370958189976920833
• Can you find the body part? N=679206928164089960010136369317092551 [factor], cipher=4427699773234871172974186441969212
• Can you find the rock band? N=879509040449463763008386484793372267 [factor], cipher=850431005415590313843011081245086829
• Can you find the animal? N=645154426308578189134388912287864207 [factor], cipher=67340510464226661815115118309943778
• Can you find something to wear? N=795781142060545778444522975346669739 [factor], cipher=519014392082457908457066775093953041

The coding is here:

from Crypto.Util.number import *
from Crypto import Random
import Crypto
import gmpy2
import sys

p=954354002755510667
q=801297755486859913
c=607778777406675887172756406181993732
#N=764721720347891218098402268606191971

if (len(sys.argv)>1):
        c=int(sys.argv[1])
if (len(sys.argv)>2):
        p=int(sys.argv[2])
if (len(sys.argv)>3):
        q=int(sys.argv[3])

n = p*q
PHI=(p-1)*(q-1)

e=65537
d=(gmpy2.invert(e, PHI))

res=pow(c,d, n)

print "Cipher: ",c
print "p: ",p
print "q: ",q

print "\n=== Calc ==="
print "d=",d
print "n=",n
print "Decrypt: %s" % ((long_to_bytes(res)))