An Area-Efficient Composite Field Inverter for Elliptic Curve Cryptosystems

An Area-Efficient Composite Field Inverter for Elliptic Curve Cryptosystems

M. M. Wong (Swinburne University of Technology – Sarawak, Malaysia) and M. L. D. Wong (Swinburne University of Technology – Sarawak, Malaysia)
DOI: 10.4018/978-1-4666-5808-0.ch009


This chapter presents a new area-efficient composite field inverter of the form GF(q1) with q=2n.m suitable for the hardware realization of an elliptic curve (EC) cryptosystem. Considering both the security aspect and the hardware cost required, the authors propose the utilization of the composite field GF(((22)2)41) for EC cryptosystem. For efficient implementation, they have derived a compact inversion circuit over GF(2164)=GF(((22)2)41) to achieve an optimal saving in the hardware cost required. Furthermore, the authors have also developed a composite field digit serial Sunar-Koc multiplier for the multiplication in the extension field. All of the arithmetic operations in the subfield GF(24) are performed in its isomorphic composite field, GF((22)2), leading to a full combinatorial implementation without resorting to the conventional look-up table approach. To summarize the work, the final hardware implementation and the complexity analysis of the inversion is reported towards the end of this chapter.
Chapter Preview


In recent years, elliptic curve cryptography (ECC) (Koblitz, 1991; Miller, 1986) has attracted an increasing research interest among cryptography researchers. Many researchers have proposed ECC as the means for public key cryptography where two separate keys (credentials) are used for encrypting and decrypting data. The main reason for the popularity of ECC is owing to the elegance of the mathematics behind ECC and its ability to achieve strong cryptosystems efficiently.

Along with the emergence of ECC in public key cryptography, several EC hardware cryptographic applications have gained their popularity as well. Unlike the software cryptosystems, which are flexible in designs, the hardware cryptosystem realizations are rather constrained in terms of area cost, power consumption and achievable performance.

In the literature, several efficient EC hardware cryptosystems were reported (Chelton & Benaissa, 2008; Sakiyama, Batina, Preneel, & Verbauwhede, 2007; Hein, Wolkerstorfer, & Felber, 2009; Gutub, Tenca, Savas, &Koç, 2003; Goodman & Chandrakasan, 2001; Bednara, Daldrup, Gathen, Shokrollahi, & Teich, 2002; Rodríguez-Henríquez, Morales-Luna, Saqib, & Cruz-Cortés, 2007). Most of these architectures were designed for arbitrary finite fields (either prime fields or binary fields) as opposed to using a specific field. Hence, the efforts were mostly devoted to the issues of reconfigurability and scalability of the ECC processor in achieving high speed or compact cryptosystem. Very few studies were reported on the algorithmic optimization in EC hardware cryptosystem.

As ECC works in the finite field, the complexity of the arithmetic of its underlying field will determine the resources required in the final cryptosystem. Consequently, the first, and the most essential step in constructing a compact and efficient EC hardware cryptosystem is to choose the suitable field for ECC computation. In addition, the scalar multiplication, kP, is the most crucial and yet the most complicated operation in any ECC applications. The reason being is that the scalar multiplication in affine space involves a repetition of point additions and point doublings, both requires inversions over the finite field (Hankerson, Menezes, & Vanstone, 2004). Therefore, optimization in the field level is required to search for the potential area minimization of scalar multiplication defined in the affine space. In this work, we present a new efficient inversion circuit through the exploitation of composite field arithmetic for EC hardware cryptosystem.

Overall, our contributions in this work are twofold: First, we introduce an efficient three-level isomorphism composite field, , suitable for hardware EC cryptosystems. Second, we propose a new combinatorial inverter using the Itoh and Tsujii inversion (ITI) algorithm in optimal normal type II basis representation (ONBII) to eliminate the need for LUTs completely. In addition to that, we present a series of algorithmic optimizations in the subfield operations, and also a composite field digit serial Sunar-Koc multiplier in the extension field, in order to achieve better area reduction in our design.

Complete Chapter List

Search this Book: