Efficient big integer multiplication and squaring algorithms for cryptographic applications. (English) Zbl 1437.94068

Summary: Public-key cryptosystems are broadly employed to provide security for digital information. Improving the efficiency of public-key cryptosystem through speeding up calculation and using fewer resources are among the main goals of cryptography research. In this paper, we introduce new symbols extracted from binary representation of integers called Big-ones. We present a modified version of the classical multiplication and squaring algorithms based on the Big-ones to improve the efficiency of big integer multiplication and squaring in number theory based cryptosystems. Compared to the adopted classical and Karatsuba multiplication algorithms for squaring, the proposed squaring algorithm is 2 to 3.7 and 7.9 to 2.5 times faster for squaring 32-bit and 8-Kbit numbers, respectively. The proposed multiplication algorithm is also 2.3 to 3.9 and 7 to 2.4 times faster for multiplying 32-bit and 8-Kbit numbers, respectively. The number theory based cryptosystems, which are operating in the range of 1-Kbit to 4-Kbit integers, are directly benefited from the proposed method since multiplication and squaring are the main operations in most of these systems.


94A60 Cryptography
68P25 Data encryption (aspects in computer science)


Full Text: DOI


[1] Boudriga, N., Security of mobile communications, Proceedings of the IEEE International Conference on Signal Processing and Communications (ICSPC ’07)
[2] Li, L.; Tao, L., Security study of mobile business based on WPKI, Proceedings of the 8th International Conference on Mobile Business (ICMB ’09)
[3] Rivest, R. L.; Shamir, A.; Adleman, L., A method for obtaining digital signatures and public-key cryptosystems, Communications of the Association for Computing Machinery, 21, 2, 120-126 (1978) · Zbl 0368.94005
[4] Diffie, W.; Hellman, M. E., New directions in cryptography, Institute of Electrical and Electronics Engineers, 22, 6, 644-654 (1976) · Zbl 0435.94018
[5] ElGamal, T., A public key cryptosystem and a signature scheme based on discrete logarithms, Advances in Cryptology. Advances in Cryptology, Lecture Notes in Computer Science, 196, 10-18 (1985) · Zbl 1359.94590
[6] Gordon, D. M., A survey of fast exponentiation methods, Journal of Algorithms, 27, 1, 129-146 (1998) · Zbl 0915.11064
[7] Nedjah, N.; de Macedo Mourelle, L., A review of modular multiplication methods and respective hardware implementations, Informatica, 30, 1, 111-129 (2006) · Zbl 1111.68303
[8] Chang, T.-J.; Wu, C.-L.; Lou, D.-C.; Chen, C.-Y., A low-complexity LUT-based squaring algorithm, Computers & Mathematics with Applications, 57, 9, 1494-1501 (2009) · Zbl 1186.94430
[9] Zhengbing, H.; Al Shboul, R. M.; Shirochin, V. P., An efficient architecture of 1024-bits cryptoprocessor for RSA cryptosystem based on modified Montgomery’s algorithm, Proceedings of the 4th IEEE Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS ’07)
[10] Bajard, J.-C.; Imbert, L., A full RNS implementation of RSA, IEEE Transactions on Computers, 53, 6, 769-774 (2004)
[11] Szabo, N. S.; Tanaka, R. I., Residue Arithmetic and Its Applications to Computer Technology (1967), McGraw-Hill · Zbl 0168.15303
[12] Montgomery, P. L., Modular multiplication without trial division, Mathematics of Computation, 44, 170, 519-521 (1985) · Zbl 0559.10006
[13] Barrett, P., Implementing the Rivest, Shamir and Aldham public-key encryption algorithm on standard digital signal processor, Proceedings of CRYPTO’86
[14] Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A., Handbook of Applied Cryptography (1997), New York, NY, USA: CRC Press, New York, NY, USA · Zbl 0868.94001
[15] Knuth, E., The Art of Computer Programming (1997), Addison-Wesley · Zbl 0883.68015
[16] Karatsuba, A.; Ofman, Y., Multiplication of multidigit numbers on automata, Soviet Physics Doklady, 7, 7, 595-596 (1963)
[17] Toom, A. L., The complexity of a scheme of functional elements realizing the multiplication of integers, Soviet Mathematics, 3, 714-716 (1963) · Zbl 0203.15604
[18] Cook, S. A., On the minimum computation time of functions [Ph.D. thesis] (May 1966), Department of Mathematics, Harvard University
[19] Schonhage, A.; Strassen, V., Schnelle Multiplikation großer Zahlen, Computing in Science & Engineering, 7, 139-144 (1971) · Zbl 0223.68007
[20] Karatsuba, A.; Ofman, Y., Multiplication of many-digital numbers by automatic computers, USSR Academy of Sciences, 145, 293-294 (1962)
[21] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (2000), MIT Press
[22] Levitin, A. V., Introduction to the Design and Analysis of Algorithms (2002), Addison Wesley
[23] Brent, R. P., Fast multiple-precision evaluation of elementary functions, Journal of the Association for Computing Machinery, 23, 2, 242-251 (1976) · Zbl 0324.65018
[24] Von Zur Gathen, J.; Shokrollahi, J., Fast arithmetic for polynomials over F2in hardware, Proceedings of the IEEE Information Theory Workshop (ITW ’06)
[25] Zuras, D., More on squaring and multiplying large integers, IEEE Transactions on Computers, 43, 8, 899-908 (1994) · Zbl 1066.68507
[26] Sadiq, M.; Ahmed, J., Complexity analysis of multiplication of long integers, Asian Journal of Information Technology, 5, 2 (2006)
[27] Yang, W.; Hseih, P.; Laih, C., Efficient squaring of large integers, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E87-A, 5, 1189-1192 (2004)
[28] Rampersad, N.; Shallit, J.; Wang, M. W., Avoiding large squares in infinite binary words, Theoretical Computer Science, 339, 1, 19-34 (2005) · Zbl 1099.68080
[29] Zuras, D., On squaring and multiplying large integers, Proceedings of the IEEE 11th Symposium on Computer Arithmetic
[30] Jahani, S., ZOT-\(M_K\): a new algorithm for big integer multiplication [dissertation] (2009), Universiti Sains Malaysia
[31] Jahani, S.; Samsudin, A., Karatsuba multiplication algorithm based on the big-digits and its application in cryptography, Proceedings of the 3rd International Conference on Cryptology & Computer Security (Cryptology ’12)
[32] Jahani, S.; Samsudin, A., Karatsuba-ZOT multiplication algorithm and its application in cryptography, Applied Mechanics and Materials, 241-244, 2417-2423 (2013)
[33] Matsumoto, M.; Nishimura, T., Mersenne Twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation, 8, 1, 3-30 (1998) · Zbl 0917.65005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.