DES: THE FEISTEL CIPHER

MATH 195

The Hill cipher allows us to create large invertible maps by specifying only a small amount of data (the key). However, the linearity in the cipher is its downfall: it is too easy for the eavesdropper to collect enough data and discover the key.

The central mathematical idea behind the Feistel cipher is to take random maps (which may or may not be invertible) and turning them into invertible maps. For example, for any matrix A ∈ M(k, R), we can find a larger matrix which is invertible:

(\begin{matrix}I & 0 \\ A & I \end{matrix}) ∈ GL(2k, R).

In fact, the inverse is

(\begin{matrix}I & 0 \\ −A & I \end{matrix}) .

Let V be a group, written additively. Think of V as a vector space of k bits, e.g. V = (ℤ/2ℤ)^{k}. Let g : V → V be any map. (This gives us many options: the number of elements is (#V)^{#V} = 2^{k2^{k}}. Typically, k = 4 or k = 32, which give us huge numbers!) Define

G : V × V → V × V
G(x, y) = (x, g(x) + y),

e.g. if A was the above matrix, we would have

(\begin{matrix}I & 0 \\ A & I \end{matrix}) (\begin{matrix}x \\ y \end{matrix}) = (\begin{matrix}x \\ Ax + y \end{matrix}) .

Claim. G is bijective.

Proof. Define h : V → V by h(x) = −g(x). (Note: if V = (ℤ/2ℤ)^{k}, then h = g.) h gives rise to H : V × V → V × V, H(x, y) = (x, h(x) + y) = (x, −g(x) + y).

We now calculate H ∘ G = id_{V ×V}:

(H ∘ G)(x, y) = H(G(x, y)) = H(x, g(x) + y) = (x, h(x) + (g(x) + y))
= (x, −g(x) + g(x) + y) = (x, y).

In the same way, G ∘ H = id_{V ×V}. Therefore G is bijective. □

Note: For V = (ℤ/2ℤ)^{k}, H = G so G^{2} = G ∘ G = id_{V ×V}.

Example. Let V = ℤ/5ℤ, so V × V = (ℤ/5ℤ)^{2}, a set of 25 elements, the alphabet if we do not use the letter J.

Define g : ℤ/5ℤ → ℤ/5ℤ by g(0) = 3, g(1) = 1, g(2) = 4, g(3) = 1, g(4) = 0. If x = 3, since g(3) = 1, we have G(3, y) = (3, g(3) + y) = (3, y + 1), so everything in this “column” is increased by 1. Likewise, g(2) = 4, so G(4, y) = (4, y + 4) so we “shift” by 4.

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

Notice that every other block is unchanged by G (it is unencrypted!), so we need to do better. Therefore: use your key K to produce t functions g_{1}, …, g_{t} : V → V (usually t = 2 or t = 16), where V = (ℤ/2ℤ)^{k}. These give rise to t bijections G_{1}, …, G_{t} : V × V → V × V with V × V = (ℤ/2ℤ)^{2k} = P = C. Now

E_{K} : V × V → V × V

is defined by

E_{K} = G_{t} ∘ s ∘ ⋯ ∘ G_{2} ∘ s ∘ G_{1},

with s(x, y) = (y, x) the “swap”.

Note that D_{K} = E_{K}^{−1} = G_{1} ∘ s ∘ ⋯ ∘ s ∘ G_{t}.

We would also like our cryptosystem to be secure, which means we must make sure that any statistical probabilities in the English language are erased when we garble the message.

So what is the key space K and how does an element K ∈ K produce t functions g_{1}, …, g_{t}? Let K = (ℤ/2ℤ)^{10 or 56}, and S = (ℤ/2ℤ)^{8 or 48} be the space of subkeys. Each K ∈ K produces t subkeys K_{1}, …, K_{t} ∈ S. Next there is a round function F : V × S → V given once and for all which uses S-boxes, and now g_{i} : V → V are defined by g_{i}(x) = F (x, K_{i}).