Use BN_mod_inverse_odd instead of |BN_mod_inverse| for ECC.
BN_mod_inverse_odd was always being used on 64-bit platforms and was being used
for all curves with an order of 450 bits or smaller (basically, everything but
P-521). We generally don't care much about minor differences in the speed of
verifying signatures using curves other than P-256 and P-384. It is better to
always use the same algorithm.
This also allows |bn_mod_inverse_general|, |bn_mod_inverse_no_branch|, and
|BN_mod_inverse| to be dropped from programs that can somehow avoid linking in
the RSA key generation and RSA CRT recovery code.
Change-Id: I79b94bff23d2b07d5e0c704f7d44538797f8c7a0
Reviewed-on: https://boringssl-review.googlesource.com/9103
Reviewed-by: David Benjamin <davidben@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
diff --git a/crypto/bn/gcd.c b/crypto/bn/gcd.c
index cb61186..6a11156 100644
--- a/crypto/bn/gcd.c
+++ b/crypto/bn/gcd.c
@@ -229,9 +229,17 @@
const BIGNUM *a, const BIGNUM *n,
BN_CTX *ctx);
-static int bn_mod_inverse_odd(BIGNUM *out, int *out_no_inverse, const BIGNUM *a,
- const BIGNUM *n, BN_CTX *ctx) {
- assert(BN_is_odd(n));
+int BN_mod_inverse_odd(BIGNUM *out, int *out_no_inverse, const BIGNUM *a,
+ const BIGNUM *n, BN_CTX *ctx) {
+ if (!BN_is_odd(n)) {
+ OPENSSL_PUT_ERROR(BN, BN_R_CALLED_WITH_EVEN_MODULUS);
+ return 0;
+ }
+
+ if (BN_is_negative(a) || BN_cmp(a, n) >= 0) {
+ OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED);
+ return 0;
+ }
BIGNUM *A, *B, *X, *Y;
int ret = 0;
@@ -594,7 +602,7 @@
static int bn_mod_inverse_ex(BIGNUM *out, int *out_no_inverse, const BIGNUM *a,
const BIGNUM *n, BN_CTX *ctx) {
if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS2 <= 32 ? 450 : 2048))) {
- return bn_mod_inverse_odd(out, out_no_inverse, a, n, ctx);
+ return BN_mod_inverse_odd(out, out_no_inverse, a, n, ctx);
}
return bn_mod_inverse_general(out, out_no_inverse, a, n, ctx);
}
@@ -670,7 +678,7 @@
if (!BN_rand_range_ex(&blinding_factor, 1, &mont->N) ||
!BN_mod_mul_montgomery(out, &blinding_factor, a, mont, ctx) ||
- !bn_mod_inverse_odd(out, out_no_inverse, out, &mont->N, ctx) ||
+ !BN_mod_inverse_odd(out, out_no_inverse, out, &mont->N, ctx) ||
!BN_mod_mul_montgomery(out, &blinding_factor, out, mont, ctx)) {
OPENSSL_PUT_ERROR(BN, ERR_R_BN_LIB);
goto err;
diff --git a/crypto/ec/ec_montgomery.c b/crypto/ec/ec_montgomery.c
index 45b5e9d..4c1e3b4 100644
--- a/crypto/ec/ec_montgomery.c
+++ b/crypto/ec/ec_montgomery.c
@@ -241,15 +241,15 @@
/* The straightforward way to calculate the inverse of a Montgomery-encoded
* value where the result is Montgomery-encoded is:
*
- * |BN_from_montgomery| + |BN_mod_inverse| + |BN_to_montgomery|.
+ * |BN_from_montgomery| + invert + |BN_to_montgomery|.
*
* 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.
*
* 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
+ * |BN_mod_inverse_odd| 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) ||
diff --git a/crypto/ec/simple.c b/crypto/ec/simple.c
index 4508d83..67c4602 100644
--- a/crypto/ec/simple.c
+++ b/crypto/ec/simple.c
@@ -1023,10 +1023,16 @@
}
}
- /* Now use a single explicit inversion to replace every
- * non-zero points[i]->Z by its inverse. */
-
- if (!BN_mod_inverse(tmp, prod_Z[num - 1], &group->field, ctx)) {
+ /* Now use a single explicit inversion to replace every non-zero points[i]->Z
+ * by its inverse. We use |BN_mod_inverse_odd| instead of doing a constant-
+ * time inversion using Fermat's Little Theorem because this function is
+ * usually only used for converting multiples of a public key point to
+ * affine, and a public key point isn't secret. If we were to use Fermat's
+ * Little Theorem then the cost of the inversion would usually be so high
+ * that converting the multiples to affine would be counterproductive. */
+ int no_inverse;
+ if (!BN_mod_inverse_odd(tmp, &no_inverse, prod_Z[num - 1], &group->field,
+ ctx)) {
OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
goto err;
}
diff --git a/crypto/ecdsa/ecdsa.c b/crypto/ecdsa/ecdsa.c
index a85c28a..6320992 100644
--- a/crypto/ecdsa/ecdsa.c
+++ b/crypto/ecdsa/ecdsa.c
@@ -176,7 +176,8 @@
goto err;
}
/* calculate tmp1 = inv(S) mod order */
- if (!BN_mod_inverse(u2, sig->s, order, ctx)) {
+ int no_inverse;
+ if (!BN_mod_inverse_odd(u2, &no_inverse, sig->s, order, ctx)) {
OPENSSL_PUT_ERROR(ECDSA, ERR_R_BN_LIB);
goto err;
}
diff --git a/include/openssl/bn.h b/include/openssl/bn.h
index 7d3cb3d..ff9d680 100644
--- a/include/openssl/bn.h
+++ b/include/openssl/bn.h
@@ -746,6 +746,18 @@
int BN_mod_inverse_blinded(BIGNUM *out, int *out_no_inverse, const BIGNUM *a,
const BN_MONT_CTX *mont, BN_CTX *ctx);
+/* BN_mod_inverse_odd sets |out| equal to |a|^-1, mod |n|. |a| must be
+ * non-negative and must be less than |n|. |n| must be odd. This function
+ * shouldn't be used for secret values; use |BN_mod_inverse_blinded| instead.
+ * Or, if |n| is guaranteed to be prime, use
+ * |BN_mod_exp_mont_consttime(out, a, m_minus_2, m, ctx, m_mont)|, taking
+ * advantage of Fermat's Little Theorem. It returns one on success or zero on
+ * failure. On failure, if the failure was caused by |a| having no inverse mod
+ * |n| then |*out_no_inverse| will be set to one; otherwise it will be set to
+ * zero. */
+int BN_mod_inverse_odd(BIGNUM *out, int *out_no_inverse, const BIGNUM *a,
+ const BIGNUM *n, BN_CTX *ctx);
+
/* BN_kronecker returns the Kronecker symbol of |a| and |b| (which is -1, 0 or
* 1), or -2 on error. */
OPENSSL_EXPORT int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx);
