Remove optimized even modulus mod-exp implementation There's a whole lot of logic here for some kind of windowed reciprocal exponentation. While probably interesting, it is not relevant for any cryptographic use cases. Replace it with a naive square-and-multiple algorithm atop BN_mod_mul and BN_mod_sqr. Change-Id: Ic2290fa1eccccd3bb21732d5171830f65b71670d Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/77427 Reviewed-by: Bob Beck <bbe@google.com> Auto-Submit: David Benjamin <davidben@google.com> Commit-Queue: Bob Beck <bbe@google.com>
diff --git a/crypto/fipsmodule/bn/exponentiation.cc.inc b/crypto/fipsmodule/bn/exponentiation.cc.inc index 6c3d448..53081c4 100644 --- a/crypto/fipsmodule/bn/exponentiation.cc.inc +++ b/crypto/fipsmodule/bn/exponentiation.cc.inc
@@ -122,209 +122,6 @@ return ret; } -namespace { -typedef struct bn_recp_ctx_st { - BIGNUM N; // the divisor - BIGNUM Nr; // the reciprocal - int num_bits; - int shift; - int flags; -} BN_RECP_CTX; -} // namespace - -static void BN_RECP_CTX_init(BN_RECP_CTX *recp) { - BN_init(&recp->N); - BN_init(&recp->Nr); - recp->num_bits = 0; - recp->shift = 0; - recp->flags = 0; -} - -static void BN_RECP_CTX_free(BN_RECP_CTX *recp) { - if (recp == nullptr) { - return; - } - BN_free(&recp->N); - BN_free(&recp->Nr); -} - -static int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx) { - if (!BN_copy(&(recp->N), d)) { - return 0; - } - BN_zero(&recp->Nr); - recp->num_bits = BN_num_bits(d); - recp->shift = 0; - - return 1; -} - -// len is the expected size of the result We actually calculate with an extra -// word of precision, so we can do faster division if the remainder is not -// required. -// r := 2^len / m -static int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx) { - int ret = -1; - BIGNUM *t; - - BN_CTX_start(ctx); - t = BN_CTX_get(ctx); - if (t == NULL) { - goto err; - } - - if (!BN_set_bit(t, len)) { - goto err; - } - - if (!BN_div(r, NULL, t, m, ctx)) { - goto err; - } - - ret = len; - -err: - BN_CTX_end(ctx); - return ret; -} - -static int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, - BN_RECP_CTX *recp, BN_CTX *ctx) { - int i, j, ret = 0; - BIGNUM *a, *b, *d, *r; - - BN_CTX_start(ctx); - a = BN_CTX_get(ctx); - b = BN_CTX_get(ctx); - if (dv != NULL) { - d = dv; - } else { - d = BN_CTX_get(ctx); - } - - if (rem != NULL) { - r = rem; - } else { - r = BN_CTX_get(ctx); - } - - if (a == NULL || b == NULL || d == NULL || r == NULL) { - goto err; - } - - if (BN_ucmp(m, &recp->N) < 0) { - BN_zero(d); - if (!BN_copy(r, m)) { - goto err; - } - BN_CTX_end(ctx); - return 1; - } - - // We want the remainder - // Given input of ABCDEF / ab - // we need multiply ABCDEF by 3 digests of the reciprocal of ab - - // i := max(BN_num_bits(m), 2*BN_num_bits(N)) - i = BN_num_bits(m); - j = recp->num_bits << 1; - if (j > i) { - i = j; - } - - // Nr := round(2^i / N) - if (i != recp->shift) { - recp->shift = - BN_reciprocal(&(recp->Nr), &(recp->N), i, - ctx); // BN_reciprocal returns i, or -1 for an error - } - - if (recp->shift == -1) { - goto err; - } - - // d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - - // BN_num_bits(N)))| - // = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - - // BN_num_bits(N)))| - // <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)| - // = |m/N| - if (!BN_rshift(a, m, recp->num_bits)) { - goto err; - } - if (!BN_mul(b, a, &(recp->Nr), ctx)) { - goto err; - } - if (!BN_rshift(d, b, i - recp->num_bits)) { - goto err; - } - d->neg = 0; - - if (!BN_mul(b, &(recp->N), d, ctx)) { - goto err; - } - if (!BN_usub(r, m, b)) { - goto err; - } - r->neg = 0; - - j = 0; - while (BN_ucmp(r, &(recp->N)) >= 0) { - if (j++ > 2) { - OPENSSL_PUT_ERROR(BN, BN_R_BAD_RECIPROCAL); - goto err; - } - if (!BN_usub(r, r, &(recp->N))) { - goto err; - } - if (!BN_add_word(d, 1)) { - goto err; - } - } - - r->neg = BN_is_zero(r) ? 0 : m->neg; - d->neg = m->neg ^ recp->N.neg; - ret = 1; - -err: - BN_CTX_end(ctx); - return ret; -} - -static int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, - BN_RECP_CTX *recp, BN_CTX *ctx) { - int ret = 0; - BIGNUM *a; - const BIGNUM *ca; - - BN_CTX_start(ctx); - a = BN_CTX_get(ctx); - if (a == NULL) { - goto err; - } - - if (y != NULL) { - if (x == y) { - if (!BN_sqr(a, x, ctx)) { - goto err; - } - } else { - if (!BN_mul(a, x, y, ctx)) { - goto err; - } - } - ca = a; - } else { - ca = x; // Just do the mod - } - - ret = BN_div_recp(NULL, r, ca, recp, ctx); - -err: - BN_CTX_end(ctx); - return ret; -} - // BN_window_bits_for_exponent_size returns sliding window size for mod_exp with // a |b| bit exponent. // @@ -378,141 +175,37 @@ // |BN_BITS2| * |BN_SMALL_MAX_WORDS|. #define TABLE_SIZE_SMALL (1 << (TABLE_BITS_SMALL - 1)) -static int mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, +static int mod_exp_even(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx) { - int i, j, ret = 0, wstart, window; - int start = 1; - BIGNUM *aa; - // Table of variables obtained from 'ctx' - BIGNUM *val[TABLE_SIZE]; - BN_RECP_CTX recp; - - // This function is only called on even moduli. - assert(!BN_is_odd(m)); - + // No cryptographic operations require modular exponentiation with an even + // modulus. We support it for backwards compatibility with any applications + // that may have relied on the operation, but optimize for simplicity over + // performance with straightforward square-and-multiply routine. int bits = BN_num_bits(p); if (bits == 0) { return BN_one(r); } - BN_RECP_CTX_init(&recp); - BN_CTX_start(ctx); - aa = BN_CTX_get(ctx); - val[0] = BN_CTX_get(ctx); - if (!aa || !val[0]) { - goto err; + // Make a copy of |a|, in case it aliases |r|. + bssl::BN_CTXScope scope(ctx); + BIGNUM *tmp = BN_CTX_get(ctx); + if (tmp == nullptr || !BN_copy(tmp, a)) { + return 0; } - if (m->neg) { - // ignore sign of 'm' - if (!BN_copy(aa, m)) { - goto err; - } - aa->neg = 0; - if (BN_RECP_CTX_set(&recp, aa, ctx) <= 0) { - goto err; - } - } else { - if (BN_RECP_CTX_set(&recp, m, ctx) <= 0) { - goto err; + assert(BN_is_bit_set(p, bits - 1)); + if (!BN_copy(r, tmp)) { + return 0; + } + + for (int i = bits - 2; i >= 0; i--) { + if (!BN_mod_sqr(r, r, m, ctx) || + (BN_is_bit_set(p, i) && !BN_mod_mul(r, r, tmp, m, ctx))) { + return 0; } } - if (!BN_nnmod(val[0], a, m, ctx)) { - goto err; // 1 - } - if (BN_is_zero(val[0])) { - BN_zero(r); - ret = 1; - goto err; - } - - window = BN_window_bits_for_exponent_size(bits); - if (window > 1) { - if (!BN_mod_mul_reciprocal(aa, val[0], val[0], &recp, ctx)) { - goto err; // 2 - } - j = 1 << (window - 1); - for (i = 1; i < j; i++) { - if (((val[i] = BN_CTX_get(ctx)) == NULL) || - !BN_mod_mul_reciprocal(val[i], val[i - 1], aa, &recp, ctx)) { - goto err; - } - } - } - - start = 1; // This is used to avoid multiplication etc - // when there is only the value '1' in the - // buffer. - wstart = bits - 1; // The top bit of the window - - if (!BN_one(r)) { - goto err; - } - - for (;;) { - int wvalue; // The 'value' of the window - int wend; // The bottom bit of the window - - if (!BN_is_bit_set(p, wstart)) { - if (!start) { - if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx)) { - goto err; - } - } - if (wstart == 0) { - break; - } - wstart--; - continue; - } - - // We now have wstart on a 'set' bit, we now need to work out - // how bit a window to do. To do this we need to scan - // forward until the last set bit before the end of the - // window - wvalue = 1; - wend = 0; - for (i = 1; i < window; i++) { - if (wstart - i < 0) { - break; - } - if (BN_is_bit_set(p, wstart - i)) { - wvalue <<= (i - wend); - wvalue |= 1; - wend = i; - } - } - - // wend is the size of the current window - j = wend + 1; - // add the 'bytes above' - if (!start) { - for (i = 0; i < j; i++) { - if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx)) { - goto err; - } - } - } - - // wvalue will be an odd number < 2^window - if (!BN_mod_mul_reciprocal(r, r, val[wvalue >> 1], &recp, ctx)) { - goto err; - } - - // move the 'window' down further - wstart -= wend + 1; - start = 0; - if (wstart < 0) { - break; - } - } - ret = 1; - -err: - BN_CTX_end(ctx); - BN_RECP_CTX_free(&recp); - return ret; + return 1; } int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, @@ -532,7 +225,7 @@ return BN_mod_exp_mont(r, a, p, m, ctx, NULL); } - return mod_exp_recp(r, a, p, m, ctx); + return mod_exp_even(r, a, p, m, ctx); } int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,