1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ C.4 shows the polynomial representation of the ENTIRE s-box, not of the affine transformation $\endgroup$ – Richie Frame Apr 6 '15 at 19:16
  • $\begingroup$ Ok, but how did they come up with the matrix representation of the affine transformation? $\endgroup$ – Peter Apr 6 '15 at 20:02
  • $\begingroup$ Anybody has some idea on how this transformation is done? $\endgroup$ – Peter Apr 7 '15 at 7:23
  • $\begingroup$ I am answering now, give me 20 mins $\endgroup$ – Richie Frame Apr 7 '15 at 7:32
2
$\begingroup$

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.

$\endgroup$

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.