A Thomas Jefferson Enigma for July 4th

This post isn't about computer performance per se, although see end, and I certainly have better things to do with my time, but when I read this slashdot item about a 200 year old cipher, I couldn't help wondering what it would look like as a modern computer algorithm.

The backstory involves Robert Patterson, a mathematician friend of Thomas Jefferson, who wrote to him in 1801 (the same year Jefferson was elected the third President of the United States) about what he claimed to be a very robust cipher he had invented. As well as including an example of how to apply the cipher in the letter, he also included a ciphertext which neither Jefferson nor anyone else had deciphered in the past 200 years (It's not clear anyone was bothered enough to try). Inadvertently, crypto expert Lawren Smithline became aware of the letter and cracked it in 2007 using digraph frequencies and some dynamic programming techniques. It seems that Patterson's claim was well founded. Ironically, the encypted text turned out to be none other than the preamble to the Declaration of Independence; largely authored by Jefferson.

Since the cipher involves transposing text, Mathematica seemed like a natural choice to examine what Patterson had done in modern form. Here's how it looks with all the main steps shown [Click to enlarge]:


Next, we format the text to be 21 columns wide (purely arbitrary) and define Smithline's newly discovered key pairs:13, 34, 57, 65, 22, 78, 49.


Then, we do the row to column transposition and apply the new row-permutations according to the keys


which produces the final ciphertext. Only the first 7 rows of the ciphertext are shown:


This result is similar to the example shown in the WSJ article (the 2nd figure there is an interactive Flash animation). Quite a bit of work, even with the help of Mathematica, and that was only the encryption process.

In 1801, all this had to be done manually. The sender had to manually apply the cipher correctly to encrypt the plaintext and the recipient had to manually apply the reverse transformation correctly with the keys to decrypt the ciphertext. Clearly, both encryption and decryption are non-trivial manual tasks which are very error-prone, and that may explain why Patterson's cipher did not find general acceptance in the way Jefferson had hoped.

It also begs the question, why machines were not developed earlier to do this kind of tedious and exacting task? Come to think of it, that is a performance question. Automatic machines were developed eventually, e.g., the Babbage-Scheutz difference engine was finally constructed in the 1850s, but that was for calculating tedious numerical tables, not for encryption. The first mechanical encryption device seems to have been the Enigma machine built during WWII. Different sets of wheels corresponded to different keys.


Postscript (Sun July, 2009):
Of course, as soon as you make a public statement, a counter-example inevitably emerges.

1. From A Codes & Ciphers Primer: One of the most significant developments was the "polyalphabetic substitution cipher", which was described in its definitive form in a paper published in 1586 by a French diplomat named Blaise de Vigenere. ... The Vigenere cipher came into common use, assisted by a simple invention called a "cipher disk"
   
   
2. From Wikipedia: A cipher disk is an enciphering and deciphering tool developed in 1470 by the Italian architect and author Leon Battista Alberti.