Cracking RSA

Prof Bill Buchanan OBE
Oct 8 · 2 min read

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.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

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