0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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.. $\endgroup$ – Aleph Apr 7 '15 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.