Modified Montgomery for RSA Cryptosystem

Authors: Rupali Verma, Maitreyee Dutta, Renu Vig

Abstract:

Encryption and decryption in RSA are done by modular exponentiation which is achieved by repeated modular multiplication. Hence efficiency of modular multiplication directly determines the efficiency of RSA cryptosystem. This paper designs a Modified Montgomery Modular Multiplication in which addition of operands is computed by 4:2 compressor. The basic logic operations in addition are partitioned over two iterations such that parallel computations are performed. This reduces the critical path delay of proposed Montgomery design. The proposed design and RSA are implemented on Virtex 2 and Virtex 5 FPGAs. The two factors partitioning and parallelism have improved the frequency and throughput of proposed design.

Keywords: RSA, Montgomery modular multiplication, 4:2 compressor, FPGA.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1335942

References:

[1] R. Rivest et al., "A method for obtaining digital signatures and public key cryptosystems,” Commun. ACM, vol 21, issue 2, Feb 1978, pp. 120-126.
[2] P.L. Montgomery, "Modular multiplication without trial division,” Math Comput, vol 44, Apr. 1985, pp. 519-521.
[3] C.D. Walter, "Systolic modular multiplication,” IEEE Trans. Comput, vol 42, no 3, Mar 1993, pp. 376-378.
[4] S.E. Elridge et al., "Hardware implementation of Montgomery’s modular multiplication algorithm,” IEEE Trans. Comput., vol. 42, no. 6, Jun 1993, pp. 693-699.
[5] C. McIvor et al., "Fast Montgomery modular multiplication and RSA Cryptographic processor architectures,” Proc. 37th Asilomar Conf. Signals, Syst. Comput., vol. 1, Nov. 2003, pp. 379-384.
[6] C. McIvor et al., "Modified Montgomery modular multiplication and RSA exponentiation techniques,” Proc. IEEE Comput. Digit. Techniques, vol. 151, no.6, Nov. 2004, pp. 402-408.
[7] K. Manochehri et al., "Fast Montgomery modular multiplication by pipelined CSA architecture,” Proc. IEEE Int. Conf. Microelectron, Dec. 2004, pp. 144-147.
[8] K. Manochehri et al., "Modified Radix 2 Montgomery Modular Multiplication to Make It Faster and Simpler,” In Proc. Int. Conference on Information Technology: Coding and Computing, Apr 2005, pp. 598-602.
[9] H. Thapliyal et al., "Modified Montgomery Modular Multiplication Using 4:2 Compressor and CSA Adder,” In Proc. Of Third Int. Workshop on Electronic Design, Test and Applications, 2005.
[10] Y. Y Zhang et al., "An efficient CSA architecture for Montgomery modular multiplication,” Microprocessors and Microsystems, vol 31, no. 7, Nov.2007, pp. 456-459.
[11] M.D. Shieh et al., "A New Modular Exponentiation Architecture for Efficient Design of RSA Cryptosystem,” IEEE Trans. On Very Large Scale Integration Systems, vol. 16, no. 9, Sept 2008, pp. 1151-1161.
[12] C.D. Walter, "Montgomery exponentiation needs no final subtractions,” Electron. Lett., vol. 32, no. 21, Oct. 1999, pp. 1831-1832.
[13] R. Verma et al., "Modified Montgomery Modular Multiplication for RSA Cryptosystem,” Int. Journal of Computational Intelligence and Information Security, vol 2, no. 9., Sept 2011, pp. 39-47.
[14] S. Veeramachaneni et al., "Novel Architectures for High Speed and Low Power 3-2, 4-2 and 5-2 Compressors,” In 20th Int. Conf. on VLSI design, 2007.
[15] P.B. Minev et al., "The Virtex 5 Routing and Logic Architecture,” Electronics-ET 2009, 14-17 Sept, Sozopol, Bulgaria.
[16] M.D. Shieh et al., "A New Algorithm for High Speed Modular Multiplication Design,” IEEE Trans. On Circuits and Systems-I: Regular Papers, vol. 56, no. 9, Sept. 2009, pp. 2009-2019.
[17] B. Schneier, Applied Cryptography Protocols, Algorithms and Source Code in C: Second edition, Wiley.