I talked about Rijndael in a couple of previous posts: Generating the Rijndael S-box, Efficient multiplication and division in GF(2^{8}), Sieving irreducible monic polynomials over a finite field, Addition and multiplication table for GF(2^{2}).

I'm going to talk some more about it today.

The Rijndael non-linear S-box *S*(*x*) is a composition of two invertible functions *f*(*g*(*x*)). Last time we showed how to generate these, and their inverses, as 256-entry tables.

As Daemen and Rijmen point out, *any function from a finite field to itself can be expressed as a polynomial*. In fact, given a tabular form of the function, it is possible to generate the Lagrange polynomial and then simplify.

They also give the polynomial for *S*(*x*):

_{RD}[

*x*] =

**05**·

*x*

^{255}+

**09**·

*x*

^{253}+

**F9**·

*x*

^{251}+

**25**·

*x*

^{247}+

**F4**·

*x*

^{239}+

**01**·

*x*

^{223}+

**B5**·

*x*

^{191}+

**8F**·

*x*

^{127}+

**63**

Well, let's check this.

And while we're at it, let's find the polynomials for *g*(*x*), *f*(*x*) and even *S*^{-1}(*x*) too.

First of all, let's start with the Lagrange polynomial.

Given a table of entries { (**00**, *y*_{00}), (**01**, *y*_{01}), ..., (**ff**, *y*_{ff}) }, there is a polynomial *L*(*x*) which gives the same output, namely:

*L*(*x*) = Σ_{i ∈ { 00, 01, ..., ff }} *y*_{i} *p*_{i}(*x*)

where *p*_{i}(*x*) = Π_{j ∈ { 00, 01, ..., ff }, j ≠ i} (*x* - *j*) / (*i* - *j*)

Can we simplify this?

Yes. Note that (*i* - *j*)^{-1} term varies over all the non-zero elements of the finite field. Since this is a field, every non-zero element has an inverse, which might or might not be itself.

If the inverse is *not* itself, we can pair the two inverse elements together, and we get **01**, which is the multiplicative identity, so we can ignore it.

What are we left with? The product of those non-zero elements which *are* their own inverses.

In the case of GF(2^{8}), there is only one such element, namely **01**.

Great! We can ignore the (*i* - *j*)^{-1} terms altogether:

*L*(*x*) = Σ_{i ∈ { 00, 01, ..., ff }} *y*_{i} Π_{j ∈ { 00, 01, ..., ff }, j ≠ i} (*x* - *j*)

What is this? A sum of 256 different polynomials.

Each of these summands is a product of 255 polynomials of degree 1, and so is a polynomial of degree 255.

But in GF(2^{8}), *x*^{255} = **01** for all *x*. So each of the summands is actually a polynomial of degree 254, or less.

So the sum is also a polynomial of degree 254, or less; terms with an exponent >= 255 go away and just contribute to lower-order terms.

Great. We have { (**00**, *y*_{00}), (**01**, *y*_{01}), ..., (**ff**, *y*_{ff}) } for *f*, *g*, *S*, and *S*^{-1}. Let's plug them in and see what happens!

I wrote a Perl script to do this; the script is attached. Here's the output. (It's quite slow; it takes about two and a half minutes to run.)

f(x) =

63 + 05 x + 09 x^2 + f9 x^4 + 25 x^8 + f4 x^16 + 01 x^32 + b5 x^64 +

8f x^128

S(x) =

63 + 8f x^127 + b5 x^191 + 01 x^223 + f4 x^239 + 25 x^247 + f9 x^251 + 09 x^253 +

05 x^254

S^(-1)(x) =

52 + f3 x + 7e x^2 + 1e x^3 + 90 x^4 + bb x^5 + 2c x^6 + 8a x^7 +

1c x^8 + 85 x^9 + 6d x^10 + c0 x^11 + b2 x^12 + 1b x^13 + 40 x^14 + 23 x^15 +

f6 x^16 + 73 x^17 + 29 x^18 + d9 x^19 + 39 x^20 + 21 x^21 + cf x^22 + 3d x^23 +

9a x^24 + 8a x^25 + 2f x^26 + cf x^27 + 7b x^28 + 04 x^29 + e8 x^30 + c8 x^31 +

85 x^32 + 7b x^33 + 7c x^34 + af x^35 + 86 x^36 + 2f x^37 + 13 x^38 + 65 x^39 +

75 x^40 + d3 x^41 + 6d x^42 + d4 x^43 + 89 x^44 + 8e x^45 + 65 x^46 + 05 x^47 +

