;;; This file provides useful functions on which an implementation of
;;; the RSA cryptosystem may be based.
;;; Start by calling
;;; (create-keys)
;;; to create public and private keys. (The function "key-component-list"
;;; called by "create-keys" must be provided.)
;;; Then, to encode a string, call
;;; (code s key-file)
;;; which encrypts s in a big integer using the information in the given
;;; key file. To decrypt a big integer into a string, call
;;; (code bigint key-file)
;;; The function key-component-list called by create-keys and the function
;;; mod-power called by code must be completed before any of this works.
;; Global variables
(define KEY-LENGTH 40)
(define PUBLIC-KEY-FILE-NAME "public-key")
(define PRIVATE-KEY-FILE-NAME "private-key")
;; Return the result of converting the nonempty string str to a big integer,
;; essentially using the ASCII codes of the characters of str as base 256
;; digits.
(define (string->bigint str)
(accumulate
(lambda (big little) (+ (* big 256) little))
(map char->integer (string->list str)) ) )
;; Return the result of accumulating the given binary function over the
;; given list (left to right). The function, given an accumulation and
;; an element to add to it, returns the new accumulation.
(define (accumulate f L)
(accumulate-helper f (cdr L) (car L)) )
(define (accumulate-helper f L so-far)
(if (null? L)
so-far
(accumulate-helper f (cdr L) (f so-far (car L))) ) )
;; Return the result of interpreting the digits base 256 of bigint
;; as characters, then combining them into a string.
(define (bigint->string bigint)
(list->string (map integer->char (split bigint))) )
;; Return the result of splitting the bigint into base 256 digits.
(define (split bigint)
(if (< bigint 256) (list bigint)
(append (split (quotient bigint 256)) (list (remainder bigint 256))) ) )
;; Return the key stored in the given file.
;; The key consists of two positive integers; return them in a list.
(define (key-from-file file-name)
(let*
((key-file (open-input-file file-name))
(e (read key-file))
(n (read key-file)) )
(if (or (not (integer? e)) (not (integer? n)) (< e 1) (< n 1))
(error "bad key value")
(list e n) ) ) )
;; Encrypt/decrypt the given argument, using the given key file.
;; If the argument is a string, we're encrypting it; otherwise it's an integer
;; and we're decrypting it.
(define (code arg file-name)
(let
((key (key-from-file file-name)))
(if (string? arg)
(mod-power (string->bigint arg) (car key) (cadr key))
(bigint->string (mod-power arg (car key) (cadr key))) ) ) )
;; Create a public and corresponding private key, and write them to the files
;; whose names are stored in PUBLIC-KEY-FILE-NAME and PRIVATE-KEY-FILE-NAME
;; respectively. The length of the prime numbers on which these keys are based
;; is KEY-LENGTH.
(define (create-keys)
(let
((e-d-n (key-component-list (+ (expt 10 KEY-LENGTH) 1)))
(public-key-file (open-output-file PUBLIC-KEY-FILE-NAME))
(private-key-file (open-output-file PRIVATE-KEY-FILE-NAME)) )
(display (car e-d-n) public-key-file)
(display " " public-key-file)
(display (caddr e-d-n) public-key-file)
(newline public-key-file)
(close-output-port public-key-file)
(display (cadr e-d-n) private-key-file)
(display " " private-key-file)
(display (caddr e-d-n) private-key-file)
(newline private-key-file)
(close-output-port private-key-file) ) )
;; Return the list (e d n), where (e n) is an RSA public key and (d n) is
;; the corresponding private key. Start searching for the primes on which
;; these keys are based at start-value.
(define (key-component-list start-value)
(let
((prime-list (primes start-value 3 2)))
(list
3
(inverse 3 (* (- (car prime-list) 1) (- (cadr prime-list) 1)))
(* (car prime-list) (cadr prime-list)) ) ) )
;; Return a list of n primes p greater than start-value (a positive odd integer)
;; and for which forbidden does not divide p-1.
(define (primes start-value forbidden n)
(cond
((= n 0) '( ))
((and (is-prime? start-value 20) (> (remainder (- start-value 1) forbidden) 0))
(cons start-value (primes (+ start-value 2) forbidden (- n 1))) )
(else (primes (+ start-value 2) forbidden n)) ) )
;; Determine if p is probably prime, by checking up to n random values a
;; to make sure a^(p-1) == 1 mod p.
(define (is-prime? p n)
(or
(= n 0)
(and
(= (mod-power (+ 1 (random (- p 1))) (- p 1) p) 1)
(is-prime? p (- n 1)) ) ) )
;; Return the result of raising m to the exp power, mod n.
(define (mod-power m exp n)
(cond
((= exp 0) 1)
((odd? exp) (remainder (* m (mod-power (remainder (* m m) n) (quotient exp 2) n)) n))
(else (remainder (mod-power (remainder (* m m) n) (quotient exp 2) n) n)) ) )
;; Return the result of raising m to the exp power.
(define (power m exp)
(cond
((= exp 0) 1)
((odd? exp) (* m (power (* m m) (quotient exp 2))))
(else (power (* m m) (quotient exp 2))) ) )
;; Return the multiplicative inverse of a, mod n.
(define (inverse a n)
(let
((rtn (cadr (extended-euclid a n))))
(if (>= rtn 0) rtn (+ n rtn)) ) )
;; Apply the Extended Euclid algorithm for finding d = gcd(a,b).
;; This also finds x and y such that d = a*x + b*y, and returns
;; a list containing d, x, and y in that order.
(define (extended-euclid a b)
(if (= b 0)
(list a 1 0)
(let
((triple (extended-euclid b (remainder a b))))
(list
(car triple)
(caddr triple)
(- (cadr triple) (* (caddr triple) (quotient a b))) ) ) ) )