Cracking short RSA keys

Question

Given the following RSA keys, how does one go about determining what the values of p and q are?

Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)

Answer 1

Your teacher gave you:

Public Key: (10142789312725007, 5)

which means

n = 10142789312725007
e = 5 

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

In addition, you're given

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[10142789312725007]] = 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."