Implementing arithmetic for elliptic curve cryptosystems
Abstract
This thesis describes how elliptic curve cryptosystems can be efficiently implemented. The performance of these systems will be studied by comparing various methods for efficient computation in finite fields and elliptic curve groups. In addition, the latest state-of-the-art algorithms for solving the elliptic curve discrete logarithm problem will be reviewed. This will provide mathematical evidence for the assumption that elliptic curve public key cryptosystems may provide strong security with relatively small key lengths.
The mathematical theory of elliptic curves is rich, having its roots in algebraic geometry and number theory. To keep the size of the presentation within reasonable bounds, some theorems whose proof would involve deeper knowledge of their respective areas are taken here for granted. These theorems are needed in exploring the group structure of an elliptic curve over a finite field, which is a key factor in determining the security of a cryptosystem built on this curve.
The elliptic curve group operation can be performed by computing some operations in the field on which the curve is built. Since the fields used in cryptography are finite, this means that fast algorithms for finite field arithmetic play a crucial role in designing efficient implementations of elliptic curve arithmetic. Because of their practical importance, finite fields will be discussed in great detail, with emphasis on fields of characteristic 2.
Finite fields with characteristic 2 are attractive from the implementation point of view, since these fields can be considered as vector spaces over the field F2 = {0,1}. Thus, these fields can be naturally regarded as bit strings of fixed length. This in turn allows very fast implementations of field operations using logic circuits or general purpose microprocessors. Some efficient hardware architectures and software algorithms for performing arithmetical operations in large finite fields will be presented here.
The key operation in elliptic curve cryptosystems is the scalar multiplication of an elliptic curve point, which is analogous to exponentiation in multiplicative groups. Some algorithms for fast exponentiation in general groups will be described together with some more specific techniques that exploit the representation of elliptic curve points using homogeneous coordinates in the projective plane. These techniques are combined with algorithms for finite field arithmetic, resulting in efficient architectures for computing scalar multiples of elliptic curve points. The complexity of these architectures will be compared and a summary of some existing implementations in software and hardware will be presented.
Keywords: elliptic curves, elliptic curve cryptosystems, finite fields, discrete logarithm problem, implementations