Monday, July 06, 2009

Jefferson’s Cipher Cracked

Two hundred years later, Thomas Jefferson’s cipher with his friend, Robert Patterson, has finally been cracked. Patterson sent this cipher to Jefferson as an example of his idea for a perfect cipher:
To Mr. Patterson's view, a perfect code had four properties: It should be adaptable to all languages; it should be simple to learn and memorize; it should be easy to write and to read; and most important of all, "it should be absolutely inscrutable to all unacquainted with the particular key or secret for decyphering."

Mr. Patterson then included in the letter an example of a message in his cipher, one that would be so difficult to decode that it would "defy the united ingenuity of the whole human race," he wrote.

There is no evidence that Jefferson, or anyone else for that matter, ever solved the code. But Jefferson did believe the cipher was so inscrutable that he considered having the State Department use it, and passed it on to the ambassador to France, Robert Livingston.

The cipher was broken by Dr. Lawren Smithline, a mathematician who works professional in cryptology.

First, let’s go over the cipher itself:
But Mr. Patterson had a few more tricks up his sleeve. He wrote the message text vertically, in columns from left to right, using no capital letters or spaces. The writing formed a grid, in this case of about 40 lines of some 60 letters each.

Then, Mr. Patterson broke the grid into sections of up to nine lines, numbering each line in the section from one to nine. In the next step, Mr. Patterson transcribed each numbered line to form a new grid, scrambling the order of the numbered lines within each section. Every section, however, repeated the same jumbled order of lines.

The trick to solving the puzzle, as Mr. Patterson explained in his letter, meant knowing the following: the number of lines in each section, the order in which those lines were transcribed and the number of random letters added to each line.

The key to the code consisted of a series of two-digit pairs. The first digit indicated the line number within a section, while the second was the number of letters added to the beginning of that row. For instance, if the key was 58, 71, 33, that meant that Mr. Patterson moved row five to the first line of a section and added eight random letters; then moved row seven to the second line and added one letter, and then moved row three to the third line and added three random letters. Mr. Patterson estimated that the potential combinations to solve the puzzle was "upwards of ninety millions of millions."

After explaining this in his letter, Mr. Patterson wrote, "I presume the utter impossibility of decyphering will be readily acknowledged."

But Dr. Smithline tackled it:
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."

Dr. Smithline was able to finally undo the code:
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. Using that digital key, he was able to unfurl the cipher's 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..."

That, of course, is the beginning -- with a few liberties taken -- to the Declaration of Independence, written at least in part by Jefferson himself. "Patterson played this little joke on Thomas Jefferson," says Dr. Smithline. "And nobody knew until now."

No comments: