AN IMPLEMENTATION OF ELLIPTIC CURVE CRYPTOSYSTEMS OVER F(2)155

Since the introduction of the concept of public key cryptography by Di ffie and Hellman in 1976, the potential for the use of the discrete lo garithm problem in public key cryptosystems has been recognized. ElGam al gave an explicit methodology for using this problem to implement a fully functional public key cryptosystem, including digital signatures . This methodolgy has been refined and incorporated with various proto cols to meet a variety of applications, and one of its extensions form s the basis for a proposed U.S. digital signature standard. Although t he discrete logarithm problem, as first employed by Diffie and Hellman in their public key exchange algorithm, referred explicitly to the pr oblem of finding logarithms with respect to a primitive element in the multiplicative group of the field of integers modulo a prime p, this idea can be extended to arbitrary groups (with the difficulty of the p roblem apparently varying with the representation of the group). In th is paper, we describe how these protocols can be efficiently implement ed using the group of an elliptic curve over a finite field. In partic ular, we will discuss a new VLSI implementation of F2(155) and the per formance of elliptic curve systems over this ground field.