Develop modern implementations of some common elliptic curves. This implementation will use modern formulas and implementation techniques in order to improve performance while simplifying the code. The following curves are implemented under this enhancement: secp256r1, secp384r1, secp521r1.

There are two components of the implementation that are mostly independent: the elliptic curve point arithmetic and the finite field arithmetic.

For the EC point arithmetic, a good approach is to use the technique described in "Complete addition formulas for prime order elliptic curves" by Renes, Costello, and Batina. The formulas in this paper are relatively simple and efficient, and they include specializations for a=-3 as in the NIST prime curves. The same formulas can be used for all curves---the only thing that varies is one of the curve coefficients, and the finite field, which will have a different implementation for each curve.

For the finite field arithmetic, we can extend the existing field arithmetic library that was developed for X25519/X448, EdDSA, and Poly1305. The NIST primes have a similar structure to the primes used in these schemes, except they tend to have more terms, and the largest term doesn't have many useful factors. So we can continue to use the approach that was used in the Curve25519 field: use a few extra bits in the representation (e.g. 260 bits for the 256-bit field) and shift values around as necessary during reduction. The extra terms cause some extra operations during reduction (compared to more modern fields like in Curve25519), but all coefficients of these terms are +/-1, so these extra operations are all additions/subtractions.

This effort will require the implementation of 3-6 new finite field arithmetic classes, bringing the grand total up to 5-10 classes. These classes contain hand-optimized multiply/carry/reduce functions that maximize the use of primitive values to reduce temporary object allocation. They are somewhat cumbersome to develop, and very difficult to read and understand. A code generator will be used to reduce the development/maintenance burden for all these classes.