cryptlib  3.4.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Macros
bn_lib.c
Go to the documentation of this file.
1 /* crypto/bn/bn_lib.c */
2 /* Copyright (C) 1995-1998 Eric Young ([email protected])
3  * All rights reserved.
4  *
5  * This package is an SSL implementation written
6  * by Eric Young ([email protected]).
7  * The implementation was written so as to conform with Netscapes SSL.
8  *
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 ([email protected]).
15  *
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.
22  *
23  * Redistribution and use in source and binary forms, with or without
24  * modification, are permitted provided that the following conditions
25  * are met:
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 ([email protected])"
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 ([email protected])"
40  *
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
51  * SUCH DAMAGE.
52  *
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.]
57  */
58 
59 /* Removed ndebug definition - pcg */
60 /* Added proper initialisation of data in all BN_X_init() functions - pcg */
61 
62 #if defined( _WIN32_WCE ) && _WIN32_WCE < 400
63  #define assert( x )
64 #else
65  #include <assert.h>
66 #endif /* Systems without assert() */
67 #include <limits.h>
68 #include <stdio.h>
69 #if defined( INC_ALL )
70  #include "bn_lcl.h"
71 #else
72  #include "bn/bn_lcl.h"
73 #endif /* Compiler-specific includes */
74 
75 #ifdef USE_BN_DEBUG_MALLOC /* Added special BN debug-malloc - pcg */
76 
77 void *clBnAllocFn( const char *fileName, const char *fnName,
78  const int lineNo, size_t size )
79  {
80  printf( "BNDEBUG: %s:%s:%d %d bytes.\n", fileName, fnName, lineNo, size );
81  return( malloc( size ) );
82  }
83 #endif /* USE_BN_DEBUG_MALLOC */
84 
85 /* const char *BN_version="Big Number" OPENSSL_VERSION_PTEXT; - pcg */
86 
87 /* This stuff appears to be completely unused, so is deprecated */
88 #ifndef OPENSSL_NO_DEPRECATED
89 /* For a 32 bit machine
90  * 2 - 4 == 128
91  * 3 - 8 == 256
92  * 4 - 16 == 512
93  * 5 - 32 == 1024
94  * 6 - 64 == 2048
95  * 7 - 128 == 4096
96  * 8 - 256 == 8192
97  */
98 static int bn_limit_bits=0;
99 static int bn_limit_num=8; /* (1<<bn_limit_bits) */
100 static int bn_limit_bits_low=0;
101 static int bn_limit_num_low=8; /* (1<<bn_limit_bits_low) */
102 static int bn_limit_bits_high=0;
103 static int bn_limit_num_high=8; /* (1<<bn_limit_bits_high) */
104 static int bn_limit_bits_mont=0;
105 static int bn_limit_num_mont=8; /* (1<<bn_limit_bits_mont) */
106 
107 void BN_set_params(int mult, int high, int low, int mont)
108  {
109  if (mult >= 0)
110  {
111  if (mult > (int)(sizeof(int)*8)-1)
112  mult=sizeof(int)*8-1;
113  bn_limit_bits=mult;
114  bn_limit_num=1<<mult;
115  }
116  if (high >= 0)
117  {
118  if (high > (int)(sizeof(int)*8)-1)
119  high=sizeof(int)*8-1;
120  bn_limit_bits_high=high;
121  bn_limit_num_high=1<<high;
122  }
123  if (low >= 0)
124  {
125  if (low > (int)(sizeof(int)*8)-1)
126  low=sizeof(int)*8-1;
127  bn_limit_bits_low=low;
128  bn_limit_num_low=1<<low;
129  }
130  if (mont >= 0)
131  {
132  if (mont > (int)(sizeof(int)*8)-1)
133  mont=sizeof(int)*8-1;
134  bn_limit_bits_mont=mont;
135  bn_limit_num_mont=1<<mont;
136  }
137  }
138 
139 int BN_get_params(int which)
140  {
141  if (which == 0) return(bn_limit_bits);
142  else if (which == 1) return(bn_limit_bits_high);
143  else if (which == 2) return(bn_limit_bits_low);
144  else if (which == 3) return(bn_limit_bits_mont);
145  else return(0);
146  }
147 #endif
148 
149 const BIGNUM *BN_value_one(void)
150  {
151  static BN_ULONG data_one=1L;
152  static BIGNUM const_one={&data_one,1,1,0,BN_FLG_STATIC_DATA};
153 
154  return(&const_one);
155  }
156 
157 char *BN_options(void)
158  {
159  static int init=0;
160  static char data[16];
161 
162  if (!init)
163  {
164  init++;
165 #if 0 /* Removed - pcg */
166 #ifdef BN_LLONG
167  BIO_snprintf(data,sizeof data,"bn(%d,%d)",
168  (int)sizeof(BN_ULLONG)*8,(int)sizeof(BN_ULONG)*8);
169 #else
170  BIO_snprintf(data,sizeof data,"bn(%d,%d)",
171  (int)sizeof(BN_ULONG)*8,(int)sizeof(BN_ULONG)*8);
172 #endif
173 #endif /* 0 */
174  }
175  return(data);
176  }
177 
178 int BN_num_bits_word(BN_ULONG l)
179  {
180  static const char bits[256]={
181  0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
182  5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
183  6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
184  6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
185  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
186  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
187  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
188  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
189  8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
190  8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
191  8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
192  8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
193  8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
194  8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
195  8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
196  8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
197  };
198 
199 #if defined(SIXTY_FOUR_BIT_LONG)
200  if (l & 0xffffffff00000000L)
201  {
202  if (l & 0xffff000000000000L)
203  {
204  if (l & 0xff00000000000000L)
205  {
206  return(bits[(int)(l>>56)]+56);
207  }
208  else return(bits[(int)(l>>48)]+48);
209  }
210  else
211  {
212  if (l & 0x0000ff0000000000L)
213  {
214  return(bits[(int)(l>>40)]+40);
215  }
216  else return(bits[(int)(l>>32)]+32);
217  }
218  }
219  else
220 #else
221 #ifdef SIXTY_FOUR_BIT
222  if (l & 0xffffffff00000000LL)
223  {
224  if (l & 0xffff000000000000LL)
225  {
226  if (l & 0xff00000000000000LL)
227  {
228  return(bits[(int)(l>>56)]+56);
229  }
230  else return(bits[(int)(l>>48)]+48);
231  }
232  else
233  {
234  if (l & 0x0000ff0000000000LL)
235  {
236  return(bits[(int)(l>>40)]+40);
237  }
238  else return(bits[(int)(l>>32)]+32);
239  }
240  }
241  else
242 #endif
243 #endif
244  {
245 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
246  if (l & 0xffff0000L)
247  {
248  if (l & 0xff000000L)
249  return(bits[(int)(l>>24L)]+24);
250  else return(bits[(int)(l>>16L)]+16);
251  }
252  else
253 #endif
254  {
255 #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
256  if (l & 0xff00L)
257  return(bits[(int)(l>>8)]+8);
258  else
259 #endif
260  return(bits[(int)(l )] );
261  }
262  }
263  }
264 
265 int BN_num_bits(const BIGNUM *a)
266  {
267  int i = a->top - 1;
268  bn_check_top(a);
269 
270  if (BN_is_zero(a)) return 0;
271  return ((i*BN_BITS2) + BN_num_bits_word(a->d[i]));
272  }
273 
274 void BN_clear_free(BIGNUM *a)
275  {
276  int i;
277 
278  if (a == NULL) return;
279  bn_check_top(a);
280  if (a->d != NULL)
281  {
282  OPENSSL_cleanse(a->d,a->dmax*sizeof(a->d[0]));
283  if (!(BN_get_flags(a,BN_FLG_STATIC_DATA)))
284  OPENSSL_free(a->d);
285  }
286  i=BN_get_flags(a,BN_FLG_MALLOCED);
287  OPENSSL_cleanse(a,sizeof(BIGNUM));
288  if (i)
289  OPENSSL_free(a);
290  }
291 
292 void BN_free(BIGNUM *a)
293  {
294  if (a == NULL) return;
295  bn_check_top(a);
296  if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA)))
297  OPENSSL_free(a->d);
298  if (a->flags & BN_FLG_MALLOCED)
299  OPENSSL_free(a);
300  else
301  {
302 #ifndef OPENSSL_NO_DEPRECATED
303  a->flags|=BN_FLG_FREE;
304 #endif
305  a->d = NULL;
306  }
307  }
308 
309 void BN_init(BIGNUM *a)
310  {
311  memset(a,0,sizeof(BIGNUM));
312  bn_check_top(a);
313  }
314 
315 BIGNUM *BN_new(void)
316  {
317  BIGNUM *ret;
318 
319  if ((ret=(BIGNUM *)clBnAlloc("BN_new",sizeof(BIGNUM))) == NULL)
320  {
321  BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE);
322  return(NULL);
323  }
324  memset( ret, 0, sizeof( BIGNUM ) ); /* pcg */
325  ret->flags=BN_FLG_MALLOCED;
326  ret->top=0;
327  ret->neg=0;
328  ret->dmax=0;
329  ret->d=NULL;
330  bn_check_top(ret);
331  return(ret);
332  }
333 
334 /* This is used both by bn_expand2() and bn_dup_expand() */
335 /* The caller MUST check that words > b->dmax before calling this */
336 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
337  {
338  BN_ULONG *A,*a = NULL;
339  const BN_ULONG *B;
340  int i;
341 
342  bn_check_top(b);
343 
344  if (words > (INT_MAX/(4*BN_BITS2)))
345  {
346  BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_BIGNUM_TOO_LONG);
347  return NULL;
348  }
349  if (BN_get_flags(b,BN_FLG_STATIC_DATA))
350  {
351  BNerr(BN_F_BN_EXPAND_INTERNAL,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
352  return(NULL);
353  }
354  a=A=(BN_ULONG *)clBnAlloc("bn_expand_internal",sizeof(BN_ULONG)*words);
355  if (A == NULL)
356  {
357  BNerr(BN_F_BN_EXPAND_INTERNAL,ERR_R_MALLOC_FAILURE);
358  return(NULL);
359  }
360 #if 1
361  B=b->d;
362  /* Check if the previous number needs to be copied */
363  if (B != NULL)
364  {
365  for (i=b->top>>2; i>0; i--,A+=4,B+=4)
366  {
367  /*
368  * The fact that the loop is unrolled
369  * 4-wise is a tribute to Intel. It's
370  * the one that doesn't have enough
371  * registers to accomodate more data.
372  * I'd unroll it 8-wise otherwise:-)
373  *
374  * <[email protected]>
375  */
376  BN_ULONG a0,a1,a2,a3;
377  a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
378  A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
379  }
380  switch (b->top&3)
381  {
382  case 3: A[2]=B[2];
383  case 2: A[1]=B[1];
384  case 1: A[0]=B[0];
385  case 0: /* workaround for ultrix cc: without 'case 0', the optimizer does
386  * the switch table by doing a=top&3; a--; goto jump_table[a];
387  * which fails for top== 0 */
388  ;
389  }
390  }
391 
392 #else
393  memset(A,0,sizeof(BN_ULONG)*words);
394  memcpy(A,b->d,sizeof(b->d[0])*b->top);
395 #endif
396 
397  return(a);
398  }
399 
400 /* This is an internal function that can be used instead of bn_expand2()
401  * when there is a need to copy BIGNUMs instead of only expanding the
402  * data part, while still expanding them.
403  * Especially useful when needing to expand BIGNUMs that are declared
404  * 'const' and should therefore not be changed.
405  * The reason to use this instead of a BN_dup() followed by a bn_expand2()
406  * is memory allocation overhead. A BN_dup() followed by a bn_expand2()
407  * will allocate new memory for the BIGNUM data twice, and free it once,
408  * while bn_dup_expand() makes sure allocation is made only once.
409  */
410 
411 #ifndef OPENSSL_NO_DEPRECATED
412 BIGNUM *bn_dup_expand(const BIGNUM *b, int words)
413  {
414  BIGNUM *r = NULL;
415 
416  bn_check_top(b);
417 
418  /* This function does not work if
419  * words <= b->dmax && top < words
420  * because BN_dup() does not preserve 'dmax'!
421  * (But bn_dup_expand() is not used anywhere yet.)
422  */
423 
424  if (words > b->dmax)
425  {
426  BN_ULONG *a = bn_expand_internal(b, words);
427 
428  if (a)
429  {
430  r = BN_new();
431  if (r)
432  {
433  r->top = b->top;
434  r->dmax = words;
435  r->neg = b->neg;
436  r->d = a;
437  }
438  else
439  {
440  /* r == NULL, BN_new failure */
441  OPENSSL_free(a);
442  }
443  }
444  /* If a == NULL, there was an error in allocation in
445  bn_expand_internal(), and NULL should be returned */
446  }
447  else
448  {
449  r = BN_dup(b);
450  }
451 
452  bn_check_top(r);
453  return r;
454  }
455 #endif
456 
457 /* This is an internal function that should not be used in applications.
458  * It ensures that 'b' has enough room for a 'words' word number
459  * and initialises any unused part of b->d with leading zeros.
460  * It is mostly used by the various BIGNUM routines. If there is an error,
461  * NULL is returned. If not, 'b' is returned. */
462 
463 BIGNUM *bn_expand2(BIGNUM *b, int words)
464  {
465  bn_check_top(b);
466 
467  if (words > b->dmax)
468  {
469  BN_ULONG *a = bn_expand_internal(b, words);
470  if(!a) return NULL;
471  if(b->d) OPENSSL_free(b->d);
472  b->d=a;
473  b->dmax=words;
474  }
475 
476 /* None of this should be necessary because of what b->top means! */
477 #if 0
478  /* NB: bn_wexpand() calls this only if the BIGNUM really has to grow */
479  if (b->top < b->dmax)
480  {
481  int i;
482  BN_ULONG *A = &(b->d[b->top]);
483  for (i=(b->dmax - b->top)>>3; i>0; i--,A+=8)
484  {
485  A[0]=0; A[1]=0; A[2]=0; A[3]=0;
486  A[4]=0; A[5]=0; A[6]=0; A[7]=0;
487  }
488  for (i=(b->dmax - b->top)&7; i>0; i--,A++)
489  A[0]=0;
490  assert(A == &(b->d[b->dmax]));
491  }
492 #endif
493  bn_check_top(b);
494  return b;
495  }
496 
497 BIGNUM *BN_dup(const BIGNUM *a)
498  {
499  BIGNUM *t;
500 
501  if (a == NULL) return NULL;
502  bn_check_top(a);
503 
504  t = BN_new();
505  if (t == NULL) return NULL;
506  if(!BN_copy(t, a))
507  {
508  BN_free(t);
509  return NULL;
510  }
511  bn_check_top(t);
512  return t;
513  }
514 
515 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
516  {
517  int i;
518  BN_ULONG *A;
519  const BN_ULONG *B;
520 
521  bn_check_top(b);
522 
523  if (a == b) return(a);
524  if (bn_wexpand(a,b->top) == NULL) return(NULL);
525 
526 #if 1
527  A=a->d;
528  B=b->d;
529  for (i=b->top>>2; i>0; i--,A+=4,B+=4)
530  {
531  BN_ULONG a0,a1,a2,a3;
532  a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3];
533  A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3;
534  }
535  switch (b->top&3)
536  {
537  case 3: A[2]=B[2];
538  case 2: A[1]=B[1];
539  case 1: A[0]=B[0];
540  case 0: ; /* ultrix cc workaround, see comments in bn_expand_internal */
541  }
542 #else
543  memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
544 #endif
545 
546  a->top=b->top;
547  a->neg=b->neg;
548  bn_check_top(a);
549  return(a);
550  }
551 
552 void BN_swap(BIGNUM *a, BIGNUM *b)
553  {
554  int flags_old_a, flags_old_b;
555  BN_ULONG *tmp_d;
556  int tmp_top, tmp_dmax, tmp_neg;
557 
558  bn_check_top(a);
559  bn_check_top(b);
560 
561  flags_old_a = a->flags;
562  flags_old_b = b->flags;
563 
564  tmp_d = a->d;
565  tmp_top = a->top;
566  tmp_dmax = a->dmax;
567  tmp_neg = a->neg;
568 
569  a->d = b->d;
570  a->top = b->top;
571  a->dmax = b->dmax;
572  a->neg = b->neg;
573 
574  b->d = tmp_d;
575  b->top = tmp_top;
576  b->dmax = tmp_dmax;
577  b->neg = tmp_neg;
578 
579  a->flags = (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
580  b->flags = (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
581  bn_check_top(a);
582  bn_check_top(b);
583  }
584 
585 void BN_clear(BIGNUM *a)
586  {
587  bn_check_top(a);
588  if (a->d != NULL)
589  memset(a->d,0,a->dmax*sizeof(a->d[0]));
590  a->top=0;
591  a->neg=0;
592  }
593 
594 BN_ULONG BN_get_word(const BIGNUM *a)
595  {
596  if (a->top > 1)
597  return BN_MASK2;
598  else if (a->top == 1)
599  return a->d[0];
600  /* a->top == 0 */
601  return 0;
602  }
603 
604 int BN_set_word(BIGNUM *a, BN_ULONG w)
605  {
606  bn_check_top(a);
607  if (bn_expand(a,(int)sizeof(BN_ULONG)*8) == NULL) return(0);
608  a->neg = 0;
609  a->d[0] = w;
610  a->top = (w ? 1 : 0);
611  bn_check_top(a);
612  return(1);
613  }
614 
615 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
616  {
617  unsigned int i,m;
618  unsigned int n;
619  BN_ULONG l;
620  BIGNUM *bn = NULL;
621 
622  if (ret == NULL)
623  ret = bn = BN_new();
624  if (ret == NULL) return(NULL);
625  bn_check_top(ret);
626  l=0;
627  n=len;
628  if (n == 0)
629  {
630  ret->top=0;
631  return(ret);
632  }
633  i=((n-1)/BN_BYTES)+1;
634  m=((n-1)%(BN_BYTES));
635  if (bn_wexpand(ret, (int)i) == NULL)
636  {
637  if (bn) BN_free(bn);
638  return NULL;
639  }
640  ret->top=i;
641  ret->neg=0;
642  while (n--)
643  {
644  l=(l<<8L)| *(s++);
645  if (m-- == 0)
646  {
647  ret->d[--i]=l;
648  l=0;
649  m=BN_BYTES-1;
650  }
651  }
652  /* need to call this due to clear byte at top if avoiding
653  * having the top bit set (-ve number) */
654  bn_correct_top(ret);
655  return(ret);
656  }
657 
658 /* ignore negative */
659 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
660  {
661  int n,i;
662  BN_ULONG l;
663 
664  bn_check_top(a);
665  n=i=BN_num_bytes(a);
666  while (i--)
667  {
668  l=a->d[i/BN_BYTES];
669  *(to++)=(unsigned char)((l>>(8*(i%BN_BYTES)))&0xff);
670  }
671  return(n);
672  }
673 
674 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
675  {
676  int i;
677  BN_ULONG t1,t2,*ap,*bp;
678 
679  bn_check_top(a);
680  bn_check_top(b);
681 
682  i=a->top-b->top;
683  if (i != 0) return(i);
684  ap=a->d;
685  bp=b->d;
686  for (i=a->top-1; i>=0; i--)
687  {
688  t1= ap[i];
689  t2= bp[i];
690  if (t1 != t2)
691  return((t1 > t2) ? 1 : -1);
692  }
693  return(0);
694  }
695 
696 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
697  {
698  int i;
699  int gt,lt;
700  BN_ULONG t1,t2;
701 
702  if ((a == NULL) || (b == NULL))
703  {
704  if (a != NULL)
705  return(-1);
706  else if (b != NULL)
707  return(1);
708  else
709  return(0);
710  }
711 
712  bn_check_top(a);
713  bn_check_top(b);
714 
715  if (a->neg != b->neg)
716  {
717  if (a->neg)
718  return(-1);
719  else return(1);
720  }
721  if (a->neg == 0)
722  { gt=1; lt= -1; }
723  else { gt= -1; lt=1; }
724 
725  if (a->top > b->top) return(gt);
726  if (a->top < b->top) return(lt);
727  for (i=a->top-1; i>=0; i--)
728  {
729  t1=a->d[i];
730  t2=b->d[i];
731  if (t1 > t2) return(gt);
732  if (t1 < t2) return(lt);
733  }
734  return(0);
735  }
736 
737 int BN_set_bit(BIGNUM *a, int n)
738  {
739  int i,j,k;
740 
741  if (n < 0)
742  return 0;
743 
744  i=n/BN_BITS2;
745  j=n%BN_BITS2;
746  if (a->top <= i)
747  {
748  if (bn_wexpand(a,i+1) == NULL) return(0);
749  for(k=a->top; k<i+1; k++)
750  a->d[k]=0;
751  a->top=i+1;
752  }
753 
754  a->d[i]|=(((BN_ULONG)1)<<j);
755  bn_check_top(a);
756  return(1);
757  }
758 
759 int BN_clear_bit(BIGNUM *a, int n)
760  {
761  int i,j;
762 
763  bn_check_top(a);
764  if (n < 0) return 0;
765 
766  i=n/BN_BITS2;
767  j=n%BN_BITS2;
768  if (a->top <= i) return(0);
769 
770  a->d[i]&=(~(((BN_ULONG)1)<<j));
771  bn_correct_top(a);
772  return(1);
773  }
774 
775 int BN_is_bit_set(const BIGNUM *a, int n)
776  {
777  int i,j;
778 
779  bn_check_top(a);
780  if (n < 0) return 0;
781  i=n/BN_BITS2;
782  j=n%BN_BITS2;
783  if (a->top <= i) return 0;
784  return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
785  }
786 
787 int BN_mask_bits(BIGNUM *a, int n)
788  {
789  int b,w;
790 
791  bn_check_top(a);
792  if (n < 0) return 0;
793 
794  w=n/BN_BITS2;
795  b=n%BN_BITS2;
796  if (w >= a->top) return 0;
797  if (b == 0)
798  a->top=w;
799  else
800  {
801  a->top=w+1;
802  a->d[w]&= ~(BN_MASK2<<b);
803  }
804  bn_correct_top(a);
805  return(1);
806  }
807 
808 void BN_set_negative(BIGNUM *a, int b)
809  {
810  if (b && !BN_is_zero(a))
811  a->neg = 1;
812  else
813  a->neg = 0;
814  }
815 
816 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
817  {
818  int i;
819  BN_ULONG aa,bb;
820 
821  aa=a[n-1];
822  bb=b[n-1];
823  if (aa != bb) return((aa > bb)?1:-1);
824  for (i=n-2; i>=0; i--)
825  {
826  aa=a[i];
827  bb=b[i];
828  if (aa != bb) return((aa > bb)?1:-1);
829  }
830  return(0);
831  }
832 
833 /* Here follows a specialised variants of bn_cmp_words(). It has the
834  property of performing the operation on arrays of different sizes.
835  The sizes of those arrays is expressed through cl, which is the
836  common length ( basicall, min(len(a),len(b)) ), and dl, which is the
837  delta between the two lengths, calculated as len(a)-len(b).
838  All lengths are the number of BN_ULONGs... */
839 
840 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b,
841  int cl, int dl)
842  {
843  int n,i;
844  n = cl-1;
845 
846  if (dl < 0)
847  {
848  for (i=dl; i<0; i++)
849  {
850  if (b[n-i] != 0)
851  return -1; /* a < b */
852  }
853  }
854  if (dl > 0)
855  {
856  for (i=dl; i>0; i--)
857  {
858  if (a[n+i] != 0)
859  return 1; /* a > b */
860  }
861  }
862  return bn_cmp_words(a,b,cl);
863  }
864 
865 int BN_high_bit(BIGNUM *a) /* pcg */
866  {
867  int i;
868  BN_ULONG l;
869 
870  i=BN_num_bytes(a);
871  if(!i) return(0);
872  i--;
873  l=a->d[i/BN_BYTES];
874  return((l>>(8*(i%BN_BYTES)))&0x80?1:0);
875  }
876 
877 void BN_checksum(BIGNUM *a, BN_ULONG *chk) /* pcg */
878  {
879  int i;
880  BN_ULONG sum1 = 0, sum2 = *chk;
881 
882  for (i=a->top-1; i>=0; i--)
883  {
884  sum1 += a->d[i];
885  sum2 += sum1;
886  }
887  *chk = sum2;
888  }
Generated on Thu Jan 10 2013 10:00:43 for cryptlib by   doxygen 1.8.2