Highly efficient elliptic curve crypto-processor with parallel GF field multipliers

Journal of Computer Science,  May, 2006  by Turki F. Al-Somani,  M.K. Ibrahim,  Adnan Gutub

• E-mail
• Print
• Link

Abstract: This study presents a high performance GF([2.sup.m]) Elliptic Curve Crypto-processor architecture. The proposed architecture exploits parallelism at the projective coordinate level to perform parallel field multiplications. In the proposed architecture, normal basis representation is used. Comparisons between the Projective, Jacobian and Mixed coordinate systems using sequential and parallel designs are presented. Results show that parallel designs using normal basis gives better area-time complexity (A[T.sup.2]) than sequential designs by 33-252% which leads to a wide range of design tradeoffs. The results also show that mixed coordinate system is the best in both sequential and parallel designs and gives the least number of multiplications levels when using 3 multipliers and the best A[T.sup.2] when using only 2 multipliers.

Key words: Elliptic curves cryptosystems, projective coordinate, parallel designs, normal basis

INTRODUCTION

Recently, Elliptic Curves Cryptosystems (ECC) [1,2] has attracted many researchers and has been included in many standards [3-8]. ECC is evolving as an attractive alternative to other public-key schemes such as RSA by offering the smallest key size and the highest strength per bit. Extensive research has been done on the underlying math, security strength and efficient implementations. Among the different fields that can underlie elliptic curves, prime fields GF(p) and binary polynomial fields GF([2.sup.m]) have shown to be best suited for cryptographic applications. In particular, binary fields allow for fast computation in software as well as in hardware. Small key sizes and computational efficiency make ECC not only applicable to hosts processing security protocols over wired networks, but also to small wireless devices such as cell phones, PDAs and Smartcards.

Inversion operations, which are needed in point addition over Elliptic Curves are the most expensive operation over Finite Fields [9-12]. The approach adopted in the literature is to represent Elliptic Curve points in projective coordinate in order to replace the inversion operations with repetitive multiplications [9-15]. Recently, several ECC processors have been proposed in the literature [10-12,14,15] based on projective coordinate representation. There are many projective coordinate systems to choose from. In exiting architectures, the selection of a projective coordinate is based on the number of arithmetic operations, mainly multiplications. This is to be expected due to the sequential nature of these architectures where a single multiplier is used.

For high performance servers, such sequential architectures are too slow to meet the demand of increasing number of users. For such servers, high-speed crypto processors are becoming crucial. One solution for meeting this requirement is to exploit the inherent parallelism within Elliptic curve point operations in projective coordinate. Recently, ECC processor architectures have been proposed where the choice of the projective coordinate system used also depends on its inherent parallelism [11,12]. Since multiplication is the most dominant operation and most time consuming when computing point operations in projective coordinate, three multipliers that can work in parallel are used in the architectures in [11,12]. These architectures give better area-time complexity (A[T.sup.2]) than the architectures that are based in a single multiplier. In this study we are proposing an alternative parallel design using normal basis representation which is more suitable for hardware implementations. In addition, the complexity and parallelism in several homogenous and heterogeneous projective coordinate are given.

GF([2.sup.m]) Arithmetic background: The finite GF([2.sup.m]) field has particular importance in cryptography since it leads to particularly efficient hardware implementations. Elements of the field are represented in terms of a basis. Most implementations use either a Polynomial Basis or a Normal Basis [16]. For the proposed cryptoprocessor described in this study, a normal basis is chosen since it leads to more efficient hardware implementations. Normal basis is more suitable for hardware implementations than polynomial basis since operations are mainly comprised of rotation, shifting and exclusive-OR operations which can be efficiently implemented in hardware. A normal basis of GF([2.sup.m]) is a basis of the form

([beta], [[beta].sup.2], [[beta].sup.4], [[beta].sup.8],... [[beta].sup.2^(m-1)]), where [beta] [member of] GF([2.sup.m])

In a normal basis, an element A [member of] GF([2.sup.m]) can be uniquely represented in the form

A = [[summation].sub.i=0.sup.m-1][a.sub.i][[beta].sup.2.sup.i],

where [a.sub.i] [member of] {0, 1}.

GF([2.sup.m]) operations using normal basis are performed as follows:

Addition and subtraction: Addition and subtraction are performed by a simple bit-wise exclusive-OR (XOR) operation.

Squaring: Squaring is simply performed by a rotate left operation.