Foreign Dispatches: The Art of Keeping (and Finding) Secrets

I have to admit that I'm rather disappointed it took so long for someone amongst my usually astute readership to crack the second cipher challenge I set up two days ago, even though I gave such a blatant hint in the form of known plaintext which could be used to mount an attack (though thankfully someone did come up with a solution in the end). As I said from the very beginning, the technique behind the encryption wasn't very fancy at all, and could certainly have been broken by hand with a little patience.

Before I get into the technique used to encode the problem, though, I'd like to turn first to the easier challenge I set, which Andrew so rapidly and correctly overcame. The key thing to keep in mind with the first challenge was that it was based on a substitution cipher, which is just a fancy way of saying that it permuted the 26 letters of the English alphabet. In theory, one might expect such a cipher to be extremely difficult to crack, especially if the permutation isn't just a simple rotation as with a Caesar cipher (e.g. ROT13), there being 26! possible substitution ciphers, or approximately 4 x 10²⁶ in all.

So much, then, for theory. In reality, however, all such ciphers are pretty much trivial to break, for a very simple reason: language isn't random, and therefore neither is the distribution of letters used in any alphabet. By far the most common letters in the English language are E, T, A, I, O, N, S, H, R, D, L and U in decreasing order of frequency (ETAOIN SHRDLU for short), and one can therefore safely assume that the most common letter in any reasonably long piece of ciphertext generated by a susbtitution cipher will be the letter E, T or A. In the case of the sample text I provided, the frequency of the enciphered letters was approximately I=11%, Q=10%, N=8%, J=7%, B=C=6%,F=H=5%, with the rest of the letters occurring at a rate of 4% or less. This clue should have been enough to begin cracking the ciphertext, but another important hook was also available in it, one which Andrew also picked up on, namely the occurrence of particular telltale clusters of letters, in this case, those of one or two characters. The only instances in which isolated characters occur in English are when the vowels "A" or "I" are in use, so it should have been immediately obvious that one of these two had to correspond to "C", and the other to "N" in the encoded text; it was easy enough to settle which was which by noting that "c'g" would have to be "I'm". As if this were not enough, yet still other clues were available in the ciphertext, not least of which was the occurrence of repeated characters like "ii" and "jj", which in English could only be "ee" or "ll". With all of the foregoing alone, entire words or recognizable parts of words should have begun to emerge, making it almost trivial to decipher the rest of the material (in fact, an easily automatable chi-square test should demolish any such encipherment in a fraction of a second, by comparing the underlying distribution with that of all languages for which we have the relevant statistics).

Now, you may be asking yourself why I've devoted all this attention to what I maintain was a trivial cipher, if it really was as trivial as I claim, and the answer is very simple: because the entire rationale behind the cipher used in the second text was to combat the glaring weakness of the substitution cipher used in the first, and shared by all substitution ciphers - the unchanging frequency distribution which gives the game away must somehow be disguised, and this is just what the second cipher I chose manages to do. The name of that technique? The Vigenère cipher, named erroneously after Blaise de Vigenère, but actually invented by Leone Battista Alberti way back in 1465: in other words, the method hardly anybody managed to defeat in a timely fashion dates back to the Middle Ages (I told you it wasn't cutting edge!).

The idea behind the Vigenère cipher is actually pretty simple, as you'd expect for something that old: rather than use a single substitution cipher for all of your text, why not use a whole bunch in succession, changing ciphers character by character, using a secret password to determine which of the 26 Ceasar ciphers to use when? The following image shows the most important component of a Vigenère cipher, a table containing all the Caesar ciphers in succession:

To use the table to encode a given text, one first chooses a passphrase, making sure that none of the characters in the phrase are repeated: for example, one might choose, say, IMPOSTER as one's ultra-secure keyword. One then takes one's plaintext, say

Gallia est omnis divisa in partes tres

and repeats the passphrase underneath the plaintext characters with their spaces expunged:

Plaintext: GALLIAESTOMNISDIVISAINPARTESTRES

Key: IMPOSTERIMPOSTERIMPOSTERIMPOSTER

The encryption is then a simple matter of going to row "I" in the table to find the column corresponding to "G" (namely "O"), going to row "M" to find the column corresponding to "A" (which would be "M"), and so on and so forth, giving us the phrase

Plaintext: OMAZATIJBABBALHZDUHOAGTRZFTGLKIJ

just as in the crib I provided. As you can confirm for yourself by using the Java applet available here, the Vigenère cipher does indeed accomplish the aim for which it was invented, in that it flattens the frequency distribution of letters enough to frustrate any straightforward attempts at decipherment. In fact, it does the job so well that it was thought for almost 300 years to be unbreakable!

"But hold on", you're probably wondering, "how do you expect us to break something people couldn't handle for 300 years?" To this, I have a simple answer: it's one thing for 18th century gentlemen to not have a clue how to defeat it, but this method has been broken for over 150 years now, and pretty much any elementary introduction to cryptography on the web (of which there are many, e.g. this one) would have tipped you off to the solution; a little more digging should even turn up automated tools for grinding through the dirty work for you. The funny thing about this second exercise was that the Vigenere cipher actually figures in that most ubiquitous of middlebrow books, Dan Brown's "Da Vinci Code", which is one reason why I'd thought it would serve as a nice, gentle introduction into the sort of "Enigma" and "No Such Agency" stuff most people only get vague accounts about in movies and popular books. Clearly I'd wildly miscalibrated how much effort most people are willing to put into even moderately difficult intellectual challenges.

Comments

Ah, I figured it was something like a changing substitution, but you've hit the nail on the head with your last sentence: I just couldn't be bothered figuring out what the rule on the substitution was! (Short attention span, I guess...)

Though, having read The Da Vinci Code, I can't recall where the Vigenere cipher appeared...?

Posted by: Andrew | August 17, 2005 at 06:19 AM