Enhanced Euclid Algorithm for Modular Multiplicative Inverse and Its Application in Cryptographic Protocols

Boris S. Verkhovsky
DOI: 10.4236/ijcns.2010.312123                

Abstract

Numerous cryptographic algorithms (ElGamal, Rabin, RSA, NTRU etc) require multiple computations of modulo multiplicative inverses. This paper describes and validates a new algorithm, called the Enhanced Euclid Algorithm, for modular multiplicative inverse (MMI). Analysis of the proposed algorithm shows that it is more efficient than the Extended Euclid algorithm (XEA). In addition, if a MMI does not exist, then it is not necessary to use the Backtracking procedure in the proposed algorithm; this case requires fewer operations on every step (divisions, multiplications, additions, assignments and push operations on stack), than the XEA. Overall, XEA uses more multiplications, additions, assignments and twice as many variables than the proposed algorithm.

Keywords

Extended-Euclid Algorithm, Modular Multiplicative Inverse, Public-Key Cryptography, RSA Cryptocol, Rabin Information Hiding Algorithm, ElGamal Encryption/Decryption, NTRU Cryptosystem, Computer Simulation, Low Memory Devices

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	R. Crandall and C. Pomerance, “Prime Numbers: A Computational Perspective,” Springer, Berlin, 2001.
[2]	A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, “Handbook of Applied Cryptography,” CRC Press, Boca Raton, 1997.
[3]	R. L. Rivest, A. Shamir and L. Adleman, “A Method for Obtaining Digital Signature and Public-Key Cryptosystems,” Communications of the ACM, Vol. 21, No. 2, 1978, pp. 120-126.
[4]	B. Verkhovsky, “Overpass-Crossing Scheme for Digital Signature,” Keynote Address, Proceedings of International Conference on System Research, Informatics and Cybernetics, Baden-Baden, 30 July-4 August 2001.
[5]	T. ElGamal, “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms,” IEEE Transactions on Information Theory, Vol. 31, No. 4, 1985, pp. 469-472.
[6]	M. Rabin, “Digitized Signatures and Public Key Functions as Intractable as Factorization,” Technical Report: MIT/LCS/TR-212, MIT Laboratory for Computer Science, Cambridge, 1979.
[7]	J. Hoffstein, J. Pipher and J. H. Silverman, “An Introduction to Mathematical Cryptography,” Springer, Berlin, 2008.
[8]	B. Verkhovsky, “Multiplicative Inverse Algorithm and Its Complexity,” Proceedings of International Conference-InterSYMP-99, Baden-Baden, July 1999, pp. 62-67.
[9]	B. Verkhovsky, “Accelerated Cyber-Secure Communication Based on Reduced Encryption/Decryption and Information Assurance Protocols,” Journal of Telecommunications Management, Vol. 2, No. 3, 2009, pp. 284-293.
[10]	B. Verkhovsky, “Hybrid Authentication Cybersystem Based on Discrete Logarithm, Entanglements and Factorization,” International Journal of Communications, Network and System Sciences, Vol. 3, No. 7, 2010, 579-584.
[11]	B. Verkhovsky, “Generalized Baby-Step Giant-Step Algorithm 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.
[12]	B. Verkhovsky, “Integer Factorization: Solution via Algorithm for Constrained Discrete Logarithm Problem,” Journal of Computer Science, 2009, Vol. 5, No. 9, 674- 679.
[13]	B. Verkhovsky, “Potential Vulnerability of Encrypted Messages: Decomposability of Discrete Logarithm Problems,” International Journal of Communications, Network and System Sciences, Vol. 3, No. 8, 2010, pp. 639-644.
[14]	R. B. McClenon, “Leonardo of Pisa and His Liber Quadratorum,” American Mathematical Monthly, Vol. 26, No. 1, 1919, pp. 1-8.
[15]	D. Harkin, “On the Mathematical Works of Francois- Edouard-Anatole Lucas,” Enseignement Mathematique, Vol. 3, No. 2, 1957, pp. 276-288.