An Area-Efficient Composite Field Inverter for Elliptic Curve Cryptosystems

Introduction

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.