Add ECDSA verification benchmarks

[briansmith]

Most immediately, we need to benchmark ring against OpenSSL for the P-256 and P-384 curves on x86-64 (Haswell and later).

ECDSA verification isn't (necessarily) a constant-time operation; the speed of the verification may depend on the value of the public key and/or the value of the signature (r, s). We know that ring and recent versions of OpenSSL currently use a constant-time implementation for P-256 verification. ring uses a constant-time implementation for P-384 too, but OpenSSL uses a variable-time implementation. Therefore, we need to use multiple public keys and multiple signatures for each public key in the benchmark. This makes the benchmarking more difficult than what we do for other algorithms, where we assume that the values of the inputs don't affect the timing.

[ranweiler]

@briansmith, I'm looking at how to do this for Ed25519 verification, and presumably the solution for that applies here as well.

I'm interested in what you think about the following two items:

1. Benchmarking infrastructure: I'm imagining something similar to the machinery that lets us use ed25519_tests.txt, though we could get away with less if we didn't commit to parsing a separate file. It might be worth a little extra legwork to have a solid general mechanism for file-based tests.

2. Cases and exhaustiveness. Presumably we'd like e.g. a variety of Hamming weights in the various parameters and inputs, but I'm not sure how exhaustive we need to be, or what other special cases we should consider.

Thoughts?

[briansmith]

Benchmarking infrastructure: I'm imagining something similar to the machinery that lets us use ed25519_tests.txt, though we could get away with less if we didn't commit to parsing a separate file. It might be worth a little extra legwork to have a solid general mechanism for file-based tests.

We could either use the ring file_test framework (it's exported as ring::test) or include_bytes! or whatever.

Cases and exhaustiveness. Presumably we'd like e.g. a variety of Hamming weights in the various parameters and inputs, but I'm not sure how exhaustive we need to be, or what other special cases we should consider.

Realistically, perfect is definitely the enemy of the good here. We can always add more cases after the initial one(s) are added. It would be include BoringSSL's and/or OpenSSL's vectors, for direct comparison's sake.

[ranweiler]

Good, that agrees with what I had in mind (just wanted to get oriented before I started in on it).