Polynomial representation of the affine part of the AES S-box I have been reading up on the polynomial representation of the AES Sbox (PDF: “Essential Algebraic Structure Within the AES”  by Murphy and Robshaw) and I can't get it to produce the correct output.

Maybe I have a thinking mistake somewhere along the way, so here's what I did:


I picked a random byte: 10010101. This corresponds to $x^7 + x^4 + x^2 + 1$ in the AES-field, or $95_{16}$ in hexadecimal
I used the lookup table at Wikipedia to see what the solution should be: $2a_{16}$, or in binary 00101010 ( $ x^5 + x^3 + x $ ). I also computed it by hand with the matrix to get intermediate results and such.
I converted the coefficients of the interpolation polynomial from hex to bytes to polynomials and computed the interpolation polynomial mod the Rijndael polynomial. I used Sage to do this… my code is at the very bottom.
The result I get from this is not the result the Sbox yields. It's also not an intermediate result, nor do I get the right result when I use an intermediate result as input.


Where did I go wrong?



Sage code:

$R.&lt;x&gt;$=PolynomialRing(Integers(2))
f = x^8 + x^4 + x^3 + x + 1
a = x^7 + x^4 + x^2 + 1
l0 = x^2 + 1
l1 = x^3 + 1
l2 = x^7 + x^6 + x^5 + x^4 + x^3 + 1
l3 = x^5 + x^2 + 1
l4 = x^7 + x^6 + x^5 + x^4 + x^2
l5 = 1
l6 = x^7 + x^5 + x^4 + x^2 + 1
l7 = x^7 + x^3 + x^2 + x + 1
l8 = x^6 + x^5 + x + 1
s = l0*a + l1*(a^2) + l2*(a^4) + l3*(a^8) + l4*(a^16) + l5*(a^32) + l6*(a^64) * l7*(a^128)
q = s % f
print(q)
Your code is an attempt to implement the function $f$ which is a polynomial representation of the $\text{GF}(2)$ affine part of the S-box of the AES (usually referred to as $A$). Function $f$ is described on page 7 of the paper and your coefficients seems to be OK. 

Your code is mapping $\text a$ to $\text q$ such that $\text q=f(\text a)$.
You're however missing a huge part of the AES S-box, that is, the inversion in $\text{GF}(2^8)$. What you actually want is to map $\text a$ to $\text q$ such that $\text q=f(\text a^{-1})$ where the inversion takes place in your ring $\text R$. Note that you must handle the special case $0$ aside...