Karatsuba-ZOT Multiplication Algorithm and its Application in Cryptography

Abstract:

The number theory based cryptography algorithms are the most commonly used public-key cryptosystems. One of the fundamental arithmetic operations for such systems is the large integer multiplication. The efficiency of these cryptosystems is directly related to the efficiency of this large integer multiplication operation. Classical multiplication algorithm and Karatsuba multiplication algorithm, and their hybrid, are among the most popular multiplication algorithms used for this purpose. In this paper, we propose a hybrid of Karatsuba and a classical-based multiplication algorithm, enhanced by a new number representation system. The new number representation, known as "Big-Digits”, is used to carry out the sub-multiplication operation in the new multiplication algorithm. Big-Digits has a compact representation with lower Hamming weight. As the result, the number of sub-multiplication operations for the multiplication algorithm that is based on the Big-Digits representation is significantly reduced. Our results show that the proposed multiplication algorithm is significantly faster than the classical, Karasuba and the hybrid of Karatsuba-Classical multiplication algorithms within the implementation domain of the public-key cryptography.

• Periodical: Applied Mechanics and Materials (Volumes 241-244)
• Pages: 2417-2423
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.241-244.2417
• Online since: December 2012
• Authors: Shahram Jahani, Azman Samsudin
• Keywords: Big-Integer Calculation, Hamming Weight, Karatsuba Multiplication Algorithm, Public-Key Cryptography

References

[1] Rivest, R., A. Shamir, and L. Aldeman: A Methoed for Obtaining DigitalSignatures and Public-key Cryptosystems. J. Communications of the ACM, 21(2) (1978). pp.120-126.

DOI: 10.1145/359340.359342

[2] Denis, T.s. and G. Rose: BIGNUM MATH: IMPLEMENTING CRYPTOGRAPHIC MULTIPLE PRECISION ARITHMETIC.(SYNGRESS 2006)

[3] Karatsuba, A. and Y. Ofman: Multiplication of Multidigit Numbers on Automata. Soviet Physics Doklady (English translation), 7(7) (1963). pp.595-596.

[4] Cook, S.A.: On the Minimum Computation Time of Functions, in Mathematics. May 1966, Harvard University.

[5] Schonhage, A. and V. Strassen: Schnelle Multiplikation großer Zahlen. Computing in Science & Engineering, 7 (1971). pp.139-144.

DOI: 10.1007/bf02242355

[6] Knuth, E.: The Art of Computer Programming.(Addison-Wesley 1997)

[7] Fürer, M.: Faster integer multiplication, in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. 2007, ACM: San Diego, California, USA.

DOI: 10.1145/1250790.1250800

[8] Hars, L.: Applications of fast truncated multiplication in cryptography. EURASIP J. Embedded Syst., 2007(1) (2007). pp.3-3.

DOI: 10.1186/1687-3963-2007-061721

[9] Bernstein, D.J.: Multidigit Multiplication for Mathematicians. Advances in Applied Math, (to appear).

[10] Brent, R., et al.: Faster multiplication in GF(2)[x]. in: van der poorten, A,J., Stein, A. (eds.) ANTS-VIII 2008. LNCS, vol. 5011, pp.153-166. Springer, Heidelberg (2008)

[11] Brent, R. and P. Zimmermann: Modern computer arithmetic(June 2008)

[12] Bodrato, M.: Towards Optimal Toom-Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0, in Proceedings of the 1st international workshop on Arithmetic of Finite Fields. (2007), Springer-Verlag: Madrid, Spain.

DOI: 10.1007/978-3-540-73074-3_10

[13] Nedjah, N. and L. de Macedo Mourelle: A review of modular multiplication methods and respective hardware implementation. Informatica, 30(1) (2006). pp.111-129.

[14] Xianjin, F. and L. Longshu. On Karatsuba Multiplication Algorithm. in Data, Privacy, and E-Commerce, (2007). ISDPE 2007. The First International Symposium on. 2007.

DOI: 10.1109/isdpe.2007.11

[15] Karatsuba, A. and Y. Ofman: Multiplication of Many-Digital Numbers by Automatic Computers, in Proceedings of the USSR Academy of Sciences. (1962). pp.293-294.

[16] Cormen, T.H., C.E. Leiserson, and R.L. Rivest: Introduction to Algorithms.(MIT Press 2000)

[17] Mainzer, K.: Thinking in Complexity: The Computational Dynamics of Matter, Mind, and Mankind.(Springer 2007)

[18] Levitin, A.V.: Introduction to the Design and Analysis of Algorithms.(Addison Wesley 2002)

[19] Brent, R.P.: Fast multiple-precision evaluation of elementary functions. Journal of the ACM, 23 (1976). pp.242-251.

DOI: 10.1145/321941.321944

[20] J. Von, J.S.: Fast Arithmetic for Polynomials Over F2 in Hardware, in In Proc. IEEE Information Theory Workshop. 2002.

[21] Ehtiba, F.O. and S. Azman: Multiplication and exponentiation of big integers with hybrid Montgomery and distributed Karatsuba algorithm, in Information and Communication Technologies: From Theory to Applications. (2004), Proceedings. 2004 International Conference.

DOI: 10.1109/ictta.2004.1307811

[22] Zura, D.: More on Squaring and Multiplying Large Integers. IEEE Transactions on Computers, 43(8) (August 1994). pp.899-908.

DOI: 10.1109/12.295852

[23] Sadiq, M. and J. Ahmed: Complexity Analysis of Multiplication of Long Integers. Asian Jurnal of Information Technology, 5(2) (2006).

[24] Montgomery, P.L.: Five, six, and seven-term Karatsuba-like formulae. Computers, IEEE Transactions on, 54(3) (2005). pp.362-369.

DOI: 10.1109/tc.2005.49

[25] Haining, F. and A. Hasan: Comments on "Five, Six, and Seven-Term Karatsuba-Like Formulae'. Computers, IEEE Transactions on, 56(5) (2007). pp.716-717.

DOI: 10.1109/tc.2007.1024

[26] Bernstein, D.J., in: Advances in Cryptology - Crypto 2009, S. Halevi, Editor. (2009), Springer-Verlag Berlin: Berlin. pp.317-336.

[27] Jahani, S.: ZOT-MK: A New Algorithm for Big Integer Multiplication, in Department of Computer Science. (June 2009), Universiti Sains Malaysia: Penang.