Skip to main content
SpringerLink
Log in

Computation of discrete logarithms in prime fields

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

The presumed difficulty of computing discrete logarithms in finite fields is the basis of several popular public key cryptosystems. The secure identification option of the Sun Network File System, for example, uses discrete logarithms in a field GF(p) with p a prime of 192 bits. This paper describes an implementation of a discrete logarithm algorithm which shows that primes of under 200 bits, such as that in the Sun system, are very insecure. Some enhancements to this system are suggested.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Adleman, L.M. (forthcoming). Factoring numbers using singular integers. Proc. 23rd ACM Symp. Theory of Computing.

  • Barrett, P. 1987. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. Advances in Cryptology: Proceedings of Crypto '86, (A.M. Odlyzko, ed.), Lecture Notes in Computer Science 263, New York: Springer-Verlag, pp. 311–323.

    Google Scholar 

  • Bauspiess, F., and Knobloch, H.-J. 1990. How to keep authenticity alive in a computer network. Advances in Cryptology: Proceedings of Eurocrypt '89, (J.-J. Quisquater, J. Vandewalle, eds.), Lecture Notes in Computer Science 434, New York: Springer-Verlag, pp. 38–46.

    Google Scholar 

  • Beth, T. 1988. Efficient zero-knowledge identification scheme for smart cards. Advances in Cryptology: Proceedings of Eurocrypt '88, (C.G. Günther, ed.), Lecture Notes in Computer Science 330, New York: Springer-Verlag, pp. 77–84.

    Google Scholar 

  • Blake, I.F., Fuji-Hara, R., Mullin, R.C., and Vanstone, S.A. 1984. Computing logarithms in fields of characteristic two. SIAM J. Alg. Disc. Methods 5: 276–285.

    Google Scholar 

  • Bos, J., and Coster, M. 1990. Addition chain heuristics. Advances in Cryptology: Proceedings of Crypto '89, (G. Brassard, ed.), Lecture Notes in Computer Science 435, New York: Springer-Verlag, pp. 400–407.

    Google Scholar 

  • Brandt, J., Damgard, I., Landrock, P., and Pedersen, T. 1989. Zero-knowledge authentication scheme with secret key exchange. Advances in Cryptology: Proceedings of Crypto '88, (S. Goldwasser, ed.), Lecture Notes in Computer Science 403, New York: Springer-Verlag, pp. 583–588.

    Google Scholar 

  • Brickell, E.F. 1990. A survey of hardware implementations of RSA (Abstract). Advances in Cryptology: Proceedings of Crypto '89, (G. Brassard, ed.), Lecture Notes in Computer Science 435, New York: Springer-Verlag, pp. 368–370.

    Google Scholar 

  • Brickell, E.F., and McCurley, K.S. (forthcoming). An interactive identification scheme based on discrete logarithms and factoring. Advances in Cryptology: Proceedings of Eurocrypt '90, (I. Damgard, ed.), Lecture Notes in Computer Science, New York: Springer-Verlag.

  • Coppersmith, D. 1984. Fast evaluation of discrete logarithms in fields of characteristic two. IEEE Transactions on Information Theory 30: 587–594.

    Google Scholar 

  • Coppersmith, D. (forthcoming). Modifications to the number field sieve. J. Cryptology.

  • Coppersmith, D., Odlyzko, A., and Schroeppel, R. 1986. Discrete logarithms in GF(p). Algorithmica 1: 1–15.

    Google Scholar 

  • Denning, D., and Sacco, G. 1981. Timestamps in key distribution protocols. Communications of the ACM 24: 533–536.

    Google Scholar 

  • Diffie, W., and Hellman, M. 1976. New directions in cryptography. IEEE Transactions on Information Theory 22: 472–492.

    Google Scholar 

  • ElGamal, T. 1985. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31: 469–472.

    Google Scholar 

  • ElGamal, T. 1985. A subexponential-time algorithm for computing discrete logarithms over GF(p 2). IEEE Transactions on Information Theory 31: 473–481.

    Google Scholar 

  • Fiat, A., and Shamir, A. 1987. How to prove yourself: practical solution to identification and signature problems. Advances in Cryptology: Proceedings of Crypto '86, (A.M. Odlyzko, ed.), Lecture Notes in Computer Science 263, New York: Springer-Verlag, pp. 186–199.

    Google Scholar 

  • Gordon, D.M. (forthcoming). Discrete logarithms in GF(p) using the number field sieve.

  • Guillou, L.C., and Quisquater, J.-J., 1989. A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. Advances in Cryptology: Proceedings of Eurocrypt '88, (C. Günther, ed.), Lecture Notes in Computer Science 330, New York: Springer-Verlag, pp. 127–141.

    Google Scholar 

  • Günther, C.G. 1990. An identity-based key-exchange protocol. Advances in Cryptology: Proceedings of Eurocrypt '89, (J.-J. Quisquater, J. Vandewalle, eds.), Lecture Notes in Computer Science 434, New York: Springer-Verlag, pp. 29–37.

    Google Scholar 

  • Knuth, D.E. 1981. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. (2nd ed.), Reading, MA: Addison-Wesley.

    Google Scholar 

  • Koblitz, N. 1987. Elliptic curve cryptosystems. Math. Comp. 48: 203–209.

    Google Scholar 

  • Koyama, K., and Ohta, K. 1988. Identity-based conference key distribution systems. Advances in Cryptology: Proceedings of Crypto '87, (C. Pomerance, ed.), Lecture Notes in Computer Science 293, New York: Springer-Verlag, pp. 175–194.

    Google Scholar 

  • LaMacchia, B.A., and Odlyzko, A.M. (forthcoming). Solving large sparse linear systems over finite fields, Advances in Cryptology: Proceedings of Crypto '90, (A. Menezes, S. Vanstone, eds.), Lecture Notes in Computer Science, New York: Springer-Verlag.

  • Lenstra, A.K., Lenstra, H.W. Jr., Manasse, M.S., and Pollard, J.M. 1990. The number field sieve. Proc. 22nd ACM Symp. Theory of Computing, 564–572.

  • Lenstra, A.K., and Manasse, M.S. 1990. Factoring by electronic mail. Advances in Cryptology: Proceedings of Eurocrypt '89, (J.-J. Quisquater, J. Vandewalle, eds.), Lecture Notes in Computer Science 434, New York: Springer-Verlag, pp. 355–371.

    Google Scholar 

  • Lenstra, A.K., and Manasse, M.S. (forthcoming). Factoring with two large primes. Advances in Cryptology: Proceedings of Eurocrypt '90, (I. Damgard, ed.), Lecture Notes in Computer Science, New York: Springer-Verlag.

  • McCurley, K.S. (forthcoming). The discrete logarithm problem. In Cryptography and Computational Number Theory, (C. Pomerance, ed.), Proc. Symp. tAppl. Math. 42, Amer. Math. Soc., 1990, pp. 49–74.

  • Menezes, A., Vanstone, S., and Okamoto, T. (forthcoming). Reducing elliptic curve logarithms to logarithms in a finite field. Proc. 23rd ACM Symp. Theory of Computing.

  • Micali, S., and Shamir, A. 1989. An improvement of the Fiat-Shamir identification and signature scheme. Advances in Cryptology: Proceedings of Crypto '88, (S. Goldwasser, ed.), Lecture Notes in Computer Science 403, New York: Springer-Verlag, pp. 244–247.

  • Miller, V. 1986. Use of elliptic curves in cryptography. Advances in Cryptology: Proceedings of Crypto '85, (H.C. Williams, ed.), Lecture Notes in Computer Science 218, New York: Springer-Verlag.

    Google Scholar 

  • Montgomery, P.L. 1985. Modular multiplication without trial division. Math. Comp. 44: 519–521.

    Google Scholar 

  • Needham, R., and Schroeder, M. 1978. Using encryption for authentication in large networks of computers. Comm. ACM 21: 993–999.

    Google Scholar 

  • Odlyzko, A.M. 1985. Discrete logarithms in finite fields and their cryptographic significance. Advances in Cryptology: Proceedings of Eurocrypt '84, (T. Beth, N. Cot, I. Ingemarsson, eds.), Lecture Notes in Computer Science 209, New York: Springer-Verlag, pp. 224–314.

    Google Scholar 

  • Okamoto, E. 1988. Key distribution systems based on identification information. Advances in Cryptology: Proceedings of Crypto '87, (C. Pomerance, ed.), Lecture Notes in Computer Science 293, New York: Springer-Verlag, pp. 194–202.

    Google Scholar 

  • Okamoto, E., and Tanaka, K. 1989. Key distribution system based on identification information. IEEE J. Selected Areas Commun. SAC-7: 481–485.

    Google Scholar 

  • Pollard, J.M. 1988. Factoring with cubic integers (parts I and II). Unpublished manuscripts, August 1988 and December 1988.

  • Schnorr, C.P. 1990. Efficient identification and signatures for smart cards. Advances in Cryptology: Proceedings of Crypto '89, (G. Brassard, ed.), Lecture Notes in Computer Science 435, New York: Springer-Verlag, pp. 239–251.

    Google Scholar 

  • Taylor, B., and Goldberg, D. 1986. Secure networking in the Sun environment. Proc. USENIX Assoc. Summer Conference, Atlanta, pp. 28–37.

  • Tsujii, S., and Itoh, T. 1989. An ID-based cryptosystem based on the discrete logarithm problem. IEEE J. Selected Areas Comm. SAC-8: 467–473.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Massachusetts Institute of Technology, 02139, Cambridge, MA, USA

    B. A. LaMacchia

  2. AT&T Bell Laboratories, 07974, Murray Hill, New Jersey, USA

    A. M. Odlyzko

Authors
  1. B. A. LaMacchia
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. M. Odlyzko
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by S. Vanstone

Rights and permissions

Reprints and permissions

About this article

Cite this article

LaMacchia, B.A., Odlyzko, A.M. Computation of discrete logarithms in prime fields. Des Codes Crypt 1, 47–62 (1991). https://doi.org/10.1007/BF00123958

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00123958

Keywords

Search

Navigation