# Choice of multiplication polynomial in Rijndael s-box affine mapping

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.

• I just performed an SAC test, the more simple polynomial actually performs better by a slight margin – Richie Frame Jul 2 '14 at 20:23
• Do you have any evidence that these metrics have anything to do with the security of AES? Are there any theoretical (reduced round) attacks known against AES that would be foiled by an sbox that is better by these metrics? – poncho Jul 21 '14 at 14:38
• @poncho No I do not. They concern differential properties, better performance in these tests generally means more resistance to differential cryptanalysis. The AES s-box is already very good in these respects, what I am saying there is that their choice of affine polynomial was not chosen from a subset of those with statistically better properties, so that is not a potential reason not to use a more simple polynomial. – Richie Frame Jul 21 '14 at 20:25
• @RichieFrame Did you ever proceed with this further? I would make a nice hardware implementation. – b degnan Nov 29 '17 at 12:38
• @RichieFrame, please see new answer below. – kodlu Mar 14 '18 at 6:26

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).

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

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:=[] 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);

• So what are variables a and W in this case? – Q-Club Mar 14 '18 at 7:07
• a is the root of the GF(2^8) generating irreducible polynomial m(x). since the polynomial is not irreducible, its powers can't generate all the elements of this field, thus they can only be written as polynomials of degree up to 8 in a. W is just an indeterminate, since we are considering a mapping from GF(2^8) to itself and all mappings between finite fields can be uniquely represented as polynomials. Thus substitute a field element (polynomial in a) for W, reduce the resulting polynomial expression mod m(a) and you obtain the output corresponding to that input into SubBytes. – kodlu Mar 14 '18 at 11:21
• tables of s-box and inverse: pastebin.com/pqL4HnzD – Richie Frame Mar 14 '18 at 12:23
• You have 255 nonzero coefficients and beat the AES choice by 2 coefficients. Of course both are almost fully nonzero [256 total]. – kodlu Mar 15 '18 at 3:54
• The AES s-box should only have 9 terms, I think its inverse should be 253, are you sure the calculations are correct? – Richie Frame Mar 15 '18 at 5:03