RSA in scheme

I got tired of using factorial and fibonacci as benchmarks for my research, so I threw together an implementation of the RSA public-key cryptography system in Scheme.

Automatic support for arbitrarily large numbers makes the implementation feel more natural than an equivalent implementation in other languages. I also learned that gcd, used for coprimality testing, has been a part of the Scheme standard since at least R5RS.

The short implementation is appended below.

Note: I have also created an implementation of the Fermat and Solovay-Strassen primality tests, useful for the key-generation phase of RSA.

Code

;; Mathematical routines.

; extended-gcd(a,b) = (x,y), such that a*x + b*y = gcd(a,b)
(define (extended-gcd a b)
  (if (= (modulo a b) 0)
      (cons 0 1)
      (let* ((x:y (extended-gcd b (modulo a b)))
             (x (car x:y))
             (y (cdr x:y)))
        (cons y (- x (* y (quotient a b)))))))

; modulo-inverse(a,n) = b, such that a*b = 1 [mod n].
(define (modulo-inverse a n)
  (modulo (car (extended-gcd a n)) n))

; totient(n) = (p - 1)*(q - 1), 
;  where pq is the prime factorization of n.
(define (totient p q) (* (- p 1) (- q 1)))

; square(x) = x^2
(define (square x) (* x x))

; modulo-power(base,exp,n) = base^exp [mod n]
(define (modulo-power base exp n)
  (if (= exp 0)
      1
      (if (odd? exp)
          (modulo (* base (modulo-power base (- exp 1) n)) n)
          (modulo (square (modulo-power base (/ exp 2) n)) n))))




;; RSA routines.

; A legal public exponent e is between
;  1 and totient(n), and gcd(e,totient(n)) = 1
(define (is-legal-public-exponent? e p q)
  (and (< 1 e) 
       (< e (totient p q))
       (= 1 (gcd e (totient p q)))))

; The private exponent is the inverse of the public exponent, mod n.
(define (private-exponent e p q) 
  (if (is-legal-public-exponent? e p q)
      (modulo-inverse e (totient p q))
      (error "Not a legal public exponent for that modulus.")))

; An encrypted message is c = m^e [mod n].
(define (encrypt m e n)
  (if (> m n)
      (error "The modulus is too small to encrypt the message.")
      (modulo-power m e n)))

; A decrypted message is m = c^d [mod n].
(define (decrypt c d n)
  (modulo-power c d n))




;; RSA example.

(define p 41)       ; A "large" prime.
(define q 47)       ; Another "large" prime.
(define n (* p q))  ; The public modulus.

(define e 7)                        ; The public exponent.
(define d (private-exponent e p q)) ; The private exponent.

(define plaintext  42)           
(define ciphertext (encrypt plaintext e n)) 

(define decrypted-ciphertext (decrypt ciphertext d n))


(display "The plaintext is:            ")
(display plaintext)
(newline)

(display "The ciphertext is:           ")
(display ciphertext)
(newline)

(display "The decrypted ciphertext is: ")
(display decrypted-ciphertext)
(newline)

(if (not (= plaintext decrypted-ciphertext))
    (error "RSA fail!"))