Use Fermat's Little Theorem when converting points to affine.

Fermat's Little Theorem is already used for the custom curve implementations.
Use it, for the same reasons, for the ec_montgomery-based implementations.

I tested the performance (only) on x86-64 Windows.

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

1 files changed, 13 insertions, 3 deletions

diff --git a/crypto/ec/ec_montgomery.c b/crypto/ec/ec_montgomery.c
index 215867de..45b5e9d7 100644
--- a/crypto/ec/ec_montgomery.c
+++ b/crypto/ec/ec_montgomery.c
@@ -230,9 +230,11 @@ static int ec_GFp_mont_point_get_affine_coordinates(const EC_GROUP *group,
     BIGNUM *Z_1 = BN_CTX_get(ctx);
     BIGNUM *Z_2 = BN_CTX_get(ctx);
     BIGNUM *Z_3 = BN_CTX_get(ctx);
+    BIGNUM *field_minus_2 = BN_CTX_get(ctx);
     if (Z_1 == NULL ||
         Z_2 == NULL ||
-        Z_3 == NULL) {
+        Z_3 == NULL ||
+        field_minus_2 == NULL) {
       goto err;
     }
 
@@ -243,10 +245,18 @@ static int ec_GFp_mont_point_get_affine_coordinates(const EC_GROUP *group,
      *
      * This is equivalent, but more efficient, because |BN_from_montgomery|
      * is more efficient (at least in theory) than |BN_to_montgomery|, since it
-     * doesn't have to do the multiplication before the reduction. */
+     * doesn't have to do the multiplication before the reduction.
+     *
+     * Use Fermat's Little Theorem with |BN_mod_exp_mont_consttime| instead of
+     * |BN_mod_inverse| since this inversion may be done as the final step of
+     * private key operations. Unfortunately, this is suboptimal for ECDSA
+     * verification. */
     if (!BN_from_montgomery(Z_1, &point->Z, group->mont, ctx) ||
         !BN_from_montgomery(Z_1, Z_1, group->mont, ctx) ||
-        !BN_mod_inverse(Z_1, Z_1, &group->field, ctx)) {
+        !BN_copy(field_minus_2, &group->field) ||
+        !BN_sub_word(field_minus_2, 2) ||
+        !BN_mod_exp_mont_consttime(Z_1, Z_1, field_minus_2, &group->field,
+                                   ctx, group->mont)) {
       goto err;
     }