Scalar-mul: Constant-Time double-and-add

[mratsim]

For curves without endomorphisms

https://eprint.iacr.org/2017/669.pdf
https://www.aimsciences.org/article/exportPdf?id=5c293be6-723e-4b97-ae1d-ff359e261cdb

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ópez 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.

paulmillr/noble-secp256k1#55

This is an algorithm for EC multiplication that emulates the Montgomery
Ladder double-and-add, but in a constant time way. An early version of
this algorithm was published in 2017, and the version implemented here
was published in 2020. The result is constant time multiply that is 85%
faster than wNAF, <10% slower than endomorphic Montgommery Ladder and
~20% faster than w/o endomorphism.

bitcoin-core/secp256k1#1099

May be combined with #35