# AES inversion operation in sub byes

I was wondering why in the AES sub-bytes operation one can represent the inversion as computing $x^{254}$. What is the reason for this?

Moreoever, I was wondering what the text on page 212 of https://autonome-antifa.org/IMG/pdf/Rijndael.pdf means that the polynomial representation of the sub-bytes operation can be obtained by lagrange polynomial interpolation?

Thanks a lot, Peter

## 1 Answer

AES sub-bytes is defined over the finite field $GF(2^8).$ This field has 256 elements. Its multiplicative group $GF(2^8)^{\ast}$ has 255 elements. In any multiplicative group $a^N=identity$ for all $a$ in the group. This means the multiplicative order of all the group elements (the smallest power they can be raised to and obtain 1) divides $N.$ Here, by definition of AES, $x$ actually has maximal order $N=255$ Thus $x^{255}=1$ and $x^{254}=x^{-1}$ due to its maximal order. Sub-bytes is defined using the inversion $x^{-1}$ if $x\neq 0$ and $x$ if $x=0.$ The formula $x\mapsto x^{254}$ captures both cases.

All functions defined on a finite field can be represented as polynomials. Thus given any input/output table for a function on a finite field, Lagrange interpolation (definition widely available including on Wikipedia) can be used to find the polynomial corresponding to that function, assuming the table representation is a well defined function.

• Note that the multiplicative group of a finite field is always cyclic, not just in the case of $\mathbb F_{256}$. Not all $x$ are generators (what you refer to as having maximal order), but all of them have an inverse, which can be computed as $x^{254}$ by Fermat's little theorem.. – Aleph Apr 7 '15 at 6:48