CONVENTIONAL ENCRYPTION TECHNIQUES: SOME MATHEMATICS

MATH 195

Some Notation

Consider the set up given in Figure 2.2 (p. 23) in the course text. We will use the following notation. Let P be the set from which the plaintext message is taken (e.g., the letters {A, …, Z}). Let C be the set from which the ciphertext is taken—sometimes we will have P = C, as we shall see in the examples below, but this restriction is not necessary. Let K be the set of all possible keys.

Mathematically, encryption is a function (or map)

E : K × P → C
(K, X) ↦ E_{K}(X)

The set on the right is the Cartesian product of the sets K and P; an element of the product consists of an ordered pair of elements, one from each of the sets. Thus E eats a key K and plaintext X and spits out ciphertext E_{K}(X).

Likewise, decryption is a map

D : K × C → P
(K, Y) ↦ D_{K}(Y)

Now D eats a key and ciphertext and spits out plaintext.

In order for these functions E and D to make any sense, we would like decryption to return the correct plaintext. Therefore we insist that the functions D and E satisfy the following axiom:

Axiom. ∀X ∈ P, ∀K ∈ K, D_{K}(E_{K}(X)) = X. Equivalently, ∀K ∈ K, D_{K} ∘ E_{K} = id_{P}. □

In words, this says that for all X ∈ P and for all K ∈ K, we have D_{K}(E_{K}(X)) = X. This says nothing than encrypting and decrypting in succession gives us the original plaintext back. The second statement says that the composition of the two maps

P ⟶^{E_{K}} C ⟶^{D_{K}} P

is the identity map, which is exactly the statement that decrpytion undoes the encryption.

This is some of the material covered on Thursday, January 24, in Math 195: Cryptography, taught by Hendrik Lenstra, prepared by John Voight jvoight@math.berkeley.edu.

Caesar Cipher

The Caesar Cipher is explained in §2.3, p. 29. Here, we take P = {A, B, …, Z}, C = P, and K = {0, 1, …, 25}. The encryption function we write as

E_{K}(α) = α + K,

where we think of this arithmetic modulo 26, which we write by giving K the ring structure K = ℤ/26ℤ. For a review of modular arithmetic, you might consult §7.2 of the text. For now, it is enough to know that addition and multiplication are performed exactly the same, but we care only what remainder is left over after dividing by 26. For example,

17 + 18 = 35 = 26 + 9 ≡ 9 (mod 26)

and

17 · 18 = −9 · −8 = 72 ≡ 20 (mod 26).

Note that in order to satisfy the axiom (that decryption is inverse to encryption), we must have D_{K} = α − K, which we can also write D_{K} = E_{−K}.

Monoalphabetic Cipher

The monoalphabetic cipher is explained in §2.3, p. 31. Here, again P = {A, B, …, Z} and

K = Sym P = {σ : P → P, σ bijective}.

Recall: a map f : S → T is injective (or one-to-one, we write f : S ↪ T) if

∀t ∈ T, #{s ∈ S : f(s) = t} ≤ 1.

This says that the number of preimages of every element t ∈ T is at most one. The map f is surjective (or onto, we write f : S ↠ T) if

∀t ∈ T, #{s ∈ S : f(s) = t} ≥ 1.

This means that every element of T has at least one preimage. If f is both injective and surjective, then we say that f is bijective. For example, the map f : ℝ → ℝ by x ↦ x^{2} is neither injective nor surjective; it is surjective, though, if we restrict the image set to the nonnegative real numbers.

If S and T are finite (and have the same number of elements), then a map f : S → T is injective if and only if it is surjective if and only if it is bijective. A map f : S → T is bijective if and only if there is a map f^{−1} : T → S such that f ∘ f^{−1} = id_{T}, f^{−1} ∘ f = id_{S}. In this case, f^{−1}(t) is the unique s ∈ S such that f(s) = t.

Therefore, K consists of all bijections from the finite set P to itself; this is a set with 26! elements, since there are 26 possibilities for the image of A, 25 for B, and so on. How large is this number? Well,

26! = 403291461126605635584000000 ≈ 4 × 10^{26}.

We can also approximate this number using Stirling’s formula, which states that

n! ∼ \frac{n^{n}}{e^{n}} \sqrt{2πn}

where this statement says that

lim_{n→∞} \frac{n!}{(n^{n}/e^{n})\sqrt{2πn}} = 1.

Returning to our cipher, we see that E_{σ}(α) = σ(α), and hence D_{σ}(α) = σ^{−1}(α), where σ^{−1} is the inverse map constructed above. Therefore D_{σ} = E_{σ^{−1}}.

[If you need to review the material on functions and sets, it is ordinarily covered in the Discrete Mathematics course (Math 55) at Berkeley. The text for the course this semester is Kenneth Rosen, Discrete Mathematics and Its Applications, and this material is treated in §1.6. Of course, any such a text will do, such as one for an introduction to higher mathematics course or the text for Abstract Algebra (Math 113), e.g. Fraleigh, A First Course in Abstract Algebra, covered in Chapter A. You might want to keep such a text handy throughout the semester.]