Making, Breaking Codes

Subsection 3.1 Shift Ciphers

Suetonius, a Roman historian in the first century, wrote The Lives of the Twelve Caesars in the first century. In The Life of Julius Caesar he writes about one of the techniques Julius Caesar used for encrypting messages in approximately 50 B.C.

There are also letters of his to Cicero, as well as to his intimates on private affairs, and in the latter, if he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out. If anyone wishes to decipher these, and get at their meaning, he must substitute the fourth letter of the alphabet, namely D, for A, and so with the others.

―Suetonius, The Life of Julius Caesar

In honor of Julius Caesar, this cipher is often called the Caesar cipher. While Suetonius describes the decryption process, encryption is the reverse. Each letter of the plaintext is shifted down by three letters in the alphabet.

As an example of how to encrypt or decrypt with this cipher, we encrypt the following famous quotation from Shakespeare's Julius Caesar.

We can think of the encryption process for this cipher for every letter of the alphabet in Table 3.3 where each plaintext letter (PT) will be encrypted by the letter below it in the table. Decryption corresponds to the reverse process. Note that at the end of the alphabet we need to wrap around to the beginning of the alphabet.

While the historical reference involves shifting the alphabet by three places, we could easily perform similar ciphers with a shift of any amount between 1 and 25. These are called shift ciphers or sometimes Caesar ciphers. Curiously, Suetonius also writes about the nephew of Julius Caesar, Augustus Caesar also using a shift cipher.

Whenever he wrote in cipher, he wrote B for A, C for B, and the rest of the letters on the same principle, using AA for Z.

―Suetonius, The Life of Augustus Caesar

Its unclear why Augustus didn't like the idea of wrapping around in the alphabet to just use A for Z.

Its especially convenient to encrypt a shift cipher with a cipher disk. Some interesting historical cipher disks are pictured in Figure 3.4.

To use a cipher disk to encrypt or decrypt a shift cipher, rotate the disk to the appropriate shift. For example, if A on the outer wheel is aligned with D on the inner wheel, then a shift by three for all letters of the alphabet could be found around the wheel with plaintext letters on the outer wheel and ciphertext letters on the inner wheel. You can examine a cipher wheel in action in the Sage interactive code in Computation 3.6. Just click Evaluate (Sage) and use the slider to select the desired shift. In this case, Sage is implementing the given encryption shift with the plaintext letter on the outer wheel and the ciphertext letter on the inner wheel.

Subsection 3.2 Pigpen Ciphers

A Pig Pen cipher is a geometric substitution cipher, where symbols are used to represent letters based on how the letters are drawn in grids or “pens”. They have been used by the Society of Freemasons and are also sometimes called the masonic or Freemason's cipher. This cipher is believed to be quite ancient and variations have been used by the Knights Templar and Rosicrucians. It was documents by George Washington's army, and was used by Union prisoners in Confederate prisons. It was also used in the 17th century in civil wars in England. One way that letters can be assigned to a grid is given in Figure 3.9.

Each letter is represented by the portion of the grid surrounding the letter. Since each grid is repeated twice, the second version also include a dot to distinguish the letter.

Variations of the pigpen cipher involve other arrangements of the letters, or other types of grids or pens to hold the letters.

Encrypt the message “LOVELY” with a standard pigpen cipher. Answer

Decrypt the message given below with a standard pigpen cipher.

Answer

HELLO

Subsection 3.3 Polybius Cipher

The Polybius Cipher also known as the Polybius square or Polybius checkerboard dates back to the ancient Greeks and is described in Polybius Histories. This cipher also uses a grid but a \(5 \times 5\) or a \(6 \times 6\) grid. Letters are represented by two numbers, one indicating the row and the other indicating the column of the grid. The Greek alphabet had only 24 characters, so a \(5 \times 5\) grid was sufficient. For the standard English alphabet we will have to combine I and J as a single letter to make this work.

Note the disadvantage that the length of the ciphertext is twice as long as the plaintext since each letter is represented by two numbers. However, this was actually part of the design as this can be used to send messages over long distances either by fire/light or flags. For example, the letter L could be signaled by 3 torches in the right hand and 1 torch in the left hand. One could also signal with knocks, flashing lamps, blasts of sound, drums or smoke signals.

We can make this more difficult to break by using a keyword, or keywords, such as WONDERFUL AWARD, to rearrange the alphabet in the square. We can only enter each letter once in our grid, so we only keep a letter the first time it appears in the keyword. Thus, the keyword will be entered in our grid as WONDERFULA since we must eliminate the second W, A, R, and D from the key word.

