4.5   Going Farther: Shift Ciphers

The simplest cipher we shall consider is called the shift cipher. When implementing the shift cipher, each letter of the message is shifted a fixed distance down the alphabet. Our "alphabet," including punctuation and both upper- and lowercase letters, is numbered from 0 to 94. You can see it by clicking on "Nums->Text" below:

Your browser does not support java.

If we let

P = a number representing a letter from the unencoded message


C = the corresponding number for encoded message,

then the shift cipher can be expressed mathematically as

C = (P + k) % 95,

where k is a fixed integer called the key. We work modulo 95 because we are using an "alphabet" with 95 "letters." This congruence is used to encode each letter in the original message. Shift ciphers are sometimes called Caesar ciphers, because Julius Caesar purportedly was the first to use one.

Let's look at an example. Suppose that our unencoded message (referred to as plaintext) is "Hello!", and we want to encipher this with a key k = 4. We start by turning the plaintext into numbers using "Text->Nums" in the "Shift Cipher" applet:

Your browser does not support java.

Next, we add 4 to each number in the string, and then reduce mod 95. This can be done by setting the value of "Key" to 4, and clicking on "Shift nums":

Your browser does not support java.

Finally, we turn this number string back into the encoded text, called ciphertext, by using "Nums->Text":

Your browser does not support java.

As you've probably already guessed, the applet will perform all of these steps automatically. You need only include the plaintext, the key, and click on "Text shift to Text":

Your browser does not support java.

For example, here is a shift cipher with k = 7.

Your browser does not support java.

Decoding a shift cipher is easy if you know the key k. Since

C = (P + k) % 95,

it is easy to see that

P = (Ck) % 95.

In other words, a shift cipher with key k can be decoded with another shift cipher with key equal to –k. Here's an example:

Your browser does not support java.

And here we decode by setting k = –18:

Your browser does not support java.

4.5.1  ROT-13: Shift Ciphers and the Internet

A simpler version of the shift cipher called ROT-13 has been in use on the internet for many years. Specifically, it is used in Usenet, the collection of newsgroups where people discuss a multitude of topics. Consider, for example, the group rec.humor.funny. People submit jokes which are reviewed by a moderator, and then the funny ones are sent out over Usenet to the world. Sometimes the moderator wants to send out an "off-color" joke, but doesn't want to offend the more sensitive readers. Including a warning along with the joke does no good since a delicate reader may see the offending words before they read the warning.

The solution is that the naughty jokes are encoded by ROT-13. A plain text warning message is also included so that readers can decide if they want to "risk" decoding the joke. In ROT-13, the encryption only applies to letters of the alphabet; spaces and punctuation are left unchanged. Since there are 26 letters in the alphabet, the cipher works modulo 26. The shift which is used is k = 13 (thus the name, because it ROTates letters 13 slots through the alphabet).

Most software used for reading Usenet newsgroups have the commands built into them for decoding such messages. The user just picks "Decode" from a menu or hits a special key. Rest assured that users do not have to understand shift ciphers to read dirty jokes on the internet.

One handy feature of ROT-13 is that we can use the same function for both encoding and decoding! The reason is that we are working modulo 26. To decode a shift by 13 we need to shift by –13. But, –13 === 13 (mod 26). So, decoding is also a shift by 13. This is why 13 was chosen as the standard for this cipher in the first place.

Let's look at an example of ROT-13. To keep in the spirit of this discussion, below is a joke whose punch line has been encoded by ROT-13. The joke does not contain offensive words. However, we should warn the reader that understanding the joke requires a certain level of mathematical knowledge. Moreover, some readers may not find it funny. Here is the joke:

Q: What did the mathematician say when epsilon went to zero?
N: Jryy, gurer tbrf gur arvtuobeubbq!

To decode the punch line, you need to run ROT-13 on the encrypted text:

Your browser does not support java.

4.5.2  Getting Some Exercise

We now return to our standard shift ciphers, with a 95-letter alphabet.

Exercise 6

How many different shift ciphers are possible with a 95-letter alphabet?

How many different shift ciphers are possible with an n-letter alphabet?

Exercise 7

The following message has been encoded with a shift cipher with key 9.

ciphertext = ]qn)xk rx~|)vj}qnvj}rlju)k{njt}q{x~pq)!x~um)kn)mn \ nuxyvnw})xo)jw)nj|#)!j#)}x)ojl}x{)uj{pn)y{rvn)w~vkn{|7)66Kruu)Pj}n|

(a) Use the applet below to decode the message.

(b) The author of this message was trying to predict what important mathematical breakthroughs may occur in the near future. Explain why the statement is nonsensical.

Your browser does not support java.

Exercise 8

Below is a message that has been encoded with a shift cipher. We don't know what key k was used for the encoding, but we do know that the last character in the plain text message was a period. Use this information to decode the message.

message = r5B5:3K9;:1EK@;K@41K3;B1>:91:@K5?K8571K35B5:3KC45?71EK-:0K/->?K@;K@11:-31K.;E?YKXXK{YKuYKzR};A>71Y

Hint: In Exercise 5, you determined the numerical equivalent of a period.

Your browser does not support java.

Exercise 9

Cryptanalysis is the art of deciphering an encoded message without knowing the key. Shift ciphers are easy to cryptanalyze because there are very few keys. Take, for example, the following message, which has been encoded with a shift cipher.

ciphertext = i+An1/B

Try all 95 different possible shift ciphers on this message. What is the plaintext?

Hint: The applet below will make a list of all 95 different shifts.

Your browser does not support java.

Exercise 10

Alice and Bill are sending messages to each other by using a shift cipher. They are very careful not to reveal their key to anyone, but they don't realize that shift ciphers are very unsecure.

Oscar has been observing their messages, and so far, he has intercepted the four coded texts. Each has been preloaded into an applet below.

(a) Help Oscar decipher the messages. (Note that all of the messages start the same way.)

(b) Oscar wants to do more than just eavesdrop; he wants to create some mischief by impersonating Bill and sending a message with false information to Alice. Devise such a message for Oscar, and encrypt it for him.

Your browser does not support java.

Your browser does not support java.

Your browser does not support java.

Your browser does not support java.

Section 4.1 | Section 4.2 | Section 4.3 | Section 4.4 | Section 4.5

Chapter 4 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company