Generalised Mersenne numbers revisited

Granger, Robert; Moss, Andrew

doi:10.1090/S0025-5718-2013-02704-4

Generalised Mersenne numbers revisited
HTML articles powered by AMS MathViewer

by Robert Granger and Andrew Moss PDF

Math. Comp. 82 (2013), 2389-2420 Request permission

Abstract:

Generalised Mersenne Numbers (GMNs) were defined by Solinas in 1999 and feature in the NIST (FIPS 186-2) and SECG standards for use in elliptic curve cryptography. Their form is such that modular reduction is extremely efficient, thus making them an attractive choice for modular multiplication implementation. However, the issue of residue multiplication efficiency seems to have been overlooked. Asymptotically, using a cyclic rather than a linear convolution, residue multiplication modulo a Mersenne number is twice as fast as integer multiplication; this property does not hold for prime GMNs, unless they are of Mersenne’s form. In this work we exploit an alternative generalisation of Mersenne numbers for which an analogue of the above property — and hence the same efficiency ratio — holds, even at bitlengths for which schoolbook multiplication is optimal, while also maintaining very efficient reduction. Moreover, our proposed primes are abundant at any bitlength, whereas GMNs are extremely rare. Our multiplication and reduction algorithms can also be easily parallelised, making our arithmetic particularly suitable for hardware implementation. Furthermore, the field representation we propose also naturally protects against side-channel attacks, including timing attacks, simple power analysis and differential power analysis, which is essential in many cryptographic scenarios, in constrast to GMNs.

References

