# How to perform AES MixColumns as matrix multiplication in GF(2) (boolean values)?

AES MixColumns is done by multiplying a $4 \times 4$ matrix and a column of the AES state (a vector). Addition and multiplication are done in $\operatorname{GF}(2^8)$.

In the paper White-box AES, the authors use $32 \times 32$ matrix $\mathit{MC}$ times a $32 \times 1$ vector over $\operatorname{GF}(2)$.

My question is how this $32 \times 32$ matrix is constructed? Or more generally, how matrix multiplication in $\operatorname{GF}(2^8)$ is mapped to multiplication in $\operatorname{GF}(2)$?

• If I don't err, GF is unique only up to isomorphism. As layman in math I am afraid that the conversion you mentioned could be fairly specific for the case of AES and thus not "general". I suggest that you also post to the subcommunity "mathematics" with an appropriate formulation. Feb 27, 2016 at 9:39
• There are several ways to construct the matrix, depending on the basis that is used for the extension field $\text{GF}(2^8) / \text{GF}(2)$. Feb 28, 2016 at 8:48
• @Aleph: Can you provide a way? Also, can you check my answer? Thanks.
– vhl
Feb 28, 2016 at 10:29

Assume that we have to compute $M\times x$, where $M$ is a $n\times n$ matrix, and $x$ is a $n\times 1$ vector, all entries of $M$ and $x$ are in $GF(2^8)$.

We have:

$$M\times x = M \times \left( \begin{matrix} x_0 \\ x_1 \\ \vdots \\x_{n-1}\end{matrix}\right) = M \times \left( \begin{matrix} x_0 \\ 0\\ \vdots \\ 0\end{matrix}\right) \oplus M \times \left( \begin{matrix} 0 \\ x_1 \\ \vdots \\ 0\end{matrix}\right) \oplus M \times \left( \begin{matrix} 0 \\ 0 \\ \vdots \\x_{n-1}\end{matrix}\right)$$

Write each $x_i$ in polynomial format: $x_i = x_{i, 0} x^0 + x_{i, 1} x ^ 1 + \ldots x_{i, 7} x ^ 7, x_{i,j} \in \lbrace 0, 1 \rbrace$, which is equivalent to binary form: $x_i = x_{i,0}x_{i,1}\ldots x_{i,7}$ (little endian notation). We have:

$$M \times \left( \begin{matrix} 0 \\ \vdots \\ x_i \\ \vdots \\ 0\end{matrix}\right) = M \times \left( \begin{matrix} 0 \\ \vdots \\ \left(\begin{matrix} x_{i, 0} \\ \vdots \\ x_{i,7} \end{matrix} \right) \\ \vdots \\ 0\end{matrix}\right) \\ = M \times \left( \begin{matrix} 0 \\ \vdots \\ \left(\begin{matrix} x_{i, 0} \\ 0 \\ \vdots \\ 0 \end{matrix} \right) \\ \vdots \\ 0\end{matrix}\right) \oplus M \times \left( \begin{matrix} 0 \\ \vdots \\ \left(\begin{matrix} 0 \\ x_{i,1} \\ \vdots \\ 0 \end{matrix} \right) \\ \vdots \\ 0\end{matrix}\right) \oplus \ldots \oplus M \times \left( \begin{matrix} 0 \\ \vdots \\ \left(\begin{matrix} 0 \\ 0 \\ \vdots \\ x_{i,7} \end{matrix} \right) \\ \vdots \\ 0\end{matrix}\right)$$ (Note that $\left(0, , \ldots x_{i,j} \ldots, 0 \right)^T$ is still interpreted as a byte.)

Now, as $x_{i,j} \in \{0, 1\}$, we can check that: $$M \times \left( \begin{matrix} 0 \\ \vdots \\ \left(\begin{matrix} 0 \\ \vdots \\ x_{i,j} \\ \vdots \\ 0 \end{matrix} \right) \\ \vdots \\ 0\end{matrix}\right) = x_{i, j} \times M \times \left( \begin{matrix} 0 \\ \vdots \\ \left(\begin{matrix} 0 \\ \vdots \\ 1 \\ \vdots \\ 0 \end{matrix} \right) \\ \vdots \\ 0\end{matrix}\right) = x_{i, j} \times V_{i,j}$$

Hence: $$M \times x = \bigoplus_{0\leq i \leq n, 0\leq j \leq 7} x_{i, j} V_{i, j}$$ $V_{i,j}$ is a $n\times 1$ vector, its entries are in $GF(2^8)$. We can check that writing $V_{i, j}$ in $8n\times 1$ binary format (let's call that $V'_{i,j}$) does not change the result. So we have: $$M \times x \mbox{ is equivalent to } \bigoplus_{0\leq i \leq n, 0\leq j \leq 7} x_{i, j} V'_{i, j} \\ = (V'_{0, 0}|| V'_{0, 1} || \ldots || V'_{n, 7}) (x_{0, 0}, x_{0, 1}, \ldots x_{n, 7})^T$$ Let $MC = (V'_{0, 0}|| V'_{0, 1} || \ldots || V'_{n, 7})$, which is a $8n\times 8n$ matrix formed from $8n\times 1$ vectors, we have: $$M \times x \mbox{ is equivalent to } MC \times (x_{0, 0}, x_{0, 1}, \ldots x_{n, 7})^T$$

Thus, we have transformed a matrix multiplication in $GF(2^8)$ to matrix multiplication in $GF(2)$.

Thanks my supervisor for this answer.

• This method also works for conversion from matrix multiplication in $GF(2^n)$ to matrix multiplication in $GF(2)$.
– vhl
Feb 28, 2016 at 10:31