How can we make the AES S-box using Lagrange interpolation?

edit

Reference for the notations and defined objects:

Murphy and Robshaw, Essential Algebraic Structure Within the AES, page 7,8,...

First we implement the field $F=\mathbb F_2(t)$, defined by $$ F = \mathbb F_2[T]\ /\ (T^8 + T^4 + T^3 + T + 1)\ . $$ Here, $t$ is the image of $T$ taken modulo the irreducible polynomial $(T^8 + T^4 + T^3 + T + 1)$. This field can be simply defined in sage:

R.<T> = PolynomialRing( GF(2) )
RijndaelPolynomial = (T^8 + T^4 + T^3 + T + 1)
print "Is %s irreducible? %s" % ( RijndaelPolynomial, RijndaelPolynomial.is_irreducible() )
F.<t> = GF( 2**8, modulus = RijndaelPolynomial )

We get from the above in a further dialog with the interpreter:

Is T^8 + T^4 + T^3 + T + 1 irreducible? True
sage: F
Finite Field in t of size 2^8
sage: F.modulus()
x^8 + x^4 + x^3 + x + 1
sage: t.minpoly()
x^8 + x^4 + x^3 + x + 1

There is a more or less (humanly) canonical morphism $\psi$ $$\psi:F\to V\ ,$$ from the field $F$ to the vector space $$ V = \mathbb F_2^8\ ,$$ with the inverse $\psi^{-1}$, defined by making a vector $(a_0,a_1,a_2,\dots)$ correspond to $a_0+a_1t+a_2t^2+\dots$. This is the representation of $F$ by the forgetful functor as a vector space of dimension eight with the (humaly chosen) basis $1,t,t^2,\dots,t^7$.

The article writes instead of $\psi:F\to V$ the programmer-like joke $\psi:GF(2^8)\to GF(2)^8$.

We now consider the following composition of maps:

(0) We start with an element $(a_0,a_1,a_2,\dots)$ of $V$, and push it into $F$, obtaining $$w=\sum_{0\le k\le 7} a_kt^k\in F\ .$$

I will denote this map with $W=\psi^{-1}$, sorry, it is simpler to type it so.

(1) The "adjusted inverse map on F", for a non-zero $w\in F$ it is $w\to 1/w= w/w^2=w^{2^8}/w^2=w^{256}/w^2=w^{254}$. To have a map, we formally set $0\to 0$. The formula $w\to w^{254}$ also applies for the zero element. I will denote this map by $S$.

(2) Let $A$ be the matrix:

F2 = GF(2)
A  = matrix( F2, 8, 8,
             [ [ 1
                 if n-k in [-7,-6,-5,-4,0,1,2,3,4]
                 else 0
                 for k in [0..7] ]
               for n in [0..7] ] )
print A

So this is:

sage: A
[1 0 0 0 1 1 1 1]
[1 1 0 0 0 1 1 1]
[1 1 1 0 0 0 1 1]
[1 1 1 1 0 0 0 1]
[1 1 1 1 1 0 0 0]
[0 1 1 1 1 1 0 0]
[0 0 1 1 1 1 1 0]
[0 0 0 1 1 1 1 1]

It induces a map (left multiplication by $A$) from $V$ to $V$, where $V$ is seen as the space of column vectors with eight entries in $\mathbb F_2$.

(3) There is a further operation on $V$, namely adding v_0, which is the vector corresponding to 63.

The composition is then a map $$ V\to V\ ,\qquad v\to Wv\to SWv\to L_A(SWv)\to L_A(SWv)+v_0\ . $$

Understanding $L_A$ It turns out that we have to forget now completely the "AES" box, and look only to the matrix $A$, which does not occur explicitly or implicitly in the original post.

The linear map $L_A:V\to V$ is now moved via $\psi$ to a map from $F$ to $F$, defined by: $$ a\to \psi^{-1}(\ L_A(\ \psi(a)\ )\ )\ . $$ Note that $0$ goes to $0$.

