## Factoring RSA Moduli

### March 24, 2014

We studied RSA encryption in a previous exercise. To recap: select two prime numbers p and q and make their product n = p q the modulus of the crypto system. Choose an encryption key e and a decryption key d such that d e ≡ 1 (mod φ(p q)), where the totient φ(p q) = (p − 1) × (q − 1). Then encrypt a message m as c = me (mod n) and decrypt the cipher test c as m = cd.

In our implementation we chose p and q randomly and kept them secret, even from the user who knows the decryption key. Of course, it is hard for someone who knows who does not know d to factor n and thus compute d; that is the basis of the encryption. But it is fairly easy to recover p and q if you know n, e and d, as Boneh showed (page 205, left column, Fact 1):

1. [Initialize] Set k d e − 1.
2. [Try a random g] Choose g at random from {2, …, n − 1} and set tk.
3. [Next t] If t is divisible by 2, set tt / 2 and xg t (mod n). Otherwise go to Step 2.
4. [Finished?] If x > 1 and y = gcd(x −1, n) > 1 then set py and q &larrow; n / y, output p and q and terminate the algorithm. Otherwise go to Step 3.

For instance, given n = 25777, e = 3 and d = 16971, we calculate p = 149 and q = 173 when g = 5, noting that 149 × 173 = 25777; on average, it takes no more than two different g to complete the algorithm. Knowledge of p and q, though not necessary, is useful, because a more efficient decryption is possible using p, q and the Chinese remainder theorem, which does arithmetic with numbers the size of p and q instead of the size of their product.

Your task is to write a program that factors RSA moduli. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2