Efficient Implementation of Multi-prime RSA using Montgomery Multiplication

Mohammad Esmaeildoust¹ , Vahid Zarei² , Amer Kaabi³

Section:Research Paper, Product Type: Journal-Paper
Vol.8 , Issue.5 , pp.16-19, Oct-2020

Online published on Oct 31, 2020

Copyright © Mohammad Esmaeildoust, Vahid Zarei, Amer Kaabi . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

Abstract :
RSA cryptography is one of the most common algorithm, which exclusively employed in cryptography, digital signature and security systems. By increasing the use of this algorithm, many works are reported to improve the speed of the operation and security levels. Multi-prime RSA is one these improvements over RSA which divides operations over multi prime numbers instead of two in original RSA. In this paper, in order to achieve higher performance, encryption and decryption process of Multi-prime RSA is implemented by using Montgomery multiplication. The implementation results show the noticeable improvement in the speed of the Multi-prime RSA.

Key-Words / Index Term :
Cryptography, public key, RSA, Montgomery multiplication, Multi-prime RSA

References :
[1] Diffie, W. and M.E. Hellman, “New directions in cryptography,” IEEE Trans. Inform. Theory, Vol. 22: pp. 644-654, 1976.
[2] N. Koblitz, "Elliptic curve cryptosystems,” Math. Comp., vol. 48, no. 177, pp. 203-209, 1987.
[3] V. S. Miller, "Use of elliptic curves in cryptography," Proc. Adv. Cryptology LNCS, pp. 47-426, 1986.
[4] M. Esmaeildoust, D. Schinianakis, H. Javashi, T. Stouraitis, K. Navi, Ef?cient RNS implementation of elliptic curve point multiplication over GF(p). IEEE Trans. VLSI Syst. Vol. 21, pp. 1545–1549, 2013.
[5] C. J. McIvor, M. McLoone, J. V. McCanny, " Hardware elliptic curve cryptographic processor over ${rm GF}_{rm (P)}$ ", IEEE Trans. Circuits Syst. I Reg. Papers, vol. 53, no. 9, pp. 1946-1957, 2006.
[6] R.Rivest, A.shamir, and L. Adleman, ”A Method for Obtaining Digital Signatures and Public Key Cryptosystems”, Communications of the ACM, Vol.21, No.2, pp.120-126, 1978.
[7] N. Priya and M. Kannan, "Comparative Study of RSA and Probabilistic Encryption," International Journal Of Engineering And Computer Science, vol. 6, no. 1, pp. 19867 - 19871, January 2017.
[8] H. B. Pethe and S. R. Pande, "Comparative Study and Analysis of Cryptographic Algorithms," International Journal of Advance Research in Computer Science and Management Studies, vol. 5, no. 1, pp. 48-56, 1 January 2017.
[9] T.Collins, D.Hopkins, S.Langford, and M.Sabin, ”public key cryptographic Apparatus and method “,US Patent #5, 848,159, jan.1997.
[10] H.M Sun, M.E Wu, W.CTing and M.J Hinek, "Dual RSA and its security analysis", IEEE Transactions on Information Theory, vol. 53, no. 8, pp. 2922-2933, 2007.
[11] G. R. Blakey, "A Computer Algorithm for Calculating the Product AB Modulo M," IEEE Transaction on Computers, vol. 32, no. 5, pp. 497-500, 1983.
[12] L. Harn, "Public-Key Cryptosystem Design Based on Factoring and Discrete Logarithms," IEE Proceedings: Computers and Digital Techniques, vol. 144, no. 3, pp. 193-195, 1994.
[13] A. Fait, "Batch RSA," Advance in Cryptology CRYPTO `89, vol. 435, pp. 175-185, 1989.
[14] D. Boneh and H. Shacham, "Fast Variants of RSA," CryptoBytes, vol. 5, no. 1, pp. 1-10, 2002.
[15] T. Collins, D. Hopkins, S. Langford and M. Sabin, "Public Key Cryptographic Apparatus and Method". US Patent #5848, 1997.
[16] T. Takagi, "Fast RSA-type Cryptosystem Modulo pkq," Advances in Cryptology - CRYPTO ’98, vol. 1462, pp. 318-326, 1998.
[17] C. A. M. Paixon, "An efficient variant of the RSA cryptosystem," Cryptology ePrint Archive, 2002.
[18] D. Garg and S. Verma, "Improvement over Public Key Cryptographic Algorithm," in IEEE International Advance Computing Conference, Patiala, 2009.
[19] P.L. Montgomery, “Modular Multiplication without Trial Division,” Math. Computation, vol. 44, no. 170, pp. 519-521, 1985.
[20] K. Navi, A. S. Molahosseini and M. Esmaeildoust, "How to Teach Residue Number System to Computer Scientists and Engineers," in IEEE Transactions on Education, vol. 54, no. 1, pp. 156-163, 2011.
[21] Rupal Yadav, Kaptan Singh, Amit saxena, "Hybrid Cryptographic Solution to Overcome Drawbacks of RSA in Cloud Environment", International Journal of Computer Sciences and Engineering, Vol.8, Issue.8, pp.56-60, 2020.
[22] V. Kapoor, "Data Encryption and Decryption Using Modified RSA Cryptography Based on Multiple Public Keys and ‘n’prime Number," International Journal of Scientific Research in Network Security and Communication, Vol.1, Issue.2, pp.35-38, 2013.
[23] Harsh Sahay, "Modified RSA Cryptosystem with Data Hiding Technique in the Terms of DNA Sequences", International Journal of Computer Sciences and Engineering, Vol.7, Issue.9, pp.91-94, 2019.