This question from comes an earlier question. I have also posted this question in the CryptoStackExchange but it may be better suited here.
Thanks to the answers I have already received I know the Sage code for the AES S-box is:
- 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)
I can see that polynomial $m$ is the irreducible polynomial used in AES, $v$ is the constant term ($C6$) in the affine transform of the S-box, and $y$ corresponds to the S-box input $95$. But I do not know how the polynomials $a$ to $h$ are produced.
I also learned that the polynomials $a$ to $h$ are the result of Lagrange interpolation. I understand LI a little but I have no idea how to apply it in this case.
- Can anyone explain how to find these polynomials in Sage (or another program)?
- Why is $a=x^2+1$ for instance?
One full example of using Lagrange interpolation in Sage to produce any one of these polynomials ($a$ to $h$) should do the trick. Any help would be much appreciated. I have been trying to understand this for some time.