Mathematical Cryptography

Section 1.3 A simple example: the shift cipher

The shift cipher is a cryptosystem that almost any schoolchild should be familiar with. The basic idea is to take the alphabet and shift the letters, so that A, for example, becomes represented by the letter D, B is represented by E, and so on until we get to Z represented by C. In table form,

Under this scheme, the word BAD becomes EDG, as each letter is replaced by its coded representative. To decode an encrypted text, one reads up the table, replacing the coded letters with the plaintext that each represents. Thus, the ciphertext FED becomes the plaintext CAB.

We will now take this system and represent it in mathematical form. We need the following elements.

1. A numerical representation (that is, an encoding) of the alphabet.
2. A space or domain \(\mathcal D\) in which the messages live.

3. A function, \(e\text{,}\) that will perform the encryption, with the following properties:

   1. The function depends on a key \(k\) from a keyspace \(\mathcal K\text{,}\) that is, a secret piece of information involved in the encryption.
   2. The function is one-to-one; that is, two different inputs always produce different outputs.
   3. The encryption process can be reversed; that is, we want \(e\) to be an invertible function.

(We will demand much more from our encryption functions in subsequent discussions.)

Then the function \(e(M) = M + 3\) seems to provide our encryption function, with the caveat that we need to address cases like \(e(25) = 2\text{.}\) What we want to happen is that the encrypted letters wrap back around to A once we pass Z in the table. This can be accomplished by using clock or modular arithmetic, which will be discussed in more detail in the next chapter. The basic idea is that \(a + b \pmod{26}\) is the remainder of the quotient \((a + b) / 26\text{.}\) That is, in arithmetic modulo 26, \(25 + 3 = 2\) (corresponding to Z + a shift of 3 letters = C). The set of integers \((0, \ldots, 25)\) with arithmetic modulo 26 has the representative symbol \(\mathbb Z_{26}\text{.}\)

We now have enough information to describe our cryptosystem mathematically.

• The domain \(\mathcal D\) for the messages (individual letters in this example) is \(\Z_{26}\text{.}\)
• The keyspace \(\mathcal K\) for keys is \(\Z_{26}\text{.}\)
• The specific key \(k\) for this particular system is the shift \(k = 3\text{.}\)
• The encryption function \(e\) is \(e(M) = M + 3 \pmod{26}\text{.}\)
• The decryption function \(d\) is \(d(C) = C - 3 \pmod{26}\text{.}\)