An Analytical Study of the Gaussian Integer Method of Index Calculus for the Discrete Logarithm Problem in a Prime Field
Keywords:
Cryptography, Cryptanalysis, Gaussian Integer Method, Index Calculus, Prime Fields, AlgorithmsAbstract
This research investigates application of the Gaussian integer method under the index calculus approach for discrete logarithm problem in a prime field. For a prime field $GF(p)$ of prime order $p$, and $g$ a primitive element of $GF(p)$, the discrete logarithm base $g$ of an arbitrary non-zero $y \in GF(p)$ is an integer $x$, $0 \leq x \leq p-2$, such that $g^x = y$ in $GF(p)$. It explored the different cryptographic applications and schemes, and analyzes the index calculus method with appropriate examples. This work showcases different algorithms to simplify the discrete logarithmic problem with their advantages and backdraws. The security of many real-world cryptographic schemes depends on the difficulty of computing discrete logarithms in large finite fields. This project is a study of the discrete logarithm problem in prime field with Gaussian Integer Method of Index Calculus and implementation of this method in NTL(Number Theory Library) with C++ programming language, also comparison with other implemented methods to solve discrete logarithms.References
[1] D. Coppersmith, A.M. Odlyzko, and Schroeppel : ``Discrete logarithms in GF(p)" Algorithmica 1: 1-1.5(1986).
[2] B.A. LaMacchia and A.M. Odlyzko : ``Computation of discrete logarithms in prime fields", Designs, Codes and Cryptography, 1, 47-62 (1991).
[3] K. McCurley : ``The discrete logarithm problem", Cryptology and Computational Number Theory, Proceedings of Symposia in Applied Mathematics, American Mathematical Society, 1990.
[4] A. M. Odlyzko : ``Discrete logarithms in finite fields and their cryptographic significance" to appear, Proceedings of Eurocrypt' 84, Springer Lecture Notes in Computer Science.
[5] W. Diffie and M. E. Hellman, ``New directions in cryptography",IEEE Trans. Inform. Theory, IT-22, 644-654(1976).
[6] John Brillhart : ``Note on representing a prime as a sum of two squares", Mathematics of computation, vol 26, 1972.
[7] Dean Phillip Reiff : ``Discrete logarithm in finite field",thesis, University of Colorado at Denver, 1996.
[8] LaMaecbla, 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-Vedag.
[9] T. ElGamal, ``A public key cryptosystem and a signature scheme based on discrete logarithms", IEEE Trans. Info. Theory 31 (1985), 469-472.
[10] P. Van Oorschot, ``A comparison of practical public key cryptosystems based on integer factorization and discrete logarithms", pp. 289-322 in Contemporary Cryptology: The Science of Integrity, G.J. Simmons. ed., IEEE Press, New York, 1992.
[11] D.Coppersmith, ``Fast evaluation of logarithms in fields of characteristic two", IEEE Transactions on Information Theory 30 (1984), 587-594.
