X-Git-Url: https://git.openssl.org/gitweb/?a=blobdiff_plain;f=crypto%2Fbn%2Fbn_lib.c;h=7a8f8c1450177fcf2e2386f3d99a3f154f9ac760;hb=cc4cd8213ee3e9eb0c7925d3076647b63febca10;hp=3f607cd53249b3e4ff5695933a9ed3b907852c30;hpb=d420ac2c7d4ba9d99ff2c257a3ad71ecc6d876e2;p=openssl.git diff --git a/crypto/bn/bn_lib.c b/crypto/bn/bn_lib.c index 3f607cd532..7a8f8c1450 100644 --- a/crypto/bn/bn_lib.c +++ b/crypto/bn/bn_lib.c @@ -67,9 +67,12 @@ #include "cryptlib.h" #include "bn_lcl.h" -const char *BN_version="Big Number" OPENSSL_VERSION_PTEXT; +const char BN_version[]="Big Number" OPENSSL_VERSION_PTEXT; -/* For a 32 bit machine +/* This stuff appears to be completely unused, so is deprecated */ +#ifndef OPENSSL_NO_DEPRECATED +/*- + * For a 32 bit machine * 2 - 4 == 128 * 3 - 8 == 256 * 4 - 16 == 512 @@ -127,37 +130,19 @@ int BN_get_params(int which) else if (which == 3) return(bn_limit_bits_mont); else return(0); } +#endif const BIGNUM *BN_value_one(void) { - static BN_ULONG data_one=1L; - static BIGNUM const_one={&data_one,1,1,0,BN_FLG_STATIC_DATA}; + static const BN_ULONG data_one=1L; + static const BIGNUM const_one={(BN_ULONG *)&data_one,1,1,0,BN_FLG_STATIC_DATA}; return(&const_one); } -char *BN_options(void) - { - static int init=0; - static char data[16]; - - if (!init) - { - init++; -#ifdef BN_LLONG - BIO_snprintf(data,sizeof data,"bn(%d,%d)", - (int)sizeof(BN_ULLONG)*8,(int)sizeof(BN_ULONG)*8); -#else - BIO_snprintf(data,sizeof data,"bn(%d,%d)", - (int)sizeof(BN_ULONG)*8,(int)sizeof(BN_ULONG)*8); -#endif - } - return(data); - } - int BN_num_bits_word(BN_ULONG l) { - static const char bits[256]={ + static const unsigned char bits[256]={ 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4, 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, @@ -232,7 +217,7 @@ int BN_num_bits_word(BN_ULONG l) else #endif { -#if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) +#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) if (l & 0xff00L) return(bits[(int)(l>>8)]+8); else @@ -330,12 +315,21 @@ static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); return(NULL); } - a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*(words+1)); + a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*words); if (A == NULL) { BNerr(BN_F_BN_EXPAND_INTERNAL,ERR_R_MALLOC_FAILURE); return(NULL); } +#ifdef PURIFY + /* Valgrind complains in BN_consttime_swap because we process the whole + * array even if it's not initialised yet. This doesn't matter in that + * function - what's important is constant time operation (we're not + * actually going to use the data) + */ + memset(a, 0, sizeof(BN_ULONG)*words); +#endif + #if 1 B=b->d; /* Check if the previous number needs to be copied */ @@ -361,15 +355,18 @@ static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) case 3: A[2]=B[2]; case 2: A[1]=B[1]; case 1: A[0]=B[0]; - case 0: /* workaround for ultrix cc: without 'case 0', the optimizer does - * the switch table by doing a=top&3; a--; goto jump_table[a]; - * which fails for top== 0 */ + case 0: ; + /* + * workaround for ultrix cc: without 'case 0', the optimizer does + * the switch table by doing a=top&3; a--; goto jump_table[a]; + * which fails for top== 0 + */ } } #else - memset(A,0,sizeof(BN_ULONG)*(words+1)); + memset(A,0,sizeof(BN_ULONG)*words); memcpy(A,b->d,sizeof(b->d[0])*b->top); #endif @@ -387,6 +384,7 @@ static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) * while bn_dup_expand() makes sure allocation is made only once. */ +#ifndef OPENSSL_NO_DEPRECATED BIGNUM *bn_dup_expand(const BIGNUM *b, int words) { BIGNUM *r = NULL; @@ -430,6 +428,7 @@ BIGNUM *bn_dup_expand(const BIGNUM *b, int words) bn_check_top(r); return r; } +#endif /* This is an internal function that should not be used in applications. * It ensures that 'b' has enough room for a 'words' word number @@ -439,9 +438,6 @@ BIGNUM *bn_dup_expand(const BIGNUM *b, int words) BIGNUM *bn_expand2(BIGNUM *b, int words) { - BN_ULONG *A; - int i; - bn_check_top(b); if (words > b->dmax) @@ -453,10 +449,13 @@ BIGNUM *bn_expand2(BIGNUM *b, int words) b->dmax=words; } +/* None of this should be necessary because of what b->top means! */ +#if 0 /* NB: bn_wexpand() calls this only if the BIGNUM really has to grow */ if (b->top < b->dmax) { - A = &(b->d[b->top]); + int i; + BN_ULONG *A = &(b->d[b->top]); for (i=(b->dmax - b->top)>>3; i>0; i--,A+=8) { A[0]=0; A[1]=0; A[2]=0; A[3]=0; @@ -466,6 +465,7 @@ BIGNUM *bn_expand2(BIGNUM *b, int words) A[0]=0; assert(A == &(b->d[b->dmax])); } +#endif bn_check_top(b); return b; } @@ -520,55 +520,11 @@ BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) #endif a->top=b->top; -#ifndef BN_STRICT - if ((a->top == 0) && (a->d != NULL)) - a->d[0]=0; -#endif a->neg=b->neg; bn_check_top(a); return(a); } -BIGNUM *BN_ncopy(BIGNUM *a, const BIGNUM *b, size_t n) - { - int i, min; - BN_ULONG *A; - const BN_ULONG *B; - - bn_check_top(b); - if (a == b) - return a; - - min = (b->top < (int)n)? b->top: (int)n; - if (!min) - { - BN_zero(a); - return a; - } - if (bn_wexpand(a, min) == NULL) - return NULL; - - A=a->d; - B=b->d; - for (i=min>>2; i>0; i--, A+=4, B+=4) - { - BN_ULONG a0,a1,a2,a3; - a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3]; - A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3; - } - switch (min&3) - { - case 3: A[2]=B[2]; - case 2: A[1]=B[1]; - case 1: A[0]=B[0]; - case 0: ; - } - a->top = min; - a->neg = b->neg; - bn_correct_top(a); - return(a); - } - void BN_swap(BIGNUM *a, BIGNUM *b) { int flags_old_a, flags_old_b; @@ -613,50 +569,21 @@ void BN_clear(BIGNUM *a) BN_ULONG BN_get_word(const BIGNUM *a) { - int i,n; - BN_ULONG ret=0; - - n=BN_num_bytes(a); - if (n > (int)sizeof(BN_ULONG)) - return(BN_MASK2); - for (i=a->top-1; i>=0; i--) - { -#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */ - ret<<=BN_BITS4; /* stops the compiler complaining */ - ret<<=BN_BITS4; -#else - ret=0; -#endif - ret|=a->d[i]; - } - return(ret); + if (a->top > 1) + return BN_MASK2; + else if (a->top == 1) + return a->d[0]; + /* a->top == 0 */ + return 0; } int BN_set_word(BIGNUM *a, BN_ULONG w) { - int i,n; bn_check_top(a); if (bn_expand(a,(int)sizeof(BN_ULONG)*8) == NULL) return(0); - - n=sizeof(BN_ULONG)/BN_BYTES; - a->neg=0; - a->top=0; - a->d[0]=(BN_ULONG)w&BN_MASK2; - if (a->d[0] != 0) a->top=1; - for (i=1; i>=BN_BITS2 so compilers don't complain - * on builds where sizeof(long) == BN_TYPES */ -#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */ - w>>=BN_BITS4; - w>>=BN_BITS4; -#else - w=0; -#endif - a->d[i]=(BN_ULONG)w&BN_MASK2; - if (a->d[i] != 0) a->top=i+1; - } + a->neg = 0; + a->d[0] = w; + a->top = (w ? 1 : 0); bn_check_top(a); return(1); } @@ -666,8 +593,10 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) unsigned int i,m; unsigned int n; BN_ULONG l; + BIGNUM *bn = NULL; - if (ret == NULL) ret=BN_new(); + if (ret == NULL) + ret = bn = BN_new(); if (ret == NULL) return(NULL); bn_check_top(ret); l=0; @@ -677,13 +606,16 @@ BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) ret->top=0; return(ret); } - if (bn_expand(ret,(int)(n+2)*8) == NULL) - return(NULL); i=((n-1)/BN_BYTES)+1; m=((n-1)%(BN_BYTES)); + if (bn_wexpand(ret, (int)i) == NULL) + { + if (bn) BN_free(bn); + return NULL; + } ret->top=i; ret->neg=0; - while (n-- > 0) + while (n--) { l=(l<<8L)| *(s++); if (m-- == 0) @@ -707,7 +639,7 @@ int BN_bn2bin(const BIGNUM *a, unsigned char *to) bn_check_top(a); n=i=BN_num_bytes(a); - while (i-- > 0) + while (i--) { l=a->d[i/BN_BYTES]; *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff; @@ -825,7 +757,7 @@ int BN_is_bit_set(const BIGNUM *a, int n) i=n/BN_BITS2; j=n%BN_BITS2; if (a->top <= i) return 0; - return((a->d[i]&(((BN_ULONG)1)<d[i])>>j)&((BN_ULONG)1)); } int BN_mask_bits(BIGNUM *a, int n) @@ -849,6 +781,14 @@ int BN_mask_bits(BIGNUM *a, int n) return(1); } +void BN_set_negative(BIGNUM *a, int b) + { + if (b && !BN_is_zero(a)) + a->neg = 1; + else + a->neg = 0; + } + int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) { int i; @@ -897,3 +837,55 @@ int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, } return bn_cmp_words(a,b,cl); } + +/* + * Constant-time conditional swap of a and b. + * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set. + * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b, + * and that no more than nwords are used by either a or b. + * a and b cannot be the same number + */ +void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) + { + BN_ULONG t; + int i; + + bn_wcheck_size(a, nwords); + bn_wcheck_size(b, nwords); + + assert(a != b); + assert((condition & (condition - 1)) == 0); + assert(sizeof(BN_ULONG) >= sizeof(int)); + + condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1; + + t = (a->top^b->top) & condition; + a->top ^= t; + b->top ^= t; + +#define BN_CONSTTIME_SWAP(ind) \ + do { \ + t = (a->d[ind] ^ b->d[ind]) & condition; \ + a->d[ind] ^= t; \ + b->d[ind] ^= t; \ + } while (0) + + + switch (nwords) { + default: + for (i = 10; i < nwords; i++) + BN_CONSTTIME_SWAP(i); + /* Fallthrough */ + case 10: BN_CONSTTIME_SWAP(9); /* Fallthrough */ + case 9: BN_CONSTTIME_SWAP(8); /* Fallthrough */ + case 8: BN_CONSTTIME_SWAP(7); /* Fallthrough */ + case 7: BN_CONSTTIME_SWAP(6); /* Fallthrough */ + case 6: BN_CONSTTIME_SWAP(5); /* Fallthrough */ + case 5: BN_CONSTTIME_SWAP(4); /* Fallthrough */ + case 4: BN_CONSTTIME_SWAP(3); /* Fallthrough */ + case 3: BN_CONSTTIME_SWAP(2); /* Fallthrough */ + case 2: BN_CONSTTIME_SWAP(1); /* Fallthrough */ + case 1: BN_CONSTTIME_SWAP(0); + } +#undef BN_CONSTTIME_SWAP +}