1 /* crypto/bn/bn_lib.c */
2 /* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com)
5 * This package is an SSL implementation written
6 * by Eric Young (eay@cryptsoft.com).
7 * The implementation was written so as to conform with Netscapes SSL.
9 * This library is free for commercial and non-commercial use as long as
10 * the following conditions are aheared to. The following conditions
11 * apply to all code found in this distribution, be it the RC4, RSA,
12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13 * included with this distribution is covered by the same copyright terms
14 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
16 * Copyright remains Eric Young's, and as such any Copyright notices in
17 * the code are not to be removed.
18 * If this package is used in a product, Eric Young should be given attribution
19 * as the author of the parts of the library used.
20 * This can be in the form of a textual message at program startup or
21 * in documentation (online or textual) provided with the package.
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
26 * 1. Redistributions of source code must retain the copyright
27 * notice, this list of conditions and the following disclaimer.
28 * 2. Redistributions in binary form must reproduce the above copyright
29 * notice, this list of conditions and the following disclaimer in the
30 * documentation and/or other materials provided with the distribution.
31 * 3. All advertising materials mentioning features or use of this software
32 * must display the following acknowledgement:
33 * "This product includes cryptographic software written by
34 * Eric Young (eay@cryptsoft.com)"
35 * The word 'cryptographic' can be left out if the rouines from the library
36 * being used are not cryptographic related :-).
37 * 4. If you include any Windows specific code (or a derivative thereof) from
38 * the apps directory (application code) you must include an acknowledgement:
39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
53 * The licence and distribution terms for any publically available version or
54 * derivative of this code cannot be changed. i.e. this code cannot simply be
55 * copied and put under another distribution licence
56 * [including the GNU Public Licence.]
63 char *BN_version="Big Number part of SSLeay 0.8.1b 29-Jun-1998";
65 BIGNUM *BN_value_one()
67 static BN_ULONG data_one=1L;
68 static BIGNUM const_one={&data_one,1,1,0};
82 sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULLONG)*8,
83 (int)sizeof(BN_ULONG)*8);
85 sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULONG)*8,
86 (int)sizeof(BN_ULONG)*8);
92 int BN_num_bits_word(l)
95 static char bits[256]={
96 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
97 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
98 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
99 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
100 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
101 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
102 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
103 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
104 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
105 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
106 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
107 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
108 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
109 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
110 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
111 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
114 #ifdef SIXTY_FOUR_BIT_LONG
115 if (l & 0xffffffff00000000L)
117 if (l & 0xffff000000000000L)
119 if (l & 0xff00000000000000L)
121 return(bits[l>>56]+56);
123 else return(bits[l>>48]+48);
127 if (l & 0x0000ff0000000000L)
129 return(bits[l>>40]+40);
131 else return(bits[l>>32]+32);
136 #ifdef SIXTY_FOUR_BIT
137 if (l & 0xffffffff00000000LL)
139 if (l & 0xffff000000000000LL)
141 if (l & 0xff00000000000000LL)
143 return(bits[l>>56]+56);
145 else return(bits[l>>48]+48);
149 if (l & 0x0000ff0000000000LL)
151 return(bits[l>>40]+40);
153 else return(bits[l>>32]+32);
160 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
164 return(bits[l>>24L]+24);
165 else return(bits[l>>16L]+16);
170 #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
172 return(bits[l>>8]+8);
186 if (a->top == 0) return(0);
188 i=(a->top-1)*BN_BITS2;
192 fprintf(stderr,"BAD TOP VALUE\n");
196 return(i+BN_num_bits_word(l));
199 void BN_clear_free(a)
202 if (a == NULL) return;
205 memset(a->d,0,a->max*sizeof(a->d[0]));
208 memset(a,0,sizeof(BIGNUM));
215 if (a == NULL) return;
216 if (a->d != NULL) Free(a->d);
225 ret=(BIGNUM *)Malloc(sizeof(BIGNUM));
226 if (ret == NULL) goto err;
229 ret->max=(BN_DEFAULT_BITS/BN_BITS2);
230 p=(BN_ULONG *)Malloc(sizeof(BN_ULONG)*(ret->max+1));
231 if (p == NULL) goto err;
234 memset(p,0,(ret->max+1)*sizeof(p[0]));
237 BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE);
247 ret=(BN_CTX *)Malloc(sizeof(BN_CTX));
248 if (ret == NULL) goto err2;
250 for (i=0; i<BN_CTX_NUM; i++)
253 if (n == NULL) goto err;
257 /* There is actually an extra one, this is for debugging my
259 ret->bn[BN_CTX_NUM]=NULL;
268 BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE);
277 for (i=0; i<BN_CTX_NUM; i++)
278 BN_clear_free(c->bn[i]);
282 BIGNUM *bn_expand2(b, bits)
289 while (bits > b->max*BN_BITS2)
291 n=((bits+BN_BITS2-1)/BN_BITS2)*2;
292 p=b->d=(BN_ULONG *)Realloc(b->d,sizeof(BN_ULONG)*(n+1));
295 BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE);
298 memset(&(p[b->max]),0,((n+1)-b->max)*sizeof(BN_ULONG));
310 if (r == NULL) return(NULL);
311 return((BIGNUM *)BN_copy(r,a));
314 BIGNUM *BN_copy(a, b)
318 if (bn_expand(a,b->top*BN_BITS2) == NULL) return(NULL);
319 memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
320 /* memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/
329 memset(a->d,0,a->max*sizeof(a->d[0]));
334 unsigned long BN_get_word(a)
341 if (n > sizeof(unsigned long))
342 #ifdef SIXTY_FOUR_BIT_LONG
347 for (i=a->top-1; i>=0; i--)
349 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
350 ret<<=BN_BITS4; /* stops the compiler complaining */
363 if (bn_expand(a,sizeof(unsigned long)*8) == NULL) return(0);
365 n=sizeof(unsigned long)/BN_BYTES;
368 a->d[0]=(BN_ULONG)w&BN_MASK2;
369 if (a->d[0] != 0) a->top=1;
372 /* the following is done instead of
373 * w>>=BN_BITS2 so compilers don't complain
374 * on builds where sizeof(long) == BN_TYPES */
375 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
379 a->d[i]=(BN_ULONG)w&BN_MASK2;
380 if (a->d[i] != 0) a->top=i+1;
385 /* ignore negative */
386 BIGNUM *BN_bin2bn(s, len, ret)
395 if (ret == NULL) ret=BN_new();
396 if (ret == NULL) return(NULL);
404 if (bn_expand(ret,(int)(n+2)*8) == NULL)
406 i=((n-1)/BN_BYTES)+1;
407 m=((n-1)%(BN_BYTES));
419 /* need to call this due to clear byte at top if avoiding
420 * having the top bit set (-ve number) */
425 /* ignore negative */
437 *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
447 BN_ULONG t1,t2,*ap,*bp;
450 if (i != 0) return(i);
453 for (i=a->top-1; i>=0; i--)
458 return(t1 > t2?1:-1);
471 if ((a == NULL) || (b == NULL))
480 if (a->neg != b->neg)
488 else { gt= -1; lt=1; }
490 if (a->top > b->top) return(gt);
491 if (a->top < b->top) return(lt);
492 for (i=a->top-1; i>=0; i--)
496 if (t1 > t2) return(gt);
497 if (t1 < t2) return(lt);
510 if (a->top <= i) return(0);
516 int BN_clear_bit(a, n)
524 if (a->top <= i) return(0);
530 int BN_is_bit_set(a, n)
536 if (n < 0) return(0);
539 if (a->top <= i) return(0);
540 return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
543 int BN_mask_bits(a,n)
551 if (w >= a->top) return(0);
557 a->d[w]&= ~(BN_MASK2<<b);
558 while ((w >= 0) && (a->d[w] == 0))