November 16, 2010
The key generator takes the number of bits k and the encryption key e and returns the modulus n and the decryption key d. Large primes v are generated as a random integer on the range 2k/2−1 ≤ v < 2k/2; if v is not prime, or not co-prime to e, or not congruent to 3 mod 4 (which avoids some nasty theoretical weaknesses), then it is incremented and the tests are applied again. This process can take a while for large values of k, because the arithmetic on large integers is slow and because it can take hundreds or thousands of trial v before a suitable one is found:
(define (keygen k e)
(define (gen k)
(let loop ((v (randint (expt 2 (- k 1)) (expt 2 k))))
(if (or (< 1 (gcd e (- v 1)))
(not (= (modulo v 4) 3))
(not (prime? v)))
(loop (+ v 1))
(let* ((k2 (quotient k 2)) (p (gen k2)) (q (gen k2))
(d (inverse e (* (- p 1) (- q 1)))))
(values (* p q) d)))
Encryption and decryption can be done by a single function; as long as you feed it the right key, it will make the right calculation:
(define (crypt text modulus key)
(expm text key modulus))
Here’s a 32-bit example, using the message 42:
> (keygen 32 65537)
> (crypt 42 1893932189 65537)
> (crypt 1118138102 1893932189 1461164273)
We don’t know the random numbers p and q used by the key generator, but we can factor n to find them; of course, if n was larger, factoring would be more difficult, which is the basis for the security of the algorithm. We use Fermat’s method to do the factoring, since p and q must be close, so Fermat’s method is better than trial division:
> (factors 1893932189)
We steal much code from other sources.
randint come from the Standard Prelude.
jacobi come from the exercise on modular arithmetic.
Square? comes from the exercise on powering predicates.
Prime? is the Baillie-Wagstaff algorithm, and
factors is the Fermat method. You can run the program at http://programmingpraxis.codepad.org/rRxeR2C9.
Pages: 1 2