2
$\begingroup$

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)$?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Commented Feb 27, 2016 at 9:39
  • $\begingroup$ 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)$. $\endgroup$
    – Aleph
    Commented Feb 28, 2016 at 8:48
  • $\begingroup$ @Aleph: Can you provide a way? Also, can you check my answer? Thanks. $\endgroup$
    – vhl
    Commented Feb 28, 2016 at 10:29

1 Answer 1

2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.