Paper 2017/669

Speeding up Elliptic Curve Scalar Multiplication without Precomputation

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


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
pgitech namsukim @ aliyun com
2017-07-06: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.