Use the complete formulas for point doubling and addition - Githubissues

tlsfuzzer / python-ecdsa

pure-python ECDSA signature/verification and ECDH key agreement

Other

914 stars 315 forks source link

Use the complete formulas for point doubling and addition #297

Open tomato42 opened 2 years ago

tomato42 commented 2 years ago

https://safecurves.cr.yp.to/ is outdated, there are complete point addition and doubling formulas: https://eprint.iacr.org/2015/1060 we should use them to protect against bugs in special case handling

mratsim commented 1 year ago

I see that you use Jacobian coordinates.

You can also use conditional copies to select between add and doubles:

Derivation of efficient formulas:
- write-up: https://github.com/mratsim/constantine/blob/495ef44/constantine/math/elliptic/ec_shortweierstrass_jacobian.md
- impl: https://github.com/mratsim/constantine/blob/495ef449/constantine/math/elliptic/ec_shortweierstrass_jacobian.nim#L162-L334

And for projective coordinates complete formulas:

https://github.com/mratsim/constantine/blob/495ef44/constantine/math/elliptic/ec_shortweierstrass_projective.nim#L153-L406 (Note: Since I only configured secp256k1 and pairing-firnedly curve I only implemented the case where a==0 in the curve y² = x³+ax+b)