1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I never said anything about tables. $\endgroup$ – Melab Oct 17 '17 at 21:26
  • $\begingroup$ do you have a good reference for the AES inversion for hardware? $\endgroup$ – b degnan Oct 18 '17 at 0:34
  • $\begingroup$ @Melab I've seen log/antilog tables presented as the "standard" solution :) $\endgroup$ – Biv Oct 18 '17 at 7:56
  • $\begingroup$ @bdegnan eprint.iacr.org/2015/763.pdf ? :/ $\endgroup$ – Biv Oct 18 '17 at 8:09
  • $\begingroup$ @Biv Thanks. I hadn't seen that one, and there was nothing in IEEE or ACM so I made a complete document based on the work by Satou as I could not find one. I probably should publish it. I go through all of the math, and do the circuits. $\endgroup$ – b degnan Oct 18 '17 at 14:24

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.