Wednesday, January 16, 2008

Enoch Root and Edward Abbey on the El

In Cryptonomicon Enoch Root devises an encryption scheme that he initially calls "Pontifex" and describes with the following perl script:

#!/usr/bin/perl -s
$f=$d?-1:1;$D=pack('C*',33..86);$p=shift;
$p=~y/a-z/A-Z/;$U='$D=~s/(.*)U$/U$1/;
$D=~s/[A-Z]/$k=ord($&)-64,&e/eg;$k=0;
while(<>){y/a-z/A-Z/;y/A-Z//dc;$o.=$_}$o.='X'
while length ($o)%5&&!$d;
$o=~s/X*$// if $d;$o=~s/.{5}/$& /g;
print"$o/n";sub v{$v=ord(substr($D,$_[0]))-32;
$v>53?53:$v}
sub w{$D=~s/(.{$_[0]})(.*)(.)/$2$1$3/}
sub e{eval"$U$V$V";$D=~s/(.*)([UV].*[UV])(.*)/$3$2$1/;
&w(&v(53));$k?(&w($k)):($c=&v(&v(0)),$c>53?&e:$c)}


(The program is somewhat obfuscated; to really understand it I had to type it out in a more readable form. Also, in reality the algorithm was designed by Bruce Schneier and the Perl script written by Ian Goldberg. Here is Bruce's description of the system)

It's later revealed that the same instructions, written in natural language instead of Perl, can be followed by a person with a deck of cards to generate a "keystream" of random-looking numbers. Two people that start with their decks in the same order can generate this same random sequence. The sender writes out his message, writes a number from the keystream under each letter, then circularly-shifts each letter forward in the alphabet by that number. The receiver receives a message that looks random to anyone else, circularly-shifts each letter backward by the same number the first person used, and the result is the original message. The whole system relies on a shared secret: the two people communicating know how to arrange the deck into its initial position, but nobody else does. In this sense it's similar to a one-time pad, where the communicators generate long sequences of random numbers while physically in contact and agree on which to use for which messages before they start communicating this way. The advantage is that in this case the shared secret, instead of pages full of numbers that can be physically confiscated by eavesdroppers, could be something memorizable, like (as Bruce Schneier suggests in an appendix to the novel) a simple system for generating a deck ordering based on Bridge scenarios published in some newspaper on the day the message was written. As with a one-time pad, there are two major ways that an eavesdropper could break it. First, by discovering the shared secret. Second, by discovering a bias, that is, by mathematically analyzing the keystream-generating algorithm and finding patterns in it. Finding a bias would cut down the number of likely keystreams, perhaps enough that they can all be checked by brute force. Such a bias has been found in Solitaire, as mentioned in Bruce Schneier's page, linked above.

So.

Today after work I got on a Brown-Line train at the Merchandise Mart stop to ride all the way out to Francisco to go to my gym. Doors open on the right at Merchandise Mart, so I entered the crowded train from the right and had to stop and stand in the doorway, looking towards the left of the train. Seated to the right of the doors on the opposite side were a woman reading a book (not very interesting to watch) and a man repeatedly shuffling and fanning a deck of cards (somewhat more interesting). This guy must not have had much to do, or was practicing to escape the Chicago winters to become a card dealer in Vegas. Or maybe he was an Enoch Root, well-practiced at his card transformations, memorizing or analyzing the keystream generated from his deck transformations. It wasn't all that interesting, though, so I started reading.

Maybe at the Sedgwick stop the woman next to him got up, and I was the closest person to the seat she left, so I sat down. The man continued to shuffle his cards, sometimes accidentally jabbing me with an elbow, occasionally sneaking a glance at my book. I don't read secretly, so he may have caught a bit of Edward Abbey's description of his lazy trip down the Colorado River just before the building of the dam to form Lake Powell. At Belmont he stood up and flicked a card from his deck perfectly into the middle of the seat. The two of hearts. He walked out of the train. Transfer to Red- and Purple-Line trains at Belmont? Unlikely. Transferring at Belmont is for fools and amateurs. A man of his caliber would have obviously known to transfer at Fullerton.

So anyway a woman walked on the train, looked at the card on the seat. She recognized immediately that the first number of the keystream was 28! She probably looked at me funny, like I'd put the card there for some reason, but I don't really know because I had my face buried in Desert Solitaire trying to contain my laughter. Joy, mirth and laughter are not allowed on CTA vehicles. Do not make eye contact with other customers. If you see something, say something! Play safe; ski only in clockwise direction. Let's all have fun together. Especially with doomsday looming. She pocketed the card, sat down and started reading.