Gauche Devlog

< Release timing | Way to rationalize >

2012/07/15

Working with generators - John Nash's Cipherer

Generators and lazy sequences are relatively new addition in Gauche, and I keep looking for small exercises I can practice using them. Here's one I did several months ago.

I stumbled on John Nash's 1955 letter to NSA discussing how encryption scheme should be designed, accompanied with a concrete design of cipherer/decipherer. It is basically a state machine that reads bits and write out moified bits, and the configuration of the state machine is the "key" of encryption. The nature of the machine can be implemented naturally as a generator converter---it takes a generator that feeds input information, and returns a generator that yields encrypted/decrypted information.

Here's the code:

make-permuter is a common function that implements a bit stream (takes 1 bit, and returns 1 bit) with internal states. make-encipherer and make-decipherer return procedures that take an input bit generator and return an output bit generator.

To run this "machine", you want some convenience functions that converts between text and bit generators (Note: Recently I fixed reverse-bits->generator; you need git HEAD of Gauche at this moment to run this example):

Now, here's an example configuration (key) of the machine:

(define key '((1 3 6 2 4 0 5)
              (2 1 5 0 3 6 4)
              (#f #t #f #f #t #f #f)
              (#t #t #t #f #f #t #t)))

(define E (apply make-encipherer key))
(define D (apply make-decipherer key))

And a couple of examples. First one takes a string, encripts it by E, immediately decripts by D, and converts back to string to show it. The second one reads the text from current input port, encripts and decripts it and echo back.

($ bools->string $ D $ E $ string->bools "hi, there!")

($ write-bools $ D $ E $ read-bools (current-input-port))

It is pleasant to be able to pipe componends just like I would do with machines. Could be done with lazy sequences, but generator version has less overhead.

Tag: gauche.generator

Post a comment

Name: