;;; ===========================================================================
;;; Code for Problem Set 2, CS 212, Spring 1999
;;; RSA Encryption/Decryption
;;; Last modified 2/10/1999 by gjw5,sw77,eli

;;; First, some simple data abstraction

;;; An RSA key consists of a modulus and an exponent.
(define key-modulus  first)
(define key-exponent second)
(define (make-key modulus exponent)
  (list modulus exponent))

;;; RSA key pairs are two-element lists keys.
(define public-key  first)
(define private-key second)
(define (make-key-pair public private)
  (list public private))

;;; Random function that works on really big numbers.
(define (rand n)
  (if (< n 1073741823)
    (random n)
    (floor (* (random 1073741823) (/ n 1073741823)))))

;;; Fast modular exponentiation.
(define (square x) (* x x))
(define (expmod b e m)
  (cond ((zero? e) 1)
        ((even? e) (modulo (square (expmod b (floor (/ e 2)) m)) m))
        (else (modulo (* b (expmod b (- e 1) m)) m))))

;;; generating RSA keys:
;;; To choose a prime, we start searching at a random odd number in a
;;; specifed range.
(define (choose-prime smallest range)
  (let ((start (+ smallest (rand range))))
    (search-for-prime
     (if (even? start)
       (+ start 1)
       start))))

(define (search-for-prime guess)
  (if (fast-prime? guess)
    guess
    (search-for-prime (+ guess 2))))

;;; The Fermat test for primality
(define (fermat-test n a)
  (= (expmod a n n) a))

(define (fast-prime? n)
  (if (> n 7)
    (and (fermat-test n 2) (fermat-test n 3)
         (fermat-test n 5) (fermat-test n 7))
    (or (= n 2) (= n 3) (= n 5) (= n 7))))

;;; generate an RSA key pair (k1, k2).  This has the property that
;;; transforming by k1 and transforming by k2 are inverse operations.
;;; Thus, we can use one key as the public key and one as the private key.
(define (generate-RSA-key-pair r)
  (let* ((size (expt 2 r))
         (p (choose-prime size size))
         (q (choose-prime size size)))
    (if (= p q) ;check that we haven't chosen the same prime twice
      (generate-RSA-key-pair r) ;VERY unlikely
      (let* ((n (* p q))
             (m (* (- p 1) (- q 1)))
             (z (select-keys m))
             (e (first  z))
             (d (second z)))
        (make-key-pair (make-key n e) (make-key n d))))))

;;; The RSA exponent can be any random number relatively prime to m.
(define (select-keys m)
  (let* ((e (rand m))
         (z (Euclid e m)))
    (if (= (third z) 1)
      (list e (modulo (first z) m))
      (select-keys m))))

;;; Euclidean algorithm for integers:
;;; given m, n, calculates (s t g) where
;;; g = gcd(m,n) and sm + tn = g.
(define (Euclid m n)
  (if (zero? n) (list 1 0 m)
      (let* ((q (floor (/ m n)))
             (r (modulo m n))
             (z (Euclid n r))
             (u (first z))
             (v (second z))
             (g (third z)))
        (list v (- u (* q v)) g))))

;;; Fundamental transformation in RSA,
;;; Used to both encrypt and decrypt.
(define (RSA-transform number key)
  (expmod number (key-exponent key) (key-modulus key)))

;;; Compress a list of numbers to a single number,
;;; use when creating digital signatures.
(define (compress intlist)
  (letrec ((add-loop
            (lambda (l)
              (if (null? l)
                0
                (+ (head l) (add-loop (tail l)))))))
    (modulo (add-loop intlist) (expt 2 18))))

;;; Actual RSA encryption and decryption

(define (RSA-encrypt string key)
  (RSA-encrypt-list (string->intlist string) key))

(define (RSA-encrypt-list intlist key)
  (if (null? intlist)
    '()
    (let* ((encrypted-tail
            (RSA-encrypt-list (tail intlist) key))
           (encrypted-head
            (RSA-transform (if (null? encrypted-tail)
                             (head intlist)
                             (modulo (+ (head intlist)
                                        (head encrypted-tail))
                                     (key-modulus key)))
                           key)))
      (cons encrypted-head encrypted-tail))))

(define (RSA-decrypt intlist key)
  (intlist->string (RSA-decrypt-list intlist key)))

;;;; converting between strings and numbers

;;; The following procedures are used to convert between strings, and
;;; lists of integers in the range 0 through 2^14.  You are not
;;; responsible for studying this code -- just use it.

;;; Convert a string into a list of integers, where each integer
;;; encodes a block of characters.  Zero is used to terminate strings,
;;; so null chars (ASCII 0) cannot be used.
(define (string->intlist string)
  (letrec ((bsize 2)
           (convert
            (lambda (chlist ccount val)
              (let ((empty? (null? chlist)))
                (if (= ccount bsize)
                  (cons val (if empty? '() (convert chlist 0 0)))
                  (let ((n (if empty? 0 (char->integer (head chlist))))
                        (tail (if empty? '() (tail chlist))))
                    (convert tail (+ ccount 1)
                             (+ val (* n (expt 128 ccount))))))))))
    (convert (string->list string) 0 0)))

;;; Convert a list of integers to a string.
;;; Inverse of string->intlist.
(define (intlist->string ilst)
  (letrec ((bsize 2)
           (convert
            (lambda (ilist)
              (cond
               ((null? ilist) '())
               ((zero? (head ilist)) (convert (tail ilist)))
               (else
                (cons (integer->char (remainder (first ilist) 128))
                      (convert (cons (quotient (head ilist) 128)
                                     (tail ilist)))))))))
    (list->string (convert ilst))))

;;; Some initial test data

(define test-key-pair1
  (make-key-pair (make-key 979739 909703)
                 (make-key 979739 692407)))

(define test-key-pair2
  (make-key-pair (make-key 551687 18499)
                 (make-key 551687 94699)))

(define test-public-key1  (public-key  test-key-pair1))
(define test-private-key1 (private-key test-key-pair1))
(define test-public-key2  (public-key  test-key-pair2))
(define test-private-key2 (private-key test-key-pair2))

;;; secret message
(define secret
  '(8047026042  6031491778  5620338436 2128396417 4414828450 5276391726
    9667726550 10185065604  9557826642 2775156152 3561654253 4998025257
    7153371753  2297328003  2062934878 516704859 10080230388 7453457983
    9551941153  1778700195 10210783615 4273892595 9261866769  548425468
    4801737916  1026180403  3123556970 6728793752))

(define secret-signature 3146751876)

(define greg     (make-key  4863407657 4778116387))
(define david    (make-key  6853186687 1972819777))
(define eli      (make-key  7830893839 6830138073))
(define tony     (make-key 10585718009 7130234681))
(define aleksey  (make-key  5664859631 5015784857))
(define brandon  (make-key 10863507547 3210779197))
(define carson   (make-key 12355940249 1043358583))
(define grant    (make-key 10049119891 1037648987))
(define maverick (make-key  9043160501  437488633))
(define manish   (make-key 10561468111 3139494983))