How can I find the multiplicative inverse in the first transformation of the SubBytes() transformation in AES?

Question

In FIPS-197 §5.1.1, it says the first transformation in the SubBytes() transformation is:

1. Take the multiplicative inverse in the finite field $\text{GF}(2^8)$ described in Sec. 4.2; the element $\{00\}$ is mapped to itself.

Looking at Sec. 4.2, it says that for a given non-zero polynomial $b(x)$ you can find the inverse $b(x)^{-1}$ by using the extended Euclidean algorithm. My question is basically: how do you do this?

I've looked at a ton of examples, Wikipedia has one in $\text{GF}(2^8)$, but I still just don't understand.

Let $b(x) = x^6+x^4+x+1$, Rijndael has $m(x)=x^8+x^4+x^3+x+1$.

From the relation: $$b(x)a(x)+m(x)c(x)=1 \iff b^{-1}(x) \equiv a(x)\pmod{m(x)}$$ I can't figure out what $a(x)$ and $c(x)$ are.

The higher level explanations maybe assume you know some things, and the basic explanations
only use simple integers with Euclid's algorithm, so it's a frustrating place for a beginner.

Answer 1

They are referring to the formula for Bézout's identity which calculates the greatest common divisor, extended to a finite field, where 1 is the multiplicative neutral element.

From the relation $b(x)a(x)+m(x)c(x)=1$, $$b^{-1}(x)=a(x)\mod m(x)$$ I cant figure out what $a(x)$ and $c(x)$ are?

In this case, $b(x)$ is the element for which the inverse is desired, and $a(x)$ is the coefficient for some $c(x)$ that results in the equation being correct. Since $a(x)$ must be in the field, it is reduced modulo $m(x)$, becoming the inverse of $b(x)$. The actual calculation of the extended Euclidean algorithm does not require $c(x)$ to find $a(x)$, but it must exist in the formula for the reduction above to be correct:

$$b(x)a(x)+m(x)c(x)=1$$

$$(b(x)a(x) \mod\ m(x)) + (m(x)c(x) \mod\ m(x)) = 1 \mod\ m(x)$$

$$m(x)c(x) \mod\ m(x) = 0$$

$$b(x)a(x) \mod\ m(x) = 1 \mod\ m(x)$$

$$a(x) \mod\ m(x)={1/b(x)}\mod\ m(x)$$

$$a(x) \mod\ m(x)=b^{-1}(x)$$

Any resultant inverse can be multiplied by $b(x)$ to check for correctness, as the result should be 1 modulo $m(x)$. In practice, the multiplicative inverse is calculated using log/antilog tables for non zero elements:

$$a(x) \mod\ m(x)=log^{-1}(255 - log(b(x)))$$

Since the tables are calculated using exponentiation modulo $m(x)$, the resultant $a(x)$ is already reduced and within the field.

Since the inverse is only used in calculation of the sbox, it is not used in most AES implementations, since the precalculated sbox is stored as a table and not generated on the fly.