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$
  • $\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$ – Mok-Kong Shen Feb 27 '16 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 Feb 28 '16 at 8:48
  • $\begingroup$ @Aleph: Can you provide a way? Also, can you check my answer? Thanks. $\endgroup$ – vhl Feb 28 '16 at 10:29
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$
  • $\begingroup$ This method also works for conversion from matrix multiplication in $GF(2^n)$ to matrix multiplication in $GF(2)$. $\endgroup$ – vhl Feb 28 '16 at 10:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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