Potential Vulnerability of Encrypted Messages: Decomposability of Discrete Logarithm Problems

Boris S. Verkhovsky

.

DOI: 10.4236/ijcns.2010.38086                

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.

Keywords

Network Vulnerability, System Security, Discrete Logarithm, Integer Factorization, Multi-Level Decomposition, Complexity Analysis

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	W. Diffie and M. E. Hellman, “New Directions in Cry- ptography,” IEEE Transactions on Information Theory, Vol. 22, No. 6, 1976, pp. 644-654.
[2]	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.
[3]	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.
[4]	E. Bach, “Discrete Logarithms and Factoring,” Technical Report: CSD-84-186, University of California, Berkeley, 1984.
[5]	R. Crandall and C. Pomerance, “Prime Numbers: A Com- putational Perspective,” The Quadratic Sieve Factorization Method, Springer, Berlin, 2001, pp. 227- 244.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	O. Schirokauer, “Using Number Fields to Compute Log- arithms in Finite Fields,” Mathematics of Computation, Vol. 69, No. 231, 2000, pp. 1267-1283.
[11]	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.
[12]	J. Silverman, “The xedni Calculus and the Elliptic Curve Discrete Logarithm Problem,” Designs, Codes and Cryptography, Vol. 20, No. 1, 2000, pp. 5-40.
[13]	D. C. Terr, “A Modification of Shanks’ Baby-Step Giant- Step Algorithm,” Mathematics of Computation, Vol. 69, No. 230, 2000, pp. 767-773.
[14]	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.
[15]	R. Zuccherato, “The Equivalence between Elliptic Curve and Quadratic Function Field Discrete Logarithms in Characteristic 2,” Algorithmic Number Theory Seminar ANTS-III, Lecture Notes in Computer Science, Springer, Berlin, Vol. 1423,1998, pp. 621-638.
[16]	J. P. Pollard, “A Monte Carlo Method for Factorization,” BIT Numerical Mathematics, Vol. 15, No. 3, 1975, pp. 331-334.
[17]	C. Pomerance, J. W. Smith and R. Tuler, “A Pipeline Architecture for Factoring Large Integers with the Quadratic Sieve Algorithm,” SIAM Journal on Computing, Vol. 17, No. 2, 1988, pp. 387-403.
[18]	B. Verkhovsky, “Multiplicative Inverse Algorithm and its Complexity,” Proceedings of International Conference on System Research, Informatics & Cybernetics, Baden- Baden, 28-30 July 1999, pp. 62-67.