From 2f19065bd35dc84492c4c47ff5b706340300866f Mon Sep 17 00:00:00 2001 From: Andy Polyakov Date: Fri, 6 Jul 2018 15:13:15 +0200 Subject: [PATCH] bn/bn_{mont|exp}.c: switch to zero-padded intermediate vectors. Note that exported functions maintain original behaviour, so that external callers won't observe difference. While internally we can now perform Montogomery multiplication on fixed-length vectors, fixed at modulus size. The new functions, bn_to_mont_fixed_top and bn_mul_mont_fixed_top, are declared in bn_int.h, because one can use them even outside bn, e.g. in RSA, DSA, ECDSA... Reviewed-by: Rich Salz (Merged from https://github.com/openssl/openssl/pull/6707) (cherry picked from commit 71883868ea5b33416ae8283bcc38dd2d97e5006b) Resolved conflicts: crypto/bn/bn_exp.c crypto/bn/bn_mont.c crypto/include/internal/bn_int.h --- crypto/bn/bn_exp.c | 47 ++++++++++++++++++-------------- crypto/bn/bn_lcl.h | 3 +- crypto/bn/bn_mont.c | 45 ++++++++++++++++++++++-------- crypto/include/internal/bn_int.h | 11 ++++++++ 4 files changed, 73 insertions(+), 33 deletions(-) diff --git a/crypto/bn/bn_exp.c b/crypto/bn/bn_exp.c index dac3640446..a6ad475a0b 100644 --- a/crypto/bn/bn_exp.c +++ b/crypto/bn/bn_exp.c @@ -371,17 +371,17 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, ret = 1; goto err; } - if (!BN_to_montgomery(val[0], aa, mont, ctx)) + if (!bn_to_mont_fixed_top(val[0], aa, mont, ctx)) goto err; /* 1 */ window = BN_window_bits_for_exponent_size(bits); if (window > 1) { - if (!BN_mod_mul_montgomery(d, val[0], val[0], mont, ctx)) + if (!bn_mul_mont_fixed_top(d, val[0], val[0], mont, 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_montgomery(val[i], val[i - 1], d, mont, ctx)) + !bn_mul_mont_fixed_top(val[i], val[i - 1], d, mont, ctx)) goto err; } } @@ -403,19 +403,15 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, for (i = 1; i < j; i++) r->d[i] = (~m->d[i]) & BN_MASK2; r->top = j; - /* - * Upper words will be zero if the corresponding words of 'm' were - * 0xfff[...], so decrement r->top accordingly. - */ - bn_correct_top(r); + r->flags |= BN_FLG_FIXED_TOP; } else #endif - if (!BN_to_montgomery(r, BN_value_one(), mont, ctx)) + if (!bn_to_mont_fixed_top(r, BN_value_one(), mont, ctx)) goto err; for (;;) { if (BN_is_bit_set(p, wstart) == 0) { if (!start) { - if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) + if (!bn_mul_mont_fixed_top(r, r, r, mont, ctx)) goto err; } if (wstart == 0) @@ -446,12 +442,12 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, /* add the 'bytes above' */ if (!start) for (i = 0; i < j; i++) { - if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) + if (!bn_mul_mont_fixed_top(r, r, r, mont, ctx)) goto err; } /* wvalue will be an odd number < 2^window */ - if (!BN_mod_mul_montgomery(r, r, val[wvalue >> 1], mont, ctx)) + if (!bn_mul_mont_fixed_top(r, r, val[wvalue >> 1], mont, ctx)) goto err; /* move the 'window' down further */ @@ -461,6 +457,11 @@ int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, if (wstart < 0) break; } + /* + * Done with zero-padded intermediate BIGNUMs. Final BN_from_montgomery + * removes padding [if any] and makes return value suitable for public + * API consumer. + */ #if defined(SPARC_T4_MONT) if (OPENSSL_sparcv9cap_P[0] & (SPARCV9_VIS3 | SPARCV9_PREFER_FPU)) { j = mont->N.top; /* borrow j */ @@ -587,7 +588,7 @@ static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, } b->top = top; - bn_correct_top(b); + b->flags |= BN_FLG_FIXED_TOP; return 1; } @@ -757,16 +758,16 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, tmp.top = top; } else #endif - if (!BN_to_montgomery(&tmp, BN_value_one(), mont, ctx)) + if (!bn_to_mont_fixed_top(&tmp, BN_value_one(), mont, ctx)) goto err; /* prepare a^1 in Montgomery domain */ if (a->neg || BN_ucmp(a, m) >= 0) { if (!BN_mod(&am, a, m, ctx)) goto err; - if (!BN_to_montgomery(&am, &am, mont, ctx)) + if (!bn_to_mont_fixed_top(&am, &am, mont, ctx)) goto err; - } else if (!BN_to_montgomery(&am, a, mont, ctx)) + } else if (!bn_to_mont_fixed_top(&am, a, mont, ctx)) goto err; #if defined(SPARC_T4_MONT) @@ -1033,14 +1034,14 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, * performance advantage of sqr over mul). */ if (window > 1) { - if (!BN_mod_mul_montgomery(&tmp, &am, &am, mont, ctx)) + if (!bn_mul_mont_fixed_top(&tmp, &am, &am, mont, ctx)) goto err; if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 2, window)) goto err; for (i = 3; i < numPowers; i++) { /* Calculate a^i = a^(i-1) * a */ - if (!BN_mod_mul_montgomery(&tmp, &am, &tmp, mont, ctx)) + if (!bn_mul_mont_fixed_top(&tmp, &am, &tmp, mont, ctx)) goto err; if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, i, window)) @@ -1064,7 +1065,7 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, /* Scan the window, squaring the result as we go */ for (i = 0; i < window; i++, bits--) { - if (!BN_mod_mul_montgomery(&tmp, &tmp, &tmp, mont, ctx)) + if (!bn_mul_mont_fixed_top(&tmp, &tmp, &tmp, mont, ctx)) goto err; wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); } @@ -1077,12 +1078,16 @@ int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, goto err; /* Multiply the result into the intermediate result */ - if (!BN_mod_mul_montgomery(&tmp, &tmp, &am, mont, ctx)) + if (!bn_mul_mont_fixed_top(&tmp, &tmp, &am, mont, ctx)) goto err; } } - /* Convert the final result from montgomery to standard format */ + /* + * Done with zero-padded intermediate BIGNUMs. Final BN_from_montgomery + * removes padding [if any] and makes return value suitable for public + * API consumer. + */ #if defined(SPARC_T4_MONT) if (OPENSSL_sparcv9cap_P[0] & (SPARCV9_VIS3 | SPARCV9_PREFER_FPU)) { am.d[0] = 1; /* borrow am */ diff --git a/crypto/bn/bn_lcl.h b/crypto/bn/bn_lcl.h index 6c35ea66f8..0f80888725 100644 --- a/crypto/bn/bn_lcl.h +++ b/crypto/bn/bn_lcl.h @@ -240,7 +240,8 @@ struct bignum_st { /* Used for montgomery multiplication */ struct bn_mont_ctx_st { int ri; /* number of bits in R */ - BIGNUM RR; /* used to convert to montgomery form */ + BIGNUM RR; /* used to convert to montgomery form, + possibly zero-padded */ BIGNUM N; /* The modulus */ BIGNUM Ni; /* R*(1/R mod N) - N*Ni = 1 (Ni is only * stored for bignum algorithm) */ diff --git a/crypto/bn/bn_mont.c b/crypto/bn/bn_mont.c index e1d2973032..3ccf8eaf37 100644 --- a/crypto/bn/bn_mont.c +++ b/crypto/bn/bn_mont.c @@ -20,11 +20,22 @@ #define MONT_WORD /* use the faster word-based algorithm */ #ifdef MONT_WORD -static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont); +static int bn_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont); #endif int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_MONT_CTX *mont, BN_CTX *ctx) +{ + int ret = bn_mul_mont_fixed_top(r, a, b, mont, ctx); + + bn_correct_top(r); + bn_check_top(r); + + return ret; +} + +int bn_mul_mont_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + BN_MONT_CTX *mont, BN_CTX *ctx) { BIGNUM *tmp; int ret = 0; @@ -37,7 +48,7 @@ int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) { r->neg = a->neg ^ b->neg; r->top = num; - bn_correct_top(r); + r->flags |= BN_FLG_FIXED_TOP; return (1); } } @@ -61,13 +72,12 @@ int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, } /* reduce from aRR to aR */ #ifdef MONT_WORD - if (!BN_from_montgomery_word(r, tmp, mont)) + if (!bn_from_montgomery_word(r, tmp, mont)) goto err; #else if (!BN_from_montgomery(r, tmp, mont, ctx)) goto err; #endif - bn_check_top(r); ret = 1; err: BN_CTX_end(ctx); @@ -75,7 +85,7 @@ int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, } #ifdef MONT_WORD -static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) +static int bn_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) { BIGNUM *n; BN_ULONG *ap, *np, *rp, n0, v, carry; @@ -102,6 +112,7 @@ static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) memset(&rp[r->top], 0, sizeof(*rp) * i); r->top = max; + r->flags |= BN_FLG_FIXED_TOP; n0 = mont->n0[0]; /* @@ -120,6 +131,7 @@ static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) if (bn_wexpand(ret, nl) == NULL) return (0); ret->top = nl; + ret->flags |= BN_FLG_FIXED_TOP; ret->neg = r->neg; rp = ret->d; @@ -140,9 +152,6 @@ static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont) rp[i] = (carry & ap[i]) | (~carry & rp[i]); ap[i] = 0; } - bn_correct_top(r); - bn_correct_top(ret); - bn_check_top(ret); return (1); } @@ -156,8 +165,11 @@ int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, BIGNUM *t; BN_CTX_start(ctx); - if ((t = BN_CTX_get(ctx)) && BN_copy(t, a)) - retn = BN_from_montgomery_word(ret, t, mont); + if ((t = BN_CTX_get(ctx)) && BN_copy(t, a)) { + retn = bn_from_montgomery_word(ret, t, mont); + bn_correct_top(ret); + bn_check_top(ret); + } BN_CTX_end(ctx); #else /* !MONT_WORD */ BIGNUM *t1, *t2; @@ -195,6 +207,12 @@ int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, return (retn); } +int bn_to_mont_fixed_top(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont, + BN_CTX *ctx) +{ + return bn_mul_mont_fixed_top(r, a, &(mont->RR), mont, ctx); +} + BN_MONT_CTX *BN_MONT_CTX_new(void) { BN_MONT_CTX *ret; @@ -231,7 +249,7 @@ void BN_MONT_CTX_free(BN_MONT_CTX *mont) int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) { - int ret = 0; + int i, ret = 0; BIGNUM *Ri, *R; if (BN_is_zero(mod)) @@ -366,6 +384,11 @@ int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx) if (!BN_mod(&(mont->RR), &(mont->RR), &(mont->N), ctx)) goto err; + for (i = mont->RR.top, ret = mont->N.top; i < ret; i++) + mont->RR.d[i] = 0; + mont->RR.top = ret; + mont->RR.flags |= BN_FLG_FIXED_TOP; + ret = 1; err: BN_CTX_end(ctx); diff --git a/crypto/include/internal/bn_int.h b/crypto/include/internal/bn_int.h index 4e0c9a423a..3501ffb3b4 100644 --- a/crypto/include/internal/bn_int.h +++ b/crypto/include/internal/bn_int.h @@ -74,6 +74,17 @@ size_t bn_sizeof_BIGNUM(void); */ BIGNUM *bn_array_el(BIGNUM *base, int el); +/* + * Some BIGNUM functions assume most significant limb to be non-zero, which + * is customarily arranged by bn_correct_top. Output from below functions + * is not processed with bn_correct_top, and for this reason it may not be + * returned out of public API. It may only be passed internally into other + * functions known to support non-minimal or zero-padded BIGNUMs. + */ +int bn_mul_mont_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, + BN_MONT_CTX *mont, BN_CTX *ctx); +int bn_to_mont_fixed_top(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont, + BN_CTX *ctx); #ifdef __cplusplus } -- 2.25.1