Paper 2017/669

Speeding up Elliptic Curve Scalar Multiplication without Precomputation

Kwang Ho Kim, Junyop Choe, Song Yun Kim, Namsu Kim, and Sekung Hong

Abstract

This paper presents a series of Montgomery scalar multiplication algorithms on general short Weierstrass curves over odd characteristic fields, which need only 12 field multiplications plus 12 ~ 20 field additions per scalar bit using 8 ~ 10 field registers, thus significantly outperform the binary NAF method on average. Over binary fields, the Montgomery scalar multiplication algorithm which was presented at the first CHES workshop by L´opez and Dahab has been a favorite of ECC implementors, due to its nice properties such as high efficiency outperforming the binary NAF, natural SPA-resistance, generality coping with all ordinary curves and implementation easiness. Over odd characteristic fields, the new scalar multiplication algorithms are the first ones featuring all these properties. Building-blocks of our contribution are new efficient differential addition-and-doubling formulae and a novel conception of on-the-fly adaptive coordinates which softly represent points occurring during a scalar multiplication not only in accordance with the basepoint but also bits of the given scalar. Importantly, the new algorithms are equipped with built-in countermeasures against known side-channel attacks, while it is shown that previous Montgomery ladder algorithms with the randomized addressing countermeasure fail to thwart attacks exploiting address-dependent leakage.

Note: I have changed authors list.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
pgitech namsukim @ aliyun com
History
2017-07-06: received
Short URL
https://ia.cr/2017/669
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/669,
      author = {Kwang Ho Kim and Junyop Choe and Song Yun Kim and Namsu Kim and Sekung Hong},
      title = {Speeding up Elliptic Curve Scalar Multiplication without Precomputation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/669},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/669}},
      url = {https://eprint.iacr.org/2017/669}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.