Calculating the multiplicative inverse of a number in $GF(2^n)$ where $n > 8$

Question

Suppose that:

• We have a polynomial $g(x)$ of degree $n$.
• $n > 8$.
• $q$ is the multiplicative inverse of $p$ in $G(2^n)$ modulo $g(x)$. If $p = 0$, then $q = 0$.

This could be used:

• As a non-linear substitution stage in a block cipher, where $y_i = S(x_i)$ and $S: \{0, 1\}^{16} \rightarrow \{0, 1\}^{16}$.
• In the decryption routine of a block cipher, where the round keys are used in finite field multiplication during encryption and their inverses need to be known for decryption.

I've seen log/antilog tables presented as the "standard" solution for calculating multiplicative inverses over a finite field, but if $n$ is bigger than 8, like, say, 16 or 40, that's going to take a very long time. What would be another method of calculating $p$'s $q$ that would consume less time and computational resources?

Answer 1

First, let us take AES as an example.

We have $\operatorname{GF}(2^8)$ where each bit represent the coefficient of a polynomial in $\operatorname{GF}(2)[X]$. The modulo reduction is done with $$p(x) = x^8 + x^4 + x^3 + x+ 1$$

Thus you can generate all the elements from a $1$ to $255$ and this forms a cyclic group : $<g^1, g^{\ldots}, g^{255}>$

Notice that:
$g^{2^8-1} = g \iff g^{255} = g$
or:
$g \cdot g^{2^8-2} = 1 \iff g \cdot g^{254} = 1$
thus $g^{254}$ is the inverse of $g$ or in other words:

Computing the $254^{th}$ power of an element give its inverse (more here)

This exponentiation can be quickly done using square-and-multiply.

---

Thus for a field of $2^n$ with $p$ being an irreducible polynomial of degree $n$, for $g$ an element of $\operatorname{GF}(2)[X]$: $$g ^{-1} = g^{2^n-2} \bmod p$$

Also the use of tables is ill-advised do to the constant timeness. A bit-sliced implementation of this operation will be preferable.