Schneier on Security
A blog covering security and security technology.
« Leaving Infants in the Car |
| Hiding Behind Terrorism Law »
March 18, 2009
1801 Cipher Solved
Interesting 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.
Article only available to paid subscribers.
Anybody who's already paid, care to summarize the crypto techniques involved, or post pointers to where they're explained elsewhere? Thanks in advance....
So the key is my Visa card number?
I decrypted the text: "The Magic Words are Squeamish Ossifrage"
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.
1 hw 3 lr 32 ablr
2 eo 1 hw 11 khwl
3 lr 2 eo 20 eoyu
1 ll 1 ll 11 llty
2 od 2 od 20 odtr
And you get the ciphertext
akelobholdlwyttrluyr and key 32,11,20
It was cracked using bigrams, and guessing at alignments and section lengths
Plain text reads:
"Mr. President.. do not go to the theatre tonight!" Beware Rothschild!
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.
This greatly simplifies realigning the columns to get readable text.
I have a suspicion that a computer could brute force a solution pretty quickly..
If there is no letter substitution then why wouldn't frequency analysis be obvious from the get go.
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.
"If there is no letter substitution then why wouldn't frequency analysis be obvious from the get go."
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.
Of course this is made easier when you know which letters tend to follow each other (like q and u). So using both a substitution cipher in conjunction with the transposition cipher would have been better.
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.
@Anonymous: "would have been better?" I think we can say that his system was good enough. In fact it was good for 200 years!
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).
The main reason the cipher wasn't cracked before is because no one really looked at it before. It went mostly ignored and unexamined.
It reads: "All your liberty are belong to us."
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.
Schneier.com is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc.