$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 4.2: The Caesar Cipher and Its Variants

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\NN}{\mathbb N}$$
$$\newcommand{\RR}{\mathbb R}$$
$$\newcommand{\QQ}{\mathbb Q}$$
$$\newcommand{\ZZ}{\mathbb Z}$$
$$\newcommand{\Cc}{\mathcal C}$$
$$\newcommand{\Dd}{\mathcal D}$$
$$\newcommand{\Ee}{\mathcal E}$$
$$\newcommand{\Ff}{\mathcal F}$$
$$\newcommand{\Kk}{\mathcal K}$$
$$\newcommand{\Mm}{\mathcal M}$$
$$\newcommand{\Pp}{\mathcal P}$$
$$\newcommand{\ind}{\operatorname{ind}}$$
$$\newcommand{\ord}{\operatorname{ord}}$$

Another system which dates to ancient times was supposedly used by Julius Caesar.

Definition: Caesar Cryptosystem

Alice takes her message, removes all spaces and punctuation, and puts it all in one case (maybe upper case). Then she moves each letter $$k$$ places down the alphabet, wrapping around from Z to A if necessary, where $$k\in\ZZ$$ is a fixed number known to both Alice and Bob but no one else, called the key.

To decrypt, Bob simply moves each letter $$k$$ places earlier in the alphabet, wrapping past A to Z if necessary: i.e. Bob encrypts the ciphertext with key $$-k$$ to get the plaintext.

This is called the Caesar cryptosystem.

Apparently, Julius Caesar usually used the key value $$k=3$$. His nephew Octavian, who later became the emperor Augustus, liked to use $$k=-1$$.

When using what is called the Latin alphabet (which is not what was used in ancient Rome, though), with its 26 letters, there is one particularly nice key value: 13. The nice thing about that value is encryption and decryption are exactly the same transformation. In modern times, this transformation is called ROT13, and it has a small role in the modern history of the Internet. In particular, posts on early chat rooms and bulletin boards would sometimes want to have a bit of content that should not be automatically available to anyone who looks at the post, but would be there for the determined reader (such as, for example, a spoiler in a review of some popular new game, book, or film). These were often included in the post, but only after they had been run through ROT13.

A few commercial products used ROT13 for actual security, despite it actually being completely insecure, such as certain parts of some versions of the Windows operating system.

The Caesar ciphers were completely broken (in a number of ways; see Exercise 4.3.1) before $$1000$$CE, but a descendent was developed in the late Middle Ages and was considered the state of the cryptological art through the early modern period.

Definition: Vigenère Cryptosystem

Once again, Alice takes her message, removes all spaces and punctuation, and puts it all in one case (maybe upper case). This time, the key $$\vec{k}=(k_1,\dots,k_\ell)$$ which Alice and Bob share is an $$\ell$$-tuple, for $$\ell\in\NN$$, of integers $$k_1,\dots,k_\ell\in\ZZ$$.

To encrypt, Alice steps through her plaintext message and key sequence both one letter at a time, moving each plaintext letter forward (wrapping from A to Z if necessary) by the number of letters specified by the corresponding key number. If she runs out of key numbers, she simply starts again at the beginning of the key sequence.

To decrypt, Bob simply moves each letter $$k$$ places earlier in the alphabet, wrapping past A to Z if necessary: i.e. to decrypt, Bob encrypts with key $$-\vec{k}=(-k_1,\dots,-k_\ell)$$.

This is called the Vigenère cryptosystem.

Traditionally, the key in Vigenère is a written down, memorized, and shared between Alice and Bob in the form of a word. Then when encrypting or decrypting, the letters of the keyword are “added” to the message letters, as described above, under the convention that $$A=1$$, $$B=2$$, etc..

Notice that Vigenère with key length $$\ell$$ is essentially $$\ell$$ Caesars in parallel – in fact, if $$\ell=1$$, they are exactly the same cryptosystem. It therefore turns out that Vigenère is essentially $$\ell+1$$ times harder to crack than Caesar, the “$${}+1$$” coming from the fact that Eve doesn’t even know $$\ell$$. Nevertheless, after a couple of hundred years in which it was considered unbreakable and used as the principle diplomatic cipher in the courts of Europe, approaches to breaking Vigenère were developed.

As one final variant of the Vigenère cipher, suppose we go in the opposite direction from the $$\ell=1$$ extreme, and instead take $$\ell$$ as long as possible.

A one-time pad is a Vigenère cryptosystem in which the key is as long as the message, chosen randomly, and never re-used. [The key is also called the one-time pad in this cryptosystem1.]

(A one-time pad is sometimes called – inappropriately, given the true intellectual history of the cryptosystem – a Vernam Cipher .)

It is important to have a good key sequence in a one-time pad cryptosystem. The good news is that one can prove that with a truly random one-time pad, the resulting cryptosystem is in fact perfectly secure. In computer science, this is called information theoretically secure , because the proof of security does not rely upon any assumptions about the computational resources available to the attacker. [See [Sha49] and [Sha48] for this proof.] Other cryptosystems we shall meet below are only secure if we assume the attacker has access to a computer of a particular type (a probabilistic polynomial-time Turing machine is the usual assumption; this is the subject within computer science called computational complexity, see, e.g., [AB09]).

It is also important never to use the same pad more than once. If so, an attacker can take the letter-by-letter difference of the two ciphertexts and this will completely remove the pad from the calculation. In fact, at that point the message can usually be determined quickly.

In modern times, after the advent of digital communications networks, messages are written as computer data, so everything is stored (and transmitted) as bits, meaning $$1$$s and $$0$$s. With bits, when we do the equivalent of what was described above as shifting a letter along the alphabet, wrapping from Z to A if necessary, we are either doing nothing, if the shift is by an even amount, or simply switching $$0$$ and $$1$$ otherwise.

Another way of saying that is to say that is that if the message and the key are both written all out in bits – think of them as the elements $$[0],[1]\in\ZZ/2\ZZ$$ – then the encryption consists exactly of adding the corresponding bits mod $$2$$. A good one-time pad is therefore a very random, and very long, string of bits (congruence classes in $$\ZZ/2\ZZ$$).

The big problem with one-time pads is key distribution: Alice and Bob must share very large one-time pads before they ever start to communicate, large enough to have as many letters (or bits, in the computer age) as all of their future messages.

This does suggest an interesting approach to cryptography: find a way that Alice and Bob can share a small secret out of which they can generate arbitrarily long sequences of bits, both getting the same sequence, which seem to any attacker to be entirely random. If this were possible, they would use these pseudorandom sequences (called this because they are not actually random – after all, they can be determined in advance by both Alice and Bob using their small starting secret – they only appear so to all attackers) as one-time pads. [See [Lub96] for more about pseudorandomness.]

Exercise $$\PageIndex{1}$$

ROT13 was supposedly nice because it reduced the amount of coding which needed to be done: the same program would decrypt as the one which encrypts, since doing ROT13 a second time undoes the first ROT13’s transformation.

Is this true for other keyed Caesar ciphers? Make a conjecture about whether, given a Caesar cipher key kand a message m, there always exists an nsuch that

$\overbrace{e^C_k\circ\dots\circ e^C_k}^{\text{n times}}(m)=m \nonumber$

where $$e^C_k$$ is the function which does the Caesar encryption with key $$k$$. If so, find an expression for the smallest such $$n$$, which depends (if necessary) on $$k$$, $$m$$, and the size of the alphabet in which $$m$$ is written.2.

Exercise $$\PageIndex{2}$$

Continuing the previous exercise: Suppose now $$\vec{k} = (k_1, . . . , k_ℓ)$$ is an $$ℓ$$-tuple, for $$ℓ ∈ N$$, of integers $$k_1, . . . , k_ℓ ∈ Z$$ and $$e \dfrac{V}{k}$$ is the Vigenère encryption function with key $$\vec{k}$$. Find if for all messages $$m$$, there exists an $$n ∈ N$$ such that

$\overbrace{e^V_{\vec{k}}\circ\dots\circ e^V_{\vec{k}}}^{\text{n times}}(m)=m \nonumber$

and, if so, find an expression for the smallest such $$n$$, which depends (if necessary) on $$\vec{k}$$, $$m$$, and the size of the alphabet in which m is written.3.

Exercise $$\PageIndex{3}$$

Suppose Eve has a twin Vev, and they are both looking at an intercepted ciphertext $$c$$ sent by Alice to Bob. They think that those crazy lovebirds Alice and Bob have used a one-time pad to encrypt their communications, but Eve and Vev both do lots of calculations and think they have managed to correctly decrypt $$c$$. Unfortunately, they have different (non-gibberish!) values $$m_e$$ and $$m_v$$ which Eve and Vev, respectively, think were the plaintext that Alice meant to send to Bob.

What must have been the one-time pads $$p_e$$ and $$p_v$$ which they were somehow calculating (or guessing) that Alice used for their respective encryptions?

Could they have come up with arbitrary proposed decryptions $$m_e$$ and $$m_v$$, or is there some relationship between the proposed decryptions, the proposed pads $$p_e$$ and $$p_v$$, the true plaintext, and Alice’s actual one-time pad?

Work out a particular, concrete example: if Alice’s original cleartext message $$m$$ was aardvark, would it be possible for Eve to think the message was $$m_e=$$ iloveyou while Vev thinks it is $$m_v=$$ ihateyou? If so, give an example of what would be the corresponding ciphertext $$c$$, Alice and Bob’s one-time pad $$p_{AB}$$, the proposed decrypts $$m_e$$ and $$m_v$$, and the proposed one-time pads $$p_e$$ and $$p_v$$.

## Notes

1. Another synecdoche!