Abstract
Modular multiplication is widely used in cryptographic algorithms. In order to improve the efficiency, most of the recent implementations adopt precomputation. Precomputation improves the speed and in the meanwhile makes the algorithms more complex. The complex algorithms are not suitable for hardware implementation. We propose a new algorithm without precomputation, which is more efficient even compared with the ones with precomputation. Our algorithm is based on interleaving modular algorithm. The modulus in our algorithm is enlarged, and this modification greatly reduces the number of subtractions. By a small change of the multiplier, our algorithm does not need the last subtraction. We also propose a pipeline scheme which can achieve high frequency. Compared with existing work (including the precomputation ones), our implementation improves the throughput/area by 47%.
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
Shieh, M., Chen, J., Wu, H., Lin, W.: A new modular exponentiation architecture for efficient design of RSA cryptosystem. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 16(9), 1151–1161 (2008)
Huang, M., Gaj, K., Kwon, S., El-Ghazawi, T.: An Optimized Hardware Architecture for the Montgomery Multiplication Algorithm. In: Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp. 214–228. Springer, Heidelberg (2008)
McIvor, C., et al.: FPGA Montgomery Multiplier Architectures -A Comparison. IEEE Computer Society (2004)
Blakely, G.: A computer algorithm for calculating the product AB modulo M. IEEE Transactions on Computers 100(5), 497–500 (1983)
Koç, Ç.: Rsa hardware implementation. Tech. rep. RSA Laboratories (1996)
Koç, Ç., Hung, C.: Carry-save adders for computing the product AB modulo N. Electronics Letters 26(13), 899–900 (1990)
Koç, Ç., Hung, C.: Bit-level systolic arrays for modular multiplication. The Journal of VLSI Signal Processing 3(3), 215–223 (1991)
Koç, Ç., Hung, C.: A Fast algorithm for modular reduction. IEE Proceedings-Computers and Digital Techniques 145(4), 265–271 (1998)
Montgomery, P.: Modular multiplication without trial division. Mathematics of Computation 44(170), 519–521 (1985)
Tenca, A.F., Koç, Ç.K.: A Scalable Architecture for Montgomery Multiplication. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 94–108. Springer, Heidelberg (1999)
Harris, D., Krishnamurthy, R., Anders, M., Mathew, S., Hsu, S.: An improved unified scalable radix-2 montgomery multiplier. IEEE Computer Society (2005)
Mesquita, D., Perin, G., Herrmann, F., Martins, J.: An efficient implementation of montgomery powering ladder in reconfigurable hardware. In: Proceedings of the 23rd Symposium on Integrated Circuits and System Design, pp. 121–126. ACM (2010)
Perin, G., Mesquita, D., Herrmann, F., Martins, J.: Montgomery modular multiplication on reconfigurable hardware: fully systolic array vs parallel implementation. In: 2010 VI Southern Programmable Logic Conference (SPL), pp. 61–66. IEEE (2010)
Bunimov, V., Schimmler, M., Tolg, B.: A complexity-effective version of montgomery’s algorithm. In: Workshop on Complexity Effective Designs, ISCA, vol. 2. Citeseer (2002)
Bunimov, V., Schimmler, M.: Area and time efficient modular multiplication of large integers. In: Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors, pp. 400–409. IEEE (2003)
Schimmler, M., Bunimov, V.: Fast modular multiplication by operand changing. IEEE Computer Society (2004)
Narh Amanor, D., Paar, C., Pelzl, J., Bunimov, V., Schimmler, M.: Efficient hardware architectures for modular multiplication on FPGAs. In: Field Programmable Logic and Applications, pp. 539–542. IEEE (2005)
Knezevic, M., Batina, L., Verbauwhede, I.: Modular reduction without precomputational phase. In: IEEE International Symposium on Circuits and Systems, ISCAS 2009, pp. 1389–1392. IEEE (2009)
Knežević, M., Sakiyama, K., Fan, J., Verbauwhede, I.: Modular Reduction in GF(2n) without Pre-computational Phase. In: von zur Gathen, J., Imaña, J.L., Koç, Ç.K. (eds.) WAIFI 2008. LNCS, vol. 5130, pp. 77–87. Springer, Heidelberg (2008)
AbdelFattah, A.M., Bahaa El-Din, A.M., Fahmy, H.M.A.: An Efficient Architecture for Interleaved Modular Multiplication. World Academy of Science, Engineering and Technology (2009)
McIvor, C., McLoone, M., McCanny, J.: Modified Montgomery modular multiplication and RSA exponentiation techniques. In: IEE Proceedings - Computers and Digital Techniques, vol. 151, pp. 402–408. IET (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pan, W., Jing, J., Xia, L., Liu, Z., Yu, M. (2012). An Efficient RSA Implementation without Precomputation. In: Wu, CK., Yung, M., Lin, D. (eds) Information Security and Cryptology. Inscrypt 2011. Lecture Notes in Computer Science, vol 7537. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34704-7_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-34704-7_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34703-0
Online ISBN: 978-3-642-34704-7
eBook Packages: Computer ScienceComputer Science (R0)