# 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:

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

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

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

4. 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.<x>$=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)

• Could you explain what l0-l8 are? I'm too lazy to read the paper right now. – mikeazo Jul 18 '14 at 14:45
• @mikeazo It seems as if that may just be hinting at pages 7 and 8: “The S-box $GF(2)$-linear operation”. (Yet, I could be wrong… with a local temperature of 93.2°F outside, it’s hard to say if my brain is boiling or actually thinking.) – e-sushi Jul 18 '14 at 16:12

You did make a mistake but only in that you are missing the addition of the final vector, you correctly replicated the equation from the paper.

The problem is that the equation in the paper is only for the linear affine tranformation step of the s-box and does not include the non-linear inversion in $GF(2^{8})$, namely $a = y^{-1}$ where $y$ is the input value into the s-box:

$f(a) = \sum\limits_{k=0}^7{\lambda_ka^{2^k}}$

The correct formula you want including inversion should be:

$f(y) = \sum\limits_{k=0}^7{\lambda_ky^{-2^k}}$

Which equivalent to:

$f(y) = \sum\limits_{k=0}^7{\lambda_ky^{255-2^k}}$

Therefore you must change the exponents of $a$ in your final equation, for which I am substituting $y$ in the following Sage code in order to represent the coefficients as $\{a,b,c,d,e,f,g,h\}$, the modulus $m$, and the vector $v$:

R = PolynomialRing(GF(2),'x',1)
x = R.gen()

m = x^8 + x^4 + x^3 + x + 1
v = x^6 + x^5 + x + 1
y = x^7 + x^4 + x^2 + 1

a = x^2 + 1
b = x^3 + 1
c = x^7 + x^6 + x^5 + x^4 + x^3 + 1
d = x^5 + x^2 + 1
e = x^7 + x^6 + x^5 + x^4 + x^2
f = 1
g = x^7 + x^5 + x^4 + x^2 + 1
h = x^7 + x^3 + x^2 + x + 1

s = a*(y^254) + b*(y^253) + c*(y^251) + d*(y^247) + e*(y^239) + f*(y^223) + g*(y^191) + h*(y^127) + v

print (s % m)

• Thank you (to both answers), that solved it. Also, I am an idiot because in my equation for s I had a multiplication instead of addition at one point, so this could not have yielded the right result no matter what ;) – Angela Jul 21 '14 at 7:54

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

• also missing modulus of polynomial ring, which is different for inversion and affine transform, meaning you need 2 rings – Richie Frame Jul 18 '14 at 19:52
• Nope: that's the whole point of using the interpolation of the affine transform over $\text{GF}(2^8)$, getting rid of the $\psi$ and $\psi^{-1}$, see page 7 of the paper of Sean Murphy and Matt Robshaw. – bob Jul 18 '14 at 20:18
• they are completely missing that in the equation, which is why the op's code which is based on it is not working – Richie Frame Jul 19 '14 at 2:46
• I am misreading things it seems, i read that interpolation as relating to the inversion, which it is not, what the equation is missing is indeed the non-linear step – Richie Frame Jul 19 '14 at 3:07