;; secret.scm
;;
;; An introduction to Cryptography


;;; INTERNAL PROCEDURES
;;;
;;; These internal procedures are meant to support the problem set;
;;; some of these use Scheme mechanisms we haven't covered yet (things
;;; like lists, list higher order procedures like map, etc.). You
;;; should be able to safely ignore any procedures dealing with lists
;;; or 'intlists'.

;; Utility procedures to convert messages into numeric representations
;; that can be manipulates and/or viewed.  These representations are
;; summarized below (with example representation for the message "ab" in
;; each case).
;; 
;; 0. 'message'.  This is simply a text string containing the message to
;;    be converted into numeric form.
;;    Example: "ab"
;;
;; 1. list of integers (an 'intlist').  This is a list of integer codes
;;    for each character in a message string.  Since students haven't seen
;;    lists yet, this is an internal representation that can be ignored.
;;    Example: (1 2)
;;
;; 2. 'charcodes'.  This is a string holding a sequence of numeric codes
;;    for each character in the message.
;;    Example: " 1 2"
;;
;; 3. 'intcode'.  This a single integer formed by simply abutting each of
;;    the numeric codes for the characters in the message (each taken as
;;    a three digit integer).
;;    Example: 1002 (same as 001002)
;;    

;; message->intlist converts a message (a string) into a 'intlist'
;;
;; Details: For ease of understanding (a cryptographic oxymoron!) 
;; this simple 'number for character' substitution starts at 1 for "a"
;; and proceeds sequentially.  We assume there are only 256 possible
;; characters and thus 'wrap around' our numbers so they are in the
;; range 1 to 256.
;;
(define (message->intlist msg)
  (map (lambda (char)
         (+ 1 (modulo (- (char->integer char) 97) 256)))
       (string->list msg)))
;E.g. (message->intlist "cat")

;; and its inverse...
(define (intlist->message intlist)
  (apply string-append
         (map (lambda (code)
                (char->string (integer->char (modulo (+ code 96) 256))))
              intlist)))
;E.g. (intlist->message (list 1 2))

;; Convert intlist to charcodes
(define (intlist->charcodes intlist)
  (apply string-append
         (map (lambda (code) (string-append " " (number->string code)))
              intlist)))
;E.g. (intlist->charcodes (list 0 1))

;; MIT-scheme specific -- convert string of charcodes back into an intlist
(define (split-string charcodes)
  (read (string->input-port (string-append "(" charcodes ")"))))
;E.g. (split-string " 1 2")

;; combine-intlist merges together a whole sequence of numbers into
;; one big number.  So one can actually "look" at the numbers
;; and see the message, we will do something simple and allocate three
;; digits for each character number.  
;;
(define (combine-intlist nums)
  (define (combine-helper nums sofar)
    (if (null? nums)
        sofar
        (combine-helper (cdr nums)
                        (+ (* 1000 sofar) (car nums)))))
  (combine-helper nums 0))
;E.g. (combine-intlist (list 1 2 3))

;; split-intcode takes a big integer and pulls out the individual numbers
;; in it.
(define (split-intcode num)
  (if (< num 1000)
      (list num)
      (append (split-intcode (quotient num 1000))
              (list (remainder num 1000)))))
;E.g. (split-intcode 1003)
;     (split-intcode (combine-intlist (list 1 222 5)))

;;
;; Character Encryption Utilities
;;

;; This is the fundamental encrypter; we wrap to get the versions
;; used in the exercises.
(define (encrypt-to-intlist msg encoder key)
  (map (lambda (num) (inexact->exact (round (encoder num key))))
       (message->intlist msg)))

; The decrypter
(define (decrypt-from-intlist cipher decoder key)
  (intlist->message
   (map (lambda (num) (inexact->exact (round (decoder num key))))
        cipher)))



;;; USER PROCEDURES
;;;
;;; These are procedures you will need to use directly to complete
;;; the problem set.  Again, you do not have to understand the details
;;; of their implementation, but you do need to understand how to use
;;; them.
;;;

;;
;; Procedures to manipulate messages as a 'charcodes' string.
;;

;; message->charcodes converts a message (a string) into a 'charcodes'
;; version of that message (for further use by encyption procedures).
;;
(define (message->charcodes msg)
  (intlist->charcodes (message->intlist msg)))
;E.g. (message->charcodes "ab")
;     (message->charcodes "cat")

