From 92d60c205931fa31ce15bcee42c29e37dd807506 Mon Sep 17 00:00:00 2001 From: Brian Smith Date: Mon, 25 Jul 2016 18:24:21 -1000 Subject: 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 Commit-Queue: Adam Langley CQ-Verified: CQ bot account: commit-bot@chromium.org --- crypto/ec/ec_montgomery.c | 16 +++++++++++++--- 1 file changed, 13 insertions(+), 3 deletions(-) (limited to 'crypto') 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; } -- cgit v1.2.3