Efficient software-implementation of finite fields with applications to cryptography (Q850780)

The paper presents a survey of the existing techniques for software implementation of finite field arithmetic with a view in cryptographic applications. So the introduction discusses the types and sizes of finite fields used in Cryptography (for example the authors point out the vulnerability of the Elliptic Curve Cryptography over composite field extensions). The three types of fields \(\mathbb{F}_{2^m}, \mathbb{F}_p\) and \(\mathbb{F}_{p^m}\)\, are treated separately and in each one of the cases algorithms for the arithmetic operations of Addition, Multiplication, Field Reduction and Inversion are described. In the case of a field extension the elements are represented in a polynomial basis \(\{1, \alpha,\dots, \alpha^{m-1}\}\). Section 3 studies the case of binary fields \(\mathbb{F}_{2^m}\). The authors pay attention to the word-length of the processor, for instance they detail the Comb method for polynomial multiplication (of two \(m-1\)\, degree polynomials) in a \(w\)-bit processor. For the field reduction (of a \(2m-2\) degree polynomial modulo the degree \(m\) irreducible polynomial \(F(x)\) of \(\alpha\)) they state the convenience of choosing as \(F(x)\)\, a trinomial or pentanomial. Finally the paper discusses different ways to compute the inverse of an element in \(\mathbb{F}_{2^m}\): Binary Euclidean Algorithm, Almost Inverse Algorithm, Fermat Little Theorem and Look-up Tables. Section 4 reviews the case of fields \(\mathbb{F}_p\)\,. Firstly the paper describes ``multi-precision arithmetic'' for integers in radix \(b\)\, representation (\(b\) is chosen related to the word-length of the processor). Then the arithmetic modulo \(p\)\, is considered and the paper describes algorithms for modular reduction, both in the case of general primes \(p\)\, (Barret, Quisquater and Montgomery algorithms) and in the case of primes of special form (Crandall and Generalized Mersenne Primes). Software implementation of arithmetic over \(\mathbb{F}_{p^m}\)\, is the subject of Section 6 (although in the Introduction it is said that this case will be treated in Section 5. In fact Section 5 treats the problem of Inversion in fields \(\mathbb{F}_p\)). The so called Optimal Extension Fields allow an efficient software implementation. The paper provides a wide list of references to the studied algorithms as well as to related cryptographic aspects.