How can I get the binary form of AES's MDS matrix in MixColumns tranformation?

Question

I need to write a procedure for calculating the MixColumns's operation result in the following form:

$M*X^T,$

where $M$ is a 128x128 binary matrix, $X$ is a 128-bit vector (the state).

My question is how to build such $M$ matrix.

Help much appreciated. Thanks!

EDIT:

As far as I understand, the MixColumns transformation can be represented as

$\begin{pmatrix}MDS & 0 & 0 & 0\\0 & MDS & 0 & 0\\0 & 0 & MDS & 0\\0 & 0 & 0 & MDS\end{pmatrix} * \begin{pmatrix}s_0\\s_1\\\vdots\\s_{15}\end{pmatrix},$

where $MDS = \begin{pmatrix}02 & 03 & 01 & 01\\01 & 02 & 03 & 01\\01 & 01 & 02 & 03\\03 & 01 & 01 & 02\end{pmatrix} - $ matrix with elements over $GF(2^8)$ and

$s_0, \dots, s_{15} \in \overline{0, 255} - $ elements of the state.

I need a hint how to convert each element of the $MDS$ matrix into a 8x8 binary matrix over $GF(2)$. For example, I guess that the element $01$ would be converted into the 8x8 identity matrix.

Is that correct?

Answer 1

Here is a Sage code that creates the MDS matrix over $F_2$.

mds = matrix(GF(2), [
    [0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0],
    [0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0],
    [0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0],
    [1,0,0,0,1,0,0,0,1,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0],
    [1,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0],
    [0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0],
    [1,0,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0],
    [1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0],
    [0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0],
    [0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0],
    [0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0],
    [0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0],
    [0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0],
    [0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0],
    [0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0],
    [0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0],
    [0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0],
    [0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,1,1,0,0,0],
    [0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,0,0,0,1,1,0,0],
    [0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0],
    [0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,1,1],
    [0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1],
    [1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0],
    [0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0],
    [0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0],
    [1,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,1,0,0,0],
    [1,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0],
    [0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0],
    [1,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,1],
    [1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0],
])

Answer 2

This question can be used to get what you want.

There we use bytes (so expand those to bits) and you have to use extra XOR's (i.e. binary additions) to get the field multiplications.

Answer 3

Concretely, given an element $x \in$ GF($2^8$), to multiply it by 2, we simply do a left shift and xor with 0b100011011 if the result of the shift gets above 0b11111111 (255). To multiply by 3, we multiply by 2 and add the input.

Those two multiplications can be described with 8x8 binary matrices. The easiest way to find the matrices is to think how those operations would be implemented in hardware. Well, there is an efficient way to do it. Given a 8 bit inputs, $y_0 y_1 y_2 y_3 y_4 y_5 y_6 y_7$, first store $y_0$, do a left shift, and xor the result with (0b00011011 $\cdot \ y_0$). And the multiplication by 3 is simply a multiplication by two xored with the input.

Those multiplications by 2 and 3 are described by the following binary matrices :

$M_{mul2}$:

\begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{bmatrix}

$M_{mul3}$ (which is $M_{mul2} \oplus M_{identity}$):

\begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{bmatrix}

Actually, from $M_{mul2}$ and $M_{identity}$ you can construct all the matrices of for the multiplication in the AES field by combining them with a double and add algorithm.

From this, you can construct the 32x32 binary matrice of the the MixColumns operation (here 1 is $M_{indentity}$) :

\begin{bmatrix} M_{mul2} & M_{mul3} & 1 & 1\\ 1 & M_{mul2} & M_{mul3} & 1\\ 1 & 1 & M_{mul2} & M_{mul3}\\ M_{mul3} & 1 & 1 & M_{mul2}\\ \end{bmatrix}

and you can deduce the rest (as well as how to do the same for decryption).