ea x^48 + 77 x^49 + 50 x^50 + a3 x^51 + c5 x^52 + 01 x^53 + 0b x^54 + 46 x^55 +

bf x^56 + a7 x^57 + 0c x^58 + c7 x^59 + 8e x^60 + f2 x^61 + b1 x^62 + cb x^63 +

e5 x^64 + e2 x^65 + 10 x^66 + d1 x^67 + 05 x^68 + b0 x^69 + f5 x^70 + 86 x^71 +

e4 x^72 + 03 x^73 + 71 x^74 + a6 x^75 + 56 x^76 + 03 x^77 + 9e x^78 + 3e x^79 +

19 x^80 + 18 x^81 + 52 x^82 + 16 x^83 + b9 x^84 + d3 x^85 + 38 x^86 + d9 x^87 +

04 x^88 + e3 x^89 + 72 x^90 + 6b x^91 + ba x^92 + e8 x^93 + bf x^94 + 9d x^95 +

1d x^96 + 5a x^97 + 55 x^98 + ff x^99 + 71 x^100 + e1 x^101 + a8 x^102 + 8e x^103 +

fe x^104 + a2 x^105 + a7 x^106 + 1f x^107 + df x^108 + b0 x^109 + 03 x^110 + cb x^111 +

08 x^112 + 53 x^113 + 6f x^114 + b0 x^115 + 7f x^116 + 87 x^117 + 8b x^118 + 02 x^119 +

b1 x^120 + 92 x^121 + 81 x^122 + 27 x^123 + 40 x^124 + 2e x^125 + 1a x^126 + ee x^127 +

10 x^128 + ca x^129 + 82 x^130 + 4f x^131 + 09 x^132 + aa x^133 + c7 x^134 + 55 x^135 +

24 x^136 + 6c x^137 + e2 x^138 + 58 x^139 + bc x^140 + e0 x^141 + 26 x^142 + 37 x^143 +

ed x^144 + 8d x^145 + 2a x^146 + d5 x^147 + ed x^148 + 45 x^149 + c3 x^150 + ec x^151 +

1c x^152 + 3e x^153 + 2a x^154 + b3 x^155 + 9e x^156 + b7 x^157 + 38 x^158 + 82 x^159 +

23 x^160 + 2d x^161 + 87 x^162 + ea x^163 + da x^164 + 45 x^165 + 24 x^166 + 03 x^167 +

e7 x^168 + 19 x^169 + e3 x^170 + d3 x^171 + 4e x^172 + dd x^173 + 11 x^174 + 4e x^175 +

81 x^176 + 91 x^177 + 91 x^178 + 59 x^179 + a3 x^180 + 80 x^181 + 92 x^182 + 7e x^183 +

db x^184 + c4 x^185 + 20 x^186 + ec x^187 + db x^188 + 55 x^189 + 7f x^190 + a8 x^191 +

c1 x^192 + 64 x^193 + ab x^194 + 1b x^195 + fd x^196 + 60 x^197 + 05 x^198 + 13 x^199 +

2c x^200 + a9 x^201 + 76 x^202 + a5 x^203 + 1d x^204 + 32 x^205 + 8e x^206 + 1e x^207 +

c0 x^208 + 65 x^209 + cb x^210 + 8b x^211 + 93 x^212 + e4 x^213 + ae x^214 + be x^215 +

5f x^216 + 2c x^217 + 3b x^218 + d2 x^219 + 0f x^220 + 9f x^221 + 42 x^222 + cc x^223 +

6c x^224 + 80 x^225 + 68 x^226 + 43 x^227 + 09 x^228 + 23 x^229 + c5 x^230 + 6d x^231 +

1d x^232 + 18 x^233 + bd x^234 + 5e x^235 + 1b x^236 + b4 x^237 + 85 x^238 + 49 x^239 +

bc x^240 + 0d x^241 + 1f x^242 + a6 x^243 + 6b x^244 + d8 x^245 + 22 x^246 + 01 x^247 +

7a x^248 + c0 x^249 + 55 x^250 + 16 x^251 + b3 x^252 + cf x^253 + 05 x^254

Daemen and Rijmen's polynomial rendition of *S*(*x*) is confirmed.

Also note how simple *g*(*x*) is, and how complex *S*^{-1}(*x*) is.

Finally, I must confess that none of this is actually useful. The tabular form is much more convenient for applications. This is just a fun theoretical exercise.

(Well, *I* had fun.)

EDIT: 2015-10-31 moved script to https://github.com/mvaneerde/blog/blob/master/rijndael/lagrange-interpolation.pl