AES Mix Column Transformation

Section 3.4.3 "The MixColumns Step"(page 39) of "The Design of Rijndael", it states

The columns of the state are considered as polynomials over $\operatorname{GF}(2^8)$ and multiplied modulo $x^4 + 1$ with a fixed polynomial $c(x)$.

The polynomial $c(x)$ is given by $c(x) = \mathtt{03} \cdot x^3 + \mathtt{01} \cdot x^2 + \mathtt{01} \cdot x + \mathtt{02}$

Let $b(x) \equiv c(x) \cdot a(x) \pmod{x^4 + 1}$. Then

How this polynomial multiplication modulo $x^4+1$ is converted to Matrix Multiplication?

The columns of the state are considered as polynomials over $\operatorname{GF}(2^8)$

Bytes are values in $\operatorname{GF}(2^8)$. Thus a column composed as the 4 bytes $a_0,a_1,a_2,a_3$ represent the polynomial $a_0 x^0 + a_1 x^1 + a_2 x^2 + a_3 x^3$ (notice the ordering with respect to the power!).

Now we have:

\begin{array}{cccccccccccccccc} (a_3 x^3 &+& a_2 x^2 &+& a_1 x^1 &+& a_0 x^0) &\cdot&\\ & & (\texttt{03}x^3 &+& \texttt{01}x^2 &+& \texttt{01}x^1 &+& \texttt{02}x^0) = \\ \texttt{03}a_3 x^6&+& \texttt{01}a_3 x^5 &+& \texttt{01}a_3 x^4 &+& \texttt{02}a_3 x^3 &+& \\ & & \texttt{03}a_2 x^5&+& \texttt{01}a_2 x^4 &+& \texttt{01}a_2 x^3 &+& \texttt{02}a_2 x^2 &+& \\ & & & & \texttt{03}a_1 x^4&+& \texttt{01}a_1 x^3 &+& \texttt{01}a_1 x^2 &+& \texttt{02}a_1 x^1 &+& \\ & & & & & & \texttt{03}a_0 x^3&+& \texttt{01}a_0 x^2 &+& \texttt{01}a_0 x^1 &+& \texttt{02}a_0 x^0) \end{array}

If we apply $\mod (x^4 + 1)\$ we have: \begin{array}{cccccccccccccccc} (a_3 x^3 &+& a_2 x^2 &+& a_1 x^1 &+& a_0 x^0) &\cdot&\\ & & (\texttt{03}x^3 &+& \texttt{01}x^2 &+& \texttt{01}x^1 &+& \texttt{02}x^0) = \\ \texttt{02}a_3 x^3 &+& \texttt{03}a_3 x^2 &+& \texttt{01}a_3 x^1 &+& \texttt{01}a_3 x^0 &+& \\ \texttt{01}a_2 x^3 &+& \texttt{02}a_2 x^2 &+& \texttt{03}a_2 x^1 &+& \texttt{01}a_2 x^0 &+& \\ \texttt{01}a_1 x^3 &+& \texttt{01}a_1 x^2 &+& \texttt{02}a_1 x^1 &+& \texttt{03}a_1 x^0 &+& \\ \texttt{03}a_0 x^3 &+& \texttt{01}a_0 x^2 &+& \texttt{01}a_0 x^1 &+& \texttt{02}a_0 x^0 &= \\ b_3 x^3 &+& b_2 x^2 &+& b_1 x^1 &+& b_0 x^0 \end{array}

\begin{array}{cccccccccccccccc} b_3 = \texttt{02}a_3 + \texttt{01}a_2 + \texttt{01}a_1 + \texttt{03}a_0\\ b_2 = \texttt{03}a_3 + \texttt{02}a_2 + \texttt{01}a_1 + \texttt{01}a_0\\ b_1 = \texttt{01}a_3 + \texttt{03}a_2 + \texttt{02}a_1 + \texttt{01}a_0\\ b_0 = \texttt{01}a_3 + \texttt{01}a_2 + \texttt{03}a_1 + \texttt{02}a_0\\ \end{array}

by reordering over $b$:

\begin{array}{cccccccccccccccc} b_0 = \texttt{01}a_3 + \texttt{01}a_2 + \texttt{03}a_1 + \texttt{02}a_0\\ b_1 = \texttt{01}a_3 + \texttt{03}a_2 + \texttt{02}a_1 + \texttt{01}a_0\\ b_2 = \texttt{03}a_3 + \texttt{02}a_2 + \texttt{01}a_1 + \texttt{01}a_0\\ b_3 = \texttt{02}a_3 + \texttt{01}a_2 + \texttt{01}a_1 + \texttt{03}a_0\\ \end{array}

by reordering over $a$:

\begin{array}{cccccccccccccccc} b_0 = \texttt{02}a_0 + \texttt{03}a_1 + \texttt{01}a_2 + \texttt{01}a_3\\ b_1 = \texttt{01}a_0 + \texttt{02}a_1 + \texttt{03}a_2 + \texttt{01}a_3\\ b_2 = \texttt{01}a_0 + \texttt{01}a_1 + \texttt{02}a_2 + \texttt{03}a_3\\ b_3 = \texttt{03}a_0 + \texttt{01}a_1 + \texttt{01}a_2 + \texttt{02}a_3\\ \end{array}

Which is exactly the matrix multiplication:

\begin{array}{cccccccccccccccc} \begin{bmatrix} b_0\\ b_1\\ b_2\\ b_3 \end{bmatrix} = \begin{bmatrix} \texttt{02} & \texttt{03} & \texttt{01}& \texttt{01}\\ \texttt{01} & \texttt{02} & \texttt{03}& \texttt{01}\\ \texttt{01} & \texttt{01} & \texttt{02}& \texttt{03}\\ \texttt{03} & \texttt{01} & \texttt{01}& \texttt{02} \end{bmatrix} \times \begin{bmatrix} a_0\\ a_1\\ a_2\\ a_3 \end{bmatrix} \end{array}

• @Raza if the answer satisfies you, you can accept it. ;)
– Biv
Sep 12, 2017 at 9:11
• accepted. I upvoted it yesterday but forgot to accept it. :) Sep 12, 2017 at 11:48