From 15b5d84f9da2ce4bfae8580e56e34a859f74ad71 Mon Sep 17 00:00:00 2001 From: markus <> Date: Thu, 5 Sep 2002 12:51:50 +0000 Subject: import openssl-0.9.7-beta1 --- src/lib/libcrypto/bn/bn_lib.c | 571 ++++++++++++++++++++++++++++-------------- 1 file changed, 389 insertions(+), 182 deletions(-) (limited to 'src/lib/libcrypto/bn/bn_lib.c') diff --git a/src/lib/libcrypto/bn/bn_lib.c b/src/lib/libcrypto/bn/bn_lib.c index bfe7628ad4..a016cb7f53 100644 --- a/src/lib/libcrypto/bn/bn_lib.c +++ b/src/lib/libcrypto/bn/bn_lib.c @@ -56,13 +56,79 @@ * [including the GNU Public Licence.] */ +#ifndef BN_DEBUG +# undef NDEBUG /* avoid conflicting definitions */ +# define NDEBUG +#endif + +#include +#include #include #include "cryptlib.h" #include "bn_lcl.h" -char *BN_version="Big Number part of SSLeay 0.9.0b 29-Jun-1998"; +const char *BN_version="Big Number" OPENSSL_VERSION_PTEXT; -BIGNUM *BN_value_one() +/* For a 32 bit machine + * 2 - 4 == 128 + * 3 - 8 == 256 + * 4 - 16 == 512 + * 5 - 32 == 1024 + * 6 - 64 == 2048 + * 7 - 128 == 4096 + * 8 - 256 == 8192 + */ +static int bn_limit_bits=0; +static int bn_limit_num=8; /* (1<= 0) + { + if (mult > (sizeof(int)*8)-1) + mult=sizeof(int)*8-1; + bn_limit_bits=mult; + bn_limit_num=1<= 0) + { + if (high > (sizeof(int)*8)-1) + high=sizeof(int)*8-1; + bn_limit_bits_high=high; + bn_limit_num_high=1<= 0) + { + if (low > (sizeof(int)*8)-1) + low=sizeof(int)*8-1; + bn_limit_bits_low=low; + bn_limit_num_low=1<= 0) + { + if (mont > (sizeof(int)*8)-1) + mont=sizeof(int)*8-1; + bn_limit_bits_mont=mont; + bn_limit_num_mont=1<>56]+56); + return(bits[(int)(l>>56)]+56); } - else return(bits[l>>48]+48); + else return(bits[(int)(l>>48)]+48); } else { if (l & 0x0000ff0000000000L) { - return(bits[l>>40]+40); + return(bits[(int)(l>>40)]+40); } - else return(bits[l>>32]+32); + else return(bits[(int)(l>>32)]+32); } } else @@ -140,17 +205,17 @@ BN_ULONG l; { if (l & 0xff00000000000000LL) { - return(bits[l>>56]+56); + return(bits[(int)(l>>56)]+56); } - else return(bits[l>>48]+48); + else return(bits[(int)(l>>48)]+48); } else { if (l & 0x0000ff0000000000LL) { - return(bits[l>>40]+40); + return(bits[(int)(l>>40)]+40); } - else return(bits[l>>32]+32); + else return(bits[(int)(l>>32)]+32); } } else @@ -161,161 +226,256 @@ BN_ULONG l; if (l & 0xffff0000L) { if (l & 0xff000000L) - return(bits[l>>24L]+24); - else return(bits[l>>16L]+16); + return(bits[(int)(l>>24L)]+24); + else return(bits[(int)(l>>16L)]+16); } else #endif { #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) if (l & 0xff00L) - return(bits[l>>8]+8); + return(bits[(int)(l>>8)]+8); else #endif - return(bits[l ] ); + return(bits[(int)(l )] ); } } } -int BN_num_bits(a) -BIGNUM *a; +int BN_num_bits(const BIGNUM *a) { BN_ULONG l; int i; + bn_check_top(a); + if (a->top == 0) return(0); l=a->d[a->top-1]; + assert(l != 0); i=(a->top-1)*BN_BITS2; - if (l == 0) - { -#if !defined(NO_STDIO) && !defined(WIN16) - fprintf(stderr,"BAD TOP VALUE\n"); -#endif - abort(); - } return(i+BN_num_bits_word(l)); } -void BN_clear_free(a) -BIGNUM *a; +void BN_clear_free(BIGNUM *a) { + int i; + if (a == NULL) return; if (a->d != NULL) { - memset(a->d,0,a->max*sizeof(a->d[0])); - Free(a->d); + memset(a->d,0,a->dmax*sizeof(a->d[0])); + if (!(BN_get_flags(a,BN_FLG_STATIC_DATA))) + OPENSSL_free(a->d); } + i=BN_get_flags(a,BN_FLG_MALLOCED); memset(a,0,sizeof(BIGNUM)); - Free(a); + if (i) + OPENSSL_free(a); } -void BN_free(a) -BIGNUM *a; +void BN_free(BIGNUM *a) { if (a == NULL) return; - if (a->d != NULL) Free(a->d); - Free(a); + if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA))) + OPENSSL_free(a->d); + a->flags|=BN_FLG_FREE; /* REMOVE? */ + if (a->flags & BN_FLG_MALLOCED) + OPENSSL_free(a); } -BIGNUM *BN_new() +void BN_init(BIGNUM *a) + { + memset(a,0,sizeof(BIGNUM)); + } + +BIGNUM *BN_new(void) { BIGNUM *ret; - BN_ULONG *p; - ret=(BIGNUM *)Malloc(sizeof(BIGNUM)); - if (ret == NULL) goto err; + if ((ret=(BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL) + { + BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE); + return(NULL); + } + ret->flags=BN_FLG_MALLOCED; ret->top=0; ret->neg=0; - ret->max=(BN_DEFAULT_BITS/BN_BITS2); - p=(BN_ULONG *)Malloc(sizeof(BN_ULONG)*(ret->max+1)); - if (p == NULL) goto err; - ret->d=p; - - memset(p,0,(ret->max+1)*sizeof(p[0])); + ret->dmax=0; + ret->d=NULL; return(ret); -err: - BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE); - return(NULL); } -BN_CTX *BN_CTX_new() +/* This is used both by bn_expand2() and bn_dup_expand() */ +/* The caller MUST check that words > b->dmax before calling this */ +static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) { - BN_CTX *ret; - BIGNUM *n; - int i,j; + BN_ULONG *A,*a = NULL; + const BN_ULONG *B; + int i; - ret=(BN_CTX *)Malloc(sizeof(BN_CTX)); - if (ret == NULL) goto err2; + if (words > (INT_MAX/(4*BN_BITS2))) + { + BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_BIGNUM_TOO_LONG); + return NULL; + } - for (i=0; ibn[i]=n; + 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)); + if (A == NULL) + { + BNerr(BN_F_BN_EXPAND_INTERNAL,ERR_R_MALLOC_FAILURE); + return(NULL); + } +#if 1 + B=b->d; + /* Check if the previous number needs to be copied */ + if (B != NULL) + { + for (i=b->top>>2; i>0; i--,A+=4,B+=4) + { + /* + * The fact that the loop is unrolled + * 4-wise is a tribute to Intel. It's + * the one that doesn't have enough + * registers to accomodate more data. + * I'd unroll it 8-wise otherwise:-) + * + * + */ + 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 (b->top&3) + { + 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 */ + ; + } } - /* There is actually an extra one, this is for debugging my - * stuff */ - ret->bn[BN_CTX_NUM]=NULL; + /* Now need to zero any data between b->top and b->max */ + /* XXX Why? */ - ret->tos=0; - return(ret); -err: - for (j=0; jbn[j]); - Free(ret); -err2: - BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE); - return(NULL); + A= &(a[b->top]); + for (i=(words - b->top)>>3; i>0; i--,A+=8) + { + A[0]=0; A[1]=0; A[2]=0; A[3]=0; + A[4]=0; A[5]=0; A[6]=0; A[7]=0; + } + for (i=(words - b->top)&7; i>0; i--,A++) + A[0]=0; +#else + memset(A,0,sizeof(BN_ULONG)*(words+1)); + memcpy(A,b->d,sizeof(b->d[0])*b->top); +#endif + + return(a); } -void BN_CTX_free(c) -BN_CTX *c; +/* This is an internal function that can be used instead of bn_expand2() + * when there is a need to copy BIGNUMs instead of only expanding the + * data part, while still expanding them. + * Especially useful when needing to expand BIGNUMs that are declared + * 'const' and should therefore not be changed. + * The reason to use this instead of a BN_dup() followed by a bn_expand2() + * is memory allocation overhead. A BN_dup() followed by a bn_expand2() + * will allocate new memory for the BIGNUM data twice, and free it once, + * while bn_dup_expand() makes sure allocation is made only once. + */ + +BIGNUM *bn_dup_expand(const BIGNUM *b, int words) { - int i; + BIGNUM *r = NULL; + + if (words > b->dmax) + { + BN_ULONG *a = bn_expand_internal(b, words); - for (i=0; ibn[i]); - Free(c); + if (a) + { + r = BN_new(); + if (r) + { + r->top = b->top; + r->dmax = words; + r->neg = b->neg; + r->d = a; + } + else + { + /* r == NULL, BN_new failure */ + OPENSSL_free(a); + } + } + /* If a == NULL, there was an error in allocation in + bn_expand_internal(), and NULL should be returned */ + } + else + { + r = BN_dup(b); + } + + return r; } -BIGNUM *bn_expand2(b, words) -BIGNUM *b; -int words; - { - BN_ULONG *p; +/* This is an internal function that should not be used in applications. + * It ensures that 'b' has enough room for a 'words' word number number. + * It is mostly used by the various BIGNUM routines. If there is an error, + * NULL is returned. If not, 'b' is returned. */ - if (words > b->max) +BIGNUM *bn_expand2(BIGNUM *b, int words) + { + if (words > b->dmax) { - p=(BN_ULONG *)Realloc(b->d,sizeof(BN_ULONG)*(words+1)); - if (p == NULL) + BN_ULONG *a = bn_expand_internal(b, words); + + if (a) { - BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE); - return(NULL); + if (b->d) + OPENSSL_free(b->d); + b->d=a; + b->dmax=words; } - b->d=p; - memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); - b->max=words; + else + b = NULL; } - return(b); + return b; } -BIGNUM *BN_dup(a) -BIGNUM *a; +BIGNUM *BN_dup(const BIGNUM *a) { - BIGNUM *r; + BIGNUM *r, *t; - r=BN_new(); - if (r == NULL) return(NULL); - return((BIGNUM *)BN_copy(r,a)); + if (a == NULL) return NULL; + + bn_check_top(a); + + t = BN_new(); + if (t == NULL) return(NULL); + r = BN_copy(t, a); + /* now r == t || r == NULL */ + if (r == NULL) + BN_free(t); + return r; } -BIGNUM *BN_copy(a, b) -BIGNUM *a; -BIGNUM *b; +BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) { int i; - BN_ULONG *A,*B; + BN_ULONG *A; + const BN_ULONG *B; + + bn_check_top(b); if (a == b) return(a); if (bn_wexpand(a,b->top) == NULL) return(NULL); @@ -323,35 +483,18 @@ BIGNUM *b; #if 1 A=a->d; B=b->d; - for (i=b->top&(~7); i>0; i-=8) - { - A[0]=B[0]; - A[1]=B[1]; - A[2]=B[2]; - A[3]=B[3]; - A[4]=B[4]; - A[5]=B[5]; - A[6]=B[6]; - A[7]=B[7]; - A+=8; - B+=8; - } - switch (b->top&7) - { - case 7: - A[6]=B[6]; - case 6: - A[5]=B[5]; - case 5: - A[4]=B[4]; - case 4: - A[3]=B[3]; - case 3: - A[2]=B[2]; - case 2: - A[1]=B[1]; - case 1: - A[0]=B[0]; + for (i=b->top>>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 (b->top&3) + { + case 3: A[2]=B[2]; + case 2: A[1]=B[1]; + case 1: A[0]=B[0]; + case 0: ; /* ultrix cc workaround, see comments in bn_expand_internal */ } #else memcpy(a->d,b->d,sizeof(b->d[0])*b->top); @@ -359,52 +502,76 @@ BIGNUM *b; /* memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/ a->top=b->top; - if (a->top == 0) + if ((a->top == 0) && (a->d != NULL)) a->d[0]=0; a->neg=b->neg; return(a); } -void BN_clear(a) -BIGNUM *a; +void BN_swap(BIGNUM *a, BIGNUM *b) + { + int flags_old_a, flags_old_b; + BN_ULONG *tmp_d; + int tmp_top, tmp_dmax, tmp_neg; + + flags_old_a = a->flags; + flags_old_b = b->flags; + + tmp_d = a->d; + tmp_top = a->top; + tmp_dmax = a->dmax; + tmp_neg = a->neg; + + a->d = b->d; + a->top = b->top; + a->dmax = b->dmax; + a->neg = b->neg; + + b->d = tmp_d; + b->top = tmp_top; + b->dmax = tmp_dmax; + b->neg = tmp_neg; + + a->flags = (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA); + b->flags = (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA); + } + + +void BN_clear(BIGNUM *a) { - memset(a->d,0,a->max*sizeof(a->d[0])); + if (a->d != NULL) + memset(a->d,0,a->dmax*sizeof(a->d[0])); a->top=0; a->neg=0; } -unsigned long BN_get_word(a) -BIGNUM *a; +BN_ULONG BN_get_word(const BIGNUM *a) { int i,n; - unsigned long ret=0; + BN_ULONG ret=0; n=BN_num_bytes(a); - if (n > sizeof(unsigned long)) -#ifdef SIXTY_FOUR_BIT_LONG + if (n > sizeof(BN_ULONG)) return(BN_MASK2); -#else - return(0xFFFFFFFFL); -#endif 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); } -int BN_set_word(a,w) -BIGNUM *a; -unsigned long w; +int BN_set_word(BIGNUM *a, BN_ULONG w) { int i,n; - if (bn_expand(a,sizeof(unsigned long)*8) == NULL) return(0); + if (bn_expand(a,sizeof(BN_ULONG)*8) == NULL) return(0); - n=sizeof(unsigned long)/BN_BYTES; + n=sizeof(BN_ULONG)/BN_BYTES; a->neg=0; a->top=0; a->d[0]=(BN_ULONG)w&BN_MASK2; @@ -417,6 +584,8 @@ unsigned long w; #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; @@ -424,11 +593,7 @@ unsigned long w; return(1); } -/* ignore negative */ -BIGNUM *BN_bin2bn(s, len, ret) -unsigned char *s; -int len; -BIGNUM *ret; +BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) { unsigned int i,m; unsigned int n; @@ -448,6 +613,7 @@ BIGNUM *ret; i=((n-1)/BN_BYTES)+1; m=((n-1)%(BN_BYTES)); ret->top=i; + ret->neg=0; while (n-- > 0) { l=(l<<8L)| *(s++); @@ -465,9 +631,7 @@ BIGNUM *ret; } /* ignore negative */ -int BN_bn2bin(a, to) -BIGNUM *a; -unsigned char *to; +int BN_bn2bin(const BIGNUM *a, unsigned char *to) { int n,i; BN_ULONG l; @@ -481,13 +645,14 @@ unsigned char *to; return(n); } -int BN_ucmp(a, b) -BIGNUM *a; -BIGNUM *b; +int BN_ucmp(const BIGNUM *a, const BIGNUM *b) { int i; BN_ULONG t1,t2,*ap,*bp; + bn_check_top(a); + bn_check_top(b); + i=a->top-b->top; if (i != 0) return(i); ap=a->d; @@ -502,9 +667,7 @@ BIGNUM *b; return(0); } -int BN_cmp(a, b) -BIGNUM *a; -BIGNUM *b; +int BN_cmp(const BIGNUM *a, const BIGNUM *b) { int i; int gt,lt; @@ -519,6 +682,10 @@ BIGNUM *b; else return(0); } + + bn_check_top(a); + bn_check_top(b); + if (a->neg != b->neg) { if (a->neg) @@ -541,27 +708,25 @@ BIGNUM *b; return(0); } -int BN_set_bit(a, n) -BIGNUM *a; -int n; +int BN_set_bit(BIGNUM *a, int n) { - int i,j; + int i,j,k; i=n/BN_BITS2; j=n%BN_BITS2; if (a->top <= i) { - if (bn_expand(a,n) == NULL) return(0); + if (bn_wexpand(a,i+1) == NULL) return(0); + for(k=a->top; kd[k]=0; a->top=i+1; } - a->d[i]|=(1L<d[i]|=(((BN_ULONG)1)<top <= i) return(0); - a->d[i]&=(~(1L<d[i]&=(~(((BN_ULONG)1)<d[i]&(((BN_ULONG)1)<top=w+1; a->d[w]&= ~(BN_MASK2<= 0) && (a->d[w] == 0)) + } + bn_fix_top(a); + return(1); + } + +int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) + { + int i; + BN_ULONG aa,bb; + + aa=a[n-1]; + bb=b[n-1]; + if (aa != bb) return((aa > bb)?1:-1); + for (i=n-2; i>=0; i--) + { + aa=a[i]; + bb=b[i]; + if (aa != bb) return((aa > bb)?1:-1); + } + return(0); + } + +/* Here follows a specialised variants of bn_cmp_words(). It has the + property of performing the operation on arrays of different sizes. + The sizes of those arrays is expressed through cl, which is the + common length ( basicall, min(len(a),len(b)) ), and dl, which is the + delta between the two lengths, calculated as len(a)-len(b). + All lengths are the number of BN_ULONGs... */ + +int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, + int cl, int dl) + { + int n,i; + n = cl-1; + + if (dl < 0) + { + for (i=dl; i<0; i++) { - a->top--; - w--; + if (b[n-i] != 0) + return -1; /* a < b */ } } - return(1); + if (dl > 0) + { + for (i=dl; i>0; i--) + { + if (a[n+i] != 0) + return 1; /* a > b */ + } + } + return bn_cmp_words(a,b,cl); } -- cgit v1.2.3-55-g6feb