Discrete logarithm problem over finite prime fields
Catherine Margaret McCulloch · QUT ePrints (Queensland University of Technology) · 1998
Difficulty in solving the discrete logarithm problem has led to its use in key exchange, public key cryptography and digital signatures. To measure the security of these algorithms, it is necessary to evaluate the methods currently available for attack. Although the applications of the discrete logarithm problem can be implemented in a variety of different groups, only implementations over multiplicative integers modulo a large prime p are considered. The object of this work is to review the current methods of solving the discrete logarithm problem - key exhaustion, Shanks' baby-step giant-step algorithm, Pollard's rho algorithm, the Silver Pohlig Hellman algorithm, index calculus methods and the general number field sieve. The resulting document contains all relevant mathematics, theorems and algorithms. As only one workstation is used, the problem will not be solved for large primes, but an indication of the relative strengths and weaknesses of each algorithm will be gained. Both the theoretical and practical issues were considered when comparing the attacks available. The algorithms were implemented using the computer algebra system "Magma", which was developed at the University of Sydney. Magma was chosen as it is a flexible package that is not restricted to group theory. The source code is included in Appendix B. The simplest methods to implement are key exhaustion, which relies on testing all possibilities, and the first improvement on this method - Shank's baby-step giant-step algorithm. Both methods are infeasible when the prime number is large. Pollard's rho algorithm, again impractical for large p, has the same expected running time as Shank's baby-step giant-step algorithm, but the storage requirements are negligible. The Silver Pohlig Hellman algorithm which is again impractical for a large p unless p-1 has small factors is also covered. Index calculus methods offer improvements in the time involved to attack the system, once the prime number becomes too large for the earlier methods. Unlike the previous algorithms, the index calculus methods are not generic, they can only be used for particular groups, one of which is the field GF(p ), considered here. The methods involve two parts, a costly precomputation stage that needs to be performed only once for each prime, and the calculation of the individual logarithm. Three methods are investigated - the first by McCurley, the second by Coppersmith, Odlyzko and Schroeppel, and the third by LaMacchia and Odlyzko. By attacking with these methods, primes with fewer than 200 bits are insecure and primes with less than 512 bits should be avoided. By adapting the general number field sieve to solve logarithms, the running time of the attack in some instances can be further improved. Unlike the index calculus methods, the time required for the precomputation and that required for the evaluation of the individual logarithm, are similar. This perhaps reduces the usefulness of the algorithm in the case where the same attack is to be implemented a number of times to determine several different logarithms. If the same prime is to be used for a number of attacks, it may be quicker to use an index calculus method as the precomputation is performed once and then the logarithms can be quickly calculated.