RSA.scm

;;; [email protected]     Wed Oct 19 12:48:37 2016
  		      
#lang sicp   		      	 
(#%require (only racket/base random))
(define your-answer-here -1)   		      	 
   		      	  		      	 
;;; +mod takes two numbers and modulo n
;;; it adds up to numbers and return the value of this number in modulo n
   		      	 
(define +mod   		      	 
  (lambda (a b n)
    (modulo (+ a b) n)
))   		      	 
   		      	 
;;; -mod takes two numbers and modulo n
;;; it substract first number from the second one and return the value of this number in modulo n  		      	 
   		      	 
(define -mod   		      	 
  (lambda (a b n)   		      	 
    (modulo (- a b) n)
))   		      	 
   		      	 
;;; +mod takes two numbers and modulo n
;;; it multiplies first 2 numbers and return the value of this number in modulo n  		      	 
   		      	 
(define *mod   		      	 
  (lambda (a b n)
    (modulo (* a b) n)
))   		      	 
   		      	 		      	 
 	 
;;; Description for exptmod
;;; exptmod calculates modulo n of x to the n in an iterative way by using repeated squaring.
;;; x is an any integer, n is 0 or positive integer, m is any integer.

(define (exptmod x n m)
  (define result 1)
  (define (helper product now n m result)
    (if (= n 0)
        result
        (if (< (* now 2) n)
            (helper (*mod product product m) (* now 2) n m result)
            (helper x 1 (- n now) m (*mod result product m)))))
  
  (helper x 1 n m result))  		      	 
   		      	 

;;; Description for random-k-digit-number:
;;; it takes n as input parameter and returns a random number such that
;;; it's maximum number of digits is n.
;;; how does it works? choose a random number between [0,9] and add it to the
;;; 10 times of previous solution. Iterate n times.
   		      	 
(define (random-k-digit-number n)		      	 
    (define (helper number count max)
      (define x (random 10))
      (if (< count max)
          (helper (+ x (* number 10)) (+ count 1) max)
          number))
  (helper 0 0 n)
)   		      	 
   		      	    		      	 
;;; count-digits takes a number and returns its number of digits in an iterative way.
   		      	 
(define count-digits   		      	 
  (lambda (n)
    (define (helper2 count n)
      (if (< n 10)
          count
          (helper2 (+ 1 count) (/ n 10))))
    (helper2 1 n)
))   		      	 
   		      	 
;;; big-random takes n as input and calls k = (count-digits n).
;;; it calls random-k-digit-number k and checks if the number is smaller than n or not.
;;; if it's not smaller, calls itself again until finding a random number whose digit number is max k and smaller than n.
   		      	 
(define big-random   		      	 
  (lambda (n)   		      	 
    (define rand (random-k-digit-number (count-digits n)))
    (if (< rand n) rand (big-random n))
))   		      	 
   		      	 
   		      	 
;;; prime? takes a positive integer and returns if it is prime or not
;;; with a probabilistic approach using Fermat's Little Theorem.
   		      	 
(define prime-test-iterations 20)

(define (prime?-helper count a n)
  (if (>= count prime-test-iterations) #t
      (if (= (exptmod a n n) a) (prime?-helper (+ 1 count) (big-random n) n) #f)
      )
  )
   		      	 
(define prime?   		      	 
  (lambda (p)   		      	 
    (if (< p 2) #f
      (prime?-helper 1 (big-random p) p)
      )
    ))    		      	 
    	 
   		      	  		      	 
;;; random-prime takes n as input returns a random prime smaller than n.
;;; it calls big-random n and prime? n procedures until finding a prime number.
   		      	 
(define random-prime   		      	 
  (lambda (n)
    (define candidate-random (big-random n))
    (if (prime? candidate-random)
      candidate-random
      (random-prime n))
))   		      	 
   		      	 
;;; ax+by=1 takes a b as an input and returns a list of 2 numbers that satisfy
;;; this equation. it only succeeds iff gcd(a,b) = 1
   		      	 
(define ax+by=1   		      	 
  (lambda (a b)
    (define q (quotient a b))
  (define r (remainder a b))

  (define (helper xx yy q)
    (list yy (- xx (* q yy)))) 
  
  (if (= r 1)
      (list 1 (- q))
      (let (( res (ax+by=1 b r)))
      (helper (list-ref res 0) (list-ref res 1) q)))
))   		      	 
   		      	 
;;; inverse-mod takes e and n (both positive integers) and calculates d such that
;;; e*d = 1 (mod n). it calls ax+by=1 to solve ed + (-k)n = 1 where e and n are knowns.
   		      	 
(define inverse-mod   		      	 
  (lambda (e n)
    (define (helper e n)
    (list-ref (ax+by=1 e n) 0))
  
    (if (= (gcd e n) 1)
      (modulo (list-ref (ax+by=1 e n) 0) n)
      (display "gcd is not 1 \n")
      )
))   		      	 
   		      	       	 
(define (calc-exponent n p q)
   (define e (big-random n))
   
    (if (= (gcd e (* (- p 1) (- q 1))) 1)
        e
        (calc-exponent n p q)))

(define (calc-d-exponent e p q)
    (inverse-mod e (* (- p 1) (- q 1)))
  )

;;; Description of random-keypair

;;; make-key calls cons and returns exp and mod as a pair

(define (make-key exp mod)
  (cons exp mod))

;;; get-exponent returns the first component of the key pair = exponent

(define (get-exponent key)   		      	 
  (car key))

;;; get-modulus returns the second component of the key pair = modulus

(define (get-modulus key)   		      	 
  (cdr key))

;;; generates p q and n such that n > m
;;; using the p and q, it finds an appropriate encryption key = e
;;; decryption key is calculated by finding inverse-mod of e in modulus (p-1)*(q-1)
;;; random-keypair returns the list: ((e,n) (d,n))

(define (random-keypair m)
  (define p 0)
  (define q 0)
  (define e 0)
  (define n 0)
  (define d 0)
    (set! p (random-prime m))
    (set! q (random-prime m))
    (set! n (* p q))

  (define (get-pair n p q)
    (set! e (calc-exponent n p q))
    (set! d (calc-d-exponent e p q))
    
    (list (make-key e n) (make-key d n)))
  
    (if (< n m) (random-keypair m)
        (get-pair n p q)))
   		      	 
;;; Description of rsa
;;; rsa takes key (e,n) pair and message
;;; returns (m^e) mod n

(define rsa   		      	 
  (lambda (key message)
    (exptmod message (get-exponent key) (get-modulus key))
))   		      	 
   		      	 
    	  		      	 
   		      	 
(define encrypt   		      	 
  (lambda (public-key string)
    (define message (string->integer string))
    (rsa public-key message)
))   		      	 
   		      	 
;;; Description of encrypt:   		      	 
   		      	 
(define decrypt   		      	 
  (lambda (private-key encrypted-message)
    (define message (rsa private-key encrypted-message))
    (integer->string message)
    )) 		      	 


;; Test cases:
;(define key (random-keypair 1000000000000000000000000000))
;(define e1 (encrypt (car key) "hello Comp200!"))
;(decrypt (cadr key) e1) ; -> "hello Comp200!"
   		      	 
;(define e2 (encrypt (car key) ""))
;(decrypt (cadr key) e2) ; -> ""

;(define e3 (encrypt (car key) "This is fun!"))
;(decrypt (cadr key) e3) ; -> "This is fun!"

;(define e4 (encrypt (car key) "I am Zafer "))
;(decrypt (cadr key) e4) ;


(define slow-exptmod   		      	 
  (lambda (a b n)   		      	 
    (if (= b 0)   		      	 
	1   		      	 
	(*mod a (slow-exptmod a (- b 1) n) n))))
   		      	 
(define test-factors   		      	 
  (lambda (n k)   		      	 
    (cond ((>= k n) #t)   		      	 
	  ((= (remainder n k) 0) #f)
	  (else (test-factors n (+ k 1))))))
   		      	 
(define slow-prime?   		      	 
  (lambda (n)   		      	 
    (if (< n 2)   		      	 
	#f   		      	 
	(test-factors n 2))))   		      	 
   		      	  	 
   		      	 
(define (join-numbers list radix)
  ; Takes a list of numbers (i_0 i_1 i_2 ... i_k)
  ; and returns the number   		      	 
  ;    n = i_0 + i_1*radix + i_2*radix2 + ... i_k*radix^k + radix^(k+1)
  ; The last term creates a leading 1, which allows us to distinguish
  ; between lists with trailing zeros.
  (if (null? list)   		      	 
      1   		      	 
      (+ (car list) (* radix (join-numbers (cdr list) radix)))))
   		      	 
; test cases   		      	 
;(join-numbers '(3 20 39 48) 100) ;-> 148392003
;(join-numbers '(5 2 3 5 1 9) 10) ;-> 1915325
;(join-numbers '() 10) ;-> 1   		      	 
   		      	 
   		      	 
(define (split-number n radix)   		      	 
  ; Inverse of join-numbers.  Takes a number n generated by
  ; join-numbers and converts it to a list (i_0 i_1 i_2 ... i_k) such
  ; that   		      	 
  ;    n = i_0 + i_1*radix + i_2*radix2 + ... i_k*radix^k + radix^(k+1)
  (if (<= n 1)   		      	 
      '()   		      	 
      (cons (remainder n radix)
	    (split-number (quotient n radix) radix))))
   		      	 
; test cases   		      	 
;(split-number (join-numbers '(3 20 39 48) 100) 100) ;-> (3 20 39 48)
;(split-number (join-numbers '(5 2 3 5 1 9) 10) 10)  ;-> (5 2 3 5 1 9)
;(split-number (join-numbers '() 10) 10) ; -> ()
   		      	 
   		      	 
(define chars->bytes   		      	 
  ; Takes a list of 16-bit Unicode characters (or 8-bit ASCII
  ; characters) and returns a list of bytes (numbers in the range
  ; [0,255]).  Characters whose code value is greater than 255 are
  ; encoded as a three-byte sequence, 255 <low byte> <high byte>.
  (lambda (chars)   		      	 
    (if (null? chars)   		      	 
	'()   		      	 
	(let ((c (char->integer (car chars))))
	  (if (< c 255)   		      	 
	      (cons c (chars->bytes (cdr chars)))
	      (let ((lowbyte (remainder c 256))
		    (highbyte  (quotient c 256)))
		(cons 255 (cons lowbyte (cons highbyte (chars->bytes (cdr chars)))))))))))
   		      	 
; test cases   		      	 
;(chars->bytes (string->list "hello")) ; -> (104 101 108 108 111)
;(chars->bytes (string->list "\u0000\u0000\u0000")) ; -> (0 0 0)
;(chars->bytes (string->list "\u3293\u5953\uabab")) ; -> (255 147 50 255 83 89 255 171 171)
   		      	 
   		      	 
(define bytes->chars   		      	 
  ; Inverse of chars->bytes.  Takes a list of integers that encodes a
  ; sequence of characters, and returns the corresponding list of
  ; characters.  Integers less than 255 are converted directly to the
  ; corresponding ASCII character, and sequences of 255 <low-byte>
  ; <high-byte> are converted to a 16-bit Unicode character.
  (lambda (bytes)   		      	 
    (if (null? bytes)   		      	 
	'()   		      	 
	(let ((b (car bytes)))   		      	 
	  (if (< b 255)   		      	 
	      (cons (integer->char b)
		    (bytes->chars (cdr bytes)))
	      (let ((lowbyte (cadr bytes))
		    (highbyte (caddr bytes)))
		(cons (integer->char (+ lowbyte (* highbyte 256)))
		      (bytes->chars (cdddr bytes)))))))))
   		      	 
; test cases   		      	 
;(bytes->chars '(104 101 108 108 111)) ; -> (#\h #\e #\l #\l #\o)
;(bytes->chars '(255 147 50 255 83 89 255 171 171)) ; -> (#\u3293 #\u5953 #\uabab)
   		      	 
   		      	 
   		      	 
(define (string->integer string)
  ; returns an integer representation of an arbitrary string.
  (join-numbers (chars->bytes (string->list string)) 256))
   		      	 
; test cases   		      	 
;(string->integer "hello, world")
;(string->integer "")   		      	 
;(string->integer "April is the cruelest month")
;(string->integer "\u0000\u0000\u0000")
   		      	 
   		      	 
(define (integer->string integer)
  ; inverse of string->integer.  Returns the string corresponding to
  ; an integer produced by string->integer.
  (list->string (bytes->chars (split-number integer 256))))
   		      	 
; test cases   		      	 
;(integer->string (string->integer "hello, world"))
;(integer->string (string->integer ""))
;(integer->string (string->integer "April is the cruelest month"))
;(integer->string (string->integer "\u0000\u0000\u0000"))
;(integer->string (string->integer "\u3293\u5953\uabab"))