Choice of multiplication polynomial in Rijndael s-box affine mapping

Question

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.

update

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.

Answer 1

As I have duplicated your question by mistake and non of us have had an answer, I request help to the authors to know why those parameters where selected like that.

The affine transformation is a vector space operation $(\mathbb{F}_{2})^8$, and the simplicity comes from the fact that, from the bunch of possible transformations the one used can be also described as a product in a polynomial ring modulo $x^8+1$.

Above the criteria that the matrix (or the multiplicand constant in polynomial view) must be invertible and the vector (or the addition constant) has avoid fixed point neither opposite fixed points, they have simply picked some from the set.

The timing feature is useful when the S-Boxes are calculated on the fly, but with them pre-calculated the difference doesn't matter (I think).

Answer 2

Update: RichieFrame's Sbox is slightly more complex than AES Sbox, see below, under the algebraic expression.

I have programmed this in Magma (enter link description here) a computational algebra system. I tried to make it verbose as much as possible. This code can be run on their online calculator at the link.

(a^7 + a^6)*W^255 + (a^6 + a^5 + a^3 + a + 1)*W^254 + (a^4 + a^3)*W^253 >+ (a^6 + a^5)*W^252 + (a^4 + a^2 + 1)*W^251 + (a^6 + a^5 + a^4 + a^2)*W^250 + (a^3 + a^2 + a + 1)*W^249 + (a^5 + a^4 + a^2)*W^248 + (a^7 + a^6 + a^2 + 1)*W^247 + (a^5 + a^4 + a^3 + a^2 + a + 1)*W^246 + (a^7 + a^6 + a^5 + a^4 + a^2 + 1)*W^245 + (a^5 + a^4 + a^2)*W^244 + (a^5 + a^4 + a^2 + a + 1)*W^243 + (a^7 + a^6 + a^5 + a^4 + a^3 + a^2 + a)*W^242 + (a^7 + a^6 + a^4 + a)*W^241 + (a^6 + a^5 + a^4 + a^3 + a + 1)*W^240 + (a^6 + a^5 + a^4 + a^3 + a^2)*W^239 + (a^6 + a^5 + a^4 + a + 1)*W^238 + (a^6 + a^5 + a^4 + a^2 + a)*W^237 + (a^3 + a^2 + 1)*W^236 + (a^7 + a^4 + a^2 + 1)*W^235 + (a^5 + a^3 + a^2 + a + 1)*W^234 + (a^5 + a^4 + a^3 + a)*W^233 + (a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*W^232 + (a^7 + a^6 + a^4)*W^231 + (a^7 + a^5 + a^2 + 1)*W^230 + a^2*W^229 + (a^7 + a + 1)*W^228 + (a^7 + a^6 + a^5 + a^4 + a^2 + 1)*W^227 + (a^7 + a^6 + a^3 + a^2 + a + 1)*W^226 + (a^6 + a^5 + a^4 + a^2 + 1)*W^225 + (a^7 + a^2 + a + 1)*W^224 + (a^7 + a^3 + a)*W^223 + (a^5 + a^4 + a^3 + a^2 + a)*W^222 + (a^7 + a^6 + a^4 + a^3 + a^2)*W^221 + (a^6 + a + 1)*W^220 + (a^6 + a^4 + a^3 + a^2 + a)*W^219 + (a^7 + a^6 + a^4 + a^2 + 1)*W^218 + (a^6 + a^5 + a^4 + a^2 + a + 1)*W^217 + (a^7 + a^5 + a^2 + a)*W^216 + (a^7 + a^6 + a^2)*W^215 + (a^7 + a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*W^214 + (a^5 + a^4 + 1)*W^213 + (a^7 + a^6 + a^2 + a + 1)*W^212 + (a^4 + a)*W^211 + (a^5 + a^3 + a)*W^210 + (a^7 + a^6 + a + 1)*W^209 + (a^7 + a^6 + a^5 + a^4)*W^208 + (a^3 + a^2 + a + 1)*W^207 + (a^6 + a^5 + a^3 + 1)*W^206 + (a^4 + a^3 + a^2 + 1)*W^205 + (a^6 + a^4 + a^3 + a + 1)*W^204 + (a^4 + a^3 + a)*W^203 + (a^7 + a^3 + a^2 + a)*W^202 + (a^7 + a^6 + a^4 + a^3 + a^2 + 1)*W^201 + (a^7 + a^6 + a^5 + a^4 + a + 1)*W^200 + (a^7 + a^5 + a^4 + a)*W^199 + (a^7 + a^6 + a^5 + a^4)*W^198 + (a^5 + a^4 + a^2)*W^197 + (a^5 + a^3)*W^196 + (a^3 + a + 1)*W^195 + (a^6 + a^5 + a^3 + a^2 + a + 1)*W^194 + (a^7 + a + 1)*W^193 + (a^7 + a^6 + a^5 + a)*W^192 + (a^7 + a^6 + a^4 + a + 1)*W^191 + (a^5 + a^3 + a^2 + a)*W^190 + (a^7 + a^6 + a^2 + a + 1)*W^189 + (a^7 + a^5 + 1)*W^188 + (a^7 + a^6 + a^4 + a^2 + a)*W^187 + (a^5 + 1)*W^186 + (a^7 + a^3 + a^2 + a + 1)*W^185 + (a^7 + a^6 + a^5 + a^3 + a^2 + 1)*W^184 + (a^6 + 1)*W^183 + (a^7 + a^4 + a^3 + 1)*W^182 + (a^7 + a^5 + a^4 + a^3)*W^181 + (a^7 + a^4 + a)*W^180 + (a^7 + a^6 + a^5 + a^3 + a^2 + 1)*W^179 + (a^7 + a^6 + a^2)*W^178 + (a^7 + a^3)*W^177 + (a^7 + a^4 + a^2 + 1)*W^176 + (a^5 + 1)*W^175 + (a^6 + a^5 + a^3)*W^174 + (a^6 + a^5 + a + 1)*W^173 + (a^7 + a^4 + a^3 + a^2)*W^172 + (a^6 + a^4 + a^3 + 1)*W^171 + (a^5 + a^4 + a + 1)*W^170 + (a^7 + a^6 + a^4 + a^3 + 1)*W^168 + (a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*W^167 + (a^5 + a^3 + a + 1)*W^166 + (a^7 + a^2)*W^165 + (a^6 + a^5 + a^3 + a^2)*W^164 + (a^7 + a^6 + a^5 + a^4)*W^163 + (a^7 + a^3 + a)*W^162 + (a^7 + a^4 + 1)*W^161 + (a^7 + a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*W^160 + (a^7 + a^5 + a^3 + a^2 + a)*W^159 + (a^7 + a^6 + a^5 + a^4 + a^3 + a)*W^158 + (a^5 + a^4 + a^2 + 1)*W^157 + (a^7 + a^5 + a^4 + a + 1)*W^156 + a^7*W^155 + (a^5 + a)*W^154 + a^4*W^153 + (a^5 + a^4 + a^3 + a^2 + 1)*W^152 + (a^6 + a^5 + a^3 + 1)*W^151 + (a^6 + a^5 + a^3 + a + 1)*W^150 + (a^4 + a^2 + 1)*W^149 + (a^6 + a^4 + a^3 + a + 1)*W^148 + (a^6 + a^4 + a^3)*W^147 + (a^6 + a^5 + a^4 + a^3 + a + 1)*W^146 + (a^4 + a^3 + a^2 + 1)*W^145 + (a^6 + a^5 + a^4 + a^2 + 1)*W^144 + (a^4 + a^3 + a)*W^142 + (a^6 + a + 1)*W^141 + (a^7 + a^5 + a^3 + a^2 + a)*W^140 + (a^6 + 1)*W^139 + (a^7 + a^4 + a^2 + a)*W^138 + (a^6 + a^4 + a^3)*W^137 + (a^7 + a^3 + a)*W^136 + (a^7 + a^4 + a^2)*W^135 + (a^6 + a^4 + a^3 + a + 1)*W^134 + (a^7 + a^6 + a^5 + a^4 + a^3 + a^2)*W^133 + (a^4 + a + 1)*W^132 + (a^7 + a^3 + a + 1)*W^131 + (a^6 + a^5 + 1)*W^130 + (a^7 + a^6 + a^5 + a^2 + a)*W^129 + (a^6 + a^5)*W^128 + (a^7 + a^5 + 1)*W^127 + (a^7 + a^6 + a^5 + 1)*W^126 + (a^6 + a^5 + a^4 + a + 1)*W^125 + (a^6 + a^4 + a)*W^124 + (a^7 + a^6)*W^123 + (a^6 + a^4 + a^2)*W^122 + (a^7 + a^6 + a^5 + a^3 + a^2 + a + 1)*W^121 + (a^7 + a^6 + a^4 + a^3 + a + 1)*W^120 + (a^6 + a^5 + a^4 + a^3 + a^2 + a + 1)*W^119 + (a^5 + a^4 + a^2 + 1)*W^118 + (a^6 + a^3 + 1)*W^117 + (a^7 + a^6 + a^5 + a)*W^116 + (a^7 + a^5 + a^3 + a^2 + 1)*W^114 + (a^6 + a^4 + a + 1)*W^113 + (a + 1)*W^112 + (a^4 + a^3 + a^2 + a)*W^111 + (a^7 + a^6 + a^5 + a^2 + a + 1)*W^110 + (a^6 + a^4 + a)*W^109 + (a^7 + a^6 + a^5 + a^4 + a^2 + a)*W^108 + (a^7 + a^3 + a^2 + 1)*W^107 + (a^7 + a^6 + a^5 + a^3 + a^2 + a + 1)*W^106 + (a^7 + a^5 + a)*W^105 + (a^7 + a^6 + a^5 + a^2 + 1)*W^104 + (a^7 + a^6 + a^5 + a^2)*W^103 + (a^7 + a^5 + a^3 + a^2)*W^102 + (a^7 + a^6 + a^4 + a^3 + a^2 + a + 1)*W^101 + (a^4 + a^3 + a^2 + 1)*W^100 + (a^5 + a^3 + a^2 + 1)*W^99 + (a^6 + a^5 + a^3 + a^2 + a)*W^98 + (a^7 + a^4 + a^3 + a^2 + 1)*W^97 + (a^7 + a^5 + a^4 + a^2)*W^96 + (a^4 + a^3 + a^2 + 1)*W^95 + (a^6 + a^5 + a^3 + a^2)*W^94 + (a^6 + a^5 + a^3 + a^2 + 1)*W^93 + (a^6 + a^5 + a^2)*W^92 + (a^6 + a^5 + a^4 + a^2 + 1)*W^91 + (a^7 + a^3 + a^2 + a + 1)*W^90 + (a^6 + a^3 + a^2 + a + 1)*W^89 + (a^7 + a^3 + a)*W^88 + (a^5 + a^3 + 1)*W^87 + (a^7 + a^6 + a^5 + a^2 + a)*W^86 + (a^5 + a^4 + a^3 + a^2 + a)*W^85 + (a^7 + a^6 + a)*W^84 + (a^7 + a^6 + a^2 + a)*W^83 + (a^7 + a^5 + a^2 + 1)*W^82 + (a^7 + a^5 + a^2)*W^81 + (a^7 + a^4 + a^3 + a + 1)*W^80 + (a^7 + a^6 + a^4 + a^2 + 1)*W^79 + (a^7 + a^6 + a^5 + a^3 + a^2 + 1)*W^78 + (a^7 + a^5 + a^3 + a^2 + a + 1)*W^77 + (a^6 + a^5 + a)*W^76 + (a^6 + a^5 + a^4)*W^75 + (a^7 + a^5 + a^4)*W^74 + (a^5 + a^4 + a^2 + a + 1)*W^73 + (a^7 + a^5 + a^4 + a^2 + 1)*W^72 + (a^6 + a^5 + a^2 + 1)*W^71 + (a^5 + a^4 + a^3 + a^2)*W^70 + (a^6 + a^5 + a^3 + a^2 + a + 1)*W^69 + (a^6 + a^5 + 1)*W^68 + (a^5 + a^4 + a^3 + a^2 + 1)*W^67 + (a^6 + a^5 + a^3 + a^2)*W^66 + (a^7 + a^5 + a^4 + a^3 + a^2 + 1)*W^65 + (a^7 + a^6 + a^5 + a^3 + a^2)*W^64 + (a^6 + a^5 + a^4 + a^2 + a)*W^63 + (a^5 + a^4)*W^62 + (a^7 + a^6 + a^5 + a^3)*W^61 + (a^7 + a^5 + a^2 + a + 1)*W^60 + a^3*W^59 + a^4*W^58 + (a^4 + a + 1)*W^57 + (a^6 + a^5 + a^4 + a^3 + 1)W^56 + aW^55 + (a^6 + a + 1)*W^54 + (a^6 + a^5 + 1)*W^53 + (a^7 + a^6 + a^5 + a^4 + a^3 + 1)*W^52 + (a^7 + a)*W^51 + (a^7 + a^6 + a^5 + a^3 + 1)*W^50 + (a^6 + a + 1)*W^49 + (a^5 + a^4 + a^3 + a^2)*W^48 + (a^7 + a^3 + 1)*W^47 + (a^7 + a^5 + a^3 + a^2 + a + 1)*W^46 + (a^7 + a^6 + a^4 + a^2 + a)*W^45 + (a^7 + a^6 + a^5 + a^4 + a^3 + 1)*W^44 + (a^7 + a^6 + a^4 + a^3 + 1)*W^43 + (a^7 + a^6 + a^5 + a^2 + a + 1)*W^42 + (a^7 + a^6 + a^3 + a)*W^41 + (a^6 + a^5 + a^3 + a^2)*W^40 + (a^6 + a^5 + a^4 + a^3 + 1)*W^39 + (a^7 + a^2 + a)*W^38 + (a^3 + a^2)*W^37 + (a^7 + a^4 + a)*W^36 + (a^6 + a + 1)*W^35 + (a^6 + a^4 + a^3 + 1)*W^34 + (a^7 + a^5 + a^2 + 1)*W^33 + (a^5 + a^3 + a^2 + 1)*W^32 + (a^4 + a^3 + 1)*W^31 + (a^7 + a^6 + a^4 + a^3 + a^2 + 1)*W^30 + (a^5 + a^4 + a^3 + a^2)*W^29 + (a^4 + 1)*W^28 + (a^7 + a^6 + a^4)*W^27 + (a^6 + a^4 + a^3)*W^26 + (a^7 + a^5 + a^4 + a^3 + a)*W^25 + (a^5 + a^4 + a + 1)*W^24 + (a^4 + a^2)*W^23 + (a^7 + a^6 + a^4 + a)*W^22 + (a^6 + a^5 + a)*W^21 + (a^6 + a^5 + a^4 + a^2 + a + 1)*W^20 + (a^7 + a^6 + a^4 + a^3 + a + 1)*W^19 + (a^4 + a + 1)*W^18 + (a^7 + a^5 + a^4 + a^2 + a)*W^17 + (a^7 + a^6 + a^3 + a^2 + a)*W^16 + (a^6 + a^3 + a^2 + 1)*W^15 + (a^4 + a^3)*W^14 + (a^4 + a^3)*W^13 + (a^7 + a^6 + a^5 + a^2 + a)*W^12 + (a^7 + a^6 + a^4 + a^3 + a^2)*W^11 + (a^7 + a^4 + a^2 + a + 1)*W^10 + (a^7 + a^5 + a^4 + 1)*W^9 + (a^7 + a^6 + 1)*W^8 + a^6*W^7 + (a^7 + a^6 + a^5 + a^3 + a + 1)*W^6 + (a^7 + a^5 + a^4 + a)*W^5 + (a^7 + a^4)*W^4 + (a^5 + a^4)*W^3 + (a^4 + a^3 + a^2 + a + 1)*W^2 + (a^6 + a^5 + a^4 + a^3 + a + 1)*W + a^7 + a^6 + a^2 + a

First I display above the algebraic expression for the AES Sbox. It looks like almost all powers of W from 0 to 255 occur [I have checked and 253 of 256 coefficients are nonzero]. So this expression is algebraically very complex.

If you supply your SBox map as a table, I can compute its algebraic expression too, and we can compare them.

I found the algebraic expression for RichieFrame's SBox, it has 2 more nonzero elements than the AES, so it's slightly more complex. I haven't done the inverse SBox, since I had to manually insert ", 0x" type of separators.

Below I explain the code.

I started with the hex list for SubBytes.

SBHex:=[0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76, 0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0, 0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15, 0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75, 0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84, 0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF, 0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8, 0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2, 0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73, 0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB, 0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79, 0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08, 0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A, 0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E, 0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF, 0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16 ];

"first few entries in SubBytes as integers"; SBHex[1..5]; //magma converts it to integer

function Pad(u,n)

if (#u eq 8) then
return u; else return [0: k in [1..8-#u]] cat u; end if; end function; //pad with zeroes to 8 digits

SBList:=[Pad(IntegerToSequence(SBHex[k],2),8): k in [1..#SBHex]]; "first few entries in SubBytes as vectors"; SBList[1..5];

R:=PolynomialRing(GF(2)); m:=x^8+x^4+x^3+x+1; //field polynomial from AES definition FF:=ext; //GF(2^8) as defined in AES

SBLF:=[[GF(2)!(IntegerRing(2)!SBList[k,i]): i in [1..8]]: k in [1..#SBList]];

"a few random field elements, a is a root of m defined above"; for k in [1..3] do Random(FF); end for;

"a few elements as vectors and as polynomials";

for k in [1..5] do SBLF[k]; SequenceToElement(SBLF[k],FF); end for;

SBFF:=[SequenceToElement(SBLF[k],FF): k in [1..#SBList]]; // this list of elements of GF(2^8) in SubBytes order Ident:=[[0]] cat [Reverse(IntegerToSequence(k,2)): k in [1..255]]; Ident:=[Pad(Ident[k],8): k in [1..256]]; "first few unsorted (input to SBox) elements prior to substitution in > normal order"; Ident[1..5]; IdentFF:=[SequenceToElement([GF(2)!(IntegerRing(2)!Ident[k,i]): i in [1..8]],FF): k in [1..#SBList]]; "this is the list of elements in GF(2^8) in unsorted order"; "first few unsorted elements as field elements"; IdentFF[1..5]; R2:=PolynomialRing(FF); "defined W to be the indeterminate for the polynomials over FF, i.e., >GF(2^8) of AES";

"algebraic expression for SBox"; Interpolation(IdentFF,SBFF);

Answer 3

It was a commonly used polynomial in industry before, e.g. DVB polynomial for reed solomon. I don't think it had much to do with performance but instead familiarity and use within industry.