Elliptic curve cryptosystems

Koblitz, Neal

doi:10.1090/S0025-5718-1987-0866109-5

Elliptic curve cryptosystems

Author: Neal Koblitz
Journal: Math. Comp. 48 (1987), 203-209
MSC: Primary 94A60; Secondary 11T71, 11Y16, 68P25
DOI: https://doi.org/10.1090/S0025-5718-1987-0866109-5
MathSciNet review: 866109
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We discuss analogs based on elliptic curves over finite fields of public key cryptosystems which use the multiplicative group of a finite field. These elliptic curve cryptosystems may be more secure, because the analog of the discrete logarithm problem on elliptic curves is likely to be harder than the classical discrete logarithm problem, especially over ${\text{GF}}({2^n})$ . We discuss the question of primitive points on an elliptic curve modulo p, and give a theorem on nonsmoothness of the order of the cyclic subgroup generated by a global point.

[1] Whitfield Diffie and Martin E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory IT-22 (1976), no. 6, 644–654. MR 437208, https://doi.org/10.1109/tit.1976.1055638
[2] Taher ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inform. Theory 31 (1985), no. 4, 469–472. MR 798552, https://doi.org/10.1109/TIT.1985.1057074
[3] Rajiv Gupta and M. Ram Murty, Primitive points on elliptic curves, Compositio Math. 58 (1986), no. 1, 13–44. MR 834046
[4] Neal Koblitz, Introduction to elliptic curves and modular forms, Graduate Texts in Mathematics, vol. 97, Springer-Verlag, New York, 1984. MR 766911
[5] Serge Lang, Elliptic curves: Diophantine analysis, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 231, Springer-Verlag, Berlin-New York, 1978. MR 518817
[6] Emil Artin, The collected papers of Emil Artin, Edited by Serge Lang and John T. Tate, Addison–Wesley Publishing Co., Inc., Reading, Mass.-London, 1965. MR 0176888
[7] S. Lang and H. Trotter, Primitive points on elliptic curves, Bull. Amer. Math. Soc. 83 (1977), no. 2, 289–292. MR 427273, https://doi.org/10.1090/S0002-9904-1977-14310-3
[8] H. W. Lenstra, Jr., "Factoring integers with elliptic curves." (Preprint.)
[9] V. S. Miller, "Use of elliptic curves in cryptography," Abstracts for Crypto '85.
[10] M. Ram Murty, On Artin’s conjecture, J. Number Theory 16 (1983), no. 2, 147–168. MR 698163, https://doi.org/10.1016/0022-314X(83)90039-2
[11] A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Advances in cryptology (Paris, 1984) Lecture Notes in Comput. Sci., vol. 209, Springer, Berlin, 1985, pp. 224–314. MR 825593, https://doi.org/10.1007/3-540-39757-4_20
[12] René Schoof, Elliptic curves over finite fields and the computation of square roots mod 𝑝, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, https://doi.org/10.1090/S0025-5718-1985-0777280-6
[13] J.-P. Serre, Resumé des Cours de l'Année Scolaire, Collège de France, 1977-1978.
[14] Daniel Shanks, Solved and unsolved problems in number theory, 3rd ed., Chelsea Publishing Co., New York, 1985. MR 798284
[15] H. Trotter, personal correspondence and unpublished tables, October 29, 1985.
[16] P. K. S. Wah & M. Z. Wang, Realization and Application of the Massey-Omura Lock, Proc. Internat. Zurich Seminar, March 6-8, 1984, pp. 175-182.