How to calculate inverse affine transform in AES from forward affine transform?

Question

In AES the forward affine tranformation matrix is defined as:

$$ \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}$$

and the inverse affine transformation matrix is defined as:

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

How is the inverse affine transformation derived from the forward affine transformation?

Answer 1

The affine transformation is defined as a degree 7 polynomial multiplication modulo $x^8 + 1$.

In the format of the question, the terms are the right hand column, top to bottom.
$A = x^7 + x^6 + x^5 + x^4 + 1$, and $B = x^7 + x^5 + x^2$.

The inverse can be determined through several methods. Since there are only 254 valid polynomials (omitting 0 and 1), you can just multiply them together until you get 1. Additionally, they happen to be cubes of eachother:

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

This is because of the period of the affine transformation, which happens to be 4. The period is how many times you need to perform the transformation to arrive at the original input. Any affine transformation in $GF(2^8)$ will have a period of $2^0$ through $2^4$ in succeessive powers of 2, or {1,2,4,8,16}.

Therefore, since $A^4 = A^0$, $A^{4-1} = A^3 = A^{-1}$, and since $A^3 = B$, $B = A^{-1}$