## 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.

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.