| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Low-Weight Polynomial Form Integers for Efficient Modular Multiplication
January 2007 (vol. 56 no. 1)
pp. 44-57
In 1999, Solinas introduced families of moduli called the generalized Mersenne numbers (GMNs), which are expressed in low-weight polynomial form, p = f(t), where t is limited to a power of 2. GMNs are very useful in elliptic curve cryptosystems over prime fields since modular reduction by a GMN requires only integer additions and subtractions. However, since there are not many GMNs and each GMN requires a dedicated implementation, GMNs are hardly useful for other cryptosystems. Here, we modify GMN by removing restriction on the choice of t and restricting the coefficients of f(t) to 0 and \pm1. We call such families of moduli low-weight polynomial form integers (LWPFIs). We show an efficient modular multiplication method using LWPFI moduli. LWPFIs allow general implementation and there exist many LWPFI moduli. One may consider LWPFIs as a trade-off between general integers and GMNs.
[1] 44 A. Avizienis, “Signed-Digit Number Representation for Fast Parallel Arithmetic,” IRE Trans. Computers, vol. 10, pp. 389-400, 1961.[2] J.-C. Bajard, L. Imbert, and T. Plantard, “Modular Number Systems: Beyond the Mersenne Family,” Selected Areas in Cryptography 2004, vol. 3357, pp. 159-169, Springer-Verlag, 2004.[3] J.-C. Bajard, L. Imbert, and T. Plantard, “Arithmetic Operations in the Polynomial Modular Number System,” Proc. 17th IEEE Symp. Computer Arithmetic, pp. 206-213, 2005.[4] P. Barrett, “Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor,” Advances in Cryptology, Proc. CRYPTO '86, pp. 311-323, 1987.[5] A. Bosselaers, R. Govaerts, and J. Vandewalle, “Comparison of Three Modular Reduction Functions,” Advances in Cryptology, Proc. CRYPTO '93, pp. 175-186, 1994.[6] J. Chung and A. Hasan, “More Generalized Mersenne Numbers,” Selected Areas in Cryptography-SAC 2003, vol. 3006, pp. 335-347, Springer-Verlag, 2003.[7] S.A. Cook, “On the Minimum Computation Time of Functions,” PhD dissertation, Harvard Univ., May 1966.[8] R.E. Crandall, Method and Apparatus for Public Key Exchange in a Cryptographic System, US Patent # 5,159,632, 27 Oct. 1992.[9] J.-F. Dhem, “Efficient Modular Reduction Algorithm in ${\hbox{\rlap{I}\kern 2.0pt{\hbox{F}}}}_{q}[x]$ and Its Application to 'Left to Right' Modular Multiplication in ${\hbox{\rlap{I}\kern 2.0pt{\hbox{F}}}}_{2}[x]$ ,” Proc. Cryptographic Hardware and Embedded Systems (CHES '03), pp.203-213, 2003.[10] S.R. Dussé and B.S. Kaliski Jr., “A Cryptographic Library for the Motorola DSP56000,” Advances in Cryptology, Proc. EUROCRYPT '90, s vol. 473, pp. 230-244, Springer-Verlag, 1991.[11] Freescale Semiconductor, Inc., “MCF5307 ColdFire, Integrated Microprocessor User's Manual,” 2005, http://www.freescale. com/files/soft_dev_tools/ doc/ref_manualMCF5307BUM.pdf.[12] T. Granlund, “Instruction Latencies and Throughput for AMD and Intel x86 Processors,” 2005, http://swox.com/docx86-timing.pdf.[13] S.-M. Hong, S.-Y. Oh, and H. Yoon, “New Modular Multiplication Algorithms for Fast Modular Exponentiation,” Lecture Notes in Computer Science, vol. 1070, pp. 166-177, Springer-Verlag, 1996.[14] A. Karatsuba and Y. Ofman, “Multiplication of Multidigit Numbers on Automata,” Soviet Physics Doklady (English translation), vol. 7, no. 7, pp. 595-596, 1963.[15] S. Kawamura, K. Takabayashi, and A. Shimbo, “A Fast Modular Exponentiation Algorithm,” IEICE Trans., vol. E-74, no. 8, pp.2136-2142, Aug. 1991.[16] D. Knuth, The Art of Comuter Programming: Seminumerical Algorithms, vol. 2, second ed. Addison-Wesley, 1981.[17] N. Koblitz, “Elliptic Curve Cryptosystems,” Math. Computation, vol. 48, pp. 203-209, Jan. 1987.[18] Ç.K. Koç, T. Acar, and B.S. Kaliski Jr., “Analyzing and Comparing Montgomery Multiplication Algorithms,” IEEE Micro, vol. 16, no. 3, pp. 26-33, June 1996.[19] P. Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems,” Advances in Cryptology, Proc. CRYPTO '96, pp. 104-113, 1996.[20] A.K. Lenstra and H. Lenstra Jr., “The Development of the Number Field Sieve,” Lecture Notes in Math., vol. 1554, pp. 11-42, 1993.[21] A.K. Lenstra, H. Lenstra Jr., M. Manasse, and J. Pollard, “The Factorization of the Ninth Fermat Number,” Math. Computation, vol. 61, no. 203, pp. 319-349, 1993.[22] A.K. Lenstra and E.R. Verheul, “The XTR Public Key System,” Advances in Cryptology, Proc. CRYPTO '00, pp. 1-19, 2000.[23] C.H. Lim, H.S. Hwang, and P.J. Lee, “Fast Modular Reduction with Precomputation,” Proc. Korea-Japan Joint Workshop Information Security and Cryptology (JWISC '97), pp. 65-79, 1997.[24] A.J. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography. CRC Press, 1997.[25] V. Miller, “Use of Elliptic Curves in Cryptography,” Advances in Cryptology, Proc. CRYPTO '85, pp. 417-426, 1986.[26] P.L. Montgomery, “Modular Multiplication without Trial Division,” Math. Computation, vol. 44, no. 170, pp. 519-521, 1985.[27] P.L. Montgomery, “Five, Six, and Seven-Term Karatsuba-Like Formulae,” IEEE Trans. Computers, vol. 54, no. 3, pp. 362-369, Mar. 2005.[28] D. Naccache and H. M'Silti, “A New Modulo Computation Algorithm,” Recherche Opérationnelle-Operations Research (RAIRO-OR), vol. 24, pp. 307-313, 1990.[29] Nat'l Inst. of Standards and Tech nology, “Recommended Elliptic Curves for Federal Government Use,” July 1999.[30] Nat'l Inst. of Standards and Tech nology, “Digital Signature Standard (DSS),” FIPS Publication 186-2, Feb. 2000.[31] R. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Comm. ACM, vol. 21, no. 2, pp. 120-126, 1978.[32] O. Shirokauer, “The Special Function Field Sieve,” SIAM J. Discrete Math., vol. 16, no. 1, pp. 81-98, 2002.[33] J.A. Solinas, “Generalized Mersenne Numbers,” Technical Report CORR 99-39, Centre for Applied Cryptographic Research, Univ. of Waterloo, 1999, http://cacr.uwaterloo.ca/techreports/1999 corr99-39.ps.[34] A.L. Toom, “The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers,” Soviet Math, vol. 3, pp.714-716, 1963.[35] C.D. Walter, “Precise Bounds for Montgomery Modular Multiplication and Some Potentially Insecure RSA Moduli,” Topics in Cryptology-CT-RSA 2002, vol. 2271, pp. 30-39, Springer-Verlag, 2002.[36] A. Weimerskirch and C. Paar, “Generalization of the Karatsuba Algorithm for Efficient Implementations,” technical report, Ruhr-Universität Bochum, Gemany, 2003, http://www.crypto.ruhr-uni-bochum.deen_publications.html .[37] S. Winograd, Arithmetic Complexity of Computations. SIAM, 1980.[38] D. Zuras, “More on Squaring and Multiplying Large Integers,” IEEE Trans. Computers, vol. 43, no. 8, pp. 899-908, Aug. 1994.
Index Terms:
Cryptography, Mersenne numbers, modular multiplication, RSA, elliptic curve cryptosystems, the Montgomery reduction, the Barrett reduction.
Citation:
Jaewook Chung, M. Anwar Hasan, "Low-Weight Polynomial Form Integers for Efficient Modular Multiplication," IEEE Transactions on Computers, vol. 56, no. 1, pp. 44-57, Jan. 2007, doi:10.1109/TC.2007.13
