Parallelized radix-4 scalable montgomery multipliers

ABSTRACT

This paper describes a parallelized radix-4 scalable Montgomery multiplier implementation. The design does not require hardware multipliers, and uses parallelized multiplication to shorten the critical path. By left-shifting the sources rather than right-shifting the result, the latency between processing elements is shortened from two cycles to nearly one. The new design can perform 1024-bit modular exponentiation in 8.7 ms and 256-bit exponentiation in 0.36 ms using 5916 Virtex2 4-input lookup tables. This is comparable to radix-2 for long multiplies and nearly twice as fast for short ones.

REFERENCES

• 1: P. Montgomery, "Modular multiplication without trial division," Math. of Computation, vol. 44, no. 170, pp. 519--521, April 1985.
• 2: Alexandre F. Tenca , Çetin K. Koç, A Scalable Architecture for Modular Multiplication Based on Montgomery's Algorithm, IEEE Transactions on Computers, v.52 n.9, p.1215-1221, September 2003 [doi>10.1109/TC.2003.1228516]
• 3: David Harris, An Improved Unified Scalable Radix-2 Montgomery Multiplier, Proceedings of the 17th IEEE Symposium on Computer Arithmetic, p.172-178, June 27-29, 2005 [doi>10.1109/ARITH.2005.9]
• 4: A. Tenca and L. Tawalbeh, "An efficient and scalable radix-4 modular multiplier design using recoding techniques," Proc. Asilomar Conf. Signals, Systems, and Computers, pp. 1445--1450, 2003.
• 5: Alexandre F. Tenca , Georgi Todorov , Çetin Kaya Koç, High-Radix Design of a Scalable Modular Multiplier, Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems, p.185-201, May 14-16, 2001
• 6: Y. Fan, X. Zeng, Y. Yu, G. Wang, and Q. Zhang, "A modified high-radix scalable Montgomery multiplier," Proc. Intl. Symp. Circuits and Systems, pp. 3382--3385, 2006.
• 7: K. Kelley and D. Harris, "Parallelized very high radix scalable Montgomery multipliers," Proc. Asilomar Conf. Signals, Systems, and Computers, pp. 1196--1200, Nov. 2005.
• 8: Kyle Kelley , David Harris, Very High Radix Scalable Montgomery Multipliers, Proceedings of the Fifth International Workshop on System-on-Chip for Real-Time Applications, p.400-404, July 20-24, 2005 [doi>10.1109/IWSOC.2005.111]
• 9: Holger Orup, Simplifying Quotient Determination in High-Radix Modular Multiplication, Proceedings of the 12th Symposium on Computer Arithmetic, p.193, July 19-21, 1995
• 10: Thomas Blum , Christof Paar, High-Radix Montgomery Modular Exponentiation on Reconfigurable Hardware, IEEE Transactions on Computers, v.50 n.7, p.759-764, July 2001 [doi>10.1109/12.936241]
• 11: C. Walter, "Montgomery exponentiation needs no final subtractions," Electronics Letters, vol. 35, no. 21, pp. 1831--1832, 14 October 1999.
• 12: Gaël Hachez , Jean-Jacques Quisquater, Montgomery Exponentiation with no Final Subtractions: Improved Results, Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, p.293-301, August 17-18, 2000
• 13: N. Jiang and D. Harris, "Parallelized Radix-2 Scalable Montgomery Multiplier," submitted to IFIP Intl. Conf. on VLSI, 2007.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
          Subjects: Algorithms

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
          Subjects: Cost/performance

General Terms:
Algorithms, Design, Performance

Keywords:
Montgomery Multiplication, RSA, cryptography