Bruce Schneier | |||||||||||||||
Schneier on SecurityA blog covering security and security technology. « Leaving Infants in the Car | Main | Hiding Behind Terrorism Law » March 18, 20091801 Cipher SolvedInteresting piece of cryptographic history: a cipher designed by Robert Patterson and sent to Thomas Jefferson. The full story is behind a paywall. EDITED TO ADD (4/14): The cipher itself is here. Posted on March 18, 2009 at 7:22 AM • 16 Comments To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter. Anybody who's already paid, care to summarize the crypto techniques involved, or post pointers to where they're explained elsewhere? Thanks in advance.... Posted by: Dave Aronson at March 18, 2009 8:01 AM The cipher itself is at http://memory.loc.gov/cgi-bin/ampage?... Posted by: Steven M. Bellovin at March 18, 2009 8:17 AM I decrypted the text: "The Magic Words are Squeamish Ossifrage" Posted by: Larry Seltzer at March 18, 2009 8:24 AM It's a substitution cipher, and it works by writing the message in a number of columns. Then pick a length for a section, and exchange rows in each section in the same permutation. The in front of each row (per section) and a certain number of letters, and also add some add the end to make them the same length. so: 1 hw 3 lr 32 ablr It was cracked using bigrams, and guessing at alignments and section lengths Posted by: A nonny bunny at March 18, 2009 8:39 AM Spoiler: Posted by: Supachupa at March 19, 2009 12:02 AM One of the weaknesses, as analyzed in the article, is that there's no letter substitution. So for English plaintext, the cryptanalyst has some purchase, a wedge, to break the code because the letter Q almost always is followed by the letter U. I have a suspicion that a computer could brute force a solution pretty quickly..
Posted by: Anonymous at March 19, 2009 6:32 AM @Anonymous: If you don't know the cipher and it's a classic cipher isn't frequency analysis usually your first choice? I'm fairly new to cryptanalysis, sorry. I don't have access to the article so I might be missing something here. Posted by: epimortum at March 19, 2009 4:42 PM @epimortum Frequency analysis serves to find what substitution is used. Since there is no substitution here, there is no reason to do it. We're dealing with a transposition cipher; the _order_ of the letters needs to be found. Posted by: Anonymous at March 19, 2009 5:08 PM Gah; I just now noticed I blundered yesterday and called it a substitution cipher instead of transposition cipher. I should stop writing messages when I'm in a rush. Posted by: A nonny bunny at March 19, 2009 5:47 PM @Anonymous: "would have been better?" I think we can say that his system was good enough. In fact it was good for 200 years! Posted by: Tomer at March 19, 2009 8:30 PM @Tomer It wasn't used for any of those two hundred years. And the author went through the effort of using techniques that could have been used at the time (although it would have been more laborious then). Posted by: A nonny bunny at March 20, 2009 3:19 AM Based on the fragmentary comments by people that have read the article: The cipher could have easily been broken by Room 40 during WWI, and Bletchly Park could have done it during while feeding the ducks. At best I would call it "Hutt 33" crossword fodder. Bigram cipher methods after 1914 should be considered defunct. The only ciphers to hold up well after 1914 have been in the Vic Cipher family (a branch of the Nihilist Cipher family). At least Vic ciphers give one up to 1 billion keys, and singletons are not easy to deduce. Posted by: Max Power at April 18, 2009 9:33 PM Post a comment
Powered by Movable Type. Photo at top by Steve Woit.
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT. |
|
Comments