4
$\begingroup$

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?

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

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

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