botan icon indicating copy to clipboard operation
botan copied to clipboard

Replace BigInt based elliptic curve library

Open randombit opened this issue 2 months ago • 3 comments

Botan 3.5.0

In this release pcurves is really just used for hash to curve

  • [x] Initial pcurves (point arithmetic, fixed curve params) - that's #3979
  • [ ] Add EC_Scalar and EC_AffinePoint types and implement algorithms using them #4042
  • [x] Deprecate all the functionality that existed just to support elliptic curves using BigInt, eg mod_sub, ct_reduce_below, many more.
  • [x] ~Support for providing parameterized curves, where we eg compute Montgomery params at runtime. This is required not just for user provided/application specific curves but also I don't think it's worthwhile to provide the fully parameterized/hardcoded support for obscure curves like secp160r1.~ In the short term, application curves, secp160r1, etc fall back to the currently used BigInt code

Botan 3.6.0

In this release, we tie together EC_Scalar/EC_AffinePoint to pcurves so that everything goes fast :rocket:

  • [ ] Bridge between EC_Scalar/EC_AffinePoint and pcurves (#4143)
  • [x] RFC 6979 will need some work and could become more optimized by having dedicated EC_Scalar version to avoid EC_Scalar<->BigInt conversions. (Now in #4042)
  • [ ] Convert EC keys internally to store EC_Scalar and EC_AffinePoint instead of BigInt/EC_Point

Botan 3.6.0 or later. Nice optimizations / cleanups but not critical

  • [ ] Faster mul2_vartime. Based on some reading and experimentation best option for parameters of our size is a wNAF with w==4 which should hit on average 80% dual 0s and requiring a table of 80 group elements.
  • [ ] Avoid possibility of a doubling in the fixed window mul due to blinding (see https://github.com/randombit/botan/pull/3979#discussion_r1624604450)
  • [ ] Figure out how to speed up inversions. Either searching for addition chains at compile time and/or providing a way of conveying a specific addition chain where a good one is known. Inversions are 30-40% of the entire cost of ECDSA signature generation right now, and 15-20% of the cost of ECDSA signature verification.
  • [ ] Optimize RFC6979 further - it consumes 50K cycles which really hurts especially for P-256
  • [ ] Specific field reduction support for P-256, P-384 (#4147), secp256k1 (#4113), NUMS (handled similarly to secp256k1)
  • [ ] More curves possibly? NUMS, P-192, P-224

randombit avatar Apr 20 '24 22:04 randombit