Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
How do you invert any matrix? E.g. row operations (xor). That's mathematics, though. –  otus Jun 15 at 15:47
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.