4
$\begingroup$

I'd like to use the Itoh-Tsujii algorithm for a dynamic substitution table, but I do not get the following line: $$r\ \gets\ (p^m - 1)\,/\,(p - 1)$$

And why can $r$ be used to calculate the multiplicative innverse of a number in a Galois field containing $p^m$ elements by calculating it in the field $GF(p)$ and use this result to calculate the inversion in the $GF(p^m)$ field?

$\endgroup$
  • 1
    $\begingroup$ Welcome to crypto.SE. If you try to compute a modular inverse modulo $2^m$ (that is, in $\Bbb Z_{2^m}^*$, which is not a field), see this and if that's not clear enough leave some note, below or directly in your question. If in $\text{GF}(2^p)$, well we a question with answers in the case of AES. If you do want the full Itoh Tsuji algorithm for arbitrary Galois field, please improve the question stating that and trying to make the question more precise. Like: "used to conclude" what exactly? $\endgroup$ – fgrieu Jun 2 at 17:59
  • $\begingroup$ Thanks for the answer. I actually like to use the algorithm for the AES encryption to compute subsitution tables, but I don't understand the maths behind this algorithm. I hope the question is pecise enough now. $\endgroup$ – MrXeth Jun 2 at 21:31
6
$\begingroup$

I have recently detailed the use of Itoh-Tsuji in the article on Curve9767 (section 3.6).

In the description below, I write elements of $GF(p^m)$ as polynomials in $GF(p)[z]$, taken modulo a given irreducible unitary polynomial $M$ of degree $m$ (since all finite fields with the same cardinal are isomorphic to each other, the choice of a specific $M$ has no importance for security, but some choices of $M$ allow for better performance, as will be shown below). We consider the problem of computing the inverse $a^{-1}$ of a given element $a \in GF(p^m)$ (with $a \neq 0$).

  • $p^m-1$ is a multiple of $p-1$; in fact, the quotient is: $$ r = \frac{p^m-1}{p-1} = 1 + p + p^2 + p^3 + \cdots + p^{m-1} $$

  • For any $a \in GF(p^m)$ distinct from zero, we can express the inverse of $a$ as: $$ a^{-1} = \frac{a^{r-1}}{a^r} $$ This is true for any integer $r$, but for $r = (p^m-1)/(p-1)$, this leads to fast inversion thanks to two main facts, detailed below.

  • Fact 1: $a^r \in GF(p)$. Indeed, $(a^r)^{p-1} = a^{p^m-1} = 1$ (since $p^m-1$ is the order of the group of invertible elements in $GF(p^m)$). Thus, $a^r$ is a root of the polynomial equation $X^{p-1} - 1 = 0$. However, all non-zero elements of $GF(p)$ are roots of that polynomial (by Fermat's Little Theorem), and there are $p-1$ non-zero elements in $GF(p)$, and $X^{p-1} - 1$, being a polynomial of degree $p-1$ in a field, cannot have more than $p-1$ roots. Therefore, the roots of $X^{p-1}-1$ are exactly the non-zero elements of $GF(p)$, and $a^r$ is one of them.

    This implies that inverting $a^r$ is much easier than inverting in general an element of $GF(p^m)$, since we can work in $GF(p)$. There are various methods for computing inverses modulo $p$, but if $p$ is small, Fermat's Little Theorem works well (i.e. raising $a^r$ to the power $p-2$).

  • Fact 2: computing $a^{r-1}$ is inexpensive, thanks to the Frobenius automorphism. The $j$-th Frobenius automorphism (for $j >= 0$) is: \begin{eqnarray*} \Phi_j : GF(p^m) &\longrightarrow& GF(p^m) \\ a &\longmapsto& a^{p^j} \end{eqnarray*} i.e. $\Phi_1$ is just "raising to the power $p$", and $\Phi_j$ is "applying $\Phi_1$ exactly $j$ times".

    This operator is a field automorphism: $\Phi_j(ab) = \Phi_j(a) \Phi_j(b)$ and $\Phi_j(a+b)$ = $\Phi_j(a) + \Phi_j(b)$ for all $a, b \in GF(p^m)$. This makes it linear (if we interpret $GF(p^m)$ as a vector space of dimension $m$ over $GF(p)$) and thus reasonably easy to compute: if: $$ a = \sum_{i=0}^{m-1} a_i z^i $$ then: $$ \Phi_j(x) = \sum_{i=0}^{m-1} a_i \Phi_j(z^i) $$ Moreover, if $GF(p^m)$ is defined with a modulus of the form $M = z^m - c$ for some constant $c \in GF(p)$ (there are constants $c$ that ensure that $z^m-c$ is irreducible, as long as $m$ divides $p-1$), then $\Phi_j(z^i) = c^{ij(p-1)/m}$, and applying $\Phi_j$ on any value $a$ becomes a matter of multiplying the $m$ coefficients $a_i$ of $a$ by $m$ constants that are easily precomputed. This makes $\Phi_j$ inexpensive (much cheaper than a single multiplication in $GF(p^m)$).

    For any $a \in GF(p^m)$, we can compute $a^{r-1}$ by using a few multiplications and Frobenius operators: \begin{eqnarray*} t_1 &=& \Phi_1(a) &=& a^{p} \\ t_2 &=& t_1 \Phi_1(t_1) &=& a^{p+p^2} \\ t_3 &=& t_2 \Phi_2(t_2) &=& a^{p+p^2+p^3+p^4} \\ t_4 &=& t_3 \Phi_4(t_3) &=& a^{p+p^2+p^3+p^4+\cdots+p^{8}} \\ & & \ldots & & \end{eqnarray*} With about $\log m$ multiplications and applications of a Frobenius operator, one can obtain $a^{r-1}$.

Using all of the above, the complete inversion algorithm of $a \in GF(p^m)$ is then:

  1. Using multiplications and the Frobenius operators, compute $a^{r-1}$.
  2. Multiply $a$ by $a^{r-1}$ to get $a^r$ (this multiplication is made easy because we know that the result is in $GF(p)$, so we have only one coefficient to compute; the other ones are all zero).
  3. Invert $a^r$ in $GF(p)$ (using for instance Fermat's Little Theorem).
  4. Multiply $a^{r-1}$ by $a^{-r}$ (this multiplication is also easy, since $a^{-r} \in GF(p)$).

In Curve9767, which uses the field $GF(9767^{19})$, I can get the complete cost of the inversion down to about 6 to 7.7 times that of a multiplication in $GF(p^m)$, which is fast enough to seriously contemplate the use of affine coordinates for the operations on the elliptic curve. By comparison, usual algorithms for inversion modulo a 256-bit integer $n$ will take between 50 and 300 times the cost of a multiplication modulo $n$.


All of that is said in the generic context of $GF(p^m)$. Itoh and Tsuji first described it for $GF(2^m)$, i.e. with $p = 2$, in which case the Frobenius operator $\Phi_1$ is simply "squaring". Moreover, with $p = 2$, inversion in $GF(p)$ is a no-operation (since $GF(2)$ has only a single non-zero element, which is $1$, and $1$ is its own inverse), so $a^r = 1$; the inversion of $a^r$ and the multiplication by $a^{-r}$ can then be skipped. On the other hand, with $p = 2$, the modulus $M$ cannot be $z^m-c$ for some $c \in GF(2)$ because neither $X^m$ nor $X^m-1$ is irreducible over $GF(2)$, and you need an irreducible modulus to get a field. This makes the Frobenius operators somewhat more complex to compute (but still quite efficient).

| improve this answer | |
$\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.