botan
botan copied to clipboard
Replace BigInt based elliptic curve library
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
andEC_AffinePoint
types and implement algorithms using them #4042 - [x] Deprecate all the functionality that existed just to support elliptic curves using
BigInt
, egmod_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 avoidEC_Scalar<->BigInt
conversions. (Now in #4042) - [ ] Convert EC keys internally to store
EC_Scalar
andEC_AffinePoint
instead ofBigInt
/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