Add support for verifying P-521 signatures with SHA-512 and SHA-384

[briansmith]

Work plan:

• Add benchmarks analogous to bench/x25519.rs for P-256 and P-384 ECDH compute_public_key (covers base point multiplication), ECDH agree_ephemeral, (covers variable point multiplication), and ECDSA verification (covers twin point multiplication). We will use these benchmarks to verify that expanding the size of Point, Elem, and Scalar in src/ec/suite_b/ops does not negatively affect non-P-521 performance.
  • ECDH benchmarks: implemented in PR Generalize agreement benchmarks to support all algorithms. #1773.
  • Issue Add ECDSA verification benchmarks #1772: ECDSA verification benchmarks.
• Extend the code generator mk/generate_curves.py to also generate the boilerplate code in gfp_p384.c, in particular the definitions of the curve-specific constants.
• Extend the code generator mk/generate_curves.py to also generate the test input files p{256,384}elem{div_by_2,mul,neg,sum}_tests.txt. (Not strictly needed if we end up modifying and using generate_tests.cc to (re)generate test data files.)
• Stop using Montgomery encoding in test data files, because P-521 is the first curve we support that has different Montgomery encoding depending on the target word size (32-bit vs 64-bit):
  • Change the test input files p{256,384}_point_mul_base_tests.txt so that the points are NOT Montgomery-encoded. I started this in PR EC: Avoid Montgomery encoding in point arithmetic test data files. #1770 by creating a new test data file generator that generates non-Montgomery-encoded test data. Once the rest of the changes are made, this code generator can be run to generate the correct data files.
  • Change the test scaffolding functions consume_elem, consume_point, etc. in src/ec/suite_b/ops.rs so that when we read a not-Montgomery-encoded field element or point from a data file, the test scaffolding does the Montgomery-encoding itself before returning it.
  • Somehow replace the tests p{256,384}_point_{double,sum}_tests.txt with tests that aren't sensitive to the Montgomery encoding. Whoever picks this up, let's make a plan for doing this beforehand.
• Vlad's PR Implement NIST P521 signature verification #1631 that actually adds the P-521 signature support, extended to add P-521 benchmarks. The generators for the test data files should be supported to allow the addition of p521_elem_{div_by_2,mul,neg,sum}_test, p521_elem_{div_by_2,mul,neg,sum}_test, and p521_point_mul_test.

Work that was already done to support this:

• PR NFC EC: DRY PRIVATE_SCALAR_OPS.oneRR_mod_n.limbs #1755, PR EC: Use only array types when crossing Rust<->C boundary #1758, and PR Replace limbs initializer with const from_hex #1702 improved the existing code to serve as a better model for the P-521 code.
• PR Add simplified elliptic curve code generator. #1756 added the automation for verifying that the constants in the P-521 code are correct.
• PR EC Suite B: Remove redundant "point_mul" tests. #1769 and PR EC: Avoid Montgomery encoding in point arithmetic test data files. #1770 made progress on the Montgomery encoding issues.

[briansmith]

Regarding the test case data generation: I created a branch b/generate-curve that contains the old (current) test case data generator. See https://github.com/briansmith/ring/blob/b/generate-curve/boringssl/tool/generate_tests.cc. I am fine with removing the point multiplication test generation from generate_tests.cc as those were already usurped by crypto/fipsmodule/ec/make_ec_scalar_base_mult_tests.go. I would be fine with modifying the test of generate_tests.cc to resolve the Montgomery-encoding issues and to add P-521 test data generation as a stopgap. I am also open to alternate solutions regarding how the test data files get generated. The important thing is that we have the same level of test coverage for P-521 as we have for P-384, and that we have automation for extending these tests easily across all curves.

[briansmith]

Regarding benchmarks: It turns out that the agreement (ECDH) benchmarks are sufficient for the private key operation side, as base point multiplication is handled by compute_public_key benchmarks and variable-point benchmarks are handled by the agree_ephemeral benchmarks. I generalized the X25519 benchmarks to support all 3 currently-supported algorithms in PR #1773.

[briansmith]

Here is the original version of mk/generate_curves.py that actually generated C code:
gfp_generate.py.txt

[vkrasnov]

I think most of the plan is now addressed.
The benchmarks are merged
generate_curves.py generates the constants for p384
I have a PR open to avoid montgomery encoding in base point mul tests and regenerated the tests with generate_tests.cc
I also split my PR into two, with the first parts simply making the P384 code more generic