The grid can be expanded to a \(6 \times 6\) to add the numbers 0-9 (and not have to double up any letter). For example, we will create a grid with the keyword “MOUNTAINS”. A method must also be agreed upon for how to place the digits 0-9 into the grid.

Encryption and decryption work just as before with the additional row and column.

Subsection 3.4 Frequency Analysis

We have seen several different types of substitution ciphers, and there are many more ways to create such a cipher. A random substitution cipher where each letter of the plaintext is associated to a random letter or symbol is the hardest case to crack. Let's have a look at one and see if we can crack it! The following cipher text is a monoalphabetic cipher but the correspondence between plaintext and ciphertext has been chosen randomly. Word breaks are not preserved and the letters are arranged in blocks of five (a tradition that dates back to the era of transmitting messages via telegraph.) What techniques can we use to break this one?

LXSBQ ZOYZD OXAAB EWQAX JJAQS QZVEI QIJEJ JZELJ XYICY ZYIQO BYQTS QLJRZ QRHAJ REJYI LQOXJ BYHJA EPYZC YZJBQ ZQXRE WERJE VYHIJ YCSHZ QAKZY HJXIQ AEPYZ XIJBQ SZQSE ZEJXY IYCCZ QNHQI LKJEP AQRJB QZQEZ ZEIFQ VQIJY CLXSB QZCYZ QTEVX IEJXY IEIUJ BQJZX EAEIU CXJJX IFYCA QJJQZ JYAQJ JQZPQ CYZQJ BQVQR REFQP QFXIR JYESS QEZ

Since word breaks are not preserved, we must focus on characteristics of the given alphabet. What about a brute force attack in this case? How many random monoalphabetic ciphers are there? For the letter A it could be enciphered with any of 26 possible symbols. For B, one symbol is already used so it could be enciphered with any of the 25 remaining symbols. Similarly, C could be enciphered with any of the 24 remaining symbols. Thus, the total number of random monoalphabetic ciphers is

In general, for a set of \(n\) objects, the number of different ways to arrange all \(n\) objects in the set, is \(n!=n \times n-1 \times n-2 \times \cdots \times 2 \times 1\text{.}\)

A better strategy than brute force for breaking monoalphabetic ciphers is to try to match the statistics of the cipher text to the statistics of the underlying language. This technique, called frequency analysis, dates back to the Arab scholar Al-Kindi (c. 801–873 AD). In his manuscript, A Manuscript on Deciphering Cryptogaphic Messages he writes

One way to solve an encrypted message, if we know its [original] language, is to find a [different clear] text of the same language long enough to fill one sheet or so and then we count [the occurrences of] each letter of it. We call the most frequently occurring letter the “first”, the next most occurring the “second” the following most occurring the “third” and so on, until we finish all different letters in the cleartext [sample]. Then we look at the cryptogram we want to solve and we also classify its symbols. We find the most occurring symbol and chnge it to the form of the “first” letter [of the cleartext sample], the next most common symbol is change dot the form of the “second” letter, and the following most common symbol is changed to the form of the “third” letter and so on, until we account for all symbols of the cryptogram we want to solve.

Quirky Question: What do the words algebra, algorithm, zero and cipher have in common? Answer

To apply frequency analysis, then, we need a thorough understanding of the distribution of letters in the appropriate language. We introduce frequency analysis for the English language with a humorous presentation about alphabet characteristics. This was written by another pioneer in American cryptology, Elizebeth Smith Friedman. Elizebeth was a codemaker and codebreaker for the U.S. Navy and the U.S. Treasury Department's Bureau of Prohibition and Bureau of Customs. She was also married to the William Friedman discussed earlier. She wrote a manuscript on how to crack codes and ciphers which unfortunately was never published.

If I were appointed to act as final arbitrator at the peace conference between the warring letters what I would do would be to send my intelligence agents out and tell them to find out which ones deserved to be placed at the head of the class on the basis of the amount of work each one did. My agents would snoop around on gum shoes, spend a lot of my money and when they got tired would sit down and make an actual count of letters in a large amount of ordinary telegrams, and then like all that species called efficiency engineers, they’d probably turn in a report like this:

[parts omitted]

On the basis of our investigation if we were to arrange the letters in the order of their importance, judged by the work they do, they would appear as follows:

ETOANIRSHDLUCMPFYWGBVKJXZQ

