Abstract
Today, RSA is one of the most popular public-key crypto-system in various applications. In this paper, we present a high-speed RSA crypto-processor with modified radix-4 Montgomery multiplication algorithm and Chinese Remainder Theorem (CRT). Our design takes 0.84M clock cycles for a 1024-bit modular exponentiation and 0.25M clock cycles for two 512-bit exponentiations. Using 0.18 um standard cell library, the processor achieves 365Kbps for a 1024-bit exponentiation and 1,233Kbps for two 512-bit exponentiations at a 300MHz clock rate. For the high performance RSA crypto-system, the processor can also execute modular reduction, which is essential for calculating the Montgomery mapping constant and the modularly reduced ciphertext in CRT technique.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signature and public-key cryptosystems. Comm. ACM 21, 120–126 (1978)
Blakley, G.R.: A computer algorithm for the product ab modulo m. IEEE Trans. Comput. C-32, 497–500 (1983)
Brickell, E.F.: A fast modular multiplication algorithm with application to two-key cryptography. In: Proc. CRYPTO 1982 Advances Cryptology, pp. 51–60 (1982)
Montgomery, P.L.: Modular multiplication without trial division. Math. Computation 44, 519–521 (1985)
Koc, C.K., Acar, T., Kaliski Jr., B.S.: Analyzing and Comparing Montgomery Multiplication Algorithms. IEEE Micro. 16(3), 26–33 (1996)
Blum, T., Paar, C.: Montgomery modular exponentiation on reconfigurable hardware. In: Proc. 14th IEEE Symp. on Comp. Arith., pp. 70–77 (1999)
Takagi, N.: A radix-4 modular multiplication hardware algorithm for modular exponentiation. IEEE Trans. Comput. 41, 949–956 (1992)
Kornerup, P.: High-radix modular multiplication for cryptosystems. In: Proc. 11th IEEE Symp. Comput. Arith., Windsor, ON, Canada, June 1993, pp. 277–283 (1993)
Hong, J.-H., Wu, C.-W.: Cellular-Array Modular Multiplier for Fast RSA Public-Key Cryptosystem Based on Modified Booth’s Algorithm. IEEE Trans. on VLSI Systems 11(3), 474–484 (2003)
Couvreur, C., Quisquater, J.J.: Fast decipherment algorithm for RSA public-key cryptosystem. Electronics letters 18(21), 905–907 (1982)
McIvor, C., McLoone, M., McCanny, J.V.: A high-speed, low latency RSA decryption silicon core. In: IEEE Inter. Symp. On Circuits and Systems (ISCAS), May 2003, vol. 4, pp. 25–28 (2003)
Wu, C.-H., Hong, J.-H., Wu, C.-W.: RSA cryptosystem design based on Chinese remainder theorem. In: IEEE Proc. Asia and South Pacific Design Automation Conf. (ASP-DA), pp. 391–395 (2001)
Kwon, T.W., You, C.S., Heo, W.S., Kang, Y.K., Choi, J.R.: Two Implementation Methods of a 1024-bit RSA Cryptoprocessor Based on Modified Montgomery Algorithm. In: IEEE Inter. Symp. On Circuits and Systems (ISCAS), vol. 4, pp. 650–653 (2001)
McIvor, C., McLoone, M., McCanny, J.V.: Fast Montgomery Modular Multiplication and RSA Cryptographic Processor Architectures. In: 37th Asilomar Conference on Signals, Systems and Computers, November 2003, vol. 1(7), pp. 379–384 (2003)
Cilardo, A., Mazzeo, A., Romano, L., Saggese, G.P.: Carry-Save Montgomery Modular Exponentiation on Reconfigurable Hardware. IEEE Proc. on DATE 2004 03(3), 206–211 (2004)
Blum, T., Paar, C.: High-radix Montgomery modular exponentiation on reconfigurable hardware. IEEE Trans. Comput. 50(7), 70–77 (2001)
Kornerup, P.: Systolic, Linear-Array Multiplier for a Class of Right-Shift Algorithms. IEEE Trans. on Comp. 43(8), 892–898 (1994)
Walter, C.D.: Systolic modular multiplication. IEEE Trans. on Comp. 42(3), 376–378 (1993)
Eldridge, S.E., Walter, C.D.: Hardware implementation of Montgomery’s modular multiplication algorithm. IEEE Trans. on Comp. 42(6), 693–699 (1993)
Booth, A.D.: A signed binary multiplication technique. Q. J. Mech. Appl. Math. 4(2), 236–240 (1951)
Koc, C.K., Hung, C.Y.: Fast algorithm for modular reduction. IEE Proc. -Comput. Digit. Tech. 145(4), 265–271 (1998)
Cho, K.-S., Ryu, J.-H., Cho, J.-D.: High-speed modular multiplication algorithm for RSA cryptosystem. In: IECON 2001, pp. 479–483 (2001)
McIvor, C., McLoone, M., McCanny, J.V.: Modified Montgomery modular multiplication and RSA exponentiation techniques. IEE Proc. -Comput. Digit. Tech. 151(6), 402–408 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Koo, B., Lee, D., Ryu, G., Chang, T., Lee, S. (2006). High-Speed RSA Crypto-processor with Radix-4 Modular Multiplication and Chinese Remainder Theorem. In: Rhee, M.S., Lee, B. (eds) Information Security and Cryptology – ICISC 2006. ICISC 2006. Lecture Notes in Computer Science, vol 4296. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11927587_9
Download citation
DOI: https://doi.org/10.1007/11927587_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49112-5
Online ISBN: 978-3-540-49114-9
eBook Packages: Computer ScienceComputer Science (R0)