RIJNDAEL CIPHER (CONTINUED): DISCUSSION

MATH 195

First, we discuss the map M. Recall that we define the map

M : 𝔽_{256}^{4} → 𝔽_{256}^{4}
M(g) ≡ c · g (mod Y^{4} + 1).

where we identify the word space 𝔽_{256}^{4} with the set of polynomials

𝔽_{256}^{4} = {g ∈ 𝔽_{256}[Y] : deg g < 4}
(a_{0}, a_{1}, a_{2}, a_{3}) = a_{0} + a_{1}Y + a_{2}Y^{2} + a_{3}Y^{3}.

Here we let c ∈ 𝔽_{256}^{4} be

c = (X, 1, 1, X + 1) = X + Y + Y^{2} + (X + 1)Y^{3},

where

𝔽_{256} = 𝔽_{2}[X]/(X^{8} + X^{4} + X^{3} + X + 1).

M has the desirable properties of efficiency and diffusion. Writing this map out, we have

c · g ≡ (∑_{i=0}^{3} c_{i}Y^{i}) (∑_{j=0}^{3} a_{j}Y^{j}) (mod Y^{4} + 1)

which is

∑_{ℓ=0}^{3} ( ∑_{i+j≡ℓ mod 4} c_{i}a_{j}) Y^{ℓ}.

We want this multiplication to be efficient, so we want to pick the coefficients so that this multiplication is easy: hence we require that they (as polynomials in X) be linear. Then we have

X (∑_{i=0}^{7} b_{i}X^{i}) = ∑_{i=0}^{7} b_{i}X^{i+1} = ∑_{j=1}^{7} b_{j−1}X^{j} + b_{7}(X^{4} + X^{3} + X + 1).

Part of the secret of this choice of c, then, is that not only do the coefficients have low degree, but the sum of the coefficients is

X + 1 + 1 + (X + 1) = 1.

It is a homework problem to investigate the consequences of this magical condition.

The diffusion requirement can be put as follows: if w and w′ are two words differing in just one byte, then M(w) and M(w′) differ in all four bytes. Similarly, if w and w′ differ in two, three, or four bytes, respectively, then M(w) and M(w′) differ in at least three, at least two, or at least one byte, respectively.

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

Definition. If w, w′ are two words, then the Hamming distance d(w, w′) is the number of js such that the jth byte of w is not equal to the jth byte of w′.

The Hamming weight W (w) = d(w, 0), i.e. d(w, w′) = W (w+w′) (we are dealing with bytes). W (w) is the number of nonzero bytes of w.

We see that d(w, w′′) ≤ d(w, w′)+d(w′, w′′), d(w, w′) = d(w′, w), and d(w, w′) = 0 if and only if w = w′. We require for Rijndael that for all w ≠ w′,

d(w, w′) + d(M(w), M(w′)) ≥ 5.

Equivalently, for all v = w + w′ ≠ 0, we insist that

W (w+w′)+W (M(w)+M(w′)) = W (w+w′)+W (M(w+w′)) = W (v)+W (M(v)) ≥ 5.

Theorem. Let

c = c_{0} + c_{1}Y + c_{2}Y^{2} + c_{3}Y^{3} ∈ (𝔽_{256}[Y]/(Y^{4} + 1))^{∗}

have inverse d = d_{0} + d_{1}Y + d_{2}Y^{2} + d_{3}Y^{3}. Define

M : (𝔽_{256}[Y]/(Y^{4} + 1))^{∗} → (𝔽_{256}[Y]/(Y^{4} + 1))^{∗}

by M(g) = c · g. Then M satisfies the condition

W (v) + W (M(v)) ≥ 5

for all v ≠ 0 if and only if the following conditions are satisfied:

(i) all c_{i} ≠ 0; (ii) the elements c_{1}/c_{0}, c_{2}/c_{1}, c_{3}/c_{2}, c_{0}/c_{3} of 𝔽_{256} are pairwise distinct; (iii) the elements c_{2}/c_{0}, c_{3}/c_{1}, c_{0}/c_{2}, c_{1}/c_{3} of 𝔽_{256} are pairwise distinct; (iv) the same conditions are true for c_{j} replaced by d_{j}.

This theorem is not deep. It imposes certain limitations on your coefficients which are satisfied by the Rijndael cipher!