You will also note from Figure 1 that ten letters, E, T, O, A, N, I, R, S, H, and D, do almost 75% of the work; the four vowels, A, E, I, and O doing about 35% of it; the six consonants, D, H, N, R, S, and T doing a bit more 40%. This leaves 16 letters to do the rest, that is 25% of the work. The hardest workers are E, T, O, A, and N, and the worst slackers are J, K, Q, X, and Z.

Attached hereto is our bill for services rendered.

Very truly yours,

F. FISH ENSEE

―Elizebeth Smith Friedman, unpublished manuscript, George C. Marshall Foundation Friedman Collection

Figure 1 was not completed in her unfinished work but it would have looked something like the frequency distribution of the English alphabet in Figure 3.18.

As a government employee Elizebeth Friedman was subject to regular efficiency reviews. One suspects she found some aspects of them comical.

As we can see, the first important component in frequency analysis is understanding the distribution of individual letters. This information is summarized in the chart below.

We can visualize this distribution to see how unevenly letters are used in the English language.

From this we can see the most frequent letters in the English language. While these percentages vary a little based on different texts in English, this provides important information relative to breaking monoalphabetic ciphers.

The English language also has strong patterns with how letters combine with other letters. So the next important piece of information is digraph and trigraph frequency statistics. Digraphs are pairs of letters and trigraphs are groups of three letters. Again, these percentages will vary a little depending on the type of English text used. We reference an older collection from Parker Hitt in Figure 3.23, but it is fairly consistent with modern language.

Parker Hitt, "Manual for the Solution of Military Ciphers"", George C. Marshall Foundation Friedman Collection

Let's return to our ciphertext and examine its frequency information to try to determine the plaintext. We will first use some Sage code to calculate the frequency information for single letters, digraphs and trigraphs.

From the Sage code, we see that the most frequent trigraph is JBQ. Since Q and J are the most frequent letters in the ciphertext, B is a medium frequency letter in the ciphertext, and JB is a common digraph, we have a strong guess that JBQ corresponds to THE in the plaintext. Replacing the letters J,B,Q with t,h,e respectively gives us:

LXShe ZOYZD OXAAh EWeAX ttAeS eZVEI eItEt tZELt XYICY ZYIeO hYeTS eLtRZ eRHAt REtYI LeOXt hYHtA EPYZC YZthe ZeXRE WERtE VYHIt YCSHZ eAKZY HtXIe AEPYZ XIthe SZeSE ZEtXY IYCCZ eNHeI LKtEP AeRth eZeEZ ZEIFe VeItY CLXSh eZCYZ eTEVX IEtXY IEIUt hetZX EAEIU CXttX IFYCA etteZ tYAet teZPe CYZet heVeR REFeP eFXIR tYESS eEZ

We can now make a guess for ciphertext Z. The letter Z is the third most frequently occurring letter in the ciphertext, ZQ and QZ are frequently occurring digraphs, and BQZ is a frequently occurring trigraph. So we must have a common letter in English that pairs in both directions with Q=E, so _E and E_ must be common and the trigraph HE_ must also be common. We guess that Z is most likely N or R. Since RE and ER is more common than NE and EN, we guess Z=r. You should now be able to continue this process of identifying likely words in the plaintext to determine the remaining letter substitutions. Give it a try if you like! Answer

While we can use the technique of frequency analysis for any substitution cipher, we will first examine some common puzzles called cryptograms. While originally the word cryptogram meant any sort of encrypted message, currently it most often refers to a specific kind of cipher often found in newspapers and puzzle books. A cryptogram is a letter-for-letter substitution where each plaintext letter is replaced by a different ciphertext letter (or symbol) and it is replaced by the same ciphertext symbol wherever it appears in the plaintext. Word breaks are preserved and no letter is enciphered as itself. We'll start with an example.

As we saw in the previous example, there are lots of properties of the English language that help us to solve cryptograms. Some starting points for solving any cryptogram are short words, double letters, and frequency of letters. It is especially useful to know the following:

• The most common one letter words are: A, I.
• Common two letter words are: am, an, as, at, if, in, is, it, of, on, or, do, go, no, so, to, be, he, me, we, by, my, up, us.
• Common three letter words with repeated letters are : all, see, did, too.
• Other common three letter words are: the, and, for, are, but, not, you, any, can, had, her, was, one, our, out, day, get, has, him, his, how.
• Common four letter words with repeated letters are: that, will, been, good.
• Other common four letter words are: with, have, this, your, from, they, know, want, much, some, time.
• Common double letters include: LL,EE,SS,TT,OO,MM,FF,PP,RR,NN,CC,DD.