Abstract
The difficulty of computing discrete logarithms known to be “short” is examined, motivated by recent practical interest in using Diffie-Hellman key agreement with short exponents (e.g. over Z p with 160-bit exponents and 1024-bit primes p). A new divide-and-conquer algorithm for discrete logarithms is presented, combining Pollard’s lambda method with a partial Pohlig-Hellman decomposition. For random Diffie-Hellman primes p, examination reveals this partial decomposition itself allows recovery of short exponents in many cases, while the new technique dramatically extends the range. Use of subgroups of large prime order precludes the attack at essentially no cost, and is the recommended solution. Using safe primes also precludes this particular attack and allows improved exponentiation performance, although parameter generation costs are dramatically higher.
Chapter PDF
Similar content being viewed by others
References
A. Aziz, “Simple Key Management for Internet Protocols (SKIP)”, Internet Draft (work in progress), draft-ietf-ipsec-skip-04.txt, November 1995.
A. Bosselaers, R. Govaerts, J. Vandewalle, “Comparison of three modular reduction functions”, Crypto’93, Springer-Verlag LNCS 773, pp.175–176.
W. Diffie, M. Hellman, “New directions in cryptography”, IEEE IT-22 (1976) pp.644–654.
J. Hastad, “On using RSA with low exponent in a public-key network”, Crypto’85. Springer-Verlag LNCS 218, pp.403–408.
R. Heiman, “A note on discrete logarithms with special structure”, Eurocrypt’92, Springer-Verlag LNCS 658, pp.454–457.
P. Karn, W.A. Simpson, “The Photuris session key management protocol”. Internet Draft (work in progress), draft-ietf-ipsec-photuris-06.txt, October 1995.
D.E. Knuth, The Art of Computer Programming, vol.2: Seminumerical Algorithms, 2nd edition, Addison-Wesley, 1981.
D.E. Knuth, The Art of Computer Programming, vol.3: Sorting and Searching, Addison-Wesley, 1973.
B.A. LaMacchia, A.M. Odlyzko, “Computation of discrete logarithms in prime fields”, Designs, Codes and Cryptography, vol.1 no.1 (May 1991), pp.47–62.
K.S. McCurley, “The discrete logarithm problem”, pp.49–74 in: Cryptology and Computational Number Theory — Proc. Symp. Applied Math., vol. 42 (1990). AMS.
A.K. Lenstra, M.S. Manasse, “Factoring by electronic mail”, Eurocrypt’89. Springer-Verlag LNCS 434, pp.355–371.
U.M. Maurer, “Towards the equivalence of breaking the Diffie-Hellman protocol and computing discrete logarithms”. Crypto’94, Springer-Verlag LNCS 839. pp.271–281.
U.M. Maurer, “Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters”, J. Cryptology, vol.8 no.3 (1995), 123–156.
S.C. Pohlig, M.E. Hellman, “An improved algorithm for computing logarithms over GF(p) and its cryptographic significance”, IEEE Trans. Information Theory, vol. IT-24, no.1 (Jan. 1978), pp.106–110.
J.M. Pollard, “Monte Carlo methods for index computation (mod p)”, Math. Comp., vol.32 no.143 (July 1978) pp.918–924.
R.L. Rivest, A. Shamir, L. Adleman, “A method for obtaining digital signatures and public key cryptosystems”, C.ACM, vol.21 no.2 (Feb. 1978), pp.120–126.
R. Rueppel, P.C. van Oorschot, “Modern key agreement techniques”, Computer Communications, vol.17 no.7 (July 1994), pp.458–465.
C.P. Schnorr, “Efficient signature generation by smart cards”, J. Cryptology vol.4 (1991), pp.161–174.
U.S. Department of Commerce / N.I.S.T., Digital Signature Standard, FIPS 186, National Technical Information Service, Springfield, Virginia, May 1994.
P.C. van Oorschot, M.J. Wiener, “Parallel collision search with application to hash functions and discrete logarithms”, Proc. 2nd ACM Conference on Computer and Communications Security (Nov. 1994), Fairfax, VA, pp.210–218.
M.J. Wiener, “Cryptanalysis of short RSA secret exponents”, IEEE Trans. on Info. Theory, vol.36 no.3 (May 1990), pp.553–558.
Y. Yacobi, “Discrete-log with compressible exponents”, Crypto’90, Springer-Verlag LNCS 537, pp.639–643.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
van Oorschot, P.C., Wiener, M.J. (1996). On Diffie-Hellman Key Agreement with Short Exponents. In: Maurer, U. (eds) Advances in Cryptology — EUROCRYPT ’96. EUROCRYPT 1996. Lecture Notes in Computer Science, vol 1070. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-68339-9_29
Download citation
DOI: https://doi.org/10.1007/3-540-68339-9_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61186-8
Online ISBN: 978-3-540-68339-1
eBook Packages: Springer Book Archive
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.