It turns out that there is a polynomial (function) of a very special shape that "interpolates" this map, the very special shape being: $$ f(a) = \sum_{0\le k\le 7}\lambda_k\; a^{2^k}\ . $$ From it, we associate $$ g(a) = \sum_{0\le k\le 7}\lambda_k\; a^{255-2^k}\ . $$ The polynomial (function) $g$ differs from $f$ by the "adjusted inverse" $S$. To still have confidence that we have a chance to guess an answer to a question we will formulate soon, that even has a join to the posted question, note that the powers appearing in the line

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

namely $254, 253, 251, 247, 239, 223, 191, 127$ are in fact:

sage: [ 255 - 2^k for k in [0..7] ]
[254, 253, 251, 247, 239, 223, 191, 127]

The add on + v comes from the operation in step (3) above.

The question is now the following one:

How to compute the coefficients $$ \lambda_0, \lambda_1, \lambda_2, \lambda_3, \lambda_4, \lambda_5, \lambda_6, \lambda_7 $$ in $f$?

Let us compute them, and forget about any other ingredients, which are rather misleading.

(We do not rename them with $a,b,c,d,e,f,g,h$ so that tracing becomes difficult with the benefit of also using the letter $a$ with a different meaning.)

Because the Frobenius morphism $a\to a^2$ is a field morphism, we have first of all $$ f(a+b) = f(a)+f(b)\ . $$ So $f$ is additive, and thus $\mathbb F_2$--linear. (As $L_A$ is, too.)

So the problem is equivalent to solving a simple linear system, $8$ equations, $8$ unknowns. There is no Lagrange interpolation involved, this is just a misleading hint in a related post. (Lagrange interpolation is something about polynomials with running degrees $0,1,2,3,\dots$ and not $1,2,4,\dots$)

The matrix of the linear system is $M$, with entries $$ (t^n)^{2^k}\ , $$ with a row index $n$, and a columns index $k$.

The unknowns column vector has the entries $\lambda_k$.

The free vector $w$ has the components obtained from $L_A$, moved via $\psi$ to $F$, the applied on $(t^n)_n$ .

The solution is now simple:

F2    = GF(2)
R.<T> = PolynomialRing( F2 )
RijndaelPolynomial = (T^8 + T^4 + T^3 + T + 1)
F.<t> = GF( 2**8, modulus = RijndaelPolynomial )

A  = matrix( F2, 8, 8,
             [ [ 1
                 if n-k in [-7,-6,-5,-4,0,1,2,3,4]
                 else 0
                 for k in [0..7] ]
               for n in [0..7] ] )

def psi_inverse( v ):
    return sum( [ v[k]*t^k for k in [0..7] ] )

def psi( a ):
    coeffs = R(a).list()
    coeffs += ( [ F2(0) , ] * (8-len(coeffs)) )
    return vector( F2, coeffs )

M = matrix( F, 8, 8,
            [ [ (t^n)^(2^k) for k in [0..7] ]
              for n in [0..7] ] )

w = matrix( F, 8, 1,
            [ psi_inverse( A * psi(t^k) ) for k in [0..7] ] )

# solve M(lambda) = w
M.inverse() * w

This gives:

[                        t^2 + 1]
[                        t^3 + 1]
[t^7 + t^6 + t^5 + t^4 + t^3 + 1]
[                  t^5 + t^2 + 1]
[    t^7 + t^6 + t^5 + t^4 + t^2]
[                              1]
[      t^7 + t^5 + t^4 + t^2 + 1]
[        t^7 + t^3 + t^2 + t + 1]

Note: There is maybe an improvement idea for the framework of the site - since i feel the need of a frustration karma that each user can manage herself or himself. It looks sometimes like cryptology is a science trying to hide mathematics and structure so far, that only hardware can understand them. Not so many papers, but many discussions that arise are then by nature cryptic. This should be considered an optimistic note, stressing out now how important a software like sage can be, without it i would have no chance to recover and understand the circle of ideas, and the phenomenological aspect from the article. Sage offers a free, structural way to think mathematically while programming, implementing stuff with compact, clean, easy readable code.

Personal note: Obviously this answer is related to the question only in a thin shake-hands, and rather by the coincidence of producing t^2+1 and t^3+1 (and the next coefficients). Strictly speaking, it should be downgraded, just following the rules of the site. This happened to me these days in a similar situation.