Programming Praxis

We begin with the key generator, which is similar to the one for the exercise on RSA cryptography; input is the number of bits k, output is the set of five values n, p, q, a, b, and the process simply picks a random v in the appropriate range and keeps incrementing it by 1 until a suitable v is found:

(define (keygen k)
  (define (gen k)
    (let loop ((v (randint (expt 2 (- k 1)) (expt 2 k))))
      (if (and (prime? v) (= (modulo v 4) 3)) v
        (loop (+ v 1)))))
  (let* ((k2 (quotient k 2)) (p (gen k2)) (q (gen k2)) (n (* p q)))
    (call-with-values
      (lambda () (euclid p q))
      (lambda (a b g) (values n p q a b)))))

Then encryption and decryption follow the formulas:

(define (encrypt m n)
  (let ((m (+ (* m 256) 255)))
    (expm m 2 n)))

(define (decrypt c n p q a b)
  (let* ((r (expm c (/ (+ p 1) 4) p))
         (s (expm c (/ (+ q 1) 4) q))
         (aps (* a p s)) (bqr (* b q r))
         (x (modulo (+ aps bqr) n))
         (y (modulo (- aps bqr) n))
         (m1 x) (m2 (modulo (- x) n))
         (m3 y) (m4 (modulo (- y) n)))
    (cond ((= (remainder m1 256) 255) (quotient m1 256))
          ((= (remainder m2 256) 255) (quotient m2 256))
          ((= (remainder m3 256) 255) (quotient m3 256))
          ((= (remainder m4 256) 255) (quotient m4 256))
          (else (error 'decrypt "oops")))))

To make a system for passing full messages, we assume 8-bit ascii and choose a block size of 32 bits consisting of 24 bits of payload and 8 bits of padding; the 24 payload bits consist of 3 bytes of the message, and the 8 padding bits will all be 1-bits. The key length will also be 32 bits. We’ll mark the end of the message as recommended by Bruce Schneier by adding k blocks of the byte k, where k is the number of bytes needed to fill out the final block; if the message completely fills the last block, we add another block with 3 blocks of 11₂. Thus, the 18-character message “Programming Praxis” will be split into 6 blocks, with a full trailing block added to mark the end of the message. For real security, of course, you would want a somewhat larger block size and key length.

Two functions prepare and unprepare split the message into blocks, add the trailing block, and delete it at the end:

(define (prepare str n)
  (let ((len (- n (modulo (string-length str) n))))
    (string->list
      (string-append str
        (make-string len (integer->char len))))))

(define (unprepare xs)
  (let loop ((xs (reverse xs)))
    (if (char=? (car xs) (cadr xs))
        (loop (cdr xs))
        (reverse (cdr xs)))))

Two functions chars->num and num->chars convert back and forth between character blocks and integers:

(define (chars->num cs)
  (let loop ((cs cs) (n 0))
    (if (null? cs) n
      (loop (cdr cs)
        (+ (* n 256) (char->integer (car cs)))))))

(define (num->chars n)
  (let loop ((n n) (cs (list)))
    (if (zero? n) cs
      (loop (quotient n 256)
        (cons (integer->char (remainder n 256)) cs)))))

With those auxiliary functions available, we are ready to encipher and decipher the message. The two functions encipher and decipher are duals of each other, calling opposite functions in reverse order:

(define (encipher plaintext key blocksize)
  (list->string
    (apply append
      (map num->chars
        (map (lambda (m) (encrypt m key))
          (map chars->num
            (splits blocksize
              (prepare plaintext blocksize))))))))

(define (decipher ciphertext n p q a b blocksize)
  (list->string
    (unprepare
      (apply append
        (map num->chars
          (map (lambda (c) (decrypt c n p q a b))
            (map chars->num
              (splits (+ blocksize 1)
                (string->list ciphertext)))))))))

Here’s an example:

> (keygen 32)
2090723993
61027
34259
-14246
25377
> (decipher
    (encipher "Programming Praxis" 2090723993 3)
    2090723993 61027 34259 -14246 25377 3)
"Programming Praxis"

We used split, randint and expm from the Standard Prelude, euclid and prime? from previous exercises, and wrote a helper function splits not shown above. You can run the program at http://programmingpraxis.codepad.org/wyHgxfpg.

Pages: 1 2