# Cracking short RSA keys

Public Key: (10142789312725007, 5)

which means

``````n = 10142789312725007
e = 5
``````

where n is the modulus and e is the public exponent.

Private Key: (10142789312725007, 8114231289041741)

meaning that

`````` d = 8114231289041741
``````

where d is the decryption exponent that should remain secret.

You can “break” RSA by knowing how to factor “n” into its “p” and “q” prime factors:

``````n = p * q
``````

The easiest way is probably to check all odd numbers starting just below the square root of n:

``````Floor[Sqrt] = 100711415
``````

You would get the first factor in 4 tries:

``````10142789312725007 mod 100711415 = 100711367
10142789312725007 mod 100711413 = 100711373
10142789312725007 mod 100711411 = 100711387
10142789312725007 mod 100711409 = 0 <-- Winner since it evenly divides n
``````

So we have

`````` p = 100711409
``````

Now,

`````` q = n / p
= 10142789312725007 / 100711409
= 100711423
``````

Why is this important? It’s because d is a special number such that

``````d = e^-1 mod phi(n)
= e^-1 mod (p-1)*(q-1)
``````

We can verify this

``````d * e = 40571156445208705 = 1 mod 10142789111302176
``````

This is important because if you have a plaintext message m then the ciphertext is

``````c = m^e mod n
``````

and you decrypt it by

``````m = c^d = (m^e)^d = (m^(e*d)) = (m^(e*e^-1)) = m^1 (mod n)
``````

For example, I can “encrypt” the message 123456789 using your teacher’s public key:

``````m = 123456789
``````

This will give me the following ciphertext:

``````c = m^e mod n
= 123456789^5 mod 10142789312725007
= 7487844069764171
``````

(Note that “e” should be much larger in practice because for small values of “m” you don’t even exceed n)

Anyways, now we have “c” and can reverse it with “d”

``````m = c^d mod n
= 7487844069764171^8114231289041741 mod 10142789312725007
= 123456789
``````

Obviously, you can’t compute “7487844069764171^8114231289041741” directly because it has 128,808,202,574,088,302 digits, so you must use the modular exponentiation trick.

In the “Real World”, n is obviously much larger. If you’d like to see a real example of how HTTPS uses RSA under the covers with a 617-digit n and an e of 65537, see my blog post “The First Few Milliseconds of an HTTPS Connection.”