Abstract Many improvements have been made since the RSA orig in 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 va riants improved the encryption speed at the cost of decryption speed. This paper also improves the performance of the enc ryption 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 o f multiprime feature, the key generation time is also decreased in this case. It is decreased approximately by a factor of 2.39 f rom rebalanced RSA CRT variant. Comparison of the R SA variants with the new scheme is shown in tabular and graphical way fo r better analysis.

References

[1] Boneh D. and Durfee G., Cryptanalysis of RSA with Private Key d Less Than N0.292, IEEE Transactions on Information Theory , vol. 46, no. 4, pp. 1339)1349, 2000.

[2] Boneh D. and Shacham H., Fast Variants of RSA, CryptoBytes , vol. 5, no. 1, pp. 1)9, 2002.

[3] Collins T., Hopkins D., Lanford S., and Sabin M., Public Key Cryptographic Apparatus and Method, available at: http://www.google.com/ patents/US5848159, last visited 2012.

[4] Coppersmith D., Small Solutions to Polynomial Equations and Low Exponent RSA Vulnerabilities, the Journal of Cryptology , vol. 10, no. 4, pp. 233)260, 1997.

[5] Fiat A., Batch RSA, the Journal of Cryptology , vol. 10, no. 2, pp. 75)88,1997.

[6] Howgrave)Graham N., Finding Small Roots of Univariate Modular Equations Revisited, in Proceedings of the 16 th International Conference on Cryptography and Coding , Cirencester, UK, pp. 131)142, 1997.

[7] Jutla C., On Finding Small Solutions of Modular Multivariate Polynomial Equations, in Proceedings of International Conference on the Theory and Application of Cryptographic Techniques , Espoo, Finland, pp. 158)170, 1998.

[8] Niven I., Zuckerman H., and Montgomery H., An Introduction the Theory of Numbers , John Wiley and Sons Inc., 1991.

[9] NTL: A Library for Doing Number Theory., available at: http://shoup.net/ntl/, last visited 2008

[10] Padhye S., On DRSA Public Key Cryptosystem, the International Arab Journal of Information Technology , vol. 3, no. 4, pp. 334) 336, 2006.

[11] Paixao C. and Gazzoni Filho D., An Efficient Variant of the RSA Cryptosystem, available at: http://www.lbd.dcc.ufmg.br/colecoes/sbseg/2005/ 0010.pdf, last visited 2013.

[12] Pointcheval D., New Public Key Cryptosystem based on the Dependent)RSA Problem, in Proceedings of International Conference on the Theory and Application of Cryptographic Techniques , Prague, Czech Republic, pp. 239) 254, 1999.

[13] Qiao G. and Lam Y., RSA Signature Algorithm for Microcontroller Implementation, in Proceedings of the 3 rd International Conference on Smart Card Research and Applications , Louvain)la)Neuve, Belgium, pp. 353)356, 2000.

[14] Quisquater J. and Couvreur C., Fast Decipherment Algorithm for RSA Public)Key Cryptosystem, Eletronic Letters , vol. 18, no. 21, pp. 905)907, 1982.

[15] Rivest R., Shamir A., and Adleman L., A Method for Obtaining Digital Signatures and Public Key Cryptosystems, Communications of the ACM , vol. 21, no. 2, pp. 120)126, 1978.

[16] Sun H., Hinek M., and Wu M., On the Design of Rebalanced RSA CRT, available at: http://www.cacr.math.uwaterloo.ca/techreports/2 005/cacr2005)35.pdf, last visited 2013.

[17] Sun H., Hinek M., and Wu M., Trading Decryption for Speeding Encryption in Rebalanced)RSA, the Journal of Systems and Software , vol. 82, no. 9, pp. 1503)1512, 2009.

[18] Takagi T., Fast RSA)Type Cryptosystem Modulo p kq, in Proceedings of the 18th Annual International Cryptology Conference , California, USA, pp. 318)326, 1998.

[19] Vuillaume C., Efficiency Comparison of Several RSA Variants, Master Thesis, Darmstadt University, 2003.

[20] Wiener M., Cryptanalysis of Short RSA Secret Exponents, IEEE Transactions on Information Theory , vol. 36, no. 3, pp. 553)558, 1990. Seema Verma received her BTech. degree in computer science and engineering in 2001 and MTech degree in computer science and Engineering in 2007. Currently, she is pursuing her PhD degree in computer science and engineering and working as associate professor at Echelon Insti tute of Technology, Faridabad, affiliated to MDU India. She has more than 12 years of experience in academics. Her research interests include informati on security and cryptography. Deepak Garg has done his PhD degree in the area of efficient algorithm design from Thapar University. He has more than 85 publications in International Journals and Conferences. He is chair, IEEE India Council Computer Society and Chair, IEEE India Council Education Society.