6
$\begingroup$

I have seen in various papers like in this one page 4, that the AES s-box equation is:

$S=A \circ φ^{-1}(φ(x)^{254})$ where $φ$ is the isomorphism from $\mathbb{F}_2^{8}$ to $\mathbb{F}_{2^{8}}$ with its basis and the reduction polynomial and $A$ is the affine transformation defined in AES.

I am kind of new to this area, but what I would say is that $φ(x)^{254}$ is the inverse of $φ(x)$ since their multiplication generates the $φ(x)^{255}$. The degree with the reduction polynomial is 255 right? (Since it's irreducible, but I am not sure if we should include zero as well)

So, what I would expect is:

$S=A \circ φ(x)^{254}$

How did the first equation come up?

$\endgroup$
11
$\begingroup$

The tricky point is that $\mathbb{F}_2^8$ is not a field; it is a degree-8 vector space. Multiplications are not defined on vector spaces. However, the $A$ transform is defined only on the vector space, not on the field (it is "affine" only when considering its source/destination space as a vector space).

The $\phi$ and $\phi^{-1}$ operations are thus "type conversions". If you think of it in terms of implementations, they are akin to type casts: if $x$ is a vector, then $\phi(x)$ is the same sequence of bits, but interpreted as a field element. So you have to apply $\phi$ (i.e. switch to field interpretation) in order to do field-related things (here, exponentiation), then $\phi^{-1}$ must be apply on the result to go back to vector space interpretation, so that a vector space affine transform ($A$) may be applied.

A possible source of confusion is the notation $\phi^{-1}$ that means "the inverse function" (i.e. the one that goes in the reverse direction), but not "the inverse of the value". The same term ("inverse") and the same notation (exponentiation with $-1$) are used for two very different things.

Also, $z^{254}$ indeed computes the inverse of $z$ in the field $\mathbb{F}_{2^8}$, but it also returns 0 when the source value is 0, which is what we want in AES, while the inverse of 0 is nominally not defined. Hence the use of exponentiation in the formula, instead of inversion.

$\endgroup$

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.