The Rijndael specification details the design choices for the s-box in section 7.2. They describe the choice of affine mapping as follows:
We have chosen an affine mapping that has a very simple description per se, but a complicated algebraic expression if combined with the ‘inverse’ mapping. It can be seen as modular polynomial multiplication followed by an addition:
$b(x) = (x^7 + x^6 + x^2 + x) + a(x)(x^7 + x^6 + x^5 + x^4 + 1)$ $mod$ $x^8 + 1$
The modulus has been chosen as the simplest modulus possible. The multiplication polynomial has been chosen from the set of polynomials coprime to the modulus as the one with the simplest description. The constant has been chosen in such a way that that the S-box has no fixed points (S-box( a ) = a ) and no ’opposite fixed points' (S-box( a ) = ā ).
The multiplication polynomial being $x^7 + x^6 + x^5 + x^4 + 1$, which is irreducible and therefore coprime to the modulus $x^8 + 1$. The inverse mapping multiplication is $x^7 + x^5 + x^2$.
However, $x^7 + x + 1$ is also irreducible, and has an even more simple representation. It is the most simple irreducible polynomial of degree 7. It also has a longer affine period (8 vs 4) which is supposedly better. There are many valid choices for the added constant that result in no fixed or opposite fixed points. The inverse mapping multiplication is $x^6 + x^5 + x^3 + x^2 + 1$, which is coprime to the modulus.
Is there some obvious reason the more simple polynomial was not used? The implication in the Rijndael specification is it does not have the simplest description, which does not seem to be the case. My assumption is lack of complexity of the algebraic expression in the resulting s-box or its inverse, but I do not have the means to determine if that is the case.
Thinking that the reason may have been the statistical performance of the s-box with the given affine polynomial, I compared it against $x^7 + x + 1$, the results are below:
AES x^7 + x + 1 SAC Relative Error 12.5% 9.4% lower is better SAC Satisfaction % 67.2% 67.2% higher is better Distance to SAC 432 432 lower is better Negative DSAC 176 152 lower is better 2nd order SAC Rel Err 12.5% 12.5% lower is better 2nd order SAC Sat % 56.7% 61.2% higher is better Dist to 2nd order SAC 1664 1424 lower is better Negative 2nd order DSAC 844 684 lower is better AVAL Relative Error 3.52% 3.12% lower is better Guaranteed Avalanche 339.2 339.2 my own metric Bit Independence Rel Err 13.412% 12.856% lower is better Bit Independence Sat % 56.2% 63.8% my own metric
It is quite clear that $x^7 + x + 1$ has better results in many s-box performance metrics when compared to the chosen polynomial.
During testing I also found that the Rijndael s-box has a self inverse mapping at 0x73 and 0x8F, where an input to the s-box and the inverse s-box produce the same result. This implies that the additive constant may not have been chosen carefully enough. The optimal constant appears to be 0x15.