2.1 Shift Ciphers – Introduction to Cryptography with Coding Theory, 3rd Edition

2.1 Shift Ciphers

One of the earliest cryptosystems is often attributed to Julius Caesar. Suppose he wanted to send a plaintext such as

gaul is divided into three parts

but he didn’t want Brutus to read it. He shifted each letter backwards by three places, so d became A, e became B, f became C,  etc. The beginning of the alphabet wrapped around to the end, so a became X, b became Y,  and c became Z. The ciphertext was then

DXRIFPAFSFABAFKQLQEOBBMXOQP.

Decryption was accomplished by shifting FORWARD by three spaces (and trying to figure out how to put the spaces back in).

We now give the general situation. If you are not familiar with modular arithmetic, read the first few pages of Chapter 3 before continuing.

Label the letters as integers from 0 to 25. The key is an integer κ with 0κ25. The encryption process is

xx+κ(mod26).

Decryption is xxκ(mod26). For example, Caesar used κ=233.

Let’s see how the four types of attack work.

  1. Ciphertext only: Eve has only the ciphertext. Her best strategy is an exhaustive search, since there are only 26 possible keys. See Example 1 in the Computer Appendices. If the message is longer than a few letters (we will make this more precise later when we discuss entropy), it is unlikely that there is more than one meaningful message that could be the plaintext. If you don’t believe this, try to find some words of four or more letters that are shifts of each other. Three such words are given in Exercises 1 and 2. Another possible attack, if the message is sufficiently long, is to do a frequency count for the various letters. The letter e occurs most frequently in most English texts. Suppose the letter L appears most frequently in the ciphertext. Since e=4 and L=11, a reasonable guess is that κ=114=7. However, for shift ciphers this method takes much longer than an exhaustive search, plus it requires many more letters in the message in order for it to work (anything short, such as this, might not contain a common symbol, thus changing statistical counts).

  2. Known plaintext: If you know just one letter of the plaintext along with the corresponding letter of ciphertext, you can deduce the key. For example, if you know t(=19) encrypts to D(=3), then the key is κ3191610(mod26).

  3. Chosen plaintext: Choose the letter a as the plaintext. The ciphertext gives the key. For example, if the ciphertext is H, then the key is 7.

  4. Chosen ciphertext: Choose the letter A as ciphertext. The plaintext is the negative of the key. For example, if the plaintext is h, the key is 719 (mod26).