# 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 considerable more difficult to crack. In fact you would need all the computing 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 factoize the modulus, RSA is cracked. Unfortunately quantum computers can easily factorize the moduls.