Abstract
In this paper we address the problem of protecting elliptic curve scalar multiplication implementations against side-channel analysis by using the atomicity principle. First of all we reexamine classical assumptions made by scalar multiplication designers and we point out that some of them are not relevant in the context of embedded devices. We then describe the state-of-the-art of atomic scalar multiplication and propose an atomic pattern improvement method. Compared to the most efficient atomic scalar multiplication published so far, our technique shows an average improvement of up to 10.6%.
Chapter PDF
Similar content being viewed by others
References
ANSI X9.62–2005. Public Key Cryptography for The Financial Service Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA). American National Standards Institute, November 16 (2005)
ANSI X9.63–2001. Public Key Cryptography for The Financial Service Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography. American National Standards Institute, November 20 (2001)
Arno, S., Wheeler, F.: Signed digit representations of minimal Hamming weight. IEEE Transactions on Computers 42(8), 1007–1009 (1993)
Bernstein, D.J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted edwards curves. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol. 5023, pp. 389–405. Springer, Heidelberg (2008)
Bernstein, D.J., Lange, T.: Explicit-formulas database, http://www.hyperelliptic.org/EFD
Bernstein, D.J., Lange, T.: Faster addition and doubling on elliptic curves. Cryptology ePrint Archive, Report 2007/286 (2007), http://eprint.iacr.org/
Brier, E., Joye, M.: Weierstraß Elliptic Curves and Side-Channel Attacks. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 335–345. Springer, Heidelberg (2002)
Brown, M., Hankerson, D., López, J., Menezes, A.: Software Implementation of the NIST Elliptic Curves Over Prime Fields. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 250–265. Springer, Heidelberg (2001)
Chevallier-Mames, B., Ciet, M., Joye, M.: Low-cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity. IEEE Transactions on Computers 53(6), 760–768 (2004)
Chevallier-Mames, B., Joye, M.: Procédé cryptographique protégé contre les attaques de type á canal caché. French patent, FR 28 38 210 (April 2002)
Cohen, H., Ono, T., Miyaji, A.: Efficient Elliptic Curve Exponentiation Using Mixed Coordinate. In: Ohta, K., Dingyi, P. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 51–65. Springer, Heidelberg (1998)
Coron, J.-S.: Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 292–302. Springer, Heidelberg (1999)
Dimitrov, V., Imbert, L., Mishra, P.: Efficient and Secure Elliptic Curve Point Multiplication using Double-Base Chains. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 59–78. Springer, Heidelberg (2005)
ECC Brainpool. ECC Brainpool Standard Curves and Curve Generation. BSI, v. 1.0 (2005), http://www.ecc-brainpool.org
ECC Brainpool. ECC Brainpool Standard Curves and Curve Generation. BSI, Internet Draft v. 3 (2009), http://tools.ietf.org/html/draft-lochter-pkix-brainpool-ecc-03
Edwards, H.M.: A normal form for elliptic curves. Bulletin of the American Mathematical Society 44, 393–422 (2007)
FIPS PUB 186-3. Digital Signature Standard. National Institute of Standards and Technology, March 13 (2006), Draft
Großschädl, J., Avanzi, R.M., Savas, E., Tillich, S.: Energy-Efficient Software Implementation of Long Integer Modular Arithmetic. In: Rao, J.R., Sunar, B. (eds.) CHES 2005. LNCS, vol. 3659, pp. 75–90. Springer, Heidelberg (2005)
Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curve Cryptography, Springer Professional Computing Series (January 2003)
Hesse, O.: Uber die Elimination der Variabeln aus drei algebraischen Gleichungen vom zweiten Grade mit zwei Variabeln. Journal für die reine und angewandte Mathematik 10, 68–96 (1844)
Joye, M.: Fast Point Multiplication on Elliptic Curves Without Precomputation. In: von zur Gathen, J., Imaña, J.L., Koç, Ç.K. (eds.) WAIFI 2008. LNCS, vol. 5130, pp. 36–46. Springer, Heidelberg (2008)
Joye, M.: Highly regular m-ary powering ladders. In: Jacobson, M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, pp. 135–147. Springer, Heidelberg (2009)
Joye, M., Tymen, C.: Protections against Differential Analysis for Elliptic Curve Cryptography. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 386–400. Springer, Heidelberg (2001)
Joye, M., Yen, S.-M.: The Montgomery Powering Ladder. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 291–302. Springer, Heidelberg (2003)
Kocher, P.: Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)
Kocher, P., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
Longa, P.: Accelerating the Scalar Multiplication on Elliptic Curve Cryptosystems over Prime Fields. PhD thesis, School of Information Technology and Engineering, University of Ottawa (2007)
Longa, P., Miri, A.: New Multibase Non-Adjacent Form Scalar Multiplication and its Application to Elliptic Curve Cryptosystems (extended version). Cryptology ePrint Archive, Report 2008/052 (2008), http://eprint.iacr.org/
Medwed, M., Oswald, E.: Template attacks on ECDSA. Cryptology ePrint Archive, Report 2008/081 (2008), http://eprint.iacr.org/
Meloni, N.: New point addition formulae for ECC applications. In: Carlet, C., Sunar, B. (eds.) WAIFI 2007. LNCS, vol. 4547, pp. 189–201. Springer, Heidelberg (2007)
Meloni, N., Hasan, M.A.: Elliptic Curve Scalar Multiplication Combining Yao’s Algorithm and Double Bases. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 304–316. Springer, Heidelberg (2009)
Montgomery, P.: Speeding the Pollard and Elliptic Curve Methods of Factorization. Mathematics of Computation 48, 243–264 (1987)
SP 800-78-1. Cryptographic Algorithms and Key Sizes for Personal Identity Verification. National Institute of Standards and Technology (August 2007)
TR-03111. Elliptic Curve Cryptography Based on ISO 15946. Federal Office for Information Security (BSI), February 14 (2007)
Yao, A.C.-C.: On the Evaluation of Powers. SIAM Journal on Computing 5(1), 100–103 (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Giraud, C., Verneuil, V. (2010). Atomicity Improvement for Elliptic Curve Scalar Multiplication. In: Gollmann, D., Lanet, JL., Iguchi-Cartigny, J. (eds) Smart Card Research and Advanced Application. CARDIS 2010. Lecture Notes in Computer Science, vol 6035. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12510-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-12510-2_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12509-6
Online ISBN: 978-3-642-12510-2
eBook Packages: Computer ScienceComputer Science (R0)