Improvement in Rebalanced CRT RSA

Seema Verma and Deepak Garg

Department of Computer Science and Engineering, Thapar University, India

Abstract: Many improvements have been made since the RSA origin in terms of encryption/decryption speed and memory saving. This paper concentrates on the performance improvement. Rebalanced RSA is designed to improve the decryption speed at the cost of encryption speed. Further work was done to improve its encryption speed in terms of rebalanced Chinese Remainder Theorem (CRT) variants. rebalanced CRT variants improved the encryption speed at the cost of decryption speed.  This paper also improves the performance of the encryption side in rebalanced RSA, while still maintaining the same decryption speed as in Rebalanced RSA, by adding the MultiPrime RSA feature to the Rebalanced CRT variant. Proposed scheme gains the same advantage in encryption side as in rebalanced CRT variants, besides it is 2 times faster at decryption side than rebalanced CRT variants. Due to the use of MultiPrime feature, the key generation time is also decreased in this case. It is decreased approximately by a factor of 2.39 from rebalanced RSA CRT variant. Comparison of the RSA variants with the new scheme is shown in tabular and graphical way for better analysis.

Keywords: Cryptography, computational complexity, encryption, public key.