;;; 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))) ) ) ) )