When I wrote the first version of Nettle's ECC code back in 2013, I needed a side-channel silent modular inversion algorithm (and for some reason, I wasn't happy to just use the powering method), so I had to come up with my own algorithm, which worked fine but was rather slow.
To speed it up, I've written specialized powering code, used since nettle-3.7. A few months ago I was made aware of this 2019 paper by Daniel J. Bernstein and Bo-Yin Yang: https://eprint.iacr.org/2019/266.pdf. It's rather clever, related to the 2-adic gcd algorithm of Zimmermann and Stehlé, but with new tricks to turn it into a sequence of simple steps each step doing a single bit at the low end. And then a rather complex computer-aided proof to get a practical worst-case bound for the number of such steps needed for the algorithm to terminate. I've just pushed a branch "new-mod-inv" that replaces all old inversion code except the mod p inversion for the secp192r1 curve, where the powering code seems to still be faster. On my machine it gives a nice performance improvement for the larger curves (secp256r1, secp384r1, secp521r1, in particular for the signing operations which are 30--40% faster on my machine). Unfortunately, ed25519 doesn't get any improvement, and possibly even a small regression (puzzling, since primitives such as the modular inversion itself and the scalar multiply operations appear slightly faster). Additional benchmarks welcome. There are a few more optimiations to try for the new inversion code algorithm, but there may be lower hanging fruit to improve overall ecc performance (e.g., review use of lookup tables; sizes haven't been reviewed for a long time, and for verify operation that doesn't handle secret inputs, we can likely gain some speed by using point operations without ny side-channel silence). Regards, /Niels -- Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ nettle-bugs mailing list -- nettle-bugs@lists.lysator.liu.se To unsubscribe send an email to nettle-bugs-le...@lists.lysator.liu.se
