Efficient Hardware Implementation of Finite Fields with Applications to Cryptography
- PDF / 876,676 Bytes
- 44 Pages / 439.37 x 666.142 pts Page_size
- 88 Downloads / 177 Views
Efficient Hardware Implementation of Finite Fields with Applications to Cryptography Jorge Guajardo · Tim Güneysu · Sandeep S. Kumar · Christof Paar · Jan Pelzl
Received: 30 August 2006 / Accepted: 30 August 2006 / Published online: 26 September 2006 © Springer Science + Business Media B.V. 2006
Abstract The paper presents a survey of most common hardware architectures for finite field arithmetic especially suitable for cryptographic applications. We discuss architectures for three types of finite fields and their special versions popularly used in cryptography: binary fields, prime fields and extension fields. We summarize algorithms and hardware architectures for finite field multiplication, squaring, addition/subtraction, and inversion for each of these fields. Since implementations in hardware can either focus on high-speed or on area-time efficiency, a careful choice of the appropriate set of architectures has to be made depending on the performance requirements and available area. Key words Field arithmetic · cryptography · efficient implementation · binary field arithmetic · prime field arithmetic · extension field arithmetic · Optimal extension fields. Mathematics Subject Classifications (2000) 12-02 · 12E30 · 12E10.
J. Guajardo (B) Information and System Security Department, Philips Research, Eindhoven, The Netherlands e-mail: [email protected] T. Güneysu · S. S. Kumar · C. Paar · J. Pelzl Horst-Görtz Institute for IT-Security, Ruhr-University Bochum, Germany T. Güneysu e-mail: [email protected] S. S. Kumar e-mail: [email protected] C. Paar e-mail: [email protected] J. Pelzl e-mail: [email protected]
76
Acta Appl Math (2006) 93: 75–118
1 Introduction Before 1976, Galois fields and their hardware implementation received considerable attention because of their applications in coding theory and the implementation of error correcting codes. In 1976, Diffie and Hellman [20] invented public-key cryptography1 and single-handedly revolutionized a field which, until then, had been the domain of intelligence agencies and secret government organizations. In addition to solving the key management problem and allowing for digital signatures, publickey cryptography provided a major application area for finite fields. In particular, the Diffie-Hellman key exchange is based on the difficulty of the Discrete Logarithm (DL) problem in finite fields. It is apparent, however, that most of the work on arithmetic architectures for finite fields only appeared after the introduction of two public-key cryptosystems based on finite fields: elliptic curve cryptosystems (ECC), introduced by Miller and Koblitz [39, 47], and hyperelliptic cryptosystems (HECC), a generalization of elliptic curves introduced by Koblitz in [40]. Both, prime fields and extension fields, have been proposed for use in such cryptographic systems but until a few years ago the focus of hardware implementations was mainly on fields of characteristic 2. This is due to two main reasons. First, even characteristic fields naturally offer a s
Data Loading...
