Copyright © 2008 The Institute of Electronics, Information and Communication Engineers
Special Section on Selected Papers from the 20th Workshop on Circuits and Systems in Karuizawa -- Papers |
A High-Speed Design of Montgomery Multiplier
1 The authors are with IPS, Waseda University, Kitakyushu-shi, 808-0135 Japan. E-mail: fanyibo{at}ruri.waseda.jp
With the increase of key length used in public cryptographic algorithms such as RSA and ECC, the speed of Montgomery multiplication becomes a bottleneck. This paper proposes a high speed design of Montgomery multiplier. Firstly, a modified scalable high-radix Montgomery algorithm is proposed to reduce critical path. Secondly, a high-radix clock-saving dataflow is proposed to support high-radix operation and one clock cycle delay in dataflow. Finally, a hardware-reused architecture is proposed to reduce the hardware cost and a parallel radix-16 design of data path is proposed to accelerate the speed. By using HHNEC 0.25 µm standard cell library, the implementation results show that the total cost of Montgomery multiplier is 130 KGates, the clock frequency is 180 MHz and the throughput of 1024-bit RSA encryption is 352 kbps. This design is suitable to be used in high speed RSA or ECC encryption/decryption. As a scalable design, it supports any key-length encryption/decryption up to the size of on-chip memory.
Key Words: Montgomery multiplier, high-speed, high-radix, scalable
Manuscript received June 22, 2007. Manuscript revised October 3, 2007.
Reference
[1] R.L. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public key crypto-systems," Commun. ACM, vol.21, no.2, pp.120–126, 1978. [2] N. Koblitz, "Elliptic curve cryptosystems," Mathematics of Computation, vol.48, no.177, pp.203–209, 1987. [3] V. Miller, "Use of elliptic curves in cryptography," Proc. CRYPTO 85, pp.417–426, 1985. [4] P.L. Montgomery, "Modular multiplication without trial division," Mathematics of Computation, vol.44, no.170, pp.519–521, April 1985. [5] C. Koc, T. Acar, and B. Kaliski, "Analyzing and comparing Montgomery multiplication algorithms," IEEE Micro, vol.16, no.3, pp.26–33, June 1996. [6] A.F. Tenca and C.K. Koc, "A scalable architecture for modular multiplication based on Montgomery's algorithm," IEEE Trans. Comput., vol.52, no.9, pp.1215–1221, Sept. 2003. [7] A.F. Tenca, G. Todorov, and C.K. Koc, "High-radix design of a scalable modular multiplier," Cryptographic Hardware and embedded Systems-CHES 2001, Lect. Notes Comput. Sci., no.2162, pp.189–205, May 2001. [8] G. Todorov, ASIC design, implementation and analysis of a scalable high-radix Montgomery multiplier, M.S. Thesis, Oregon State University, June 2001. [9] Y. Fan, X.Y. Zeng, Y. Yu, G. Wang, H. Deng, and Q.L. Zhang, "High speed radix-16 design of a scalable Montgomery multiplier," Proc. 6th International Conference on ASIC-ASICON 2005, vol.1, no.24-27, pp.153–157, Oct. 2005. [10] D. Harris, R. Krishnamurthy, M. Anders, S. Mathew, and S. Hsu, "An improved unified scalable radix 2 Montgomery multiplier," Proc. 17th IEEE Symposium on Computer Arithmetic, pp.172–178, June 2005. [11] K. Kelley and D. Harris, "Very high radix scalable Montgomery multipliers," Proc. Fifth International Workshop on System-on-Chip for Real-Time Applications, pp.400–404, July 2005. [12] C.H. Wang, C.P. Su, C.T. Huang, and C.W. Wu, "A word-based RSA crypto-processor with enhanced pipeline performance," Proc. 2004 IEEE Asia-Pacific Conference on Advanced System Integrated Circuits, pp.218–221, Aug. 2004.
CiteULike 
Connotea 
Del.icio.us What's this?
This Article 
Abstract
Full Text (PDF)
Alert me when this article is cited
Alert me if a correction is posted
Services
Email this article to a friend
Similar articles in this journal
Alert me to new issues of the journal
Add to My Personal Archive
Download to citation manager
Request Permissions
Google Scholar
Articles by FAN, Y.
Articles by GOTO, S.
Search for Related Content
Social Bookmarking
What's this?