Abstract
Elliptic curves have been extensively studied for many years. Recent interest has revolved around their applicability to factoring integers, primality testing, and to cryptography. In this paper we explore the feasibility of implementing in hardware an arithmetic processor for doing elliptic curve computations over finite fields. Of special interest, for practical reasons, are the curves over fields of characteristic 2. The elliptic curve analogue of the ElGamal cryptosystem is also analyzed.
Article PDF
Similar content being viewed by others
References
G. Agnew, T. Beth, R. Mullin, and S. Vanstone, Arithmetic operations in GF(2m), Journal of Cryptology, 6 (1993), 3–13.
G. Agnew, R. Mullin, I. Onyszchuk, and S. Vanstone, An implementation for a fast public-key cryptosystem, Journal of Cryptology, 3 (1991), 63–79.
G. Agnew, R. Mullin, and S. Vanstone, Improved digital signature scheme based on discrete exponentiation, Electronics Letters, 26 (1990), 1024–1025.
G. Agnew, R. Mullin, and S. Vanstone, An implementation of elliptic curve cryptosystems over F 2155, IEEE Journal on Selected Areas in Communications, to appear.
D. Ash, I. Blake, and S. Vanstone, Low complexity normal bases, Discrete Applied Mathematics, 25 (1989), 191–210.
J. Brillhart, D. Lehmer, J. Selfridge, B. Tuckerman, and S. Wagstaff, Factorizations of b n± 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers, Contemporary Mathematics, 22, 1983.
D. Coppersmith, Fast evaluation of logarithms in fields of characteristic two, IEEE Transactions on Information Theory, 30 (1984), 587–594.
D. Coppersmith, A. Odlyzko, and R. Schroeppel, Discrete logarithms in GF(p), Algorithmica, 1 (1986), 1–15.
W. Diffie and M. Hellman, New directions in cryptography, IEEE Transactions on Information Theory, 22 (1976), 644–654.
T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory, 31 (1985), 469–472.
T. ElGamal, A subexponential-time algorithm for computing discrete logarithms over GF(p 2), IEEE Transactions on Information Theory, 31 (1985), 473–481.
J. Hastad, On using RSA with low exponent in a public key network, Advances in Cryptology: Proceedings of Crypto '85, Lecture Notes in Computer Science, Vol. 218, Springer-Verlag, Berlin, 1986, pp. 403–408.
N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation, 48 (1987), 203–209.
N. Koblitz, Course in Number Theory and Cryptography, Springer-Verlag, New York, 1987.
N. Koblitz, Constructing elliptic curve cryptosystems in characteristic 2, Advances in Cryptology: Proceedings of Crypto '90, Lecture Notes in Computer Science, Vol. 537, Springer-Verlag, Berlin, 1991, pp. 156–167.
N. Koblitz, Elliptic curve implementation of zero-knowledge blobs, Journal of Cryptology, 4 (1991), 207–213.
N. Koblitz, CM-curves with good cryptographic properties, Advances in Cryptology: Proceedings of Crypto '91, Lecture Notes in Computer Science, Vol. 576, Springer-Verlag, Berlin, 1992, pp. 279–287.
A. Menezes, T. Okamoto, and S. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing, 1991, pp. 80–89.
A. Menezes and S. Vanstone, Isomorphism classes of elliptic curves over finite fields of characteristic 2, Utilitas Mathematica, 38 (1990), 135–154.
A. Menezes, S. Vanstone, and R. Zuccherato, Counting points on elliptic curves over F 2m, Mathematics of Computation, 60 (1993), 407–420.
V. Miller, Uses of elliptic curves in cryptography, Advances in Cryptology: Proceedings of Crypto '85, Lecture Notes in Computer Science, Vol. 218, Springer-Verlag, Berlin, 1986, pp. 417–426.
P. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Mathematics of Computation, 48 (1987), 243–264.
R. Mullin, I. Onyszchuk, S. Vanstone, and R. Wilson, Optimal normal bases in GF(pn), Discrete Applied Mathematics, 22 (1988/89), 149–161.
A. Odlyzko, Discrete logarithms and their cryptographic significance, Advances in Cryptology: Proceedings of Eurocrypt '84, Lecture Notes in Computer Science, Vol. 209, Springer-Verlag, Berlin, 1985, pp. 224–314.
A. Odlyzko, Personal communication, 1986.
S. Pohlig and M. Hellman, An improved algorithm for computing logarithms over GF(p) and its crptographic significance, IEEE Transactions on Information Theory, 24 (1978), 106–110.
T. Rosati, A high speed data encryption processor for public key cryptography, Proceedings of IEEE Custom Integrated Circuits Conference, San Diego, 1989, pp. 12.3.1–12.3.5.
C. Schnorr, Efficient identification and signatures for smart cards, Advances in Cryptology: Proceedings of Crpto '89, Lecture Notes in Computer Science, Vol. 435, Springer-Verlag, Berlin, 1990, pp. 239–252.
R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Mathematics of Computation, 44 (1985), 483–494.
J. Silverman, The Arithmetic of Elliptic Curves, Springer-Verlag, New York, 1986.
Author information
Authors and Affiliations
Additional information
Communicated by Andrew M. Odlyzko
Rights and permissions
About this article
Cite this article
Menezes, A.J., Vanstone, S.A. Elliptic curve cryptosystems and their implementation. J. Cryptology 6, 209–224 (1993). https://doi.org/10.1007/BF00203817
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00203817