Bruce Schneier

Schneier on Security

A blog covering security and security technology.

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.

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....

Steven M. BellovinMarch 18, 2009 8:17 AM

The cipher itself is at http://memory.loc.gov/cgi-bin/ampage?...

Larry SeltzerMarch 18, 2009 8:20 AM

So the key is my Visa card number?

Larry SeltzerMarch 18, 2009 8:24 AM

I decrypted the text: "The Magic Words are Squeamish Ossifrage"

A nonny bunnyMarch 18, 2009 8:39 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
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

SupachupaMarch 19, 2009 12:02 AM

Spoiler:
"Mr. President.. do not go to the theatre tonight!" Beware Rothschild!

AnonymousMarch 19, 2009 6:32 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.
This greatly simplifies realigning the columns to get readable text.

I have a suspicion that a computer could brute force a solution pretty quickly..

epimortumMarch 19, 2009 4:42 PM

@Anonymous:
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.

AnonymousMarch 19, 2009 5:08 PM

@epimortum
"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.

A nonny bunnyMarch 19, 2009 5:47 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.

TomerMarch 19, 2009 8:30 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!

A nonny bunnyMarch 20, 2009 3:19 AM

@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).
The main reason the cipher wasn't cracked before is because no one really looked at it before. It went mostly ignored and unexamined.

BnonymousMarch 20, 2009 7:57 AM

1337 Cipher Solved?

CurtisMarch 22, 2009 7:39 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.

E-mail is optional and will not be displayed on the site.

Remember Me?

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.