RIJNDAEL CIPHER

MATH 195

For any cryptographic system, we need to define encryption and decryption functions

E, D : K × P → C
E : (k, x) ↦ E_{k}(x)
D : (k, x) ↦ D_{k}(x)

such that D_{k}E_{k} = id_{P}, so that these are inverse to each other. Recall K is the key space, P is the plaintext message space, and C is the ciphertext message space.

We take P = C equal to the state space S = 𝔽_{2}^{32N_{b}}, where

N_{b} = {4, 6, 8},

and we shall take N_{b} = 4 so that S = 𝔽_{2}^{128}. This is to say, S is a 128-dimensional vector space over 𝔽_{2}, or put another way, it consists of bit strings of length 128. Similarly, the key space is 𝔽_{2}^{32N_{k}} where N_{k} ∈ {4, 6, 8}; we will take N_{k} = 4 as well.

The letters τ_{s}, σ, β, μ are permutations of S from which E_{k} and D_{k} are built up. For each s ∈ S, the function

τ_{s} : S → S

is defined by

τ_{s}(x) = x + s;

hence τ_{s} is ‘translation by s’, called the AddRoundKey transformation.

A state (an element of S) is pictured as a 4×N_{b} matrix with entries that consist of 1 byte (8 bits) each, e.g.

(\begin{matrix}01010010 & 01001100 & 10101011 & 01110010 \\ 01010101 & 11010101 & 11111111 & 00110100 \\ 11011010 & 10110101 & 11010001 & 10111011 \\ 10111010 & 10111101 & 01110110 & 00000001 \end{matrix})

where we read the bytes from top to bottom, then left to right:

01010010 01010101 11011010 … 10111011 00000001

in the above example. (Recall N_{b} = 4.) The set of all bytes is 𝔽_{2}^{8}, and it is identified with the field

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

by identifying (b_{7}b_{6} … b_{1}b_{0}) with the polynomial

b_{7}X^{7} + b_{6}X^{6} + ⋯ + b_{1}X + b_{0} ∈ 𝔽_{256}.

This gives us a multiplication on 8 bit strings. Therefore S is now the set of 4 × 4 matrices with entries from 𝔽_{256}.

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

The map β : S → S is called the ByteSub transformation, and it is defined by

β (\begin{matrix}a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,0} & a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,0} & a_{3,1} & a_{3,2} & a_{3,3} \end{matrix}) = (\begin{matrix}B(a_{0,0}) & … & B(a_{0,3}) \\ ⋮ & ... & ⋮ \\ B(a_{3,0}) & … & B(a_{3,3}) \end{matrix}) .

where B : 𝔽_{256} → 𝔽_{256} is some dreadful permutation to be defined later.

The map σ : S → S is the ShiftRow transformation: σ shifts the ith row (i = 0, 1, 2, 3) cyclically by i positions to the left:

σ (\begin{matrix}a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} \\ a_{1,0} & a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,0} & a_{2,1} & a_{2,2} & a_{2,3} \\ a_{3,0} & a_{3,1} & a_{3,2} & a_{3,3} \end{matrix}) = (\begin{matrix}a_{0,0} & a_{0,1} & a_{0,2} & a_{0,3} \\ a_{1,1} & a_{1,2} & a_{1,3} & a_{1,0} \\ a_{2,2} & a_{2,3} & a_{2,0} & a_{2,1} \\ a_{3,3} & a_{3,0} & a_{3,1} & a_{3,2} \end{matrix}) .

In other words,

σ((a_{i,j}))_{i,j=0,...,3}) = (a_{i,i+j mod 4})_{i,j=0,...,3}.

The map μ : S → S is the MixColumn operation defined by

μ (\begin{matrix}| & | & | & | \\ a_{0} & a_{1} & a_{2} & a_{3} \\ | & | & | & | \end{matrix}) = (\begin{matrix}| & | & | & | \\ Ma_{0} & Ma_{1} & Ma_{2} & Ma_{3} \\ | & | & | & | \end{matrix})

where a_{i} are vectors, a_{i} ∈ 𝔽_{256}^{4}, and where M : 𝔽_{256}^{4} → 𝔽_{256}^{4} is a linear map (over 𝔽_{256}, so M can be given by a 4 × 4 matrix with coefficients from 𝔽_{256}).

The definition of M: identify 𝔽_{256}^{4} (the word space: 1 byte is 8 bits, 1 word is 4 bytes, 1 state is N_{b} words) with 𝔽_{256}[Y]/(Y^{4} +1). The elements of 𝔽_{256}[Y]/(Y^{4} +1) are represented by polynomials b_{3}Y^{3} + b_{2}Y^{2} + b_{1}Y + b_{0}, where b_{i} ∈ 𝔽_{256}. Define

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

by

