Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 

 

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


Authors: Vassil Dimitrov, Laurent Imbert and Pradeep K. Mishra
Journal: Math. Comp. 77 (2008), 1075-1104
MSC (2000): Primary 14H52; Secondary 14G50, 68R99
DOI: https://doi.org/10.1090/S0025-5718-07-02048-0
Published electronically: December 11, 2007
MathSciNet review: 2373193
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences, Cambridge University Press, Cambridge, 2003. Theory, applications, generalizations. MR 1997038
  • 2. 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
  • 3. 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.
  • 4. 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.
  • 5. 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, https://doi.org/10.1007/978-3-540-30564-4_11
  • 6. 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
  • 7. 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.
  • 8. 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
  • 9. 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, https://doi.org/10.1007/3-540-44828-4_6
  • 10. 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.
  • 11. 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, https://doi.org/10.1007/978-3-540-24654-1_24
  • 12. 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, https://doi.org/10.1007/s10623-005-3299-y
  • 13. 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.
  • 14. 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, https://doi.org/10.1007/3-540-49649-1_6
  • 15. Erik De Win, Antoon Bosselaers, Servaas Vandenberghe, Peter De Gersem, and Joos Vandewalle, A fast software implementation for arithmetic operations in 𝐺𝐹(2ⁿ), Advances in cryptology—ASIACRYPT ’96 (Kyongju), Lecture Notes in Comput. Sci., vol. 1163, Springer, Berlin, 1996, pp. 65–76. MR 1486049, https://doi.org/10.1007/BFb0034836
  • 16. 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, https://doi.org/10.1007/11593447_4
  • 17. 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.
  • 18. 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, https://doi.org/10.1016/S0020-0190(98)00044-1
  • 19. 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.
  • 20. 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.
  • 21. 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, https://doi.org/10.1007/3-540-36563-X_24
  • 22. 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.
  • 23. Daniel M. Gordon, A survey of fast exponentiation methods, J. Algorithms 27 (1998), no. 1, 129–146. MR 1613189, https://doi.org/10.1006/jagm.1997.0913
  • 24. T. Granlund, GMP, the GNU multiple precision arithmetic library, see: http://www. swox.com/gmp/.
  • 25. 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, https://doi.org/10.1007/BFb0052247
  • 26. 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.
  • 27. Darrel Hankerson, Alfred Menezes, and Scott Vanstone, Guide to elliptic curve cryptography, Springer Professional Computing, Springer-Verlag, New York, 2004. MR 2054891
  • 28. 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.
  • 29. 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.
  • 30. 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.
  • 31. -, Fast elliptic curve multiplications resistant against side channel attacks, IEICE Transactions Fundamentals E88-A (2005), no. 1, 161-171.
  • 32. 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, https://doi.org/10.1007/3-540-44709-1_31
  • 33. Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203–209. MR 866109, https://doi.org/10.1090/S0025-5718-1987-0866109-5
  • 34. 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.
  • 35. 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.
  • 36. 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.
  • 37. Kurt Mahler, On a special functional equation, J. London Math. Soc. 15 (1940), 115–123. MR 0002921, https://doi.org/10.1112/jlms/s1-15.2.115
  • 38. 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, https://doi.org/10.1007/3-540-39799-X_31
  • 39. National Institute of Standards and Technology, FIPS PUB 186-2: Digital signature standard (DSS), National Institute of Standards and Technology, January 2000.
  • 40. W. B. Pennington, On Mahler’s partition problem, Ann. of Math. (2) 57 (1953), 531–546. MR 0053959, https://doi.org/10.2307/1969735
  • 41. Christopher M. Skinner, On the Diophantine equation 𝑎𝑝^{𝑥}+𝑏𝑞^{𝑣}=𝑐+𝑑𝑝^{𝑧}𝑞^{𝑤}, J. Number Theory 35 (1990), no. 2, 194–207. MR 1057322, https://doi.org/10.1016/0022-314X(90)90112-5
  • 42. J. Solinas, Generalized mersenne numbers, Research Report CORR-99-39, Center for Applied Cryptographic Research, University of Waterloo, Waterloo, ON, Canada, 1999.
  • 43. Certicom Research The SECG group, SEC 2: Recommended elliptic curve domain parameters, Standard for Efficient Cryptography, September 2000, http://www.secg.org/.
  • 44. R. Tijdeman, On the maximal distance between integers composed of small primes, Compositio Math. 28 (1974), 159–162. MR 0345917
  • 45. Herbert S. Wilf, generatingfunctionology, 2nd ed., Academic Press, Inc., Boston, MA, 1994. MR 1277813

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 14H52, 14G50, 68R99

Retrieve articles in all journals with MSC (2000): 14H52, 14G50, 68R99


Additional Information

Vassil Dimitrov
Affiliation: Department of Mathematics, Centre for Information Security and Cryptography, University of Calgary, 2500 University drive N.W., Calgary, AB, T2N 1N4, Canada
Email: dimitrov@vlsi.enel.ucalgary.ca

Laurent Imbert
Affiliation: Department of Mathematics, Centre for Information Security and Cryptography, University of Calgary, 2500 University drive N.W., Calgary, AB, T2N 1N4, Canada
Address at time of publication: LIRMM, University Montpellier 2, CNRS, 161 rue Ada, 34392 Montpellier, France
Email: Laurent.Imbert@lirmm.fr

Pradeep K. Mishra
Affiliation: Department of Mathematics, Centre for Information Security and Cryptography, University of Calgary, 2500 University drive N.W., Calgary, AB, T2N 1N4, Canada
Email: pradeep@math.ucalgary.ca

DOI: https://doi.org/10.1090/S0025-5718-07-02048-0
Keywords: ECC, point multiplication, double-base number system, side-channel atomicity
Received by editor(s): June 5, 2006
Received by editor(s) in revised form: February 26, 2007
Published electronically: December 11, 2007
Additional Notes: This work was funded by the NSERC Strategic Grant: Novel Implementation of Cryptographic Algorithms on Custom Hardware Platforms
This work was done during the second author’s leave of absence from the CNRS at the University of Calgary.
Article copyright: © Copyright 2007 by the authors