Mathematics of Computation

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

Author(s): Vassil Dimitrov; Laurent Imbert; Pradeep K. Mishra.
Journal: Math. Comp. 77 (2008), 1075-1104.
MSC (2000): Primary 14H52; Secondary 14G50, 68R99
Posted: December 11, 2007
Retrieve article in: PDF

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

and

. 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.

1.: J.-P. Allouche and J. Shallit, Automatic sequences, Cambridge University Press, 2003. MR 1997038 (2004k:11028)
2.: R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen, and F. Vercauteren, Handbook of elliptic and hyperelliptic curve cryptography, CRC Press, 2005. MR 2162716 (2007f:14020)
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.: J.-C. Bajard, L. Imbert, and T. Plantard, Modular number systems: Beyond the Mersenne family, Proceedings of the 11th International Workshop on Selected Areas in Cryptography, SAC'04, Lecture Notes in Computer Science, vol. 3357, Springer, 2005, pp. 159-169. MR 2181315 (2006h:94071)
6.: V. Berthé, Autour du système de numération d'Ostrowski, Bulletin of the Belgian Mathematical Society 8 (2001), 209-239. MR 1838931 (2002k:68147)
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.: I. F. Blake, G. Seroussi, and N. P. Smart, Advances in elliptic curve cryptography, London Mathematical Society Lecture Note Series, no. 317, Cambridge University Press, 2005. MR 2166105
9.: É. Brier and M. Joye, Fast point multiplication on elliptic curves through isogenies, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC 2003, Lecture Notes in Computer Science, vol. 2643, Springer, 2003, pp. 43-50. MR 2042411 (2005a:14029)
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.: J. Chung and A. Hasan, More generalized Mersenne numbers, Selected Areas in Cryptography, SAC'03, Lecture Notes in Computer Science, vol. 3006, Springer, 2004, pp. 335-347. MR 2094740 (2005f:94089)
12.: M. Ciet, M. Joye, K. Lauter, and P. L. Montgomery, Trading inversions for multiplications in elliptic curve cryptography, Designs, Codes and Cryptography 39 (2006), no. 2, 189-206. MR 2209936 (2006j:94057)
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.: H. Cohen, A. Miyaji, and T. Ono, Efficient elliptic curve exponentiation using mixed coordinates, Advances in Cryptology, ASIACRYPT'98, Lecture Notes in Computer Science, vol. 1514, Springer, 1998, pp. 51-65. MR 1726152
15.: E. De Win, S. Bosselaers, S. Vandenberghe, P. De Gersem, and J. Vandewalle, A fast software implementation for arithmetic operations in $\mathrm{GF}(2^n)$ , Advances in Cryptology, ASIACRYPT'96, Lecture Notes in Computer Science, vol. 1163, Springer, 1996, pp. 65-76. MR 1486049
16.: V. Dimitrov, L. Imbert, and P. K. Mishra, Efficient and secure elliptic curve point multiplication using double-base chains, Advances in Cryptology, ASIACRYPT'05, Lecture Notes in Computer Science, vol. 3788, Springer, 2005, pp. 59-78. MR 2236727
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, Information Processing Letters 66 (1998), no. 3, 155-159. MR 1627991 (99d:94023)
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.: K. Eisenträger, K. Lauter, and P. L. Montgomery, Fast elliptic curve arithmetic and improved Weil pairing evaluation, Topics in Cryptology - CT-RSA 2003, Lecture Notes in Computer Science, vol. 2612, Springer, 2003, pp. 343-354. MR 2080147
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.: D. M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms 27 (1998), no. 1, 129-146. MR 1613189 (99g:94014)
24.: T. Granlund, GMP, the GNU multiple precision arithmetic library, see: http://www. swox.com/gmp/.
25.: J. Guajardo and C. Paar, Efficient algorithms for elliptic curve cryptosystems, Advances in Cryptology, CRYPTO'97, Lecture Notes in Computer Science, vol. 1294, Springer, 1997, pp. 342-356. MR 1630403 (99b:94033)
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.: D. Hankerson, A. Menezes, and S. Vanstone, Guide to elliptic curve cryptography, Springer, 2004. MR 2054891 (2005c:94049)
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.: M. Joye and C. Tymen, Protections against differential analysis for elliptic curve cryptography - an algebraic approach, Cryptographic Hardware and Embedded Systems, CHES'01, Lecture Notes in Computer Science, vol. 2162, Springer, 2001, pp. 377 - 390. MR 1946618 (2003k:94031)
33.: N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation 48 (1987), no. 177, 203-209. MR 866109 (88b:94017)
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.: K. Mahler, On a special functional equation, Journal of the London Mathematical Society s1-15 (1940), no. 2, 115-123. MR 0002921 (2:133e)
38.: V. S. Miller, Uses of elliptic curves in cryptography, Advances in Cryptology, CRYPTO'85, Lecture Notes in Computer Science, vol. 218, Springer, 1986, pp. 417-428. MR 851432 (88b:68040)
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, Annals of Mathematics 57 (1953), no. 3, 531-546. MR 0053959 (14:846m)
41.: C. M. Skinner, On the diophantine equation , Journal of Number Theory 35 (1990), 194-207. MR 1057322 (91h:11021)
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 Mathematica 28 (1974), 159-162. MR 0345917 (49:10646)
45.: H. S. Wilf, Generatingfunctionology, 2nd ed., Academic Press Inc., 1994. MR 1277813 (95a:05002)

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

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: 10.1090/S0025-5718-07-02048-0
PII: S 0025-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
Posted: 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.
Copyright of article: Copyright 2007, by the authors

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS