The double-base number system and its application to elliptic curve cryptography. (English) Zbl 1133.14034

This paper, an extension of a previous paper of the authors [Advances in Cryptology, ASIACRYPT’96, LNCS vol. 3788, Springer, 59–78 (2005; Zbl 1154.94388)], presents a representation of a natural number as a sum of powers of 2 and 3 and its application to scalar multiplication on elliptic curves.
The scalar multiplication of a point on an elliptic curve by a natural number \(n\) is the basic operation in the discrete logarithm based Elliptic Curve Cryptography. To minimize its computational cost, alternatives to the usual binary representation of \(n\), such as Non-Adjacent Form (NAF) or windows methods (w-NAF), as well as different coordinate representations of the points of the curve have been proposed. For a good overview of the problem to see the book of D. Hankerson, A. Menezes and S. Vanstone [Guide to elliptic curve cryptography. Springer Professional Computing. New York, NY: Springer. (2004; Zbl 1059.94016)].
In the present paper the authors propose to use the representation of the scalar \(n\) as a sum of mixed powers of 2 and 3. This double-base number system (DBNS), in the authors’ words, “leads to fewer point additions that others classical methods”, and it can also provides protection against various kinds of side channels attacks.
Section 2 studies the DBNS representations and gives a greedy algorithm (Algorithm 1) to find a sparse signed DBNS representation (although maybe not a minimal one). Section 2 also recalls the basic of elliptic curves and the cost of point addition and point doubling in both affine and Jacobian projective coordinates.
Section 3 studies efficient ways to perform elliptic curve operations (point tripling, point quadrupling, etc) to be applied in the DBNS scalar multiplication algorithm presented in Section 4. In order to reduce the number of operations the algorithm uses a modified DBNS representation of the scalar \(n\) (Algorithm 2).
The authors illustrate the efficiency of the proposed algorithm in Section 5, providing results of numerical experiments over 10.000 randomly chosen 160 bits integers and giving the comparison with others classical (double-and-add, NAF, w-NAF) and recent representation methods.


14G50 Applications to coding theory and cryptography of arithmetic geometry
94A60 Cryptography
11A63 Radix representation; digital problems
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)


Full Text: DOI


[1] Jean-Paul Allouche and Jeffrey Shallit, Automatic sequences, Cambridge University Press, Cambridge, 2003. Theory, applications, generalizations. · Zbl 1086.11015
[2] Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren , Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006. · Zbl 1082.94001
[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. · Zbl 1172.94558
[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. · Zbl 1295.94010
[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. · Zbl 1117.94008 · doi: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). · Zbl 0994.68100
[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 , Advances in elliptic curve cryptography, London Mathematical Society Lecture Note Series, vol. 317, Cambridge University Press, Cambridge, 2005. · Zbl 1089.94018
[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. · Zbl 1030.11027 · doi: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. · Zbl 1300.94045
[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. · Zbl 1081.94021 · doi: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. · Zbl 1116.14026 · doi: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. · Zbl 1126.94326
[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. · Zbl 0939.11039 · doi: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\(^{n}\)), Advances in cryptology — ASIACRYPT ’96 (Kyongju), Lecture Notes in Comput. Sci., vol. 1163, Springer, Berlin, 1996, pp. 65 – 76. · Zbl 1005.94535 · doi: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. · Zbl 1154.94388 · doi: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. · Zbl 1078.94510 · doi: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. · Zbl 1151.94506
[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. · Zbl 1175.94076
[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. · Zbl 1038.11079 · doi: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. · Zbl 0915.11064 · doi: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. · Zbl 0937.94009 · doi: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. · Zbl 0998.94534
[27] Darrel Hankerson, Alfred Menezes, and Scott Vanstone, Guide to elliptic curve cryptography, Springer Professional Computing, Springer-Verlag, New York, 2004. · Zbl 1059.94016
[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. · Zbl 0955.94004
[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. · Zbl 1033.11502
[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. · Zbl 1055.94516
[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. · Zbl 1012.94550 · doi:10.1007/3-540-44709-1_31
[33] Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203 – 209. · Zbl 0622.94015
[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. · Zbl 0942.94501
[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. · Zbl 1329.94070
[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. · Zbl 0027.15704 · doi: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. · doi: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. · Zbl 0050.04005 · doi:10.2307/1969735
[41] Christopher M. Skinner, On the Diophantine equation \?\?^{\?}+\?\?^{\?}=\?+\?\?^{\?}\?^{\?}, J. Number Theory 35 (1990), no. 2, 194 – 207. · Zbl 0703.11017 · doi: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. · Zbl 0283.10024
[45] Herbert S. Wilf, generatingfunctionology, 2nd ed., Academic Press, Inc., Boston, MA, 1994. · Zbl 0831.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.