## 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* = *m ^{e}* (mod

*n*) and decrypt the cipher test

*c*as

*m*=

*c*.

^{d}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):

- [Initialize] Set
*k*←*d e*− 1. - [Try a random
*g*] Choose*g*at random from {2, …,*n*− 1} and set*t*←*k*. - [Next
*t*] If*t*is divisible by 2, set*t*←*t*/ 2 and*x*←*g t*(mod*n*). Otherwise go to Step 2. - [Finished?] If
*x*> 1 and*y*= gcd(*x*−1,*n*) > 1 then set*p*←*y*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.

In Erlang; gcd and powmod are defined in the module.

Ok, here’s some Python: I’ve rearranged the algorithm a little to hopefully be more efficient – find the smallest possible value of x by repeated halving, then we only need one call to pow per value of g, the rest can be got by squaring. Also I’ve checked that we don’t have a trivial root of unity (and if we do, we can bail out early):

The Wiener attack described in the Boneh paper is quite fun as well.