Efficient hardware implementation of finite fields with applications to cryptography (Q850794)

This survey should be seen as complementary of another paper of four of the authors of this paper dedicated to the topic of Software Implementation of Finite Fields Arithmetic and published in the same issue of the same journal. In both cases the authors follow the same scheme: they consider the three types of fields, binary fields, prime fields and extensions fields, and in each one of the cases they survey the existing algorithms for finite field Addition, Multiplication and Inversion, always thinking in architectures ``specially suitable for cryptographic applications''. The Introduction (Section 1) analyzes the influence of the development of Public Key Cryptography in the work on architectures for finite fields arithmetic and how performance gains in the computation of such arithmetic operations (in particular the modular exponentiation) ``directly affect the performance of the entire cryptosystem''. The paper is interested in the area and time complexity of the different architectures and points out that the choice of one or another of them will depend on the computational constraints of the platform to be used (specially in the case of devices with small memory and computation capability such as smart cards and RIFD tags). Section 2 studies the case of prime fields \(\mathbb{F}_p\),\, describing the different Adders (ripple-carry adders, carry-lookahead adders, carry-save adders and carry-delayed adders), Multipliers (parallel and sequential algorithms, interleaved modular multiplication, Montgomery and Barret modular multiplication), etc. Section 3 discusses the several types of basis of an extension of fields: polynomial, normal and dual basis, although in the rest of the paper the elements will be represented in a polynomial base \(\{1, \alpha,\dots, \alpha^{m-1}\}\). The hardware implementation techniques for binary field extension are reviewed in Section 4 (bit multipliers, digit multipliers and single-accumulator multipliers), while Section 5 studies the case of fields \(\mathbb{F}_{p^n}\). The case \(p=3\),\, due to its cryptographic applications, deserves particular attention. Finally Section 6 summarizes the generalization (to extension fields with a polynomial basis representation) due to two of the authors of the present paper [see \textit{J. Guarjardo} and \textit{C. Paar}, Des. Codes Cryptogr. 25, No. 2, 207--216 (2002; Zbl 1030.11070)] of the Itoh-Tsujii algorithm [\textit{T. Itoh} and \textit{S. Tsujii}, Inf. Comput. 78, 171--177 (1988; Zbl 0672.68015)], for computing the inverse of a non-zero element in \(\mathbb{F}_{2^n}\)\, when using a normal basis representation.