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

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?

• How do you invert any matrix? E.g. row operations (xor). That's mathematics, though.
– otus
Jun 15 '14 at 15:47

The affine transformation is defined as a degree 7 polynomial multiplication modulo $x^8 + 1$.
$A = x^7 + x^6 + x^5 + x^4 + 1$, and $B = x^7 + x^5 + x^2$.
$$(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}$