It's no secret I like Python and Sage a lot. Today, I had the pleasure of working with Sage again: as a school assignment, I was required to show the calculations that prove that the value of the Rijndael S-box in row 2, column d, was indeed d8. While I am able to invert a polynome of this size by hand (let alone apply an affine transformation), I see no reason to do it, as a suitable tool is available.
So, here we go, the Rijndael S-box in Sage:
F.<y> = GF(2, name='y')[]
K.<x> = GF(2**8, name='x', modulus=y^8 + y^4 + y^3 + y + 1)
bin_digits = lambda h: [((int(str(h), 16))//(2^i)) % 2
for i in range(3, -1, -1)]
bin_poly = lambda n : sum([b * x^(3-i)
for i,b in enumerate(bin_digits(n))])
b1 = 2
b2 = 'd'
s = x^4 * bin_poly(b1) + bin_poly(b2)
p = (1/s).polynomial().coeffs()
p.reverse()
b = [0]*(8 - len(p)) + p
b.reverse()
c = [1,1,0,0,0,1,1,0]
d = [int((b[i] + b[(i + 4) % 8] + b[(i + 5) % 8] +
b[(i + 6) % 8] + b[(i + 7) % 8] + c[i]).n()) % 2
for i in range(8)]
d.reverse()
s1 = sum([d[i] * 2^(3-i) for i in range(4)])
s2 = sum([d[i+4] * 2^(3-i) for i in range(4)])
print hex(s1), hex(s2)
I admit: the above is code, not calculations, but I did the calculations in class and worked hard on the code. My main problem was the bit order. Nowhere in the original publication did it say to reverse the bytes. Adding all the reverses was a moment of desperation, and imagine my surprise when it worked. I wonder how much credit that solution will get me.
A great Friday night it was.
