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

This post is a wiki. Anyone with karma >750 is welcome to improve it.

I found the Sage code for the AES S-box online. It is given below.

However, I do not know how to find the coefficients of a to h using Lagrange interpolation. They seem to appear from nowhere, but I am told they are the result of Lagrange interpolation. I only know how to apply Lagrange interpolation if I have a function and some given points. But it seems there are no given points.

Can anyone help? An example of how to use Lagrange interpolation in Sage for just one or two of these polynomials, say $a =x^2+1$, and $b = x^3+1$ would be very helpful.

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)

edit retag close merge delete

Please review the text for the question and make clear what is given and what should be computed.

• What is AES S-box? Do we really need to know and understand it?
• Are in fact only v, y given, then we build s by the above formula and ask for a,b,c,d,e,f,g,h ? I do not think so, but it is really hard to figure out a sensible question in the given framework...
• Which is the Lagrange interpolation problem, written mathematically?
( 2017-12-08 08:30:29 -0500 )edit

Tip: don't tick the "community wiki" checkbox when posting questions.

Usually the "community wiki" tag is for questions that are not about Sage, but about Ask Sage itself.

Additionally, with the "community wiki" checkbox ticked, upvotes to the question don't earn you karma.

You need karma to be able to post links, to upvote questions and answers by others, etc.

( 2017-12-08 09:27:42 -0500 )edit

@dan_fulea

• AES S-box is the substitution box in the encryption cipher AES. I don't think it is necessary to know exactly what it is to understand the question.
• $m$, $v$ and $y$ (and $s$) are all given. The S-box takes an input of 8 bits (written in hexadecimal) and produces an output. For example $S-[2A] = E5$ These outputs come from Lagrange interpolations (somehow) but I don't know how to do it .. even on paper. But I heard it can be done in Sage.
• I am not sure which Lagrange interpolation.
( 2017-12-09 02:55:08 -0500 )edit

@slelievre Nice tip. But how do I untick my question from the community wiki?

( 2017-12-09 05:46:36 -0500 )edit

The question has its story in the www, notations differ from place to place, but still it is hard to get the "right framework" for the question. (For me and other answerers.)

Please understand that it is your task to make a clean, clear description of what is given and what should be computed how.

S−[2A]=E5 makes no sense.

Here is the path of the searches for related issues:

(cryptography post)[https://crypto.stackexchange.com/questions/18199/polynomial-representation-of-the-affine-part-of-the-aes-s-box]

(stackexchange post)[https://crypto.stackexchange.com/questions/18199/polynomial-representation-of-the-affine-part-of-the-aes-s-box]

(Paper by Murphy and Robshaw)[https://pdfs.semanticscholar.org/b0fe/cd3913af3a01b85c332737386bce26ac68fe.pdf]

Please give references step by step

( 2017-12-09 06:53:22 -0500 )edit

Sort by » oldest newest most voted

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.

more