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 Zp 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.

Additional Metadata
Series Lecture Notes in Computer Science
Citation
Van Oorschot, P, & Wiener, M.J. (Michael J.). (1996). On diffie-hellman key agreement with short exponents. In Lecture Notes in Computer Science.