The alternative method to speed up RSA’s decryption process

Somsuk, Kritsanapong

doi:10.1080/09720529.2021.1962026

Open Access Research Article

The alternative method to speed up RSA’s decryption process

^*Kritsanapong SomsukCorresponding authorkritsanapong@udru.ac.thDepartment of Computer and Communication EngineeringFaculty of TechnologyUdon Thani Rajabhat UniversityUDRU, Udon Thani, Thailand0000-0002-7264-4628View full profile →

* Corresponding author · click or hover a name for details

pp. 1005–1026Vol. 26Issue 4June 2023DOI: 10.1080/09720529.2021.1962026 Crossmark XML

Received:: 01 Feb 2021
Accepted:: 01 Jun 2021
Published Online:: 08 Mar 2022
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-1425
Pages:: 1005–1026

Abstract

The aim of this paper is to propose the special methods to speed up RSA’ s decryption process. In fact, this method gives the option of selecting the best parameters to recover the plaintext. Assuming that the new integer has a lower Hamming Weight than the private key and is mathematically related to the private key, it will be used as the exponent in the decryption process instead of the private key. Furthermore, this method can be used in conjunction with the Chinese Remainder Theorem (CRT) to determine the best exponents. In addition, a method derived from the Square and Multiplication Algorithm is proposed to compute modular exponentiation in order to reduce computation time. However, this method can be performed when number 1 of the exponent’s binary value is not adjacent to each other. Assuming that the new integers for CRT have the lowest Hamming Weight, the experimental results show that if the proposed integers meet the condition, the proposed method is the best algorithm for completing the task. Furthermore, when 2048 bits of modulus is chosen and compared to CRT, the average time is reduced about 8%. Moreover, three-fourths of the cases require the proposed method with CRT in order to save the most computation costs on the decryption side. As a result, the proposed method is very likely to be chosen to complete the decrypting task.

Keywords

RSA Decryption process Modular multiplication Modular exponentiation Modular square

Subject Classifications

94A60 (Cryptography)00A69 (General applied mathematics)68M25 (Computer security)

References

[1] R.L. Rivest, A. Shamir and L. Adleman, “A method for obtaining digital signatures and public key cryptosystems”, Communications of ACM, vol. 21, pp. 120 – 126, 1978.
[2] V. Guleria, S. Sabir and D.C. Mishra, “Security of multiple RGB images by RSA cryptosystem combined with FrDCT and Arnold transform”, Journal of Information Security and Applications, vol. 54, pp. 1 – 13, 2020.
[3] L. Yang, T. Shanyu, L. Ran, Z. Liping and M. Zhao, “Secure and robust digital image watermarking scheme using logistic and RSA encryption”, Expert Systems with Applications, vol. 97, pp. 95 - 105, 2018.
[4] K. Jiao, G. Ye, Y. Dong, X. Huang and J. He, “Image Encryption Scheme Based on a Generalized Arnold Map and RSA Algorithm”, Security and Communication Networks, vol. 2020, pp. 1 - 14, 2020.
[5] Y. Wang and Z. Tan, “Modified RSA Encryption Algorithm Based on Chaos and Its Application in Voice Encryption System”, in Proc. of International Conference on Computational Intelligence and Security, pp. 439 - 444, November 16 – 19, 2018.
[6] H. Om, and M.R. Reddy, “RSA based remote password authentication using smart card”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 15, pp. 105-111, 2012 .
[7] F.J. Aufa, Endroyono and A. Affandi, “Security System Analysis in Combination Method: RSA Encryption and Digital Signature Algorithm”, in Proc. of International Conference on Science and Technology, pp. 1-5, November 15, 2018.
[8] K.G. Chol, L.S. Chol and H.H. Cho, “Fast rebalanced RSA signature scheme with typical prime generation”, Theoretical Computer Science, vol. 830 - 831, pp.1 - 19, 2020.
[9] S.M. Sedjelmaci, “On a parallel extended Euclidean algorithm”, in Proc. of ACS/IEEE International Conference on Computer Systems and Applications, pp. 235 - 241, June 25 – 29, 2001.
[10] D. Chandravathi and P.V. Lakshmi, “Privacy Preserving Using Extended Euclidean Algorithm Applied To RSA-Homomorphic Encryption Technique”, International Journal of Innovative Technology and Exploring Engineering, vol. 8, pp.3175 - 3179, 2019.
[11] M. Wiener, “Cryptanalysis of short RSA secret exponents”, IEEE Transactions on Information Theory, vol. 36, pp. 553-558, 1990.
[12] D. Boneh, and G. Durfee, “Cryptanalysis of RSA with Private Key d less than N0.292”. Lecture Notes in Computer Science, vol.1592, pp. 1 – 11, 1999.
[13] K. Somsuk, “A New Methodology to Find Private Key of RSA Based on Euler Totient Function”, Baghdad Science Journal, vol. 18(2), pp.338– 348, 2021.
[14] F. Kong, D. Zhou, Y. Jiang, J. Shang and J. Yu, “Fault Attack on an Improved CRT-RSA algorithm with the Modulus Chaining Method”, in Proc. of IEEE International Conference on Computational Science and Engineering and IEEE International Conference on Embedded and Ubiquitous Computing, pp. 866 - 869, July 21 - 24, 2017.
[15] J. Park, E. Park, S. Moon, D. Choi, Y. Kang and J. Ha, “Fault resistant CRT-RSA scheme adopting a small exponent”, in Proc. of International Conference on Computer Sciences and Convergence Information Technology, pp. 544 - 549, November 30 – December 2, 2010.
[16] K. Somsuk, “The improving decryption process of RSA by choosing new private key”, in Proc. of International Computer Science and Engineering Conference, pp. 1-5, November 15 – 18, 2017.
[17] K. Somsuk, “The New Equation for RSA’s Decryption Process Appropriate with High Private Key Exponent”, in Proc. of International Conference on Information Technology and Electrical Engineering, pp. 1-4, October 5 - 6, 2016.
[18] A.Mazzero, L.Romano, G.P. Saggese and N. Mazzocca, “FPGA-based Implementation of a serial RSA processor”, in Proc. of Design, Automation and Test in Europe Conference and Exhibition, pp. 582 - 587, December 19, 2003.
[19] A. Hayashi, “A New Fast Modular Multiplication Method and Its Application to Modular Exponentiation-Based Cryptography”, Electronics and Communications in Japan, Part 3, vol. 83, pp. 1372 - 1376, 2000.
[20] A. Rawat, K. Sehgal, A. Tiwari, A. Sharma and A. Joshi, “A novel accelerated implementation of RSA using parallel processing”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 22(2), pp. 309 - 322, 2019.
[21] M. Mumtaz and L. Ping, “Forty years of attacks on the RSA cryptosystem: A brief survey”, Journal of Discrete Mathematical Sciences and Cryptography, vol. 22(1), pp. 9-29, 2019.

Views: 348Downloads: 136Citations: 0