Abstract
RSA public-key cryptography requires modular exponentiation and modular multiplication on large numbers. Montgomery Modular Multiplication is a fast method for performing modular multiplication. The modular exponentiation can be performed by repeatedly calling Montgomery Modular Multiplication. Transformations to the Montgomery Domain are required before the calculations, and a transformation back to the normal domain is also required to get the final result. The domain transformations require a value that is calculated by costly modular arithmetic. Many hardware RSA implementations use precomputed values for such domain transformations. As a result, the flexibility to use different public keys is lost. This paper introduces a Shift-Sub Modular Multiplication (SSMM) algorithm for calculating such values in fields. The algorithm does not require modular arithmetic and precomputed values. Instead, it uses shift and addition/subtraction calculations. The SSMM algorithm can also be used directly for RSA public-key cryptography. We give the hardware implementation of RSA public-key cryptography using SSMM in Verilog HDL and compare the cost and performance to that of the RSA public-key cryptography implementation using Montgomery Modular Multiplication. The results show that the performance of the two implementations is about the same, but the implementation using SSMM uses fewer hardware resources (55% to 59% adaptive logic modules and 69% to 85% flip-flops) because it does not require domain transformations.
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
Similar content being viewed by others
References
Acar, T., Shumow, D.: Modular reduction without pre-computation for special moduli. Technical report, Microsoft Research, January 2010
Cao, Z., Wei, R., Lin, X.: A fast modular reduction method. IACR Cryptology ePrint Archive, 2014:1–12 (2014)
Coulouris, G., Dollimore, J., Kindberg, T., Blair, G.: Distributed Systems Concepts and Design, 5th edn. Addison-Wesley, Boston (2012)
Eldridge, S.E., Walter, C.D.: Hardware implementation of montgomery’s modular multiplication algorithm. IEEE Trans. Comput. 42(6), 693–699 (1993)
Erdem, S.S., Yanık, T., Celebi, A.: A general digit-serial architecture for montgomery modular multiplication. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 25(5), 1658–1668 (2017)
Huang, M., Gaj, K., Kwon, S., El-ghazawi, T.: An optimized hardware architecture of montgomery multiplication algorithm. IACR Cryptology ePrint Archive 2007:1–14, January 2007
Lim, C.H., Hwang, H.S., Lee, P.J.: Fast modular reduction with precomputation. In: Korea-Japan Joint Workshop on Information Security and Cryptology (JWISC 1997), pp. 65–79 (1997)
Montgomery, P.L.: Modular multiplication without trial division. Math. Comput. 44(170), 519–521 (1985)
Paar, C.: Implementation of Cryptographic Schemes 1. Ruhr University Bochum (2015)
Rivest, R.L., Shamir, A., Adleman, L.M.: A method of obtaining digital signatures and public key cryptosystems. Commun. ACM 21(2), 120–126 (1978)
Walter, C.D., Holloway, R.: 3 - hardware aspects of montgomery modular multiplication. Cambridge University Press, October 2017
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Li, Y., Chu, W. (2022). Shift-Sub Modular Multiplication Algorithm and Hardware Implementation for RSA Cryptography. In: Abraham, A., et al. Hybrid Intelligent Systems. HIS 2021. Lecture Notes in Networks and Systems, vol 420. Springer, Cham. https://doi.org/10.1007/978-3-030-96305-7_50
Download citation
DOI: https://doi.org/10.1007/978-3-030-96305-7_50
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-96304-0
Online ISBN: 978-3-030-96305-7
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)