Efficient software-implementation of finite fields with applications to cryptography

DOI10.1007/S10440-006-9046-1MaRDI QIDQ850780zbMATH OpenOpenAlexFDO

Authors Jorge Guajardo, Sandeep S. Kumar, Christof Paar, Jan Pelzl

Publication date 6 November 2006

Published in Acta Applicandae Mathematicae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10440-006-9046-1

binary field arithmetic cryptography efficient implementation extension field arithmetic field arithmetic optimal extension field prime field arithmetic

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Research exposition (monographs, survey articles) pertaining to field theory (12-02) Special polynomials in general fields (12E10) Field arithmetic (12E30)

Review text

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.

Recommendations

Cites work

Cited in

(26)

Describes a project that uses

Uses Software

DSP56000

This page was built for publication: Efficient software-implementation of finite fields with applications to cryptography

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q850780)