A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), no. 203, 29–68. MR 1199989, DOI 10.1090/S0025-5718-1993-1199989-X
Paul Barrett, Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor, Advances in cryptology—CRYPTO ’86 (Santa Barbara, Calif., 1986) Lecture Notes in Comput. Sci., vol. 263, Springer, Berlin, 1987, pp. 311–323. MR 907099, DOI 10.1007/3-540-47721-7_{2}4
Paul T. Bateman and Roger A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp. 16 (1962), 363–367. MR 148632, DOI 10.1090/S0025-5718-1962-0148632-7
D.J. Bernstein. A software implementation of NIST P-224. Presentation at the 5th Workshop on Elliptic Curve Cryptography (ECC 2001), University of Waterloo, October 29-31, 2001. Slides available from http://cr.yp.to/talks.html.
Daniel J. Bernstein, Curve25519: new Diffie-Hellman speed records, Public key cryptography—PKC 2006, Lecture Notes in Comput. Sci., vol. 3958, Springer, Berlin, 2006, pp. 207–228. MR 2423191, DOI 10.1007/11745853_{1}4
D.J. Bernstein, N. Duif, T. Lange, P. Schwabe and B. Yang. High-speed high-security signatures. Cryptology ePrint Archive, Report 2011/368, 2011.
Daniel J. Bernstein and Tanja Lange, Faster addition and doubling on elliptic curves, Advances in cryptology—ASIACRYPT 2007, Lecture Notes in Comput. Sci., vol. 4833, Springer, Berlin, 2007, pp. 29–50. MR 2565722, DOI 10.1007/978-3-540-76900-2_{3}
I.F. Blake, R.M. Roth and G. Seroussi. Efficient Arithmetic in $GF(2^m)$ through Palindromic Representation. Technical Report HPL-98-134, 1998. Available from http://www.hpl.hp.com/techreports/98/HPL-98-134.html.
I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, Cambridge, 2000. Reprint of the 1999 original. MR 1771549
Ian F. Blake, Gadiel Seroussi, and Nigel P. Smart (eds.), Advances in elliptic curve cryptography, London Mathematical Society Lecture Note Series, vol. 317, Cambridge University Press, Cambridge, 2005. MR 2166105, DOI 10.1017/CBO9780511546570
Michael Brown, Darrel Hankerson, Julio López, and Alfred Menezes, Software implementation of the NIST elliptic curves over prime fields, Topics in cryptology—CT-RSA 2001 (San Francisco, CA), Lecture Notes in Comput. Sci., vol. 2020, Springer, Berlin, 2001, pp. 250–265. MR 1907102, DOI 10.1007/3-540-45353-9_{1}9
Certicom Research. SEC 2: Recommended elliptic curve domain parameters, 2010.
Jaewook Chung and Anwar Hasan, More generalized Mersenne numbers, Selected areas in cryptography, Lecture Notes in Comput. Sci., vol. 3006, Springer, Berlin, 2004, pp. 335–347. MR 2094740, DOI 10.1007/978-3-540-24654-1_{2}4
Jaewook Chung and M. Anwar Hasan, Low-weight polynomial form integers for efficient modular multiplication, IEEE Trans. Comput. 56 (2007), no. 1, 44–57. MR 2361668, DOI 10.1109/TC.2007.250622
J. Chung and A. Hasan. Montgomery Reduction Algorithm for Modular Multiplication Using Low-Weight Polynomial Form Integers. In ARITH 18, 230–239, 2007.
Richard Crandall and Barry Fagin, Discrete weighted transforms and large-integer arithmetic, Math. Comp. 62 (1994), no. 205, 305–324. MR 1185244, DOI 10.1090/S0025-5718-1994-1185244-1
Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. MR 2156291
J.S. Coron. Resistance against differential power analysis for elliptic curve cryptosystems. In Cryptographic Hardware and Embedded Systems – CHES’99, LNCS 1717, pp. 292–302, 1999.
Harvey Dubner, Generalized repunit primes, Math. Comp. 61 (1993), no. 204, 927–930. MR 1185243, DOI 10.1090/S0025-5718-1993-1185243-9
Harvey Dubner and Yves Gallot, Distribution of generalized Fermat prime numbers, Math. Comp. 71 (2002), no. 238, 825–832. MR 1885631, DOI 10.1090/S0025-5718-01-01350-3
Harvey Dubner and Torbjörn Granlund, Primes of the form $(b^n+1)/(b+1)$, J. Integer Seq. 3 (2000), no. 2, Article 00.2.7, 8. MR 1800881
Germain Drolet, A new representation of elements of finite fields $\textrm {GF}(2^m)$ yielding small complexity arithmetic circuits, IEEE Trans. Comput. 47 (1998), no. 9, 938–946. MR 1655771, DOI 10.1109/12.713313
ECC Brainpool Standard Curves and Curve Generation. Available from http://www.bsi.bund.de/english/index.htm.
FIPS 186-2. Digital Signature Standard. Federal Information Processing Standards Publication 186-2, US Department of Commerce/N.I.S.T. 2000.
Steven D. Galbraith, Xibin Lin, and Michael Scott, Endomorphisms for faster elliptic curve cryptography on a large class of curves, J. Cryptology 24 (2011), no. 3, 446–469. MR 2786038, DOI 10.1007/s00145-010-9065-y
P. Gaudry and E. Thomé. The mpFq library and implementing curve-based key exchanges. In SPEED: Software Performance Enhancement for Encryption and Decryption, ECRYPT Workshop, 49–64, 2007.
W. Geiselmann and D. Gollmann, VLSI design for exponentiation in $\textrm {GF}(2^n)$, Advances in cryptology—AUSCRYPT ’90 (Sydney, 1990) Lecture Notes in Comput. Sci., vol. 453, Springer, Berlin, 1990, pp. 398–405. MR 1083786
Louis Goubin, A refined power-analysis attack on elliptic curve cryptosystems, Public key cryptography—PKC 2003, Lecture Notes in Comput. Sci., vol. 2567, Springer, Berlin, 2002, pp. 199–210. MR 2171927, DOI 10.1007/3-540-36288-6_{1}5
G. Hachez and J.J. Quisquater. Montgomery Exponentiation with No Final Subtractions: Improved Results. In Cryptographic Hardware and Embedded Systems (CHES), Springer-Verlag LNCS 1965, pp. 293–301, 2000.
Darrel Hankerson, Alfred Menezes, and Scott Vanstone, Guide to elliptic curve cryptography, Springer Professional Computing, Springer-Verlag, New York, 2004. MR 2054891, DOI 10.1016/s0012-365x(04)00102-5
D. Hankerson, A. Menezes, and S. Vanstone. Software Implementation of Pairings Technical report available from http://www.cacr.math.uwaterloo.ca http://citeseer.ist.psu.edu
Hüseyin Hisil. Elliptic curves, group law, and efficient computation. Ph.D. thesis, Queensland University of Technology, 2010. URL: http://eprints.qut.edu.au/33233.
Internet Engineering Task Force. Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS), 2006. http://www.ietf.org/rfc/rfc4492.
Toshiya Itoh and Shigeo Tsujii, Structure of parallel multipliers for a class of fields $\textrm {GF}(2^m)$, Inform. and Comput. 83 (1989), no. 1, 21–40. MR 1019954, DOI 10.1016/0890-5401(89)90045-X
J. Jonsson and B. Kaliski. Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specification Version 2.1 http://citeseer.ist.psu.edu/jonsson03publickey.html
A. Karatsuba and Y. Ofman. Multiplication of multidigit numbers on automata. In Soviet Physics, Doklady 7, 595–596, 1963.
E. Käsper. Fast elliptic curve cryptography in OpenSSL. In Financial Cryptography and Data Security: FC 2011 Workshops (RLCPS and WECSR), LNCS 7126, pp. 27–39, Springer-Verlag, 2011.
Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
C.K. Koç, T. Acar and B.S. Kaliski Jr. Analyzing and comparing Montgomery multiplication algorithms. In IEEE Micro, vol. 16, 3, pp. 26–33, 1996.
P.C. Kocher. Timing attacks on implementations of Diffie-Hellman, RSA, DSS and other systems. In Advances in Cryptology – CRYPTO 96, LNCS 1109, pp. 104–113, 1996.
P.C. Kocher, J. Jaffe and B. Jun. Differential power analysis. In Advances in Cryptology – CRYPTO 99, LNCS 1666, pp. 388–397, 1999.
Soonhak Kwon, Chang Hoon Kim, and Chun Pyo Hong, Gauss period, sparse polynomial, redundant basis, and efficient exponentiation for a class of finite fields with small characteristic, Algorithms and computation, Lecture Notes in Comput. Sci., vol. 2906, Springer, Berlin, 2003, pp. 736–745. MR 2088253, DOI 10.1007/978-3-540-24587-2_{7}5
A.K. Lenstra. Using cyclotomic polynomials to construct efficient discrete logarithm cryptosystems over finite fields. In Proc ACISP’97, Springer-Verlag LNCS 1270 (1997), 127-138.
H. W. Lenstra Jr., The number field sieve: an annotated bibliography, The development of the number field sieve, Lecture Notes in Math., vol. 1554, Springer, Berlin, 1993, pp. 1–3. MR 1321217, DOI 10.1007/BFb0091535
H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
P. Longa and C.H. Gebotys. Efficient techniques for high-speed elliptic curve cryptography. In Cryptographic hardware and embedded systems, CHES 2010, LNCS 6225, pp. 80–94, Springer 2010.
Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of applied cryptography, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. With a foreword by Ronald L. Rivest. MR 1412797
Alfred Menezes, Edlyn Teske, and Annegret Weng, Weak fields for ECC, Topics in cryptology—CT-RSA 2004, Lecture Notes in Comput. Sci., vol. 2964, Springer, Berlin, 2004, pp. 366–386. MR 2092257, DOI 10.1007/978-3-540-24660-2_{2}8
Peter L. Montgomery, Modular multiplication without trial division, Math. Comp. 44 (1985), no. 170, 519–521. MR 777282, DOI 10.1090/S0025-5718-1985-0777282-X
David Naccache, Nigel P. Smart, and Jacques Stern, Projective coordinates leak, Advances in cryptology—EUROCRYPT 2004, Lecture Notes in Comput. Sci., vol. 3027, Springer, Berlin, 2004, pp. 257–267. MR 2153177, DOI 10.1007/978-3-540-24676-3_{1}6
Y. Nogami, A. Saito, and Y. Morikawa. Finite extension field with modulus of all-one polynomial and representation of its elements for fast arithmetic operations. In IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol. E86-A No. 9, 2376–2387, 2003.
E. Ozturk, B. Sunar, and E. Savas. Low-power elliptic curve cryptography using scaled modular arithmetic. In CHES 2004, LNCS 3156, Springer-Verlag, pp. 92–106, 2004.
D.S. Phatak and T. Goff. Fast Modular Reduction for Large Wordlengths via One Linear and One Cyclic Convolution. In 17th IEEE Symposium on Computer Arithmetic (ARITH’05), pp. 179–186, 2005.
R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2, 120–126. MR 700103, DOI 10.1145/359340.359342
Y. Sakai and K. Sakurai. Simple power analysis on fast modular reduction with generalized Mersenne prime for elliptic curve cryptosystems. In Ieice Transactions - IEICE, vol. 89-A, no. 1, pp. 231–237, 2006.
A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, Acta Arith. 4 (1958), 185–208; erratum 5 (1958), 259 (French). MR 106202, DOI 10.4064/aa-4-3-185-208
J.H. Silverman. Fast multiplication in finite fields $GF(2^N)$. In Proc. Workshop Cryptographic Hardware and Embedded Systems (CHES ’99), LNCS 1717, 122–134. Springer 1999.
N.P. Smart, E. Oswald and D. Page. Randomised representations. In IET Information Security, vol. 2, no. 2, pp. 19–27, 2008.
W. M. Snyder, Factoring repunits, Amer. Math. Monthly 89 (1982), no. 7, 462–466. MR 673635, DOI 10.2307/2321382
J.A. Solinas. Generalized Mersenne Numbers. Technical report CORR-39, Dept. of C&O, University of Waterloo, 1999. Available from http://www.cacr.math.uwaterloo.ca
C.D. Walter. Faster modular multiplication by operand scaling. Advances in Cryptology LNCS 576, 313–323, Springer-Verlag, 1992.
C.D. Walter. Montgomery exponentiation needs no final subtractions. In Electronics Letters, 35, pp. 1831–1832, 1999.
C.D. Walter. Montgomery’s multiplication technique: How to make it smaller and faster. In Cryptographic Hardware and Embedded Systems (CHES), Springer-Verlag LNCS 1717, pp. 80–93, 1999.
Colin D. Walter and Susan Thompson, Distinguishing exponent digits by observing modular subtractions, Topics in cryptology—CT-RSA 2001 (San Francisco, CA), Lecture Notes in Comput. Sci., vol. 2020, Springer, Berlin, 2001, pp. 192–207. MR 1907098, DOI 10.1007/3-540-45353-9_{1}5
H. C. Williams and E. Seah, Some primes of the form $(a^{n}-1)/(a-1)$, Math. Comp. 33 (1979), no. 148, 1337–1342. MR 537980, DOI 10.1090/S0025-5718-1979-0537980-7
J.K. Wolf. Low complexity finite field multiplication. In Discrete Math., no.s 106/107, 497–502, 1992.
Huapeng Wu, M. Anwar Hasan, Ian F. Blake, and Shuhong Gao, Finite field multiplier using redundant representation, IEEE Trans. Comput. 51 (2002), no. 11, 1306–1316. MR 2015123, DOI 10.1109/TC.2002.1047755
Sergey Yekhanin, Towards 3-query locally decodable codes of subexponential length, STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 266–274. MR 2402450, DOI 10.1145/1250790.1250830