# 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 = 954354002755510667q = 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:  607778777406675887172756406181993732p:  954354002755510667q:  801297755486859913=== Calc ===d= 487033582336704937347300968187062897n= 764721720347891218098402268606191971Decrypt: 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.

Written by

## ASecuritySite: When Bob Met Alice

#### This publication brings together interesting articles related to cyber security.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just \$5/month. Upgrade