Title :
A Technique for Accelerating Characteristic 2 Elliptic Curve Cryptography
Author :
Gueron, Shay ; Kounavis, Michael
Abstract :
In this paper we describe a novel approach for speeding up the computations of characteristic 2 elliptic curve cryptography. Using a projective space such as the Lopez-Dahab space (1999) for representing point coordinates we accelerate point additions and point doublings by introducing a novel way for multiply elements in finite fields of the form GF(2m). Our technique uses a CPU instruction for carry-less multiplication (GFMUL) and single iteration Karatsuba-like formulae (Kounavis, 2007) for computing the carry-less product of large degree polynomials in GF(2). It then performs the reduction of the carry-less product of these polynomials by taking into account the fact that many curves specify fields with irreducible polynomials which are sparse. For example NIST curves specify polynomials with either three terms (trinomials) or five terms (pentanomials). We demonstrate results from a prototype implementation showing that our technique speeds up Elliptic Curve Diffie Hellman based on the NIST B-233 curve by 55% in software on a 3.6 GHz Pentium 4 processor. If a 3 clock latency GFMUL instruction is introduced to the CPU then the acceleration factor becomes 5.2times. We also show that further software optimizations have the potential to further increase the speedup beyond 10times.
Keywords :
cryptography; digital arithmetic; microcomputers; CPU instruction; GFMUL instruction; NIST B-233 curve; carry-less multiplication; carry-less product; elliptic curve Diffie Hellman; elliptic curve cryptography; irreducible polynomials; large degree polynomials; pentanomials; single iteration Karatsuba-like formulae; software optimizations; trinomials; Acceleration; Clocks; Computer aided instruction; Delay; Elliptic curve cryptography; Elliptic curves; Galois fields; NIST; Polynomials; Software prototyping;
Conference_Titel :
Information Technology: New Generations, 2008. ITNG 2008. Fifth International Conference on
Conference_Location :
Las Vegas, NV
Print_ISBN :
0-7695-3099-0
DOI :
10.1109/ITNG.2008.193