## Subsection 3.2 The Caesar/shift cipher

The

*Caesar cipher*is an example of a*monoalphabetic substitution cipher*, in which every character is replaced by some other character. It is the earliest known example of a substitution cipher and, according to the Roman historian Suetonius, was used by Julius Caesar himself. It is currently understood as encrypting messages by shifting every letter forward in the alphabet by \(3\text{;}\) that is, as the function \(f(p)=p+3\mod26\text{.}\) More generally, a*shift cipher*may shift every letter forward by any amount.It is easy to generate example shift ciphertext and have students decrypt this ciphertext. Prompt them to continually investigate the methods they use to cryptanalyze shift ciphers: does it involve brute force? Counting the number of occurrences of each letter and comparing to English letter frequencies, then guessing the most common ciphertext letter corresponds to \(e\text{?}\) Spotting patterns between adjacent letters? There is no “wrong” way, but it is the goal of cryptographers to find a general method for decrypting a given family of cipher no matter the particular message or peculiarities of the cipher; therefore, we want to move students’ thinking toward counting letter frequencies as a method of cryptanalyzing any monoalphabetic substitution cipher.

Inform students that there is a faster way to decrypt shift ciphers than saying the alphabet backwards in their heads. Ask them to try decrypting a message that was encrypted with a very large forward shift such as \(+25\text{.}\) How would they do it? Likely by shifting each letter

*forwards*by \(1\) to obtain the plaintext message. This means that in the English alphabet, \(0=25+1=26\text{,}\) and now you can introduce modular arithmetic (working with modulus \(26\) for the foreseeable future). It’s beneficial to provide students with a*letter-to-number correspondence sheet*, which numbers English letters in increasing order starting with \(a=0\text{.}\)
2.

*Have students decrypt a message (long enough or rigged so that its letter frequencies are close to those in English in general) that was encrypted using each of the following:**A Caesar cipher \(c\equiv p+3\mod26\text{.}\)**A shift cipher with a shift other than \(3\) (without telling students the shift).**A shift cipher with a shift greater than \(26\) (without telling students the shift).**How many different shift ciphers are there in the English alphabet? In other words, how hard is it to cryptanalyze the shift cipher by brute force?*

The usefulness of the clock metaphor for introducing modular arithmetic cannot be overstated: we are thinking of the alphabet as a clock with \(26\) numbers on it, going from \(0\) on the top to \(25\text{.}\) Can students determine various times on this clock? Up until this point, students were not likely to fully understand our definition of a cipher as a function modulo \(26\text{,}\) but now they can. The following activity is one I’ve used to help students learn basic modular arithmetic without any prerequisites:

3.

*Reduce several numbers modulo \(26\text{,}\) including numbers much larger than \(26\text{,}\) using various notions of “congruence modulo \(26\)” (e.g. \(a\equiv b\mod26\) if \(a\text{:}\)00 and \(b\text{:}\)00 are the same time on a \(26\)-hour clock, \(a\) and \(b\) have the same remainder upon division by \(26\text{,}\) \(26\mid (a-b)\text{,}\) subtracting a multiple of \(26\) from \(b\) yields \(a\)).**Create addition and multiplication tables modulo 5 and modulo 14. What patterns do students notice? What do they wonder about these tables?*