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:

Integer Factorization

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

p = 954354002755510667
q =…