Research ArticleOpen AccessGoogle Scholar indexed
Potential Vulnerability of Encrypted Messages: Decomposability of Discrete Logarithm Problems
- 1
International Journal of Communications, Network and System Sciences·Volume 03 (2010)·Pages 639–644·Published 31 August 2010·DOI10.4236/ijcns.2010.38086
Copy link · social · email
Abstract
This paper provides a framework that reduces the computational complexity of the discrete logarithm problem. The paper describes how to decompose the initial DLP onto several DLPs of smaller dimensions. Decomposability of the DLP is an indicator of potential vulnerability of encrypted messages transmitted via open channels of the Internet or within corporate networks. Several numerical examples illustrate the frame- work and show its computational efficiency.
KeywordsNetwork VulnerabilitySystem SecurityDiscrete LogarithmInteger FactorizationMulti-Level DecompositionComplexity Analysis
- W. Diffie and M. E. Hellman, “New Directions in Cry- ptography,” IEEE Transactions on Information Theory, Vol. 22, No. 6, 1976, pp. 644-654.
- T. ElGamal, “A Public Key Cryptosystem and a Digital Signature Scheme Based on Discrete Logarithms,” IEEE Transactions on Information Theory, Vol. 31, No. 4, 1985, pp. 469-472.
- L. M. Adleman and J. DeMarrais, “A Sub-Exponential Algorithm for Discrete Logarithms over all Finite Fields,” Mathematics of Computation, Vol. 61, No. 203, 1993, pp. 1-15.
- E. Bach, “Discrete Logarithms and Factoring,” Technical Report: CSD-84-186, University of California, Berkeley, 1984.
- R. Crandall and C. Pomerance, “Prime Numbers: A Com- putational Perspective,” The Quadratic Sieve Factorization Method, Springer, Berlin, 2001, pp. 227- 244.
- A. Enge and P. Gaudry, “A General Framework for Sub- Exponential Discrete Logarithm Algorithms,” Research Report LIX/RR/00/04, Luxembourg Internet eXchange (LIX), Luxembourg Kirchberg, Vol. 102, June 2000, pp. 83-103.
- B. A. LaMacchia and A. M. Odlyzko, “Computation of Discrete Logarithms in Prime Fields,” Designs, Codes and Cryptography, Vol. 19, No. 1, 1991, pp. 47-62.
- A. K. Lenstra and J. H. W. Lenstra, “The Development of the Number Field Sieve,” Lecture Notes in Mathematics, Springer-Verlag, Berlin, Vol. 1554, 1993, pp. 95-102.
- V. Müller, A. Stein and C. Thiel, “Computing Discrete Logarithms in Real Quadratic Congruence Function Fie- lds of Large Genus,” Mathematics of Computation, Vol. 68, No. 226, 1999, pp. 807-822.
- O. Schirokauer, “Using Number Fields to Compute Log- arithms in Finite Fields,” Mathematics of Computation, Vol. 69, No. 231, 2000, pp. 1267-1283.
- D. Shanks, “Class Number, a Theory of Factorization and Genera,” Proceedings of Symposium in Pure Mathematics, Vol. 20, American Mathematical Society, Providence, 1971, pp. 415-440.
- J. Silverman, “The xedni Calculus and the Elliptic Curve Discrete Logarithm Problem,” Designs, Codes and Cryptography, Vol. 20, No. 1, 2000, pp. 5-40.
- D. C. Terr, “A Modification of Shanks’ Baby-Step Giant- Step Algorithm,” Mathematics of Computation, Vol. 69, No. 230, 2000, pp. 767-773.
- B. Verkhovsky, “Generalized Baby-Step Giant-Step Alg- orithm for Discrete Logarithm Problem,” Advances in Decision Technology and Intelligent Information Systems, International Institute for Advanced Studies in Systems Research and Cybernetics, Baden-Baden, 2008, pp. 88- 89.