Affine transformation in AES: Matrix representation

Question

I know that the affine transformation of the AES can be represented both as a polynomial evaluation over $\operatorname{GF}(2^8)$ and as a matrix-vector multiplication (see, e.g., p.212 C.4 of The Design of Rijndael for the polynomial representation and p.36 3.9 for the matrix-vector multiplication). I would like to know how this change of representation is done. In other words: given the polynomial representation (or maybe a slightly different polynomial), how can we come up with the matrix-vector representation? Is there some algorithm for this, or is the only way to do it just by "brute-forcing" all possibilites?

Answer 1

In literature there are 2 ways to show the affine transform for a given polynomial, and that depends on the location of the MSB in the input as a polynomial.

The polynomial representation of the full transformation, in the format of the original Rijndael paper, is:

$b(x) = a(x)(x^7 + x^6 + x^5 + x^4 + 1) + (x^7 + x^6 + x^2 + x) ~~mod~~ x^8 + 1$

Where $a(x)$ is the input polynomial, and $(x^7 + x^6 + x^5 + x^4 + 1)$ is the polynomial formula of the affine matrix. $(x^7 + x^6 + x^2 + x)$ is the 'vector' constant.

The original Rijndael paper and Wikipedia use the same representation of the affine transform matrix, so we will start there.

$$ \begin{bmatrix} y_0 \\ y_1 \\ y_2 \\ y_3 \\ y_4 \\ y_5 \\ y_6 \\ y_7 \\ \end{bmatrix}= \begin{bmatrix} 1& 0& 0& 0& 1& 1& 1& 1 \\ 1& 1& 0& 0& 0& 1& 1& 1 \\ 1& 1& 1& 0& 0& 0& 1& 1 \\ 1& 1& 1& 1& 0& 0& 0& 1 \\ 1& 1& 1& 1& 1& 0& 0& 0 \\ 0& 1& 1& 1& 1& 1& 0& 0 \\ 0& 0& 1& 1& 1& 1& 1& 0 \\ 0& 0& 0& 1& 1& 1& 1& 1 \\ \end{bmatrix} \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \\ \end{bmatrix}+ \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ \end{bmatrix}$$

The rightmost column of the matrix top to bottom and the top row right to left is the start representation of the affine transform polynomial, the other rows/columns are simply rotations of the polynomial, since it is a rotational matrix. The vector constant top to bottom is the representation of the vector constant polynomial. Note $x_0$ is the LSB of the input.

The other representation is from The Design of Rijndael (page 36), to which you posted a link. You can see the matrix is the same, but rotated 180°. You can also see the input and output have their MSB locations flipped. Make note that addition and XOR in the field are the same.

$$ \begin{bmatrix} b_7 \\ b_6 \\ b_5 \\ b_4 \\ b_3 \\ b_2 \\ b_1 \\ b_0 \\ \end{bmatrix}= \begin{bmatrix} 1& 1& 1& 1& 1& 0& 0& 0 \\ 0& 1& 1& 1& 1& 1& 0& 0 \\ 0& 0& 1& 1& 1& 1& 1& 0 \\ 0& 0& 0& 1& 1& 1& 1& 1 \\ 1& 0& 0& 0& 1& 1& 1& 1 \\ 1& 1& 0& 0& 0& 1& 1& 1 \\ 1& 1& 1& 0& 0& 0& 1& 1 \\ 1& 1& 1& 1& 0& 0& 0& 1 \\ \end{bmatrix} \begin{bmatrix} a_7 \\ a_6 \\ a_5 \\ a_4 \\ a_3 \\ a_2 \\ a_1 \\ a_0 \\ \end{bmatrix}+ \begin{bmatrix} 0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ \end{bmatrix}$$

The bottom row of the matrix left to right and the first column bottom to top is the start representation of the affine transform polynomial, the other rows/columns are simply rotations of the polynomial. The vector constant bottom to top is the representation of the vector constant polynomial.