From 0c86c87c6091793a9e428abd9b05d980fef5a5f3 Mon Sep 17 00:00:00 2001 From: Andy Polyakov Date: Mon, 11 Jun 2007 16:43:29 +0000 Subject: [PATCH] Updates from stable branch: BN_*_no_branch privatization and elimination of conditional final subtraction in Montgomery multiplication. --- crypto/bn/bn.h | 4 --- crypto/bn/bn_div.c | 8 +++-- crypto/bn/bn_gcd.c | 4 ++- crypto/bn/bn_mont.c | 84 ++++++++++++++++++++++++++++++++++++++------- util/libeay.num | 2 -- 5 files changed, 79 insertions(+), 23 deletions(-) diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h index b2d621fe97..c05a65d397 100644 --- a/crypto/bn/bn.h +++ b/crypto/bn/bn.h @@ -435,8 +435,6 @@ void BN_set_negative(BIGNUM *b, int n); int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx); -int BN_div_no_branch(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, - const BIGNUM *d, BN_CTX *ctx); #define BN_mod(rem,m,d,ctx) BN_div(NULL,(rem),(m),(d),(ctx)) int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx); int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx); @@ -505,8 +503,6 @@ int BN_gcd(BIGNUM *r,const BIGNUM *a,const BIGNUM *b,BN_CTX *ctx); int BN_kronecker(const BIGNUM *a,const BIGNUM *b,BN_CTX *ctx); /* returns -2 for error */ BIGNUM *BN_mod_inverse(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n,BN_CTX *ctx); -BIGNUM *BN_mod_inverse_no_branch(BIGNUM *ret, - const BIGNUM *A, const BIGNUM *n,BN_CTX *ctx); BIGNUM *BN_mod_sqrt(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n,BN_CTX *ctx); diff --git a/crypto/bn/bn_div.c b/crypto/bn/bn_div.c index 514b2c2c82..8655eb118e 100644 --- a/crypto/bn/bn_div.c +++ b/crypto/bn/bn_div.c @@ -169,13 +169,15 @@ int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, #endif /* OPENSSL_NO_ASM */ -/* BN_div computes dv := num / divisor, rounding towards zero, and sets up - * rm such that dv*divisor + rm = num holds. +/* BN_div[_no_branch] computes dv := num / divisor, rounding towards + * zero, and sets up rm such that dv*divisor + rm = num holds. * Thus: * dv->neg == num->neg ^ divisor->neg (unless the result is zero) * rm->neg == num->neg (unless the remainder is zero) * If 'dv' or 'rm' is NULL, the respective value is not returned. */ +static int BN_div_no_branch(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, + const BIGNUM *divisor, BN_CTX *ctx); int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, BN_CTX *ctx) { @@ -406,7 +408,7 @@ err: /* BN_div_no_branch is a special version of BN_div. It does not contain * branches that may leak sensitive information. */ -int BN_div_no_branch(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, +static int BN_div_no_branch(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, BN_CTX *ctx) { int norm_shift,i,loop; diff --git a/crypto/bn/bn_gcd.c b/crypto/bn/bn_gcd.c index 85e4b50c10..4a352119ba 100644 --- a/crypto/bn/bn_gcd.c +++ b/crypto/bn/bn_gcd.c @@ -203,6 +203,8 @@ err: /* solves ax == 1 (mod n) */ +static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, + const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx); BIGNUM *BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) { @@ -501,7 +503,7 @@ err: /* BN_mod_inverse_no_branch is a special version of BN_mod_inverse. * It does not contain branches that may leak sensitive information. */ -BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, +static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) { BIGNUM *A,*B,*X,*Y,*M,*D,*T,*R=NULL; diff --git a/crypto/bn/bn_mont.c b/crypto/bn/bn_mont.c index 961ca67ea1..bf45fe916d 100644 --- a/crypto/bn/bn_mont.c +++ b/crypto/bn/bn_mont.c @@ -176,7 +176,6 @@ int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, max=(nl+al+1); /* allow for overflow (no?) XXX */ if (bn_wexpand(r,max) == NULL) goto err; - if (bn_wexpand(ret,max) == NULL) goto err; r->neg=a->neg^n->neg; np=n->d; @@ -228,19 +227,76 @@ int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, } bn_correct_top(r); - /* mont->ri will be a multiple of the word size */ -#if 0 - BN_rshift(ret,r,mont->ri); -#else - ret->neg = r->neg; - x=ri; + /* mont->ri will be a multiple of the word size and below code + * is kind of BN_rshift(ret,r,mont->ri) equivalent */ + if (r->top <= ri) + { + ret->top=0; + retn=1; + goto err; + } + al=r->top-ri; + +# define BRANCH_FREE 1 +# if BRANCH_FREE + if (bn_wexpand(ret,ri) == NULL) goto err; + x=0-(((al-ri)>>(sizeof(al)*8-1))&1); + ret->top=x=(ri&~x)|(al&x); /* min(ri,al) */ + ret->neg=r->neg; + rp=ret->d; - ap= &(r->d[x]); - if (r->top < x) - al=0; - else - al=r->top-x; + ap=&(r->d[ri]); + nrp=ap; + + /* This 'if' denotes violation of 2*MN.d[ri-1]>>(BN_BITS2-2))!=0) + { + size_t m1,m2; + + v=bn_sub_words(rp,ap,mont->N.d,ri); + /* this -----------------------^^ works even in alri) nrp=rp; else nrp=ap; */ + /* in other words if subtraction result is real, then + * trick unconditional memcpy below to perform in-place + * "refresh" instead of actual copy. */ + m1=0-(size_t)(((al-ri)>>(sizeof(al)*8-1))&1); /* al>(sizeof(al)*8-1))&1); /* al>ri */ + m1|=m2; /* (al!=ri) */ + m1|=(0-(size_t)v); /* (al!=ri || v) */ + m1&=~m2; /* (al!=ri || v) && !al>ri */ + nrp=(BN_ULONG *)(((size_t)rp&~m1)|((size_t)ap&m1)); + } + + /* 'itop=al; + ret->neg=r->neg; + + rp=ret->d; + ap=&(r->d[ri]); al-=4; for (i=0; iri)) goto err; #endif /* MONT_WORD */ +#if !defined(BRANCH_FREE) || BRANCH_FREE==0 if (BN_ucmp(ret, &(mont->N)) >= 0) { if (!BN_usub(ret,ret,&(mont->N))) goto err; } +#endif retn=1; bn_check_top(ret); err: diff --git a/util/libeay.num b/util/libeay.num index f07ea71cc4..9149a53f08 100755 --- a/util/libeay.num +++ b/util/libeay.num @@ -3511,8 +3511,6 @@ BIO_get_callback_arg 3902 EXIST::FUNCTION: BIO_set_callback 3903 EXIST::FUNCTION: d2i_ASIdOrRange 3904 EXIST::FUNCTION:RFC3779 i2d_ASIdentifiers 3905 EXIST::FUNCTION:RFC3779 -BN_div_no_branch 3906 EXIST::FUNCTION: -BN_mod_inverse_no_branch 3907 EXIST::FUNCTION: SEED_decrypt 3908 EXIST::FUNCTION:SEED SEED_encrypt 3909 EXIST::FUNCTION:SEED SEED_cbc_encrypt 3910 EXIST::FUNCTION:SEED -- 2.25.1