Optimized Multiple Word Radix - 2 Montgomery Multiplication Algorithm

  ijett-book-cover  International Journal of Engineering Trends and Technology (IJETT)          
  
© 2013 by IJETT Journal
Volume-4 Issue-7                      
Year of Publication : 2013
Authors : Harmeet Kaur , Charu Madhu

Citation 

Harmeet Kaur , Charu Madhu. "Optimized Multiple Word Radix - 2 Montgomery Multiplication Algorithm". International Journal of Engineering Trends and Technology (IJETT). V4(7):2836-2841 Jul 2013. ISSN:2231-5381. www.ijettjournal.org. published by seventh sense research group.

Abstract

Montgomery multiplication algorithm is used in the implementation of RSA and other cryptosystems based on modular arithmetic. Several improvements have been suggested to increase its suitability for hardware implementation. Radix - 2 Montgomery architectures are easier to implement in hardware. In this paper a modified optimized algorithm for radix - 2 Montgomery Multiplication is presented wh ich is based on parallelizing the multiplications within each Processing Element and pre - computation of par tial results using assumptions regarding the most significant bit of the previous design thereby improving speed . The design has been modeled using VHDL. The VHDL code has been synthesized and simulated using Xilinx ISE 10.1

References

[1] R.L. Rivest, A. Shamir, and L. Adleman, “A Method for ObtainingDigital Signatures and Public - Key Cryptosystems,” Comm. ACM, vol. 21, no. 2, pp. 120 - 126, 1978.
[2] en.wikipedia.org/wiki/ RSA (algorithm)
[3 ] P .L. Montgomery, “Modular Multiplication without Trial Division,”Math. of Computation, vol. 44, no. 170, pp. 519 - 521, Apr. 1985.
[4] Nadia Nedjah , Luiza de Macedo Mourelle , “ A Review of M odular Multiplication Methods and Respective Hardware Implementations ” Informatica 30 (2006) 111 – 129 .
[5] A.F. Tenca, G. Todorov, and C ? .K. Koc ?, “High - Radix Design of a Scalable Modular Multiplier,” Pro c. Third Int’l Workshop Crypto graphic Hardware and Embedded S ystems (CHES ’01), pp. 185 - 201, 2001.
[6] D. Harris, R. Krishnamurthy, M. Anders, S. Mathew, and S. Hsu, “An Improved Unified Scalable Radix - 2 Montgomery Multiplier,” Proc. 17th IEEE Symp. Computer A rithmetic (ARITH), pp. 172 - 178, June 2005.
[7] N. Jiang and D. Harris, “Paralle lized Radix - 2 Scalable Montgom ery Multiplier,” Proc. IFIP Int’l Con f. Very Large Scale Integration (VLSI - SoC ’07), pp. 14 6 - 150, Oct. 2007.
[8] N. Pinckney and D.M. Harris, “Parallelized Radix - 4 Scalable Montgomery Multipliers,” J. Integrate d Circuits and Systems, vol. 3, no. 1, pp. 39 - 45, Mar. 2008.
[9] K. Kelly and D. Harris, “Parall elized Very Hi gh Radix Scalable Montgomery Multipliers,” Pro c. 39th Asilomar Conf. Signals, Systems and Computers, pp. 1196 - 1200, Oct. 2005.
[10] E.A. Michalski and D.A. Buell, “A Scalable Architecture for RSACryptography on Large FPGAs,” Proc. Int’l Conf. Field Program - m able Logic and Applications, (FPL ’06), pp. 145 - 152, Aug. 2006.
[11] C. McIvor, M. McLoone, and J.V . McCanny, “High - Radix Systolic Modular Multiplication on Recon figurable Hardware,” Proc. IEEE I nt’l Conf. Field - Programmable Tec hnology (ICFPT ’05), pp. 13 - 18, Dec. 2005.
[12] Miaoqing Huang, Kris Gaj, and Tarek El - Ghazawi, “ New Hardwa re Architectures for Montgomery Modular Multiplication Algorithm ,” IEEE transactions on computers, vol. 60, no. 7, july 2011 .
[13] Koç, Ç.K., High speed RSA implementation, Technical repo rt, RSA Laboratories, RSA Data Security Inc. CA, version 2, 1994.
[14] H. Orup, “Simplifying quotient determination in high - radix modular multiplication,” Proc 12 th IEEE Symp. Computer Arithmetic, pp - 193 - 199, 1995.

Keywords
Montgomery Multipli cation, RSA, Modular Multiplication , MWR2MM Algorithm