Page MenuHomePhabricator

[secp256k1] Use modified divsteps with initial delta=1/2 for constant-time
ClosedPublic

Authored by Fabien on May 27 2025, 12:43.

Details

Summary
This updates the divsteps-based modular inverse code to use the modified version which starts with delta=1/2. For variable time, the delta=1 variant is still used as it appears to be faster.

See https://github.com/sipa/safegcd-bounds/tree/master/coq and https://medium.com/blockstream/a-formal-proof-of-safegcd-bounds-695e1735a348 for a proof of correctness of this variant.

Backport of secp256k1#906.

Test Plan
ninja check-secp256k1