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):
- [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.
Programming Praxis 
In Erlang; gcd and powmod are defined in the module.
-module(ex1). -export([rsa_factors/3]). gcd(A, 0) -> A; gcd(A, B) -> gcd(B, A rem B). powmod(_, 0, _) -> 1; powmod(A, N, M) -> case N band 1 of 0 -> X = powmod(A, N bsr 1, M), X*X rem M; 1 -> A*powmod(A, N-1, M) rem M end. try_random(N) -> random:uniform(N-2) + 1. rsa_factors(N, E, D) -> K = E*D - 1, rsa_factors(N, E, D, K, K, try_random(N)). rsa_factors(N, E, D, K, T, G) -> if T band 1 =:= 1 -> rsa_factors(N, E, D, K, K, try_random(N)); true -> T2 = T bsr 1, X = powmod(G, T2, N), Y = gcd(X-1, N), if (X > 1) and (Y > 1) -> {Y, N div Y}; true -> rsa_factors(N, E, D, K, T2, G) end end. 9> ex1:rsa_factors(25777, 3, 16971). {173,149} 10>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):
#!/usr/bin/python from random import randrange def gcd (a,b): while b != 0: a,b = b,a%b return a def factor(n,d,e): k = d*e-1 while True: g = randrange(2,n) t = k while t%2 == 0: t = t//2 x = pow(g,t,n) while t < k and x != 1 and x != n-1: if x*x%n==1: a = gcd(x-1,n) b = n//a if a>b: return (b,a) else: return (a,b) x = x*x%n t = t*2 def test(n,d,e): (a,b) = factor(n,d,e) print(n,d,e,a,b) assert(a != 1) assert(b != 1) assert(a*b == n) test(25777,3,16971) test(0xa66791dc6988168de7ab77419bb7fb0c001c62710270075142942e19a8d8c51d053b3e3782a1de5dc5af4ebe99468170114a1dfe67cdc9a9af55d655620bbab, 0x10001, 0x123c5b61ba36edb1d3679904199a89ea80c09b9122e1400c09adcf7784676d01d23356a7d44d6bd8bd50e94bfc723fa87d8862b75177691c11d757692df8881)The Wiener attack described in the Boneh paper is quite fun as well.