One of the more popular cryptosystems is the substitution cipher. It is commonly used in the puzzle section of the weekend newspapers, for example. The principle is simple: Each letter in the alphabet is replaced by another (or possibly the same) letter. More precisely, a permutation of the alphabet is chosen and applied to the plaintext. In the puzzle pages, the spaces between the words are usually preserved, which is a big advantage to the solver, since knowledge of word structure becomes very useful. However, to increase security it is better to omit the spaces.

The shift and affine ciphers are examples of substitution ciphers. The Vigenère cipher (see Section 2.3) is not, since it permutes blocks of letters rather than one letter at a time.

Everyone “knows” that substitution ciphers can be broken by frequency counts. However, the process is more complicated than one might expect.

Consider the following example. Thomas Jefferson has a potentially treasonous message that he wants to send to Ben Franklin. Clearly he does not want the British to read the text if they intercept it, so he encrypts it using a substitution cipher. Fortunately, Ben Franklin knows the permutation being used, so he can simply reverse the permutation to obtain the original message (of course, Franklin was quite clever, so perhaps he could have decrypted it without previously knowing the key).

Now suppose we are working for the Government Code and Cypher School in England back in 1776 and are given the following intercepted message to decrypt.

LWNSOZBNWVWBAYBNVBSQWVWOHWDIZWRBBNPBPOOUWRPAWXAW

PBWZWMYPOBNPBBNWJPAWWRZSLWZQJBNWIAXAWPBSALIBNXWA

BPIRYRPOIWRPQOWAIENBVBNPBPUSREBNWVWPAWOIHWOIQWAB

JPRZBNWFYAVYIBSHNPFFIRWVVBNPBBSVWXYAWBNWVWAIENBV

ESDWARUWRBVPAWIRVBIBYBWZPUSREUWRZWAIDIREBNWIATYV

BFSLWAVHASUBNWXSRVWRBSHBNWESDWARWZBNPBLNWRWDWAPR

JHSAUSHESDWARUWRBQWXSUWVZWVBAYXBIDWSHBNWVWWRZVIB

IVBNWAIENBSHBNWFWSFOWBSPOBWASABSPQSOIVNIBPRZBSIR

VBIBYBWRWLESDWARUWRBOPJIREIBVHSYRZPBISRSRVYXNFAI

RXIFOWVPRZSAEPRIKIREIBVFSLWAVIRVYXNHSAUPVBSVWWUU

SVBOICWOJBSWHHWXBBNWIAVPHWBJPRZNPFFIRWVV

A frequency count yields the following (there are 520 letters in the text):

The approximate frequencies of letters in English were given in Section 2.3. We repeat some of the data here in Table 2.2. This allows us to guess with reasonable confidence that $W$ represents $e$ (though $B$ is another possibility). But what about the other letters? We can guess that $B\text{,}R\text{,}S\text{,}I$, $V\text{,}A\text{,}P\text{,}N$, with maybe an exception or two, are probably the same as $t\text{,}a\text{,}o\text{,}i\text{,}n\text{,}s\text{,}h\text{,}r$ in some order. But a simple frequency count is not enough to decide which is which. What we need to do now is look at digrams, or pairs of letters. We organize our results in Table 2.3 (we only use the most frequent letters here, though it would be better to include all).

Table 2.2 Frequencies of Most Common Letters in English

Table 2.3 Counting Digrams

The entry 1 in the $W$ row and $N$ column means that the combination $WN$ appears 1 time in the text. The entry 14 in the $N$ row and $W$ column means that $NW$ appears 14 times.

We have already decided that $W=e$, but if we had extended the table to include low-frequency letters, we would see that $W$ contacts many of these letters, too, which is another characteristic of $e$. This helps to confirm our guess.

The vowels $a\text{,}i\text{,}o$ tend to avoid each other. If we look at the $R$ row, we see that $R$ does not precede $S\text{,}I\text{,}A\text{,}N$ very often. But a look at the $R$ column shows that $R$ follows $S\text{,}I\text{,}A$ fairly often. So we suspect that $R$ is not one of $a\text{,}i\text{,}o\text{.}$ $V$ and $N$ are out because they would require $a$, $i$, or $o$ to precede $W=e$ quite often, which is unlikely. Continuing, we see that the most likely possibilities for $a\text{,}i\text{,}o$ are $S\text{,}I\text{,}P$ in some order.

The letter $n$ has the property that around 80% of the letters that precede it are vowels. Since we already have identified $W\text{,}S\text{,}I\text{,}P$ as vowels, we see that $R$ and $A$ are the most likely candidates. We’ll have to wait to see which is correct.

The letter $h$ often appears before $e$ and rarely after it. This tells us that $N=h$.

The most common digram is $th$. Therefore, $B=t$.

Among the frequent letters, $r$ and $s$ remain, and they should equal $V$ and one of $A\text{,}R$. Since $r$ pairs more with vowels and $s$ pairs more with consonants, we see that $V$ must be $s$ and $r$ is represented by either $A$ or $R$.

The combination $rn$ should appear more than $nr$, and $AR$ is more frequent than $RA$, so our guess is that $A=r$ and $R=n$.

We can continue the analysis and determine that $S=o$ (note that $to$ is much more common than $ot$), $I=i$, and $P=a$ are the most likely choices. We have therefore determined reasonable guesses for 382 of the 520 characters in the text:

At this point, knowledge of the language, middle-level frequencies ($l\text{,}d\text{,}\dots$), and educated guesses can be used to fill in the remaining letters. For example, in the first line a good guess is that $Y=u$ since then the word $truths$ appears. Of course, there is a lot of guesswork, and various hypotheses need to be tested until one works.

Since the preceding should give the spirit of the method, we skip the remaining details. The decrypted message, with spaces (but not punctuation) added, is as follows (the text is from the middle of the Declaration of Independence):

we hold these truths to be self evident that all men are created equal that they are endowed by their creator with certain unalienable rights that among these are life liberty and the pursuit of happiness that to secure these rights governments are instituted among men deriving their just powers from the consent of the governed that whenever any form of government becomes destructive of these ends it is the right of the people to alter or to abolish it and to institute new government laying its foundation on such principles and organizing its powers in such form as to seem most likely to effect their safety and happiness