Add Intel's P-256

This change incorporates Intel's P-256 implementation. The record of
Intel's submission under CLA is in internal bug number 25330687.

Before:
Did 3582 ECDH P-256 operations in 1049114us (3414.3 ops/sec)
Did 8525 ECDSA P-256 signing operations in 1028778us (8286.5 ops/sec)
Did 3487 ECDSA P-256 verify operations in 1008996us (3455.9 ops/sec)
build/tool/bssl is 1434704 bytes after strip -s

After:
Did 8618 ECDH P-256 operations in 1027884us (8384.2 ops/sec)
Did 21000 ECDSA P-256 signing operations in 1049490us (20009.7 ops/sec)
Did 8268 ECDSA P-256 verify operations in 1079481us (7659.2 ops/sec)
build/tool/bssl is 1567216 bytes after strip -s

Change-Id: I147971a8e19849779c8ed7e20310d41bd4962299
Reviewed-on: https://boringssl-review.googlesource.com/6371
Reviewed-by: Adam Langley <agl@google.com>

1 files changed, 15 insertions, 1 deletions

diff --git a/crypto/ecdsa/ecdsa.c b/crypto/ecdsa/ecdsa.c
index 8403d60e..a718cf89 100644
--- a/crypto/ecdsa/ecdsa.c
+++ b/crypto/ecdsa/ecdsa.c
@@ -325,7 +325,21 @@ static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
   } while (BN_is_zero(r));
 
   /* compute the inverse of k */
-  if (!BN_mod_inverse(k, k, order, ctx)) {
+  if (ec_group_get_mont_data(group) != NULL) {
+    /* We want inverse in constant time, therefore we use that the order must
+     * be prime and thus we can use Fermat's Little Theorem. */
+    if (!BN_set_word(X, 2) ||
+        !BN_sub(X, order, X)) {
+      OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB);
+      goto err;
+    }
+    BN_set_flags(X, BN_FLG_CONSTTIME);
+    if (!BN_mod_exp_mont_consttime(k, k, X, order, ctx,
+                                   ec_group_get_mont_data(group))) {
+      OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB);
+      goto err;
+    }
+  } else if (!BN_mod_inverse(k, k, order, ctx)) {
     OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB);
     goto err;
   }