Extract the single-subtraction reduction into a helper function. We do this in four different places, with the same long comment, and I'm about to add yet another one. Change-Id: If28e3f87ea71020d9b07b92e8947f3848473d99d Reviewed-on: https://boringssl-review.googlesource.com/26964 Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/bn/div.c b/crypto/fipsmodule/bn/div.c index 2a3bcdd..d29ea34 100644 --- a/crypto/fipsmodule/bn/div.c +++ b/crypto/fipsmodule/bn/div.c
@@ -414,6 +414,35 @@ return (d->neg ? BN_sub : BN_add)(r, r, d); } +BN_ULONG bn_reduce_once(BN_ULONG *r, const BN_ULONG *a, BN_ULONG carry, + const BN_ULONG *m, size_t num) { + assert(r != a); + // |r| = |a| - |m|. |bn_sub_words| performs the bulk of the subtraction, and + // then we apply the borrow to |carry|. + carry -= bn_sub_words(r, a, m, num); + // We know 0 <= |a| < 2*|m|, so -|m| <= |r| < |m|. + // + // If 0 <= |r| < |m|, |r| fits in |num| words and |carry| is zero. We then + // wish to select |r| as the answer. Otherwise -m <= r < 0 and we wish to + // return |r| + |m|, or |a|. |carry| must then be -1 or all ones. In both + // cases, |carry| is a suitable input to |bn_select_words|. + // + // Although |carry| may be one if it was one on input and |bn_sub_words| + // returns zero, this would give |r| > |m|, violating our input assumptions. + assert(carry == 0 || carry == (BN_ULONG)-1); + bn_select_words(r, carry, a /* r < 0 */, r /* r >= 0 */, num); + return carry; +} + +BN_ULONG bn_reduce_once_in_place(BN_ULONG *r, BN_ULONG carry, const BN_ULONG *m, + BN_ULONG *tmp, size_t num) { + // See |bn_reduce_once| for why this logic works. + carry -= bn_sub_words(tmp, r, m, num); + assert(carry == 0 || carry == (BN_ULONG)-1); + bn_select_words(r, carry, r /* tmp < 0 */, tmp /* tmp >= 0 */, num); + return carry; +} + // bn_mod_sub_words sets |r| to |a| - |b| (mod |m|), using |tmp| as scratch // space. Each array is |num| words long. |a| and |b| must be < |m|. Any pair of // |r|, |a|, and |b| may alias. @@ -431,27 +460,8 @@ // |r|, |a|, and |b| may alias. static void bn_mod_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, const BN_ULONG *m, BN_ULONG *tmp, size_t num) { - // tmp = a + b. Note the result fits in |num|+1 words. We store the extra word - // in |carry|. - BN_ULONG carry = bn_add_words(tmp, a, b, num); - // r = a + b - m. We use |bn_sub_words| to perform the bulk of the - // subtraction, and then apply the borrow to |carry|. - carry -= bn_sub_words(r, tmp, m, num); - // |a| and |b| were both fully-reduced, so we know: - // - // 0 + 0 - m <= r < m + m - m - // -m <= r < m - // - // If 0 <= |r| < |m|, |r| fits in |num| words and |carry| is zero. We then - // wish to select |r| as the answer. Otherwise -m <= r < 0 and we wish to - // return |r| + |m|, or |tmp|. |carry| must then be -1 or all ones. In both - // cases, |carry| is a suitable input to |bn_select_words|. - // - // Although |carry| may be one if |bn_add_words| returns one and - // |bn_sub_words| returns zero, this would give |r| > |m|, which violates are - // input assumptions. - assert(carry == 0 || carry == (BN_ULONG)-1); - bn_select_words(r, carry, tmp /* r < 0 */, r /* r >= 0 */, num); + BN_ULONG carry = bn_add_words(r, a, b, num); + bn_reduce_once_in_place(r, carry, m, tmp, num); } int bn_div_consttime(BIGNUM *quotient, BIGNUM *remainder, @@ -504,27 +514,14 @@ // extra word in |carry|. BN_ULONG carry = bn_add_words(r->d, r->d, r->d, divisor->width); r->d[0] |= (numerator->d[i] >> bit) & 1; - // tmp = r - divisor. We use |bn_sub_words| to perform the bulk of the - // subtraction, and then apply the borrow to |carry|. - carry -= bn_sub_words(tmp->d, r->d, divisor->d, divisor->width); // |r| was previously fully-reduced, so we know: - // - // 2*0 - divisor <= tmp <= 2*(divisor-1) + 1 - divisor - // -divisor <= tmp < divisor - // - // If 0 <= |tmp| < |divisor|, |tmp| fits in |divisor->width| and |carry| - // is zero. We then wish to select |tmp|. Otherwise, - // -|divisor| <= |tmp| < 0 and we wish to select |tmp| + |divisor|, which - // is |r|. |carry| must then be -1 (all ones). In both cases, |carry| is a - // suitable input to |bn_select_words|. - // - // Although |carry| may be one if |bn_add_words| returns one and - // |bn_sub_words| returns zero, this would give |r| > |d|, which violates - // the loop invariant. - bn_select_words(r->d, carry, r->d /* tmp < 0 */, tmp->d /* tmp >= 0 */, - divisor->width); + // 2*0 <= r <= 2*(divisor-1) + 1 + // 0 <= r <= 2*divisor - 1 < 2*divisor. + // Thus |r| satisfies the preconditions for |bn_reduce_once_in_place|. + BN_ULONG subtracted = bn_reduce_once_in_place(r->d, carry, divisor->d, + tmp->d, divisor->width); // The corresponding bit of the quotient is set iff we needed to subtract. - q->d[i] |= (~carry & 1) << bit; + q->d[i] |= (~subtracted & 1) << bit; } }
diff --git a/crypto/fipsmodule/bn/internal.h b/crypto/fipsmodule/bn/internal.h index a8ad129..7d96151 100644 --- a/crypto/fipsmodule/bn/internal.h +++ b/crypto/fipsmodule/bn/internal.h
@@ -375,6 +375,21 @@ OPENSSL_EXPORT int bn_rshift_secret_shift(BIGNUM *r, const BIGNUM *a, unsigned n, BN_CTX *ctx); +// bn_reduce_once sets |r| to |a| mod |m| where 0 <= |a| < 2*|m|. It returns +// zero if |a| < |m| and a mask of all ones if |a| >= |m|. Each array is |num| +// words long, but |a| has an additional word specified by |carry|. |carry| must +// be zero or one, as implied by the bounds on |a|. +// +// |r|, |a|, and |m| may not alias. Use |bn_reduce_once_in_place| if |r| and |a| +// must alias. +BN_ULONG bn_reduce_once(BN_ULONG *r, const BN_ULONG *a, BN_ULONG carry, + const BN_ULONG *m, size_t num); + +// bn_reduce_once_in_place behaves like |bn_reduce_once| but acts in-place on +// |r|, using |tmp| as scratch space. |r|, |tmp|, and |m| may not alias. +BN_ULONG bn_reduce_once_in_place(BN_ULONG *r, BN_ULONG carry, const BN_ULONG *m, + BN_ULONG *tmp, size_t num); + // Constant-time non-modular arithmetic. //
diff --git a/crypto/fipsmodule/bn/montgomery.c b/crypto/fipsmodule/bn/montgomery.c index d6e2ad5..7ce8c4c 100644 --- a/crypto/fipsmodule/bn/montgomery.c +++ b/crypto/fipsmodule/bn/montgomery.c
@@ -289,18 +289,7 @@ a += num_n; // |a| thus requires at most one additional subtraction |n| to be reduced. - // Subtract |n| and select the answer in constant time. - OPENSSL_COMPILE_ASSERT(sizeof(BN_ULONG) <= sizeof(crypto_word_t), - crypto_word_t_too_small); - BN_ULONG v = bn_sub_words(r, a, n, num_n) - carry; - // |v| is one if |a| - |n| underflowed or zero if it did not. Note |v| cannot - // be -1. That would imply the subtraction did not fit in |num_n| words, and - // we know at most one subtraction is needed. - v = 0u - v; - for (size_t i = 0; i < num_n; i++) { - r[i] = constant_time_select_w(v, a[i], r[i]); - a[i] = 0; - } + bn_reduce_once(r, a, carry, n, num_n); return 1; }