CLASSIFICATION OF METHODS FOR SOLVING THE ELLIPTIC CURVE DISCRETE LOGARITHM PROBLEM
DOI:
https://doi.org/10.35546/kntu2078-4481.2024.1.37Keywords:
discrete logarithm problem, cryptography, crypto resistance, elliptic curve, Shanks' method, Pollard's rho method, Pohlig-Hellman method, Las Vegas method, finite fields, Galois fieldsAbstract
In this work, the analysis and classification of methods for solving the discrete logarithm problem in multiplicative and additive groups is carried out, as well as the relevance of such an analysis is substantiated. Special emphasis is placed on solving this problem on elliptic curves over finite fields. The work is aimed at increasing the stability of cryptographic systems by analyzing and classifying existing methods for solving the discrete logarithm problem. The following methods are considered in the article: the brute force method, the Pohlig-Hellman method, the Daniel Shanks method and its modifications, namely the Kangaroo method and the "Two Grumpy Giants and a Baby" method. In addition, the work considers Pollard's rho method and its modification, which involves parallelization in several execution threads, as well as the Las Vegas method – a modern method that uses matrix calculations to solve a discrete logarithm problem. The key aspect of this article is a comprehensive comparative analysis of discrete logarithm methods, the results of the analysis are given in the corresponding tables, where their temporal and spatial complexity, as well as a number of other indicators, are presented. The conducted analysis provides information on the effectiveness, security and practicality of each method, lays the foundation for further research, and also allows building more stable cryptosystems. Pollard's rho algorithm was found to have the best balance between speed and memory usage, and hypotheses were put forward to improve it. The first hypothesis is that when checking for the existence of a collision at each iteration of the algorithm, it is advisable to compare not the points, but their equivalence classes. The second hypothesis of improvement consists in shortening the interval in which the collision occurs. Another promising method for solving the discrete logarithm problem is the Las Vegas method, which has high performance, but this method does not guarantee a solution and has high spatial complexity.
References
Koblitz N. Elliptic curve cryptosystems. Mathematics of Computation. 1987. Vol. 19, No. 177, P. 203–209.
Miller V. Use of elliptic curves in cryptography. Conference on the theory and application of cryptographic techniques: Berlin, Heidelberg: Springer Berlin Heidelberg, August. 1987. Berlin, 1987. P. 417–426.
McCurley K. S., The discrete logarithm problem. In Proc. of Symp. in Applied Math. 1990. Vol. 42, P. 49–74.
Weisstein E. W. Smooth Number. URL: https://mathworld.wolfram.com/SmoothNumber.html.
Shanks D. Class number, a theory of factorization and genera. In Proceedings of symposia Math. Soc. 1971. Vol. 20, P. 415–440.
Galbraith S. D., Wang P., Zhang F. Computing elliptic curve discrete logarithms with improved baby-step giant-step algorithm. ePrint Archive. 2015.
Pollard J. Kangaroos, Monopoly and discrete logarithms. Journal of cryptology. 2000. Vol. 13, No. 4, P. 437–447.
Daniel J. Bernstein et. al. On the Correct Use of the Negation Map in the Pollard rho Method. In Public Key Cryptography 2011: 14th International Conference on Practice and Theory in Public Key Cryptography, Taormina, Italy, March 6–9. 2011. Taormina, 2011. Proc. 14, P. 128–146.
Pollard, J. M. Monte Carlo methods for index computation (
