Two centuries ago, Robert Patterson (no, not the Twilight star) sent a letter to Thomas Jefferson. Both men were members of the American Philosophical Society and frequently wrote to each other. In this particular letter, Patterson discussed the 4 requirements for a “perfect” cipher:
- It should work in any language.
- It should be easy to memorize.
- It should be simple to perform.
- It should be indecipherable to anyone who doesn’t have the key.
The last requirement was especially important to Patterson and to demonstrate he included a cipher which he said would “defy the united ingenuity of the whole human race to decypher to the end of time”.
Harvard Magazine explains exactly how complicated the cipher was:
In his more sophisticated code, Patterson wrote his message openly, without capitals or spaces, but vertically on ruled paper, “in the Chinese manner,” in columns from left to right. This produces a grid of lowercase letters that are gibberish when read left to right, but a perfectly clear message when read in columns. Next he broke this grid into sections of up to nine lines each, numbering each line 1, 2, 3, etc., and re-ordering them randomly within the section—though all sections would repeat the same reordered sequence of numbers. He also inserted up to nine arbitrary letters at the beginning of each line, which had no bearing on the message content but drastically increased the inscrutability factor. He filled vacant spaces at the end of the line with similarly random letters.
The cipher became something that Jefferson historians would occasionally reference but proved too difficult to break. That is, until Lawren Smithline, a 36-year-old mathematician and professional cryptologist, decided to take a crack at it. He used techniques that were available in the 19th century but used computers to perform the computations.
The Wall Street Journal explains how Smithline cracked the ciper:
Undaunted, Dr. Smithline decided to tackle the cipher by analyzing the probability of digraphs, or pairs of letters. Certain pairs of letters, such as “dx,” don’t exist in English, while some letters almost always appear next to a certain other letter, such as “u” after “q”.
To get a sense of language patterns of the era, Dr. Smithline studied the 80,000 letter-characters contained in Jefferson’s State of the Union addresses, and counted the frequency of occurrences of “aa,” “ab,” “ac,” through “zz.”
Dr. Smithline then made a series of educated guesses, such as the number of rows per section, which two rows belong next to each other, and the number of random letters inserted into a line.
To help vet his guesses, he turned to a tool not available during the 19th century: a computer algorithm. He used what’s called “dynamic programming,” which solves large problems by breaking puzzles down into smaller pieces and linking together the solutions.
The overall calculations necessary to solve the puzzle were fewer than 100,000, which Dr. Smithline says would be “tedious in the 19th century, but doable.”
After about a week of working on the puzzle, the numerical key to Mr. Patterson’s cipher emerged — 13, 34, 57, 65, 22, 78, 49.
The cracked text?
“In Congress, July Fourth, one thousand seven hundred and seventy six. A declaration by the Representatives of the United States of America in Congress assembled. When in the course of human events…”
A clever joke by Patterson.
Links: 1, 2, 3.
| © 2010