Abstract
This paper proposes a fast elliptic curve multiplication algorithm applicable for any types of curves over finite fields Fp (p a prime), based on [Mon87], together with criteria which make our algorithm resistant against the side channel attacks (SCA). The algorithm improves both on an addition chain and an addition formula in the scalar multiplication. Our addition chain requires no table look-up (or a very small number of pre-computed points) and a prominent property is that it can be implemented in parallel. The computing time for n-bit scalar multiplication is one ECDBL + (n - 1) ECADDs in the parallel case and (n - 1) ECDBLs + (n - 1) ECADDs in the single case. We also propose faster addition formulas which only use the x-coordinates of the points. By combination of our addition chain and addition formulas, we establish a faster scalar multiplication resistant against the SCA in both single and parallel computation. The improvement of our scalar multiplications over the previous method is about 37% for two processors and 5.7% for a single processor. Our scalar multiplication is suitable for the implementation on smart cards.
This work was done while the first author was staying at the Centre for Appllied CryptographicResearc h (CACR), University of Waterloo and part of this work was done while the first author was visiting Fachbereich Informatik, Technische Universität Darmstadt.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
G. Agnew, R. Mullin and S. Vanstone, “An implementation of elliptic curve cryptosystems over F 2 155”, IEEE Journal on Selected Areas in Communications, vol.11, pp.804–813, 1993.
ANSI X9.62, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), draft, 1998.
I. Blake, G. Seroussi and N. Smart, Elliptic Curves in Cryptography, Cambridge University Press, 1999.
J. Coron, “Resistance against differential power analysis for elliptic curve cryptosystems”, CHES’99, LNCS 1717, pp.292–302, Springer-Verlag, 1999.
H. Cohen, A. Miyaji and T. Ono, “Efficient elliptic curve exponentiation using mixed coordinates”, Asiacrypt’98, LNCS 1514, pp.51–65, Springer-Verlag, 1998.
C. Clavier and M. Joye, “Universal exponentiation algorithm — A first step towards provable SPA-resistance —”, CHES2001, LNCS 2162, pp.300–308, Springer-Verlag, 2001.
D. Gordon, “A survey of fast exponentiation methods”, J. Algorithms, vol.27, pp.129–146, 1998.
IEEE. IEEE P1363, Standard Specifications for Public-Key Cryptography, 2000. Available from http://groupe.ieee.org/groups/1363/
M. Joye and J. Quisquater, “Hessian elliptic curves and side-channel attacks”, CHES2001, LNCS 2162, pp.402–410, Springer-Verlag, 2001.
M. Joye and C. Tymen, “Protections against differential analysis for elliptic curve cryptography”, CHES2001, LNCS 2162, pp.377–390, Springer-Verlag, 2001.
C. Kocher, “Timing attacks on Implementations of Diffie-Hellman, RSA, DSS, and other systems”, Crypto’96, LNCS 1109, pp.104–113, Springer-Verlag, 1996.
C. Kocher, J. Jaffe and B. Jun, “Differential power analysis”, Crypto’99, LNCS 1666, pp.388–397, Springer-Verlag, 1999.
LiDIA, A C++ Library For Computational Number Theory, Technische Universtät Darmstadt, http://www.informatik.tu-darmstadt.de/TI/LiDIA/
P. Liardet and N. Smart, “Preventing SPA/DPA in ECC systems using the Jacobi form”, CHES2001, LNCS 2162, pp.391–401, Springer-Verlag, 2001.
C. Lim and P. Lee, “More flexible exponentiation with precomputation”, Crypto’94, LNCS 839, p.95–107, Springer-Verlag, 1994.
B. Möller, “Securing elliptic curve point multiplication against side-channel attacks”, ISC 2001, LNCS 2200. p.324–334, Springer-Verlag, 2001.
P. Montgomery, “Speeding the Pollard and elliptic curve methods for factorizations”, Math. of Comp, vol.48, pp.243–264, 1987.
F. Morain and J. Olivos, “Speeding up the computation on an elliptic curve using addition-subtraction chains”, Inform. Theory Appl. 24, pp.531–543, 2000.
National Institute of Standards and Technology, Recommended Elliptic Curves for Federal Government Use, in the appendix of FIPS 186-2, Available from http://csrc.nist.gov/publication/fips/fips186-2/fips186-2.pdf
K. Okeya, H. Kurumatani and K. Sakurai, “Ellipticc urves with the Montgomery form and their cryptographic applications”, PKC2000, LNCS 1751, pp.446–465, Springer-Verlag, 2000.
K. Okeya and K. Sakurai, “Power analysis breaks elliptic curve cryptosystems even secure against the timing attack”, Indocrypt 2000, LNCS 1977, pp.178–190, Springer-Verlag, 2000.
K. Okeya and K. Sakurai, “Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery-form ellipticc urve”, CHES2001, LNCS 2162, pp.126–141, Springer-Verlag, 2001.
N. Smart, “The Hessian form of an elliptic curve”, CHES2001, LNCS 2162, pp.118–125, Springer-Verlag, 2001.
Standards for Efficient Cryptography Group (SECG), Specification of Standards for Efficient Cryptography. Available from http://www.secg.org
Wireless Application Protocol (WAP) Forum, Wireless Transport Layer Security (WTLS) Specification. Available from http://www.wapforum.org
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Izu, T., Takagi, T. (2002). A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks. In: Naccache, D., Paillier, P. (eds) Public Key Cryptography. PKC 2002. Lecture Notes in Computer Science, vol 2274. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45664-3_20
Download citation
DOI: https://doi.org/10.1007/3-540-45664-3_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43168-8
Online ISBN: 978-3-540-45664-3
eBook Packages: Springer Book Archive