AES MixColumns

MixColumns overviewSearch on YouTubeBookmarkSaved

PurposeSearch on YouTubeBookmarkSaved

SubBytes changes each byte on its own. MixColumns makes each output byte of a column depend on all four input bytes of that column. This gives diffusion.

MixColumns works on one column of the 4 x 4 state at a time. Each full round applies it to all four columns.

The matrixSearch on YouTubeBookmarkSaved

Each column $[s_0, s_1, s_2, s_3]$ is multiplied by a fixed matrix over $GF(2^8)$:

$$\begin{pmatrix} s_0' \\ s_1' \\ s_2' \\ s_3' \end{pmatrix} = \begin{pmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{pmatrix} \begin{pmatrix} s_0 \\ s_1 \\ s_2 \\ s_3 \end{pmatrix}$$

Each row gives one equation:

$$\begin{aligned} s_0' &= 02\cdot s_0 \oplus 03\cdot s_1 \oplus 01\cdot s_2 \oplus 01\cdot s_3 \\ s_1' &= 01\cdot s_0 \oplus 02\cdot s_1 \oplus 03\cdot s_2 \oplus 01\cdot s_3 \\ s_2' &= 01\cdot s_0 \oplus 01\cdot s_1 \oplus 02\cdot s_2 \oplus 03\cdot s_3 \\ s_3' &= 03\cdot s_0 \oplus 01\cdot s_1 \oplus 01\cdot s_2 \oplus 02\cdot s_3 \end{aligned}$$

The "$\oplus$" is XOR. A multiplication by 01 does not change the byte.

GF(2^8) arithmeticSearch on YouTubeBookmarkSaved

The fieldSearch on YouTubeBookmarkSaved

All MixColumns arithmetic is in $GF(2^8)$ with the AES irreducible polynomial:

$$m(x) = x^8 + x^4 + x^3 + x + 1 = (1\,0001\,1011) = \{11B\}$$

• Each byte is a polynomial of degree 7 or less. Each bit is one coefficient.
• Addition is XOR.
• Multiplication is done modulo $m(x)$.

Multiply by 02Search on YouTubeBookmarkSaved

The byte 02 is $0000\,0010 = x$. To multiply by 02:

1. Shift the byte left by one bit.
2. If the bit that shifts out is 0, the result is complete.
3. If the bit that shifts out is 1, XOR the result with $\{11B\}$.

This rule is called xtime.

Multiply by 03Search on YouTubeBookmarkSaved

The byte 03 is $0000\,0011 = x + 1$. Thus $03 \cdot b = (02 \cdot b) \oplus b$.

Worked columnSearch on YouTubeBookmarkSaved

Input stateSearch on YouTubeBookmarkSaved

The handwritten notes use the state after ShiftRows from the AES deck:

$$\begin{pmatrix} 87 & F2 & 4D & 97 \\ 6E & 4C & 90 & EC \\ 46 & E7 & 4A & C3 \\ A6 & 8C & D8 & 95 \end{pmatrix}$$

The first column is $\{87\}, \{6E\}, \{46\}, \{A6\}$.

First byteSearch on YouTubeBookmarkSaved

$$s_0' = (02 \cdot \{87\}) \oplus (03 \cdot \{6E\}) \oplus (01 \cdot \{46\}) \oplus (01 \cdot \{A6\})$$

Other bytesSearch on YouTubeBookmarkSaved

Use the same method for the other three rows:

The intermediate products are:

• $02 \cdot \{6E\} = \{DC\}$ and $03 \cdot \{46\} = \{8C\} \oplus \{46\} = \{CA\}$.
• $02 \cdot \{46\} = \{8C\}$ and $03 \cdot \{A6\} = \{57\} \oplus \{A6\} = \{F1\}$.
• $03 \cdot \{87\} = \{15\} \oplus \{87\} = \{92\}$ and $02 \cdot \{A6\} = \{57\}$.

The full column changes from $\{87\}, \{6E\}, \{46\}, \{A6\}$ to $\{47\}, \{37\}, \{94\}, \{ED\}$. This is the first column of the MixColumns output in the AES deck.

Other viewsSearch on YouTubeBookmarkSaved

Polynomial viewSearch on YouTubeBookmarkSaved

The AES deck gives an alternative view of MixColumns. Each column is a 4-term polynomial with coefficients in $GF(2^8)$:

$$a(x) = a_3x^3 + a_2x^2 + a_1x + a_0$$

This polynomial is multiplied by a fixed polynomial modulo $x^4 + 1$:

$$c(x) = \{03\}x^3 + \{01\}x^2 + \{01\}x + \{02\}$$

The result is the same as the matrix multiplication.

Inverse MixColumnsSearch on YouTubeBookmarkSaved

Decryption uses the inverse matrix:

$$\begin{pmatrix} 0E & 0B & 0D & 09 \\ 09 & 0E & 0B & 0D \\ 0D & 09 & 0E & 0B \\ 0B & 0D & 09 & 0E \end{pmatrix}$$

The coefficients are larger. Each multiplication needs more xtime and XOR steps. Thus decryption is a little harder.

Coefficient choiceSearch on YouTubeBookmarkSaved

The AES deck says that the coefficients come from a linear code with maximal distance between codewords. The forward coefficients 01, 02 and 03 are small, so encryption is fast. A multiplication by 02 needs one xtime. A multiplication by 03 needs one xtime and one XOR.

Quick self-testSearch on YouTubeBookmarkSaved

What does MixColumns do, and why does AES need it?

It multiplies each state column by a fixed matrix over $GF(2^8)$. Each output byte then depends on all four input bytes of the column. This gives diffusion.

Write the first row of the MixColumns matrix and the $s_0'$ equation.

The row is 02 03 01 01. Thus $s_0' = 02\cdot s_0 \oplus 03\cdot s_1 \oplus s_2 \oplus s_3$.

What is xtime?

It is multiplication by 02. Shift the byte left by one bit. If the bit that shifts out is 1, XOR the result with $\{1B\}$.

Calculate $\{02\} \cdot \{87\}$.

The shift gives $1\,0000\,1110$. XOR with $1\,0001\,1011$ gives $0001\,0101 = \{15\}$.

Calculate $\{03\} \cdot \{6E\}$.

$02 \cdot \{6E\} = \{DC\}$. Then $\{DC\} \oplus \{6E\} = \{B2\}$.

Calculate $s_0'$ for the column 87, 6E, 46, A6.

$\{15\} \oplus \{B2\} \oplus \{46\} \oplus \{A6\} = \{47\}$.

Give the full output column for the input 87, 6E, 46, A6.

$\{47\}, \{37\}, \{94\}, \{ED\}$.

Which polynomial and modulus give the polynomial view of MixColumns?

Multiply the column polynomial by $c(x) = \{03\}x^3 + \{01\}x^2 + \{01\}x + \{02\}$, modulo $x^4 + 1$.

Give the inverse matrix coefficients. Why is decryption harder?

The coefficients are $\{0E\}$, $\{0B\}$, $\{0D\}$ and $\{09\}$. They are larger, so each multiplication needs more xtime and XOR steps.