Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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:
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).
