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)

Solution 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."

Solution 2

Here's a relatively simple way to look at it (and one that is doable by hand). If you were to factor the number completely, then the highest factor you would need to consider is sqrt(N):

sqrt(10142789312725007) = 100711415.9999997567

The first prime below this is 100711409, just 6 below the sqrt(N).

10142789312725007 / 100711409 = 100711423 

therefore these are two factors of N. Your professor made it pretty easy - the trick is to recognize that no one would choose a small p or q so starting your check from the bottom (as in the python script someone posted) is a bad idea. If it's going to be practical by hand, the large p and q must lie near sqrt(N).

Solution 3

There are various fast algorithms to solve the problem of factoring n given n, e, and d. You can find a good description of one such algorithm in the Handbook of Applied Cryptography, Chapter 8, section 8.2.2. You can find these chapters online for free download here. The algorithm is essentially a careful elaboration of Henno Brandsma's answer to this very question.

UPDATE Sep 25, 2019:

In the comment below, user Imperishable Night suggests an alternative method which should be at least conceptually easier to understand.

He notes that usually e is small. In fact e is almost always 65537. In the case that e is small you can develop a quadratic equation in the unknown prime p and thus easily solve for it using e.g. the quadratic formula. To proceed, lets set x=p and solve for x, just to stick with convention. We know that ed = 1 mod phi(n), or equivalently ed - 1 = k * (p-1)*(q-1). Now setting x=p, and therefore n/x=q, multiplying both sides by x and rearranging terms we have
k*x² + (d*e - k*n - k - 1)*x + k*n = 0.
Now we have an equation of the form ax² + bx + c = 0 and we can solve for x using the quadratic formula. So we can try values of k in a small range around e and there should be only one integer solution to the quadratic, the solution for the correct k.

Notes:

1. Everything must be an integer, thus the discriminant must be a perfect square or we can discard k and try the next one. Also, the numerator must be divisible by 2*k.
2. Sometimes the Carmichael lambda function is used in place of the Euler phi function. This complicates things just a little bit because we must now also guess the g = gcd(p-1, q-1). g is always even, is often 2, and is otherwise almost always a small multiple of 2.

UPDATE Sep 26, 2019:

Finding k is actually very easy when e is small. By taking the equation ed - 1 = k * (p-1)*(q-1) and dividing both sides by n it is fairly easy to see that floor((ed-1)/n) + 1 == k. Now using equations 31 and 32 of M.J. Wiener's "Cryptanalysis of Short RSA Secret Exponents" one can directly recover p and q.

Solution 4

Wolframalpha tells me that the factors are 100711409 and 100711423

I just wrote a naive Python script to bruteforce it. As amdfan pointed out, starting from the top is a better approach:

p = 10142789312725007
for i in xrange(int(p**0.5+2), 3, -2):
    if p%i == 0:
        print i
        print p/i
        break

This could be heavily improved, but it still works without a problem. You could improve it by just testing primfactors, but for small values like yours this should be enough.

Solution 5

The definition of RSA tells you that the modulus n = pq. You know n so you just need to find two numbers p and q that multiply to produce n. You know that p and q are prime, so this is the prime factorisation problem.

You can solve this by brute force for relatively small numbers but the overall security of RSA depends on the fact that this problem is intractable in general.

View more solutions