The double-base number system and its application to elliptic curve cryptography

Dimitrov, Vassil; Imbert, Laurent; Mishra, Pradeep

doi:10.1090/S0025-5718-07-02048-0

The double-base number system and its application to elliptic curve cryptography
HTML articles powered by AMS MathViewer

by Vassil Dimitrov, Laurent Imbert and Pradeep K. Mishra PDF

Math. Comp. 77 (2008), 1075-1104

Abstract:

We describe an algorithm for point multiplication on generic elliptic curves, based on a representation of the scalar as a sum of mixed powers of $2$ and $3$. The sparseness of this so-called double-base number system, combined with some efficient point tripling formulae, lead to efficient point multiplication algorithms for curves defined over both prime and binary fields. Side-channel resistance is provided thanks to side-channel atomicity.

References

Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences, Cambridge University Press, Cambridge, 2003. Theory, applications, generalizations. MR 1997038, DOI 10.1017/CBO9780511546563
Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren (eds.), Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006. MR 2162716
R. Avanzi, V. Dimitrov, C. Doche, and F. Sica, Extending scalar multiplication using double bases, Advances in Cryptology, ASIACRYPT’06, Lecture Notes in Computer Science, vol. 4284, Springer, 2006, pp. 130–144.
R. Avanzi and F. Sica, Scalar multiplication on Koblitz curves using double bases, Cryptology ePrint Archive, Report 2006/067, 2006, http://eprint.iacr.org/2006/067.
Jean-Claude Bajard, Laurent Imbert, and Thomas Plantard, Modular number systems: beyond the Mersenne family, Selected areas in cryptography, Lecture Notes in Comput. Sci., vol. 3357, Springer, Berlin, 2005, pp. 159–169. MR 2181315, DOI 10.1007/978-3-540-30564-4_{1}1
Valérie Berthé, Autour du système de numération d’Ostrowski, Bull. Belg. Math. Soc. Simon Stevin 8 (2001), no. 2, 209–239 (French, with French summary). Journées Montoises d’Informatique Théorique (Marne-la-Vallée, 2000). MR 1838931
V. Berthé and L. Imbert, On converting numbers to the double-base number system, Advanced Signal Processing Algorithms, Architecture and Implementations XIV, Proceedings of SPIE, vol. 5559, SPIE, 2004, pp. 70–78.
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
Eric Brier and Marc Joye, Fast point multiplication on elliptic curves through isogenies, Applied algebra, algebraic algorithms and error-correcting codes (Toulouse, 2003) Lecture Notes in Comput. Sci., vol. 2643, Springer, Berlin, 2003, pp. 43–50. MR 2042411, DOI 10.1007/3-540-44828-4_{6}
B. Chevalier-Mames, M. Ciet, and M. Joye, Low-cost solutions for preventing simple side-channel analysis: Side-channel atomicity, IEEE Transactions on Computers 53 (2004), no. 6, 760–768.
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
Mathieu Ciet, Marc Joye, Kristin Lauter, and Peter L. Montgomery, Trading inversions for multiplications in elliptic curve cryptography, Des. Codes Cryptogr. 39 (2006), no. 2, 189–206. MR 2209936, DOI 10.1007/s10623-005-3299-y
M. Ciet and F. Sica, An analysis of double base number systems and a sublinear scalar multiplication algorithm, Progress of Cryptology, Mycrypt 2005, Lecture Notes in Computer Science, vol. 3715, Springer, 2005, pp. 171–182.
Henri Cohen, Atsuko Miyaji, and Takatoshi Ono, Efficient elliptic curve exponentiation using mixed coordinates, Advances in cryptology—ASIACRYPT’98 (Beijing), Lecture Notes in Comput. Sci., vol. 1514, Springer, Berlin, 1998, pp. 51–65. MR 1726152, DOI 10.1007/3-540-49649-1_{6}
Erik De Win, Antoon Bosselaers, Servaas Vandenberghe, Peter De Gersem, and Joos Vandewalle, A fast software implementation for arithmetic operations in $\textrm {GF}(2^n)$, Advances in cryptology—ASIACRYPT ’96 (Kyongju), Lecture Notes in Comput. Sci., vol. 1163, Springer, Berlin, 1996, pp. 65–76. MR 1486049, DOI 10.1007/BFb0034836
Vassil Dimitrov, Laurent Imbert, and Pradeep Kumar Mishra, Efficient and secure elliptic curve point multiplication using double-base chains, Advances in cryptology—ASIACRYPT 2005, Lecture Notes in Comput. Sci., vol. 3788, Springer, Berlin, 2005, pp. 59–78. MR 2236727, DOI 10.1007/11593447_{4}
V. S Dimitrov, K. Järvinen, M. J. Jacobson, Jr., W. F. Chan, and Z. Huang, FPGA implementation of point multiplication on Koblitz curves using Kleinian integers, Cryptographic Hardware and Embedded Systems, CHES’06, Lecture Notes in Computer Science, vol. 4249, Springer, 2006, pp. 445–459.
V. S. Dimitrov, G. A. Jullien, and W. C. Miller, An algorithm for modular exponentiation, Inform. Process. Lett. 66 (1998), no. 3, 155–159. MR 1627991, DOI 10.1016/S0020-0190(98)00044-1
C. Doche, T. Icart, and D. R. Kohel, Efficient scalar multiplication by isogeny decompositions, Public Key Cryptography, PKC’06, Lecture Notes in Computer Science, vol. 3958, Springer, 2006, pp. 191–206.
C. Doche and L. Imbert, Extended double-base number system with applications to elliptic curve cryptography, Progress in Cryptology, INDOCRYPT’06, Lecture Notes in Computer Science, vol. 4329, Springer, 2006, pp. 335–348.
Kirsten Eisenträger, Kristin Lauter, and Peter L. Montgomery, Fast elliptic curve arithmetic and improved Weil pairing evaluation, Topics in cryptology—CT-RSA 2003, Lecture Notes in Comput. Sci., vol. 2612, Springer, Berlin, 2003, pp. 343–354. MR 2080147, DOI 10.1007/3-540-36563-X_{2}4
K. Fong, D. Hankerson, J. Lòpez, and A. Menezes, Field inversion and point halving revisited, IEEE Transactions on Computers 53 (2004), no. 8, 1047–1059.
Daniel M. Gordon, A survey of fast exponentiation methods, J. Algorithms 27 (1998), no. 1, 129–146. MR 1613189, DOI 10.1006/jagm.1997.0913
T. Granlund, GMP, the GNU multiple precision arithmetic library, see: http://www. swox.com/gmp/.
Jorge Guajardo and Christof Paar, Efficient algorithms for elliptic curve cryptosystems, Advances in cryptology—CRYPTO ’97 (Santa Barbara, CA, 1997) Lecture Notes in Comput. Sci., vol. 1294, Springer, Berlin, 1997, pp. 342–356. MR 1630403, DOI 10.1007/BFb0052247
D. Hankerson, J. Lòpez Hernandez, and A. Menezes, Software implementation of elliptic curve cryptography over binary fields, Cryptographic Hardware and Embedded Systems, CHES’00, Lecture Notes in Computer Science, vol. 1965, Springer, 2000, pp. 1–24.
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
K. Itoh, M. Takenaka, N. Torii, S. Temma, and Y. Kurihara, Fast implementation of public-key cryptography on a DSP TMS320C6201, Cryptographic Hardware and Embedded Systems, CHES’99, Lecture Notes in Computer Science, vol. 1717, Springer, 1999, pp. 61 – 72.
T. Izu, B. Möller, and T. Takagi, Improved elliptic curve multiplication methods resistant against side channel attacks, Progress in Cryptology, INDOCRYPT’02, Lecture Notes in Computer Science, vol. 2551, Springer, 2002, pp. 269–313.
T. Izu and T. Takagi, A fast parallel elliptic curve multiplication resistant against side channel attacks, Public Key Cryptography, PKC’02, Lecture Notes in Computer Science, vol. 2274, Springer, 2002, pp. 280–296.
—, Fast elliptic curve multiplications resistant against side channel attacks, IEICE Transactions Fundamentals E88-A (2005), no. 1, 161–171.
Marc Joye and Christophe Tymen, Protections against differential analysis for elliptic curve cryptography: an algebraic approach, Cryptographic hardware and embedded systems—CHES 2001 (Paris), Lecture Notes in Comput. Sci., vol. 2162, Springer, Berlin, 2001, pp. 377–390. MR 1946618, DOI 10.1007/3-540-44709-1_{3}1
Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203–209. MR 866109, DOI 10.1090/S0025-5718-1987-0866109-5
P. Kocher, J. Jaffe, and B. Jun, Differential power analysis, Advances in Cryptology, CRYPTO’99, Lecture Notes in Computer Science, vol. 1666, Springer, 1999, pp. 388–397.
P. C. Kocher, Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems, Advances in Cryptology, CRYPTO’96, Lecture Notes in Computer Science, vol. 1109, Springer, 1996, pp. 104–113.
J. Lopez and R. Dahab, An improvement of the Guajardo-Paar method for multiplication on non-supersingular elliptic curves, Proceedings of the XVIII International Conference of the Chilean Society of Computer Science, SCCC’98, 1998, pp. 91–95.
Kurt Mahler, On a special functional equation, J. London Math. Soc. 15 (1940), 115–123. MR 2921, DOI 10.1112/jlms/s1-15.2.115
Victor S. Miller, Use of elliptic curves in cryptography, Advances in cryptology—CRYPTO ’85 (Santa Barbara, Calif., 1985) Lecture Notes in Comput. Sci., vol. 218, Springer, Berlin, 1986, pp. 417–426. MR 851432, DOI 10.1007/3-540-39799-X_{3}1
National Institute of Standards and Technology, FIPS PUB 186-2: Digital signature standard (DSS), National Institute of Standards and Technology, January 2000.
W. B. Pennington, On Mahler’s partition problem, Ann. of Math. (2) 57 (1953), 531–546. MR 53959, DOI 10.2307/1969735
Christopher M. Skinner, On the Diophantine equation $ap^x+bq^v=c+dp^zq^w$, J. Number Theory 35 (1990), no. 2, 194–207. MR 1057322, DOI 10.1016/0022-314X(90)90112-5
J. Solinas, Generalized mersenne numbers, Research Report CORR-99-39, Center for Applied Cryptographic Research, University of Waterloo, Waterloo, ON, Canada, 1999.
Certicom Research The SECG group, SEC 2: Recommended elliptic curve domain parameters, Standard for Efficient Cryptography, September 2000, http://www.secg.org/.
R. Tijdeman, On the maximal distance between integers composed of small primes, Compositio Math. 28 (1974), 159–162. MR 345917
Herbert S. Wilf, generatingfunctionology, 2nd ed., Academic Press, Inc., Boston, MA, 1994. MR 1277813