;; and its inverse...
(define (charcodes->message str)
  (intlist->message (split-string str)))
;E.g. (charcodes->message " 3 1 20")

;;
;; Procedures to manipulate messages as an 'intcode'
;;

; message->intcode converts a message (a string) into an 'intcode' (a
; single large integer version of the message).
;
(define (message->intcode msg)
  (combine-intlist (message->intlist msg)))
;E.g. (message->charcodes  "cat")
;     (message->intcode "cat")

;; and its inverse...
(define (intcode->message num)
  (intlist->message (split-intcode num)))
;E.g. (intcode->message 3001002)
;E.g. (intcode->message (message->intcode "this is a test"))

;;
;; Character by Character Encryption
;;

;; Here we do message encryption on a single character by single character
;; basis.  In this case, one provides to the encrypter an "encoder"
;; procedure that takes the numeric value for an INDIVIDUAL CHARACTER
;; and a key, and encrypts that value somehow.  It needs an inverse "decoder"
;; operation so the decryption can also work, given the key.  The encrypter
;; procedure (encrypt-to-charcodes) does all the magic of using the "encoder"
;; on each successive character in the message and pasting the results all
;; together to produce an encrypted 'charcodes' output for the message.
;;
;; The "encoder" should take two arguments: the num and the key, and return
;; a new number (which should be an integer) encoding for that individual 
;; character.
;;
;; The "decoder" should take two arguments: an integer and the key, and return
;; the original numeric code for that character (and thus the decoder acts 
;; to undo the encoder transformation of the character).

(define (encrypt-to-charcodes msg encoder key)
  (intlist->charcodes (encrypt-to-intlist msg encoder key)))

(define (decrypt-from-charcodes cipher decoder key)
  (decrypt-from-intlist (split-string cipher) decoder key))


;; Some sample encoders and decoders that work with these:

;; Caesar Character by Character Encryption
;;

(define (caesar-encode num key)
  (modulo (+ num key) 256))
;E.g. (caesar-encode 1 3)

(define (caesar-decode num key)
  (modulo (- num key) 256))
;E.g. (caesar-decode 4 3)

;;Example uses -- try these out to see what they do:

;(encrypt-to-charcodes "cat" caesar-encode 4)

;(encrypt-to-charcodes "ab" caesar-encode 77)
;(decrypt-from-charcodes (encrypt-to-charcodes "ab" caesar-encode 77)
;                        caesar-decode 77)

;(define cipher-1
;  (encrypt-to-charcodes "The Ides of March" caesar-encode 77))

;cipher-1

;(decrypt-from-charcodes cipher-1 caesar-decode 77)

;; "NSA" Character by Character Encryption
;;

(define (nsa-encode num key)
  (modulo (+ (* -1 num) key) 256))
;E.g. (nsa-encode 1 2)
;E.g. (nsa-encode 2 2)

; COMPLETE THIS PROCEDURE 

(define (nsa-decode num key)
  ...)

;E.g. (nsa-decode 1 2)
;E.g. (nsa-decode 0 2)
;E.g. (nsa-decode (nsa-encode 203 192) 192)

;Example uses:
;(encrypt-to-charcodes "bc" nsa-encode 1)
;(decrypt-from-charcodes (encrypt-to-charcodes "bc" nsa-encode 1) nsa-decode 1)


;;
;; Full Message (as intcode) Encryption
;;

;; Here we do encryption using the alternative representation of the
;; message as an 'intcode' rather than as 'charcodes'.  The 'intcode'
;; version of a message is a single big integer for the whole message,
;; allowing us to apply a single mathematical function once to the entire
;; message.
;;
;; These versions of the encrypter and decrypter also take encoder and
;; decoder procedures, but in this case the input num is the whole intcode
;; rather than a single small integer for a single character.  Specifically:
;;
;; The "encoder" should take two arguments: the (large) intcode representing
;; the entire message and the key, and return a new encrypted intcode.
;;
;; The "decoder" should take two arguments: the (large) intcode that is
;; the encrypted message and the key, and return the unencrypted intcode
;; representing the entire message.

; The encrypter
(define (encrypt-to-intcode msg encoder key)
  (encoder (message->intcode msg) key))

; The decrypter
(define (decrypt-from-intcode cipher decoder key)
  (intcode->message (inexact->exact (round (decoder cipher key)))))

