crypto/bn/bn_lib.c

   1 /* crypto/bn/bn_lib.c */
   2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   3  * All rights reserved.
   4  *
   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.
   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 (tjh@cryptsoft.com).
  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 (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)"
  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 #include <stdio.h>
  60 #include "cryptlib.h"
  61 #include "bn_lcl.h"
  62
  63 char *BN_version="Big Number part of OpenSSL 0.9.2 31-Dec-1998";
  64
  65 /* For a 32 bit machine
  66  * 2 -   4 ==  128
  67  * 3 -   8 ==  256
  68  * 4 -  16 ==  512
  69  * 5 -  32 == 1024
  70  * 6 -  64 == 2048
  71  * 7 - 128 == 4096
  72  * 8 - 256 == 8192
  73  */
  74 int bn_limit_bits=0;
  75 int bn_limit_num=8;        /* (1<<bn_limit_bits) */
  76 int bn_limit_bits_low=0;
  77 int bn_limit_num_low=8;    /* (1<<bn_limit_bits_low) */
  78 int bn_limit_bits_high=0;
  79 int bn_limit_num_high=8;   /* (1<<bn_limit_bits_high) */
  80 int bn_limit_bits_mont=0;
  81 int bn_limit_num_mont=8;   /* (1<<bn_limit_bits_mont) */
  82
  83 void BN_set_params(mult,high,low,mont)
  84 int mult,high,low,mont;
  85         {
  86         if (mult >= 0)
  87                 {
  88                 if (mult > (sizeof(int)*8)-1)
  89                         mult=sizeof(int)*8-1;
  90                 bn_limit_bits=mult;
  91                 bn_limit_num=1<<mult;
  92                 }
  93         if (high >= 0)
  94                 {
  95                 if (high > (sizeof(int)*8)-1)
  96                         high=sizeof(int)*8-1;
  97                 bn_limit_bits_high=high;
  98                 bn_limit_num_high=1<<high;
  99                 }
 100         if (low >= 0)
 101                 {
 102                 if (low > (sizeof(int)*8)-1)
 103                         low=sizeof(int)*8-1;
 104                 bn_limit_bits_low=low;
 105                 bn_limit_num_low=1<<low;
 106                 }
 107         if (mont >= 0)
 108                 {
 109                 if (mont > (sizeof(int)*8)-1)
 110                         mont=sizeof(int)*8-1;
 111                 bn_limit_bits_mont=mont;
 112                 bn_limit_num_mont=1<<mont;
 113                 }
 114         }
 115
 116 int BN_get_params(which)
 117 int which;
 118         {
 119         if      (which == 0) return(bn_limit_bits);
 120         else if (which == 1) return(bn_limit_bits_high);
 121         else if (which == 2) return(bn_limit_bits_low);
 122         else if (which == 3) return(bn_limit_bits_mont);
 123         else return(0);
 124         }
 125
 126 BIGNUM *BN_value_one()
 127         {
 128         static BN_ULONG data_one=1L;
 129         static BIGNUM const_one={&data_one,1,1,0};
 130
 131         return(&const_one);
 132         }
 133
 134 char *BN_options()
 135         {
 136         static int init=0;
 137         static char data[16];
 138
 139         if (!init)
 140                 {
 141                 init++;
 142 #ifdef BN_LLONG
 143                 sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULLONG)*8,
 144                         (int)sizeof(BN_ULONG)*8);
 145 #else
 146                 sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULONG)*8,
 147                         (int)sizeof(BN_ULONG)*8);
 148 #endif
 149                 }
 150         return(data);
 151         }
 152
 153 int BN_num_bits_word(l)
 154 BN_ULONG l;
 155         {
 156         static char bits[256]={
 157                 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
 158                 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
 159                 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
 160                 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
 161                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 162                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 163                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 164                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 165                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 166                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 167                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 168                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 169                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 170                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 171                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 172                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 173                 };
 174
 175 #if defined(SIXTY_FOUR_BIT_LONG)
 176         if (l & 0xffffffff00000000L)
 177                 {
 178                 if (l & 0xffff000000000000L)
 179                         {
 180                         if (l & 0xff00000000000000L)
 181                                 {
 182                                 return(bits[(int)(l>>56)]+56);
 183                                 }
 184                         else    return(bits[(int)(l>>48)]+48);
 185                         }
 186                 else
 187                         {
 188                         if (l & 0x0000ff0000000000L)
 189                                 {
 190                                 return(bits[(int)(l>>40)]+40);
 191                                 }
 192                         else    return(bits[(int)(l>>32)]+32);
 193                         }
 194                 }
 195         else
 196 #else
 197 #ifdef SIXTY_FOUR_BIT
 198         if (l & 0xffffffff00000000LL)
 199                 {
 200                 if (l & 0xffff000000000000LL)
 201                         {
 202                         if (l & 0xff00000000000000LL)
 203                                 {
 204                                 return(bits[(int)(l>>56)]+56);
 205                                 }
 206                         else    return(bits[(int)(l>>48)]+48);
 207                         }
 208                 else
 209                         {
 210                         if (l & 0x0000ff0000000000LL)
 211                                 {
 212                                 return(bits[(int)(l>>40)]+40);
 213                                 }
 214                         else    return(bits[(int)(l>>32)]+32);
 215                         }
 216                 }
 217         else
 218 #endif
 219 #endif
 220                 {
 221 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 222                 if (l & 0xffff0000L)
 223                         {
 224                         if (l & 0xff000000L)
 225                                 return(bits[(int)(l>>24L)]+24);
 226                         else    return(bits[(int)(l>>16L)]+16);
 227                         }
 228                 else
 229 #endif
 230                         {
 231 #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 232                         if (l & 0xff00L)
 233                                 return(bits[(int)(l>>8)]+8);
 234                         else
 235 #endif
 236                                 return(bits[(int)(l   )]  );
 237                         }
 238                 }
 239         }
 240
 241 int BN_num_bits(a)
 242 BIGNUM *a;
 243         {
 244         BN_ULONG l;
 245         int i;
 246
 247         bn_check_top(a);
 248
 249         if (a->top == 0) return(0);
 250         l=a->d[a->top-1];
 251         i=(a->top-1)*BN_BITS2;
 252         if (l == 0)
 253                 {
 254 #if !defined(NO_STDIO) && !defined(WIN16)
 255                 fprintf(stderr,"BAD TOP VALUE\n");
 256 #endif
 257                 abort();
 258                 }
 259         return(i+BN_num_bits_word(l));
 260         }
 261
 262 void BN_clear_free(a)
 263 BIGNUM *a;
 264         {
 265         int i;
 266
 267         if (a == NULL) return;
 268         if (a->d != NULL)
 269                 {
 270                 memset(a->d,0,a->max*sizeof(a->d[0]));
 271                 if (!(BN_get_flags(a,BN_FLG_STATIC_DATA)))
 272                         Free(a->d);
 273                 }
 274         i=BN_get_flags(a,BN_FLG_MALLOCED);
 275         memset(a,0,sizeof(BIGNUM));
 276         if (i)
 277                 Free(a);
 278         }
 279
 280 void BN_free(a)
 281 BIGNUM *a;
 282         {
 283         if (a == NULL) return;
 284         if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA)))
 285                 Free(a->d);
 286         a->flags|=BN_FLG_FREE; /* REMOVE? */
 287         if (a->flags & BN_FLG_MALLOCED)
 288                 Free(a);
 289         }
 290
 291 void BN_init(a)
 292 BIGNUM *a;
 293         {
 294         memset(a,0,sizeof(BIGNUM));
 295         }
 296
 297 BIGNUM *BN_new()
 298         {
 299         BIGNUM *ret;
 300
 301         if ((ret=(BIGNUM *)Malloc(sizeof(BIGNUM))) == NULL)
 302                 {
 303                 BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE);
 304                 return(NULL);
 305                 }
 306         ret->flags=BN_FLG_MALLOCED;
 307         ret->top=0;
 308         ret->neg=0;
 309         ret->max=0;
 310         ret->d=NULL;
 311         return(ret);
 312         }
 313
 314
 315 BN_CTX *BN_CTX_new()
 316         {
 317         BN_CTX *ret;
 318
 319         ret=(BN_CTX *)Malloc(sizeof(BN_CTX));
 320         if (ret == NULL)
 321                 {
 322                 BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE);
 323                 return(NULL);
 324                 }
 325
 326         BN_CTX_init(ret);
 327         ret->flags=BN_FLG_MALLOCED;
 328         return(ret);
 329         }
 330
 331 void BN_CTX_init(ctx)
 332 BN_CTX *ctx;
 333         {
 334         memset(ctx,0,sizeof(BN_CTX));
 335         ctx->tos=0;
 336         ctx->flags=0;
 337         }
 338
 339 void BN_CTX_free(c)
 340 BN_CTX *c;
 341         {
 342         int i;
 343
 344         if(c == NULL)
 345             return;
 346
 347         for (i=0; i<BN_CTX_NUM; i++)
 348                 BN_clear_free(&(c->bn[i]));
 349         if (c->flags & BN_FLG_MALLOCED)
 350                 Free(c);
 351         }
 352
 353 BIGNUM *bn_expand2(b, words)
 354 BIGNUM *b;
 355 int words;
 356         {
 357         BN_ULONG *A,*B,*a;
 358         int i,j;
 359
 360         bn_check_top(b);
 361
 362         if (words > b->max)
 363                 {
 364                 bn_check_top(b);
 365                 if (BN_get_flags(b,BN_FLG_STATIC_DATA))
 366                         {
 367                         BNerr(BN_F_BN_EXPAND2,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
 368                         return(NULL);
 369                         }
 370                 a=A=(BN_ULONG *)Malloc(sizeof(BN_ULONG)*(words+1));
 371                 if (A == NULL)
 372                         {
 373                         BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE);
 374                         return(NULL);
 375                         }
 376 memset(A,0x5c,sizeof(BN_ULONG)*(words+1));
 377 #if 1
 378                 B=b->d;
 379                 if (B != NULL)
 380                         {
 381                         for (i=b->top&(~7); i>0; i-=8)
 382                                 {
 383                                 A[0]=B[0]; A[1]=B[1]; A[2]=B[2]; A[3]=B[3];
 384                                 A[4]=B[4]; A[5]=B[5]; A[6]=B[6]; A[7]=B[7];
 385                                 A+=8;
 386                                 B+=8;
 387                                 }
 388                         switch (b->top&7)
 389                                 {
 390                         case 7:
 391                                 A[6]=B[6];
 392                         case 6:
 393                                 A[5]=B[5];
 394                         case 5:
 395                                 A[4]=B[4];
 396                         case 4:
 397                                 A[3]=B[3];
 398                         case 3:
 399                                 A[2]=B[2];
 400                         case 2:
 401                                 A[1]=B[1];
 402                         case 1:
 403                                 A[0]=B[0];
 404                         case 0:
 405                                 /* I need the 'case 0' entry for utrix cc.
 406                                  * If the optimiser is turned on, it does the
 407                                  * switch table by doing
 408                                  * a=top&7
 409                                  * a--;
 410                                  * goto jump_table[a];
 411                                  * If top is 0, this makes us jump to 0xffffffc
 412                                  * which is rather bad :-(.
 413                                  * eric 23-Apr-1998
 414                                  */
 415                                 ;
 416                                 }
 417                         B= &(b->d[b->top]);
 418                         j=b->max-8;
 419                         for (i=b->top; i<j; i+=8)
 420                                 {
 421                                 B[0]=0; B[1]=0; B[2]=0; B[3]=0;
 422                                 B[4]=0; B[5]=0; B[6]=0; B[7]=0;
 423                                 B+=8;
 424                                 }
 425                         for (j+=8; i<j; i++)
 426                                 {
 427                                 B[0]=0;
 428                                 B++;
 429                                 }
 430 #else
 431                         memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
 432 #endif
 433
 434 /*              memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); */
 435 /*      { int i; for (i=b->max; i<words+1; i++) p[i]=i;} */
 436                         Free(b->d);
 437                         }
 438
 439                 b->d=a;
 440                 b->max=words;
 441                 }
 442         return(b);
 443         }
 444
 445 BIGNUM *BN_dup(a)
 446 BIGNUM *a;
 447         {
 448         BIGNUM *r;
 449
 450         bn_check_top(a);
 451
 452         r=BN_new();
 453         if (r == NULL) return(NULL);
 454         return((BIGNUM *)BN_copy(r,a));
 455         }
 456
 457 BIGNUM *BN_copy(a, b)
 458 BIGNUM *a;
 459 BIGNUM *b;
 460         {
 461         int i;
 462         BN_ULONG *A,*B;
 463
 464         bn_check_top(b);
 465
 466         if (a == b) return(a);
 467         if (bn_wexpand(a,b->top) == NULL) return(NULL);
 468
 469 #if 1
 470         A=a->d;
 471         B=b->d;
 472         for (i=b->top&(~7); i>0; i-=8)
 473                 {
 474                 A[0]=B[0];
 475                 A[1]=B[1];
 476                 A[2]=B[2];
 477                 A[3]=B[3];
 478                 A[4]=B[4];
 479                 A[5]=B[5];
 480                 A[6]=B[6];
 481                 A[7]=B[7];
 482                 A+=8;
 483                 B+=8;
 484                 }
 485         switch (b->top&7)
 486                 {
 487         case 7:
 488                 A[6]=B[6];
 489         case 6:
 490                 A[5]=B[5];
 491         case 5:
 492                 A[4]=B[4];
 493         case 4:
 494                 A[3]=B[3];
 495         case 3:
 496                 A[2]=B[2];
 497         case 2:
 498                 A[1]=B[1];
 499         case 1:
 500                 A[0]=B[0];
 501         case 0:
 502                 /* I need the 'case 0' entry for utrix cc.
 503                  * If the optimiser is turned on, it does the
 504                  * switch table by doing
 505                  * a=top&7
 506                  * a--;
 507                  * goto jump_table[a];
 508                  * If top is 0, this makes us jump to 0xffffffc which is
 509                  * rather bad :-(.
 510                  * eric 23-Apr-1998
 511                  */
 512                 ;
 513                 }
 514 #else
 515         memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
 516 #endif
 517
 518 /*      memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/
 519         a->top=b->top;
 520         if ((a->top == 0) && (a->d != NULL))
 521                 a->d[0]=0;
 522         a->neg=b->neg;
 523         return(a);
 524         }
 525
 526 void BN_clear(a)
 527 BIGNUM *a;
 528         {
 529         if (a->d != NULL)
 530                 memset(a->d,0,a->max*sizeof(a->d[0]));
 531         a->top=0;
 532         a->neg=0;
 533         }
 534
 535 BN_ULONG BN_get_word(a)
 536 BIGNUM *a;
 537         {
 538         int i,n;
 539         BN_ULONG ret=0;
 540
 541         n=BN_num_bytes(a);
 542         if (n > sizeof(BN_ULONG))
 543                 return(BN_MASK2);
 544         for (i=a->top-1; i>=0; i--)
 545                 {
 546 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
 547                 ret<<=BN_BITS4; /* stops the compiler complaining */
 548                 ret<<=BN_BITS4;
 549 #endif
 550                 ret|=a->d[i];
 551                 }
 552         return(ret);
 553         }
 554
 555 int BN_set_word(a,w)
 556 BIGNUM *a;
 557 BN_ULONG w;
 558         {
 559         int i,n;
 560         if (bn_expand(a,sizeof(BN_ULONG)*8) == NULL) return(0);
 561
 562         n=sizeof(BN_ULONG)/BN_BYTES;
 563         a->neg=0;
 564         a->top=0;
 565         a->d[0]=(BN_ULONG)w&BN_MASK2;
 566         if (a->d[0] != 0) a->top=1;
 567         for (i=1; i<n; i++)
 568                 {
 569                 /* the following is done instead of
 570                  * w>>=BN_BITS2 so compilers don't complain
 571                  * on builds where sizeof(long) == BN_TYPES */
 572 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
 573                 w>>=BN_BITS4;
 574                 w>>=BN_BITS4;
 575 #endif
 576                 a->d[i]=(BN_ULONG)w&BN_MASK2;
 577                 if (a->d[i] != 0) a->top=i+1;
 578                 }
 579         return(1);
 580         }
 581
 582 /* ignore negative */
 583 BIGNUM *BN_bin2bn(s, len, ret)
 584 unsigned char *s;
 585 int len;
 586 BIGNUM *ret;
 587         {
 588         unsigned int i,m;
 589         unsigned int n;
 590         BN_ULONG l;
 591
 592         if (ret == NULL) ret=BN_new();
 593         if (ret == NULL) return(NULL);
 594         l=0;
 595         n=len;
 596         if (n == 0)
 597                 {
 598                 ret->top=0;
 599                 return(ret);
 600                 }
 601         if (bn_expand(ret,(int)(n+2)*8) == NULL)
 602                 return(NULL);
 603         i=((n-1)/BN_BYTES)+1;
 604         m=((n-1)%(BN_BYTES));
 605         ret->top=i;
 606         while (n-- > 0)
 607                 {
 608                 l=(l<<8L)| *(s++);
 609                 if (m-- == 0)
 610                         {
 611                         ret->d[--i]=l;
 612                         l=0;
 613                         m=BN_BYTES-1;
 614                         }
 615                 }
 616         /* need to call this due to clear byte at top if avoiding
 617          * having the top bit set (-ve number) */
 618         bn_fix_top(ret);
 619         return(ret);
 620         }
 621
 622 /* ignore negative */
 623 int BN_bn2bin(a, to)
 624 BIGNUM *a;
 625 unsigned char *to;
 626         {
 627         int n,i;
 628         BN_ULONG l;
 629
 630         n=i=BN_num_bytes(a);
 631         while (i-- > 0)
 632                 {
 633                 l=a->d[i/BN_BYTES];
 634                 *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
 635                 }
 636         return(n);
 637         }
 638
 639 int BN_ucmp(a, b)
 640 BIGNUM *a;
 641 BIGNUM *b;
 642         {
 643         int i;
 644         BN_ULONG t1,t2,*ap,*bp;
 645
 646         bn_check_top(a);
 647         bn_check_top(b);
 648
 649         i=a->top-b->top;
 650         if (i != 0) return(i);
 651         ap=a->d;
 652         bp=b->d;
 653         for (i=a->top-1; i>=0; i--)
 654                 {
 655                 t1= ap[i];
 656                 t2= bp[i];
 657                 if (t1 != t2)
 658                         return(t1 > t2?1:-1);
 659                 }
 660         return(0);
 661         }
 662
 663 int BN_cmp(a, b)
 664 BIGNUM *a;
 665 BIGNUM *b;
 666         {
 667         int i;
 668         int gt,lt;
 669         BN_ULONG t1,t2;
 670
 671         if ((a == NULL) || (b == NULL))
 672                 {
 673                 if (a != NULL)
 674                         return(-1);
 675                 else if (b != NULL)
 676                         return(1);
 677                 else
 678                         return(0);
 679                 }
 680
 681         bn_check_top(a);
 682         bn_check_top(b);
 683
 684         if (a->neg != b->neg)
 685                 {
 686                 if (a->neg)
 687                         return(-1);
 688                 else    return(1);
 689                 }
 690         if (a->neg == 0)
 691                 { gt=1; lt= -1; }
 692         else    { gt= -1; lt=1; }
 693
 694         if (a->top > b->top) return(gt);
 695         if (a->top < b->top) return(lt);
 696         for (i=a->top-1; i>=0; i--)
 697                 {
 698                 t1=a->d[i];
 699                 t2=b->d[i];
 700                 if (t1 > t2) return(gt);
 701                 if (t1 < t2) return(lt);
 702                 }
 703         return(0);
 704         }
 705
 706 int BN_set_bit(a, n)
 707 BIGNUM *a;
 708 int n;
 709         {
 710         int i,j,k;
 711
 712         i=n/BN_BITS2;
 713         j=n%BN_BITS2;
 714         if (a->top <= i)
 715                 {
 716                 if (bn_wexpand(a,i+1) == NULL) return(0);
 717                 for(k=a->top; k<i+1; k++)
 718                         a->d[k]=0;
 719                 a->top=i+1;
 720                 }
 721
 722         a->d[i]|=(1L<<j);
 723         return(1);
 724         }
 725
 726 int BN_clear_bit(a, n)
 727 BIGNUM *a;
 728 int n;
 729         {
 730         int i,j;
 731
 732         i=n/BN_BITS2;
 733         j=n%BN_BITS2;
 734         if (a->top <= i) return(0);
 735
 736         a->d[i]&=(~(1L<<j));
 737         bn_fix_top(a);
 738         return(1);
 739         }
 740
 741 int BN_is_bit_set(a, n)
 742 BIGNUM *a;
 743 int n;
 744         {
 745         int i,j;
 746
 747         if (n < 0) return(0);
 748         i=n/BN_BITS2;
 749         j=n%BN_BITS2;
 750         if (a->top <= i) return(0);
 751         return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
 752         }
 753
 754 int BN_mask_bits(a,n)
 755 BIGNUM *a;
 756 int n;
 757         {
 758         int b,w;
 759
 760         w=n/BN_BITS2;
 761         b=n%BN_BITS2;
 762         if (w >= a->top) return(0);
 763         if (b == 0)
 764                 a->top=w;
 765         else
 766                 {
 767                 a->top=w+1;
 768                 a->d[w]&= ~(BN_MASK2<<b);
 769                 }
 770         bn_fix_top(a);
 771         return(1);
 772         }
 773
 774 int bn_cmp_words(a,b,n)
 775 BN_ULONG *a,*b;
 776 int n;
 777         {
 778         int i;
 779         BN_ULONG aa,bb;
 780
 781         aa=a[n-1];
 782         bb=b[n-1];
 783         if (aa != bb) return((aa > bb)?1:-1);
 784         for (i=n-2; i>=0; i--)
 785                 {
 786                 aa=a[i];
 787                 bb=b[i];
 788                 if (aa != bb) return((aa > bb)?1:-1);
 789                 }
 790         return(0);
 791         }
 792