Rail-Fence Cipher

The obvious solution uses arithmetic to extract characters at the various positions of the text in the desired order. But the details are tricky and hard to get right. Matthias Felleisen, a Professor in the Computer Science department at Northeastern University in Boston and one of the authors of The Little Schemer proposes instead the following solution:

(define X '_) ; a unique tag for padding the data structure

Waves splits a text into pieces of length equal to the key; alternate pieces are reversed and have their first and last characters padded. For instance, (waves (string->list "PROGRAMMING PRAXIS") 4) evaluates to ((#\P #\R #\O #\G) (_ #\A #\R _) (#\M #\M #\I #\N) (_ #\space #\G _) (#\P #\R #\A #\X) (_ #\S #\I _)).

(define (waves str h)
  (define (down str)
    (if (>= h (length str))
        (list (fill h str))
        (cons (take h str) (up (drop h str)))))
  (define (up str)
    (if (>= (- h 2) (length str))
        (list (pad (fill (- h 2) str)))
        (cons (pad (take (- h 2) str)) (down (drop (- h 2) str)))))
  (define (pad str) (append (list X) (reverse str) (list X)))
  (define (fill h str) (append str (make-list (- h (length str)) X)))
  (down str))

Fence uses waves to produce a list of the positions from which the transposed characters will be taken. For instance, (fence (range (string-length "PROGRAMMING PRAXIS")) 4) produces the list (0 6 12 1 5 7 11 13 17 2 4 8 10 14 16 3 9 15).

Fence uses waves to perform the transposition:

(define (fence lox h)
  (define a (apply append (transpose (waves lox h))))
  (filter (lambda (e) (not (eq? X e))) a))

Encipherment is done by calling fence:

(define (encipher str h)
  (list->string (fence (string->list str) h)))

Decipherment is somewhat more difficult. Fence builds a list of the positions of the transposed characters; for our running example, e will be (0 6 12 1 5 7 11 13 17 2 4 8 10 14 16 3 9 15). Those positions are melded with the cipher-text in x, the position/character pairs are sorted into order in y, and the characters extracted in z:

(define (decipher str h)
  (define e (fence (range (string-length str)) h))
  (define x (map list e (string->list str)))
  (define y (sort (lambda (i j) (<= (car i) (car j))) x))
  (define z (map cadr y))
  (list->string z))

Felleisen's program is simple and clear, a fine example of beautiful code by a master of the craft. Running the rail-fence cipher looks like this:

> (encipher "PROGRAMMING PRAXIS" 4)
"PMPRAM RSORIGAIGNX"
> (decipher "PMPRAM RSORIGAIGNX" 4)
"PROGRAMMING PRAXIS"

We can test the functions using assert; remember that, with the assert macro, no news is good news:

(do ((i 2 (+ i 1))) ((< 18 i))
  (assert (decipher (encipher "PROGRAMMING PRAXIS" i) i)
          "PROGRAMMING PRAXIS"))

We use take, drop, range, filter, make-list, sort and assert from the Standard Prelude. We also use the utility function (transpose m), which transposes the rows and columns of a list of lists:

(define (transpose m)
  (if (null? (car m)) '()
    (cons (map car m) (transpose (map cdr m)))))

You can run this program at http://programmingpraxis.codepad.org/9abH1QKb.

Pages: 1 2