Cryptology by Discovery: An Introduction to Conjecture and Proof

Section 2.1 Shift Ciphers

To begin our historical journey we examine one of the oldest written references about 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 2.1.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 2.1.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. (Outer/inner wheel for plaintext/ciphertext doesn't really matter as long as you are consistent.) You can examine a cipher wheel in action in the Sage interactive code in Sage Computation 2.1.6. Sage is an open source mathematical software package that we will use extensively in this course. However, you don't have to know anything about Sage programming yet. 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.

In Investigation: Shift Ciphers you discovered that when word breaks are no longer preserved, some of the previous strategies for cryptograms no long work. Frequently occurring letters or groups of letters may still help, and double letters may help. However, there is a new strategy that will work for shift ciphers! Since the shift is the same for all letters and there are only 25 different shifts, you can just try all the cases and see which one produces sensible plain text. An attack which just tries all the possibilities is called a brute force attack.

One way to speed up a brute force attack for shift ciphers would be use multiple strips of paper with the alphabet on them that you can line up with the cipher text. Friedman in Elements of Cryptanalysis suggests preparing

a set of cardboard strips each bearing the normal alphabet repeated (to get coincidence at any setting). Then align each cardboard strip with the cipher text, so that you don’t have to write all 26 lines every time you do this.

This method of analysis is called a “Solution by Completing the Plain Component” and is one of the most valuable methods in cryptanlysis.

―William Friedman, “Elements of Cryptanalysis”, George C. Marshall Foundation Friedman Collection

It is interesting to note that breaking codes given by shift ciphers, or in Friedman's terms “direct standard alphabets”, was a topic of instruction in his training manuals. Given the low security of these ciphers, it is interesting that anyone was still using them in the early 20th century!

While you are encouraged to make your own paper strips and try this historical (and fun!) technique out for yourself, we will allow technology to help us and again turn to the softward package Sage for that purpose. Click on the Evaluate (Sage) button to run the Sage code.

Suppose we want a formula for encrypting messages under the shift cipher. That is, we want

for some mathematical function \(f\text{.}\) To get a mathematical formula, we first need to convert the letters to numbers. We will use the following technique.

It may seem odd to start at 0 instead of 1, but it turns out to be a little bit easier mathematically this way. For the Caesar cipher, the encryption formula should be something like:

However, for the letter \(Y\) this formula isn't quite right. \(Y=24\text{.}\) Applying the formula, \(24+3 = 27\text{,}\) but 27 doesn't correspond to a letter. Here we need to remember that for our shift alphabet we needed to wrap around back to the beginning of the alphabet. We need a way to do the same thing mathematically. When we get to 26 we really want to equate 26 with 0 to wrap around numerically. This is exactly the idea of modular arithmetic. That is,

So we can now fix our formula to be exactly correct:

We can also contruct a decryption formula for this cipher.

Note this also takes care of the wrap around issue but in the opposite way. If \(CT=B\) then \(PT=1-3=-2 \equiv 24 \pmod {26}=Y\text{.}\) We will study this idea of modular arithmetic in the next section.