M(w) = c · w (mod Y^{4} + 1)

where

c = 03Y^{3} + 01Y^{2} + 01Y + 02 ∈ 𝔽_{256}[Y]/(Y^{4} + 1)

where 03 = 00000011 = X + 1 in 𝔽_{256}, and similarly 01 = 00000001 = 1 ∈ 𝔽_{256}, 02 = 00000010 = X ∈ 𝔽_{256}.

Note that c(1) = 1, so since Y^{4} + 1 = 0, c^{4} = 1.

The key space K = S. Key expansion transforms a given key k ∈ K into a sequence k_{0}(= k), k_{1}, …, k_{10} “round key” that belong to S, to be explained.

The formula for E_{k}, given as maps, is:

E_{k} = τ_{k_{10}}σβτ_{k_{9}}μσβ … τ_{k_{2}}μσβτ_{k_{1}}μσβτ_{k_{0}}.

Notice that we do not have a final application of μ: since μ is a known map, the additional application would be wasteful, as μ and τ commute (μτ_{s} = τ_{μ(s)}μ) any cryptanalyst could easily undo this map.

To decrypt, we apply the inverse of these maps in the opposite order, using commutation relations:

D_{k} = E_{k}^{−1} = τ_{k_{0}}σ^{−1}β^{−1}τ_{μ^{−1}(k_{1})}μ^{−1}σ^{−1}β^{−1}τ_{μ^{−1}(k_{2})}μ^{−1} … τ_{μ^{−1}(k_{9})}μ^{−1}σ^{−1}β^{−1}τ_{k_{10}}.

Note that there would be asymmetry in the application of the maps if we applied an additional μ to conclude E_{k}, as we would then have to apply μ^{−1} at the beginning of D_{k}.

There are two maps still left to define. First, we define A : {f ∈ 𝔽_{2}[X] : deg f < 8} to itself by

A(f) ≡ (X^{4} + X^{3} + X^{2} + X + 1)f + (X^{6} + X^{5} + X + 1) (mod X^{8} + 1).

Note that in 𝔽_{2}[X], X^{8} + 1 is not irreducible, so 𝔽_{2}[X]/(X^{8} + 1) is not a field! Indeed, by the freshperson’s dream X^{8} + 1 = (X + 1)^{8}. (We say ‘A’ for affine, since it is a homomorphism followed by a translation.)

In fact, A^{4} is the identity map, A^{−1} = A^{3}, and

A^{−1}(f) ≡ (X^{6} + X^{3} + X)f + (X^{2} + 1) (mod X^{8} + 1).

Define B : 𝔽_{256} → 𝔽_{256} by

B(a) = \begin{cases}A(a^{−1}), & a ≠ 0, a^{−1} computed in 𝔽_{256}; \\ A(0), & a = 0. \end{cases}

Note: B(a) = A(a^{254}), where a^{254} is computed in 𝔽_{256}, and B is the composition of A and the ‘inversion’ map. This is the only nonlinear ingredient in the entire scheme.

Finally, we must give key expansion: Given a key k ∈ K = S, we produce 11 round keys k_{0}, …, k_{10} ∈ S. Write

k = (\begin{matrix}| & | & | & | \\ w_{0} & w_{1} & w_{2} & w_{3} \\ | & | & | & | \end{matrix})

We expand k into

k = (\begin{matrix}| & | & | & | & & | & | & | \\ w_{0} & w_{1} & w_{2} & w_{3} & … & w_{41} & w_{42} & w_{43} \\ | & | & | & | & & | & | & | \end{matrix})

so that

k_{i} = (\begin{matrix}| & | & | & | \\ w_{4i} & w_{4i+1} & w_{4i+2} & w_{4i+3} \\ | & | & | & | \end{matrix})

where

w_{j} = \begin{cases}w_{j−1} + w_{j−4}, & j ≢ 0 (mod 4), \\ γ(w_{j−1}) + w_{j−4}, & j ≡ 0 (mod 4), \end{cases}

and

γ (\begin{matrix}a \\ b \\ c \\ d \end{matrix}) = (\begin{matrix}B(b) \\ B(c) \\ B(d) \\ B(a) \end{matrix}) + (\begin{matrix}X^{(j−4)/4} mod m(X) \\ 0 \\ 0 \\ 0 \end{matrix})

and m(X) = X^{8} + X^{4} + X^{3} + X + 1.

In fact, B : 𝔽_{256} → 𝔽_{256} for all a ∈ 𝔽_{256} one has

B(a) = 63 + 8fa^{127} + b5a^{191} + 01a^{223} + f4a^{239} + 25a^{247} + f9a^{251} + 09a^{253} + 05a^{254}

where the coefficients are written in hexadecimal (e.g. 63=01100011). Note that this has all 9 terms (there is no easy algebraic relation).