×

Revisiting sum of residues modular multiplication. (English) Zbl 1229.94046

Summary: In the 1980s, when the introduction of public key cryptography spurred interest in modular multiplication, many implementations performed modular multiplication using a sum of residues. As the field matured, sum of residues modular multiplication lost favor to the extent that all recent surveys have either overlooked it or incorporated it within a larger class of reduction algorithms. In this paper, we present a new taxonomy of modular multiplication algorithms. We include sum of residues as one of four classes and argue why it should be considered different to the other, now more common, algorithms. We then apply techniques developed for other algorithms to reinvigorate sum of residues modular multiplication. We compare FPGA implementations of modular multiplication up to 24 bits wide. The sum of residues multipliers demonstrate reduced latency at nearly 50% compared to Montgomery architectures at the cost of nearly doubled circuit area. The new multipliers are useful for systems based on the residue number system (RNS).

MSC:

94A60 Cryptography
68M07 Mathematical problems of computer architecture
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Barrett, “Implementing the Rivest, Shamir and Adleman public-keyencryption algorithm on a standard digital signal processor,” in Proceedings of the Advancesin Cryptology (Crypto ’86), vol. 263 of Lecture Notes in Computer Science, pp. 311-323, 1986.
[2] P. L. Montgomery, “Modular multiplication without trial division,” Mathematics of Computation, vol. 44, no. 170, pp. 519-521, 1985. · Zbl 0559.10006 · doi:10.2307/2007970
[3] C. D. Walter, “Still faster modular multiplication,” Electronics Letters, vol. 31, no. 4, pp. 263-264, 1995. · doi:10.1049/el:19950217
[4] A. Tomlinson, “Bit-serial modular multiplier,” Electronics Letters, vol. 25, no. 24, p. 1664, 1989.
[5] E. F. Brickell, “A fast modular multiplication algorithm with application to two key cryptography,” in Proceedings of the Advancesin Cryptology (Crypto ’82), Lecture Notes in Computer Science, pp. 51-60, 1982. · Zbl 0519.68058
[6] M. A. Soderstrand, W. Jenkins, and G. Jullien, “Residue Number System Arithmetic: Modern Applications-Digital Signal Processing,” 1986. · Zbl 0649.94001
[7] M. Bhardwaj and B. Ljusanin, “The renaissance-a residue number system based vector co-processor,” in Proceedings of the 32nd Asilomar Conferenceon Signals, Systems & Computers, vol. 2, pp. 202-207, 1998.
[8] G. Alia and E. Martinelli, “Optimal VLSI complexity design for high speed pipeline FFT using RNS,” Computers and Electrical Engineering, vol. 24, no. 3-4, pp. 167-182, 1998.
[9] J.-C. Bajard and L. Imbert, “A full RNS implementation of RSA,” IEEE Transactions on Computers, vol. 53, no. 6, pp. 769-774, 2004. · doi:10.1109/TC.2004.2
[10] J.-C. Bajard, L.-S. Didier, and P. Kornerup, “Modular multiplication and base extensions in residue number systems,” in Proceedings of the 15th IEEE Symposium on Computer Arithmetic, vol. 2, pp. 59-65, 2001.
[11] N. S. Szabo and R. H. Tanaka, Residue Arithmetic and Its Applications to Computer Technology, McGraw-Hill, New York, NY, USA, 1967. · Zbl 0168.15303
[12] S.-I. Kawamura and K. Hirano, “A fast modular arithmetic algorithmusing a residue table,” in Proceedings of the Advances in Cryptology (Eurocrypt ’88), vol. 330 of Lecture Notes in Computer Science, pp. 245-250, 1988.
[13] P. A. Findlay and B. A. Johnson, “Modular exponentiation using recursivesums of residues,” in Proceedings of the Advancesin Cryptology (Crypto ’89), vol. 435 of Lecture Notes in Computer Science, pp. 371-386, 1989.
[14] F. F. Su and T. Hwang, “Comments on iterative modular multiplication without magnitude comparison,” in Proceedings of the 6th National Conference on Information Security, pp. 21-22, Taichung, Taiwan, 1996.
[15] C.-Y. Chen and C.-C. Chang, “Fast modular multiplication algorithm for calculating the product ab modulo n,” Information Processing Letters, vol. 72, no. 3, pp. 77-81, 1999. · Zbl 1004.94017 · doi:10.1016/S0020-0190(99)00137-4
[16] G. R. Blakley, “A computer algorithm for calculation the product ab modulo m,” IEEE Transactions on Computers, vol. C-32, no. 5, pp. 497-500, 1983. · Zbl 0522.68045 · doi:10.1109/TC.1983.1676262
[17] H. Orup and P. Kornerup, “A high-radix hardware algorithm for calculating the exponential me modulo n,” in Proceedings of the 10th IEEE Symposium on Computer Arithmetic, vol. 576, pp. 51-57, June 1991.
[18] C. D. Walter, “Faster multiplication by operand scaling,” in Proceedings of the Advancesin Cryptology (Crypto ’91), vol. 576 of Lecture Notes in Computer Science, pp. 313-323, 1991. · Zbl 0825.94185
[19] R. Modugu and M. Choi, “A fast low-power modulo 2n+1 multiplier design,” in Proceedings of the IEEE International Instrumentation and Measurement Technology Conference (I2MTC ’09), 2009.
[20] J. E. Robertson, “A new class of digital division methods,” IRE Transactions on Electronic Computers, vol. 7, pp. 218-222, 1958.
[21] C. D. Walter, “Logarithmic speed modular multiplication,” Electronics Letters, vol. 30, no. 17, pp. 1397-1398, 1994. · doi:10.1049/el:19940969
[22] J.-F. Dhem, Design of an efficient public-key cryptographic library forRISC based smart cards, Ph.D. thesis, Université Catholique de Louvain, May 1998.
[23] M. Shand and J. Vuillemin, “Fast Implementations of RSA cryptography,” in Proceedings of the 11th IEEE Symposium on Computer Arithmetic, pp. 252-259, July 1993.
[24] H. Orup, “Simplifying quotient determination in high-radix modular multiplication,” in Proceedings of the 12th IEEE Symposium on Computer Arithmetic, pp. 193-199, July 1995.
[25] A. Bosselaers, R. Govaerts, and J. Vandewalle, “Comparisons of three modular reduction functions,” in Proceedings of the Advancesin Cryptology (Crypto ’93), vol. 773 of Lecture Notes in Computer Science, pp. 175-186, 1993. · Zbl 0871.94026
[26] A. Bosselaers, R. Govaerts, and J. Vandewalle, “A fast and flexible software library for large integer arithmetic,” in Proceedings of the 15th Symposiumon Information Theory in the Benelux, Louvain-La-Neuve(B), pp. 82-89, 1994.
[27] F. C. Chang and C. J. Wang, “Architectural tradeoff in implementing RSA processors,” ACM SIGARCH Computer Architecture News, vol. 30, no. 1, pp. 5-11, 2002.
[28] C. D. Walter, “Montgomery’s multiplication technique: how to make it smaller and faster,” in Proceedings of the 1st International Workshop on Cryptographic Hardware and Embedded Systems (CHES ’99), C.-K. Koc and C. Paar, Eds., vol. 1717 of Lecture Notes in Computer Science, pp. 80-93, Worcester, Ma, USA, August 1999. · Zbl 0955.68007
[29] C. W. Chiou and T. C. Yang, “Iterative modular multiplication algorithm without magnitude comparison,” Electronics Letters, vol. 30, no. 24, pp. 2017-2018, 1994. · doi:10.1049/el:19941383
[30] C. H. Lim, H. S. Hwang, and P. J. Lee, “Fast modular reduction with precomputation,” in Proceedings of the Japan-Korea Joint Workshop on Information Security and Cryptology (JW-ISC ’97), pp. 65-79, October 1997.
[31] C. Mclvor, M. McLoone, and J. V. McCanny, “Modified Montgomery modular multiplication and RSA exponentiation techniques,” IEE Proceedings: Computers and Digital Techniques, vol. 151, no. 6, pp. 402-408, 2004. · doi:10.1049/ip-cdt:20040791
[32] H. Nozaki, M. Motoyama, A. Shimbo, and S. Kawamura, “Implementation of RSA algorithm based on RNS montgomery multiplication,” in Proceedings of the Cryptographic Hardware and Embedded Systems (CHES ’01), pp. 364-376, September 2001. · Zbl 1007.68996
[33] Y. Kong and B. Phillips, “Montgomery modular multiplier,” Tech. Rep., The University of Adelaide, Adelaide, Australia, 2005.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.