Factoring RSA Moduli
March 24, 2014
Our function is a simple translation of the algorithm into Scheme:
(define (rsa-factors n e d)
(let ((k (- (* d e) 1)))
(let loop ((g 2) (t k))
(when verbose?
(display g) (display " ")
(display t) (newline))
(if (positive? (modulo t 2))
(loop (next-prime g) k)
(let* ((t (/ t 2))
(x (expm g t n))
(y (gcd (- x 1) n)))
(if (and (< 1 x) (< 1 y))
(values y (/ n y))
(loop g t)))))))
We cheat by choosing g as a small prime instead of choosing it at random. Since the function never takes a large number of trials, we implement next-prime simply by making a list of the primes to a thousand:
(define primes
(let ((sieve (make-vector 1001 #t)) (ps (list)))
(do ((p 2 (+ p 1))) ((< 1000 p) (reverse ps))
(when (vector-ref sieve p)
(set! ps (cons p ps))
(do ((i (* p p) (+ i p))) ((< 1000 i))
(vector-set! sieve i #f))))))
(define (next-prime n) (cadr (member n primes)))
Here are two examples:
> (define verbose? #t)
> (rsa-factors 25777 3 16971)
2 50912
2 25456
2 12728
2 6364
2 3182
2 1591
3 50912
3 25456
3 12728
3 6364
3 3182
3 1591
5 50912
5 25456
5 12728
5 6364
149
173
> (define n #xa66791dc6988168de7ab77419bb7fb0c001c62710270075142942e19a8d8c51d053b3e3782a1de5dc5af4ebe99468170114a1dfe67cdc9a9af55d655620bbab)
> (define e #x10001)
> (define d #x123c5b61ba36edb1d3679904199a89ea80c09b9122e1400c09adcf7784676d01d23356a7d44d6bd8bd50e94bfc723fa87d8862b75177691c11d757692df8881)
> (rsa-factors n e d)
2 3912086784511471289561151952301925086168946454709316095960618800742799369173365724802767882894790378640224771497700744632822349777243736269522672978216650880
2 1956043392255735644780575976150962543084473227354658047980309400371399684586682862401383941447395189320112385748850372316411174888621868134761336489108325440
2 978021696127867822390287988075481271542236613677329023990154700185699842293341431200691970723697594660056192874425186158205587444310934067380668244554162720
2 489010848063933911195143994037740635771118306838664511995077350092849921146670715600345985361848797330028096437212593079102793722155467033690334122277081360
23234950162188993388155927630085331316851060055334470382368804331834850828939
23443439767333138692938389505422341860387525814723848738690073331642118819681
You can run the program at http://programmingpraxis.codepad.org/IPzF6L68.
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.