tree 2e627d17d1cff98d428255769b37d0de3181c68e
parent a1bc1ba47c33bcf5c13a347bf854fbebf7ad31b2
author David Benjamin <davidben@google.com> 1515536841 +0100
committer CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org> 1516746307 +0000

Use 51-bit limbs from fiat-crypto in 64-bit.

Our 64-bit performance was much lower than it could have been, since we
weren't using the 64-bit multipliers. Fortunately, fiat-crypto is
awesome, so this is just a matter of synthesizing new code and
integration work.

Functions without the signature fiat-crypto curly braces were written by
hand and warrant more review. (It's just redistributing some bits.)

These use the donna variants which takes (and proves) some of the
instruction scheduling from donna as that's significantly faster.
Glancing over things, I suspect but have not confirmed the gap is due to
this:
https://github.com/mit-plv/fiat-crypto/pull/295#issuecomment-356892413

Clang without OPENSSL_SMALL (ECDH omitted since that uses assembly and
is unaffected by this CL).

Before:
Did 105149 Ed25519 key generation operations in 5025208us (20924.3 ops/sec)
Did 125000 Ed25519 signing operations in 5024003us (24880.6 ops/sec)
Did 37642 Ed25519 verify operations in 5072539us (7420.7 ops/sec)

After:
Did 206000 Ed25519 key generation operations in 5020547us (41031.4 ops/sec)
Did 227000 Ed25519 signing operations in 5005232us (45352.5 ops/sec)
Did 69840 Ed25519 verify operations in 5004769us (13954.7 ops/sec)

Clang + OPENSSL_SMALL:

Before:
Did 68598 Ed25519 key generation operations in 5024629us (13652.4 ops/sec)
Did 73000 Ed25519 signing operations in 5067837us (14404.6 ops/sec)
Did 36765 Ed25519 verify operations in 5078684us (7239.1 ops/sec)
Did 74000 Curve25519 base-point multiplication operations in 5016465us (14751.4 ops/sec)
Did 45600 Curve25519 arbitrary point multiplication operations in 5034680us (9057.2 ops/sec)

After:
Did 117315 Ed25519 key generation operations in 5021860us (23360.9 ops/sec)
Did 126000 Ed25519 signing operations in 5003521us (25182.3 ops/sec)
Did 64974 Ed25519 verify operations in 5047790us (12871.8 ops/sec)
Did 134000 Curve25519 base-point multiplication operations in 5058946us (26487.7 ops/sec)
Did 86000 Curve25519 arbitrary point multiplication operations in 5050478us (17028.1 ops/sec)

GCC without OPENSSL_SMALL (ECDH omitted since that uses assembly and
is unaffected by this CL).

Before:
Did 35552 Ed25519 key generation operations in 5030756us (7066.9 ops/sec)
Did 38286 Ed25519 signing operations in 5001648us (7654.7 ops/sec)
Did 10584 Ed25519 verify operations in 5068158us (2088.3 ops/sec)

After:
Did 92158 Ed25519 key generation operations in 5024021us (18343.5 ops/sec)
Did 99000 Ed25519 signing operations in 5011908us (19753.0 ops/sec)
Did 31122 Ed25519 verify operations in 5069878us (6138.6 ops/sec)

Change-Id: Ic0c24d50b4ee2bbc408b94965e9d63319936107d
Reviewed-on: https://boringssl-review.googlesource.com/24805
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
Reviewed-by: Adam Langley <agl@google.com>