Abstract
Recently it has been shown that smart cards as cryptographic devices are vulnerable to power attacks if they have no defence against them. Randomization on ECC scalar multiplication is one of the fundamental concepts in methods of defence against side-channel attacks. In this paper by using the randomization concept together with the NAF recoding algorithm, we propose an efficient countermeasure for ECCs against power attacks. The countermeasure provides a randomized signed-scalar representation at every scalar multiplication to resist DPA. To protect against SPA it additionally employs a simple SPA-immune addition-subtraction multiplication algorithm. Our analysis shows that it needs no additional computation load compared to the ordinary binary scalar multiplication, where the average number of doublings plus additions for a bit length n is 1.5n+O(1).
Chapter PDF
Similar content being viewed by others
Keywords:
References
V. S. Miller, “Use of elliptic curve in cryptography,” In Advances in Cryptology-CRYPTO’85, LNCS 218, pp. 417–426, Springer-Verlag, 1986.
N. Koblitz, Elliptic curve cryptosystems, In Mathematics of Computation, vol. 48, pp. 203–209, 1987.
R. Anderson and M. Kuhn, “Low cost attacks on tamper resistant devices,” In Pre-proceedings of Security Protocol Workshop, pp. 125–136, Springer-Verlag, April 1997.
D. Boneh, R. A. DeMillo, and R. J. Lipton, “On the importance of checking cryptographic protocols for faults,” In Advances in Cryptology-EUROCRYPT’97, LNCS 1233, pp. 37–51, Springer-Verlag, 1997.
F. Bao, R. H. Deng, Y. Han, A. Jeng, A. D. Narasimbalu, and T. Ngair, “Breaking public key cryptosystems on tamper resistant devices in the presence of transient faults,” In Pre-proceedings of Security Protocol Workshop, pp. 115–124, Springer-Verlag, April 1997.
P. Kocher, J. Jaffe and B. Jun, “Differential power analysis,” In Advances in Cryptology-CRYPTO’99, LNCS 1666, pp. 388–397, Springer-Verlag, 1999.
J. S. Coron, “Resistance against differential power analysis for elliptic curve cryptosystems,” In Cryptographic Hardware and Embedded Systems-CHES’ 99, LNCS 1717, pp. 292–302, Springer-Verlag, 1999.
E. Oswald and M. Aigner, “Randomized addition-subtraction chains as a countermeasure against power attacks,” In Cryptographic Hardware and Embedded Systems-CHES’ 01, LNCS 2162, pp. 39–50, Springer-Verlag, 2001.
B. Möller, “Securing elliptic curve point multiplication against side-channel attacks,” In Information Security Conference-ISC’01, LNCS 2200, pp. 324–334, 2001.
T.S. Messerges, E.A. Dabbish, and R.H. Sloan, “Power analysis attacks of modular exponentiation in smartcards,” In Cryptographic Hardware and Embedded Systems-CHES’ 99, LNCS 1717, pp. 144–157, Springer-Verlag, 1999.
M. A. Hasan, “Power analysis attacks and algorithmic approaches to their countermeasures for Koblitz curve cryptosystems,” In Cryptographic Hardware and Embedded Systems-CHES’ 00, LNCS 1965, pp. 93–108, Springer-Verlag, 2000.
K. Okeya and K. Sakurai, “Power analysis breaks elliptic curve cryptosystems even secure against the timing attack,” In Advances in Cryptology-INDOCRYPT’00, LNCS 1977, pp. 178–190, Springer-Verlag, 2000.
P. Y. Liardet and N. P. Smart, “Preventing SPA/DPA in ECC systems using the Jacobi form,” In Cryptographic Hardware and Embedded Systems-CHES’ 01, LNCS 2162, pp. 391–401, Springer-Verlag, 2001.
M. Joye and J. J. Quisquater, “Hessian elliptic curves and side-channel attacks,” In Cryptographic Hardware and Embedded Systems-CHES’ 01, LNCS 2162, pp. 402–410, Springer-Verlag, 2001.
D. E. Knuth, The art of computer programming, vol 2: Seminumerical Algorithms, Reading, MA: Addison-Wesley, 2nd Edition, 1981.
F. Morain and J. Olivos, “Speeding up the computation on an elliptic curve using addition-subtraction chains,” Inform Theory Appl., vol. 24, pp. 531–543, 1990.
G. W. Reitwiesner, Binary arithmetic, Advances in Computers, 1:231–308, 1960.
O. Eğecioğlu and ç. K. Koç, “Exponentiation using canonical recoding,” Theoretical Computer Science, vol. 129, no. 2, pp. 407–417, 1994.
O. Eğecioğlu and ç. K. Koç, “Fast modular exponentiation,” In E. Arikan, editor, Communication, Control, and Signal Processing: Proceedings of 1990 Bilkent International Conference on New Trends in Communication, Control, and Signal Processing, pp. 188–194, Bilkent Univ. Ankara, Turkey, July 1990.
C. N. Zhang, “An improved binary algorithm for RSA,” Computer Math. Applic., vol. 25, no. 6, pp. 15–24, 1993.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cheol Ha, J., Jae Moon, S. (2003). Randomized Signed-Scalar Multiplication of ECC to Resist Power Attacks. In: Kaliski, B.S., Koç, ç.K., Paar, C. (eds) Cryptographic Hardware and Embedded Systems - CHES 2002. CHES 2002. Lecture Notes in Computer Science, vol 2523. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36400-5_40
Download citation
DOI: https://doi.org/10.1007/3-540-36400-5_40
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00409-7
Online ISBN: 978-3-540-36400-9
eBook Packages: Springer Book Archive