Replace BigInt based elliptic curve library

[randombit]

Botan 3.5.0

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

• Initial pcurves (point arithmetic, fixed curve params) - that's Add library for compile time instantiation of elliptic curves #3979
• Deprecate all the functionality that existed just to support elliptic curves using BigInt, eg mod_sub, ct_reduce_below, many more.
• 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 🚀

• Convert EC keys internally to store EC_Scalar and EC_AffinePoint instead of BigInt/EC_Point (In EC keys store the data as EC_Scalar / EC_AffinePoint #4203)
• Bridge between EC_Scalar/EC_AffinePoint and pcurves (Bridge pcurves into the main elliptic curve arithmetic #4143)
• Add EC_Scalar and EC_AffinePoint types and implement algorithms using them Add EC_Scalar and EC_AffinePoint types #4042
• 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 Add EC_Scalar and EC_AffinePoint types #4042)

Bumped to 3.7.0

Work originally planned for 3.6.0 but bumped to 3.7.0

• Add new constructors to EC keys, deprecate old constructors
• Technical debt patrol - remove duplicated logic between the various types
• Start removing stuff replaced by pcurves, eg CurveGFP_NIST (we can just use Montgomery for everything)

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. JSF or bust it seems
• Better variable base mul algorithms. OpenSSL ECDH uses https://link.springer.com/content/pdf/10.1007/3-540-45664-3_20.pdf
• co-Z mul? https://eprint.iacr.org/2011/338.pdf
• Faster doubling. We saw a huge bump for ECDH and ECDSA verify from Add fast iterated point doubling #4221 / Improve field element halving #4225 / Faster iterated point doubling for generic A and A == 0 cases #4257, this maybe the lowest hanging fruit right now. Maybe dbl-2004-hmv
• Avoid possibility of a doubling in the fixed window mul due to blinding (see Add library for compile time instantiation of elliptic curves #3979 (comment))
• Optimize RFC6979 further - it consumes 50K cycles which really hurts especially for P-256
• More curves possibly? NUMS (Add NUMS curve numsp512d1 #4251), P-192 (Add P-192 to pcurves #4190), P-224 (Add pcurves P-224 #4218)
• Optimize bytes_to_words kind of comically inefficient right now
• 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. Support fast field inversion for P-256, P-384, and P-521 #4209 Faster modular inversion #1479 Avoid an inversion during ECDSA/SM2/etc signature verification #4211 Apply projection trick in pcurves as well #4215 Faster scalar inversions for P-384 and P-521 #4213
• Specific field reduction support for P-256, P-384 (Faster pcurves reductions for P-256 and P-384 #4147), secp256k1 (Add faster reduction for secp256k1 pcurves #4113), NUMS (handled similarly to secp256k1), sm2p256v1 (Solinas prime so handled like P-256 Add sm2p256v1 pcurves optimizations #4240)

[reneme]

We should consider compile time configuration of which curves get instantiated (as pointed out here). Much like the compile-time configuration of having "kyber" and/or "kyber_90s", for instance.

Adding one build module per curve should do the trick, and probably provides the best affordance for users. On the other hand, it produces quite a bit of boilerplate due to subdirectories, info.txt files and code machinery.

Alternatively, I could see this as a dedicated compile-time switch: Like:

• ./configure.py --enable-elliptic-curves=all (the default)
• ./configure.py --enable-elliptic-curves=p256,brainpool256 (a restricted set)

and then simply #ifdef the instantiations in pcurves.cpp accordingly.

[randombit]

The --enable-elliptic-curves approach is potentially confusing since even if you disable the pcurves module entirely, the elliptic curves still exist. All that ends up happening is you fall back to the slower BigInt code. [*]

[*] I mean right now ECDSA etc still use BigInt, even after both #3979 and #4042 land. There are several more steps here until the whole thing hangs together. But in the end state, we'll have fast ECC for specific curves, plus fallback code for weird curves, application curves, etc. If you disable the fast curve, it doesn't disable the curve, just disables it going fast.

That said there may be environments where the code size becomes an issue. I tried out a module per curve and it was not so bad. There are likely to not be more than ~5 new curves added here over time so I don't think it's an issue in an ongoing way.

In the end we could consider also having a way of disabling the slowpath BigInt stuff, which would benefit environments that are using just P-256 or something.

[reneme]

Nice! I saw that you split the curve into compile-time modules. Indeed the boilerplate isn't so bad. Also provides a nice place to keep curve-specific special cases. 👍

I added a few minor suggestions, in which the type -> "Internal" might need some extra attention. Perhaps have a new module type "Feature" (which might also be better suited for "Kyber" vs. "Kyber90s", and similar situations...)?

[Honzaik]

Hello,

I am new to this library so I might be missing something, but from what I understand, you are deprecating EC_Point and replacing it with EC_AffinePoint. My concern is, that currently I dont see currently how to add two distinct EC_AffinePoints. Of course, for Diffie-Hellman all one needs is interface that takes a scalar n and calculates n*P for some point P. However, in other applications you may want to add distinct points.

So my question is, is there a way to add two EC_AffinePoints?

Thank you in advance.