;E.g. (define (identity int key) int)
; (decrypt-from-intcode (encrypt-to-intcode "test" identity 99) identity 99)

;; An example encoder and decoder
(define (encode-add int key) (+ int key))
(define (decode-add int key) (- int key))

;; Simple example
;(define add-key 8)
;(message->intcode "ab")
;;Value: 1002
;(encrypt-to-intcode "ab" encode-add add-key)
;;Value: 1010
;(decrypt-from-intcode 1010 decode-add add-key)
;;Value: "ab"

;; Bigger example
;(define add-key 9234827538182374765023)
;(define cipher-3 (encrypt-to-intcode "This is TOP SECRET" encode-add add-key))
;cipher-3
;;Value: 244008009019192009019192244239240201478056765424604009216
;(decrypt-from-intcode cipher-3 decode-add add-key)
;;Value: "This is TOP SECRET"

;;;___________________________________________________________________
;;; PROBLEMS
;;;___________________________________________________________________

;;; Problem 1

; Try some examples using the Caesar encoder/decoder.
; List them below, showing the output you get.

; Decrypt the following:
(define cipher-2 " 111 140 138 130 140 62 61 111 140 138 130 140 62 61 116 133 130 143 130 131 140 143 130 61 126 143 145 61 145 133 140 146 61 75 75 75 75 61 140 140 141 144 62 61 116 143 140 139 132 61 112 133 126 136 130 144 141 130 126 143 130 126 139 61 141 137 126 150 62 61 112 140 143 143 150 62 62")

; Write nsa-decode
; PUT YOUR DEFINITION OF nsa-decode HERE
; show it running on some test cases

; verify by decrypting the following (with nsa-decode, key=007)

(define cipher-4 " 36 255 2 4 252 71 248 242 243 71 243 255 2 71 240 2 5 71 244 254 243 2 71 255 243 243 247 45 56 56 240 240 240 57 249 244 6 57 0 248 241 56 250 242 244 2 242 250 56 71 243 248 71 244 2 2 71 244 248 250 2 71 1 6 244 4 254 249 6 243 254 249 0 71 6 245 243 2 1 6 4 243 244 71 1 245 248 250 71 4 245 238 247 243 248 251 248 0 254 4 71 255 254 244 243 248 245 238 57")

;;; Problem 3

;; The message was:
(define al-cap1-plaintext  "Eliot Ness is a wus.  He doesn't even know how to program in Scheme!")
(define al-cap1-ciphertext " 130 169 166 172 177 93 139 162 176 176 93 166 176 93 158 93 180 178 176 107 93 93 133 162 93 161 172 162 176 171 100 177 93 162 179 162 171 93 168 171 172 180 93 165 172 180 93 177 172 93 173 175 172 164 175 158 170 93 166 171 93 144 160 165 162 170 162 94")

; Write crack-caesar and then crack the above transmission
(define (crack-caesar plaintext ciphertext)
  ...)

;E.g. (crack-caesar al-cap1-plaintext al-cap1-ciphertext)

;;; Problem 4

(define better-al-cap1-plaintext "Let's meet at the Watergate Suites at midnight.  We'll get what we need and give it to Nixon tomorrow.")
(define better-al-cap1-ciphertext " 159 134 119 196 120 203 126 134 134 119 203 138 119 203 119 131 134 203 148 138 119 134 121 132 138 119 134 203 152 118 130 119 134 120 203 138 119 203 126 130 135 125 130 132 131 119 189 203 203 148 134 196 127 127 203 132 134 119 203 116 131 138 119 203 116 134 203 125 134 134 135 203 138 125 135 203 132 130 117 134 203 130 119 203 119 124 203 157 130 115 124 125 203 119 124 126 124 121 121 124 116 189")

;; Generalize your cracker and then crack the above transmission
(define (crack-string-encryption encoder plaintext ciphertext max-key-digits)
  ...)

;;; Problem 5

; Write quick-crack-add as a special purpose cracker for the encode-add:
(define (quick-crack-add plaintext ciphertext)
  ...)

; and crack the following...
(define add-plain-1 "One plus one is two")
(define add-cipher-1 239014005192016012021019192015014005192009019192020031308)

(define add-plain-2 "One plus one modulo two is zero")
(define add-cipher-2 239014005192016012021019192015014005431027020196037024036211212038029197201028211218025049323)