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 SSLeay 0.9.1a 06-Jul-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         for (i=0; i<BN_CTX_NUM; i++)
 345                 BN_clear_free(&(c->bn[i]));
 346         if (c->flags & BN_FLG_MALLOCED)
 347                 Free(c);
 348         }
 349
 350 BIGNUM *bn_expand2(b, words)
 351 BIGNUM *b;
 352 int words;
 353         {
 354         BN_ULONG *A,*B,*a;
 355         int i,j;
 356
 357         bn_check_top(b);
 358
 359         if (words > b->max)
 360                 {
 361                 bn_check_top(b);
 362                 if (BN_get_flags(b,BN_FLG_STATIC_DATA))
 363                         {
 364                         BNerr(BN_F_BN_EXPAND2,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
 365                         return(NULL);
 366                         }
 367                 a=A=(BN_ULONG *)Malloc(sizeof(BN_ULONG)*(words+1));
 368                 if (A == NULL)
 369                         {
 370                         BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE);
 371                         return(NULL);
 372                         }
 373 memset(A,0x5c,sizeof(BN_ULONG)*(words+1));
 374 #if 1
 375                 B=b->d;
 376                 if (B != NULL)
 377                         {
 378                         for (i=b->top&(~7); i>0; i-=8)
 379                                 {
 380                                 A[0]=B[0]; A[1]=B[1]; A[2]=B[2]; A[3]=B[3];
 381                                 A[4]=B[4]; A[5]=B[5]; A[6]=B[6]; A[7]=B[7];
 382                                 A+=8;
 383                                 B+=8;
 384                                 }
 385                         switch (b->top&7)
 386                                 {
 387                         case 7:
 388                                 A[6]=B[6];
 389                         case 6:
 390                                 A[5]=B[5];
 391                         case 5:
 392                                 A[4]=B[4];
 393                         case 4:
 394                                 A[3]=B[3];
 395                         case 3:
 396                                 A[2]=B[2];
 397                         case 2:
 398                                 A[1]=B[1];
 399                         case 1:
 400                                 A[0]=B[0];
 401                         case 0:
 402                                 /* I need the 'case 0' entry for utrix cc.
 403                                  * If the optimiser is turned on, it does the
 404                                  * switch table by doing
 405                                  * a=top&7
 406                                  * a--;
 407                                  * goto jump_table[a];
 408                                  * If top is 0, this makes us jump to 0xffffffc
 409                                  * which is rather bad :-(.
 410                                  * eric 23-Apr-1998
 411                                  */
 412                                 ;
 413                                 }
 414                         B= &(b->d[b->top]);
 415                         j=b->max-8;
 416                         for (i=b->top; i<j; i+=8)
 417                                 {
 418                                 B[0]=0; B[1]=0; B[2]=0; B[3]=0;
 419                                 B[4]=0; B[5]=0; B[6]=0; B[7]=0;
 420                                 B+=8;
 421                                 }
 422                         for (j+=8; i<j; i++)
 423                                 {
 424                                 B[0]=0;
 425                                 B++;
 426                                 }
 427 #else
 428                         memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
 429 #endif
 430
 431 /*              memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); */
 432 /*      { int i; for (i=b->max; i<words+1; i++) p[i]=i;} */
 433                         Free(b->d);
 434                         }
 435
 436                 b->d=a;
 437                 b->max=words;
 438                 }
 439         return(b);
 440         }
 441
 442 BIGNUM *BN_dup(a)
 443 BIGNUM *a;
 444         {
 445         BIGNUM *r;
 446
 447         bn_check_top(a);
 448
 449         r=BN_new();
 450         if (r == NULL) return(NULL);
 451         return((BIGNUM *)BN_copy(r,a));
 452         }
 453
 454 BIGNUM *BN_copy(a, b)
 455 BIGNUM *a;
 456 BIGNUM *b;
 457         {
 458         int i;
 459         BN_ULONG *A,*B;
 460
 461         bn_check_top(b);
 462
 463         if (a == b) return(a);
 464         if (bn_wexpand(a,b->top) == NULL) return(NULL);
 465
 466 #if 1
 467         A=a->d;
 468         B=b->d;
 469         for (i=b->top&(~7); i>0; i-=8)
 470                 {
 471                 A[0]=B[0];
 472                 A[1]=B[1];
 473                 A[2]=B[2];
 474                 A[3]=B[3];
 475                 A[4]=B[4];
 476                 A[5]=B[5];
 477                 A[6]=B[6];
 478                 A[7]=B[7];
 479                 A+=8;
 480                 B+=8;
 481                 }
 482         switch (b->top&7)
 483                 {
 484         case 7:
 485                 A[6]=B[6];
 486         case 6:
 487                 A[5]=B[5];
 488         case 5:
 489                 A[4]=B[4];
 490         case 4:
 491                 A[3]=B[3];
 492         case 3:
 493                 A[2]=B[2];
 494         case 2:
 495                 A[1]=B[1];
 496         case 1:
 497                 A[0]=B[0];
 498         case 0:
 499                 /* I need the 'case 0' entry for utrix cc.
 500                  * If the optimiser is turned on, it does the
 501                  * switch table by doing
 502                  * a=top&7
 503                  * a--;
 504                  * goto jump_table[a];
 505                  * If top is 0, this makes us jump to 0xffffffc which is
 506                  * rather bad :-(.
 507                  * eric 23-Apr-1998
 508                  */
 509                 ;
 510                 }
 511 #else
 512         memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
 513 #endif
 514
 515 /*      memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/
 516         a->top=b->top;
 517         if ((a->top == 0) && (a->d != NULL))
 518                 a->d[0]=0;
 519         a->neg=b->neg;
 520         return(a);
 521         }
 522
 523 void BN_clear(a)
 524 BIGNUM *a;
 525         {
 526         if (a->d != NULL)
 527                 memset(a->d,0,a->max*sizeof(a->d[0]));
 528         a->top=0;
 529         a->neg=0;
 530         }
 531
 532 BN_ULONG BN_get_word(a)
 533 BIGNUM *a;
 534         {
 535         int i,n;
 536         BN_ULONG ret=0;
 537
 538         n=BN_num_bytes(a);
 539         if (n > sizeof(BN_ULONG))
 540                 return(BN_MASK2);
 541         for (i=a->top-1; i>=0; i--)
 542                 {
 543 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
 544                 ret<<=BN_BITS4; /* stops the compiler complaining */
 545                 ret<<=BN_BITS4;
 546 #endif
 547                 ret|=a->d[i];
 548                 }
 549         return(ret);
 550         }
 551
 552 int BN_set_word(a,w)
 553 BIGNUM *a;
 554 BN_ULONG w;
 555         {
 556         int i,n;
 557         if (bn_expand(a,sizeof(BN_ULONG)*8) == NULL) return(0);
 558
 559         n=sizeof(BN_ULONG)/BN_BYTES;
 560         a->neg=0;
 561         a->top=0;
 562         a->d[0]=(BN_ULONG)w&BN_MASK2;
 563         if (a->d[0] != 0) a->top=1;
 564         for (i=1; i<n; i++)
 565                 {
 566                 /* the following is done instead of
 567                  * w>>=BN_BITS2 so compilers don't complain
 568                  * on builds where sizeof(long) == BN_TYPES */
 569 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
 570                 w>>=BN_BITS4;
 571                 w>>=BN_BITS4;
 572 #endif
 573                 a->d[i]=(BN_ULONG)w&BN_MASK2;
 574                 if (a->d[i] != 0) a->top=i+1;
 575                 }
 576         return(1);
 577         }
 578
 579 /* ignore negative */
 580 BIGNUM *BN_bin2bn(s, len, ret)
 581 unsigned char *s;
 582 int len;
 583 BIGNUM *ret;
 584         {
 585         unsigned int i,m;
 586         unsigned int n;
 587         BN_ULONG l;
 588
 589         if (ret == NULL) ret=BN_new();
 590         if (ret == NULL) return(NULL);
 591         l=0;
 592         n=len;
 593         if (n == 0)
 594                 {
 595                 ret->top=0;
 596                 return(ret);
 597                 }
 598         if (bn_expand(ret,(int)(n+2)*8) == NULL)
 599                 return(NULL);
 600         i=((n-1)/BN_BYTES)+1;
 601         m=((n-1)%(BN_BYTES));
 602         ret->top=i;
 603         while (n-- > 0)
 604                 {
 605                 l=(l<<8L)| *(s++);
 606                 if (m-- == 0)
 607                         {
 608                         ret->d[--i]=l;
 609                         l=0;
 610                         m=BN_BYTES-1;
 611                         }
 612                 }
 613         /* need to call this due to clear byte at top if avoiding
 614          * having the top bit set (-ve number) */
 615         bn_fix_top(ret);
 616         return(ret);
 617         }
 618
 619 /* ignore negative */
 620 int BN_bn2bin(a, to)
 621 BIGNUM *a;
 622 unsigned char *to;
 623         {
 624         int n,i;
 625         BN_ULONG l;
 626
 627         n=i=BN_num_bytes(a);
 628         while (i-- > 0)
 629                 {
 630                 l=a->d[i/BN_BYTES];
 631                 *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
 632                 }
 633         return(n);
 634         }
 635
 636 int BN_ucmp(a, b)
 637 BIGNUM *a;
 638 BIGNUM *b;
 639         {
 640         int i;
 641         BN_ULONG t1,t2,*ap,*bp;
 642
 643         bn_check_top(a);
 644         bn_check_top(b);
 645
 646         i=a->top-b->top;
 647         if (i != 0) return(i);
 648         ap=a->d;
 649         bp=b->d;
 650         for (i=a->top-1; i>=0; i--)
 651                 {
 652                 t1= ap[i];
 653                 t2= bp[i];
 654                 if (t1 != t2)
 655                         return(t1 > t2?1:-1);
 656                 }
 657         return(0);
 658         }
 659
 660 int BN_cmp(a, b)
 661 BIGNUM *a;
 662 BIGNUM *b;
 663         {
 664         int i;
 665         int gt,lt;
 666         BN_ULONG t1,t2;
 667
 668         if ((a == NULL) || (b == NULL))
 669                 {
 670                 if (a != NULL)
 671                         return(-1);
 672                 else if (b != NULL)
 673                         return(1);
 674                 else
 675                         return(0);
 676                 }
 677
 678         bn_check_top(a);
 679         bn_check_top(b);
 680
 681         if (a->neg != b->neg)
 682                 {
 683                 if (a->neg)
 684                         return(-1);
 685                 else    return(1);
 686                 }
 687         if (a->neg == 0)
 688                 { gt=1; lt= -1; }
 689         else    { gt= -1; lt=1; }
 690
 691         if (a->top > b->top) return(gt);
 692         if (a->top < b->top) return(lt);
 693         for (i=a->top-1; i>=0; i--)
 694                 {
 695                 t1=a->d[i];
 696                 t2=b->d[i];
 697                 if (t1 > t2) return(gt);
 698                 if (t1 < t2) return(lt);
 699                 }
 700         return(0);
 701         }
 702
 703 int BN_set_bit(a, n)
 704 BIGNUM *a;
 705 int n;
 706         {
 707         int i,j,k;
 708
 709         i=n/BN_BITS2;
 710         j=n%BN_BITS2;
 711         if (a->top <= i)
 712                 {
 713                 if (bn_wexpand(a,i+1) == NULL) return(0);
 714                 for(k=a->top; k<i+1; k++)
 715                         a->d[k]=0;
 716                 a->top=i+1;
 717                 }
 718
 719         a->d[i]|=(1L<<j);
 720         return(1);
 721         }
 722
 723 int BN_clear_bit(a, n)
 724 BIGNUM *a;
 725 int n;
 726         {
 727         int i,j;
 728
 729         i=n/BN_BITS2;
 730         j=n%BN_BITS2;
 731         if (a->top <= i) return(0);
 732
 733         a->d[i]&=(~(1L<<j));
 734         bn_fix_top(a);
 735         return(1);
 736         }
 737
 738 int BN_is_bit_set(a, n)
 739 BIGNUM *a;
 740 int n;
 741         {
 742         int i,j;
 743
 744         if (n < 0) return(0);
 745         i=n/BN_BITS2;
 746         j=n%BN_BITS2;
 747         if (a->top <= i) return(0);
 748         return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
 749         }
 750
 751 int BN_mask_bits(a,n)
 752 BIGNUM *a;
 753 int n;
 754         {
 755         int b,w;
 756
 757         w=n/BN_BITS2;
 758         b=n%BN_BITS2;
 759         if (w >= a->top) return(0);
 760         if (b == 0)
 761                 a->top=w;
 762         else
 763                 {
 764                 a->top=w+1;
 765                 a->d[w]&= ~(BN_MASK2<<b);
 766                 }
 767         bn_fix_top(a);
 768         return(1);
 769         }
 770
 771 int bn_cmp_words(a,b,n)
 772 BN_ULONG *a,*b;
 773 int n;
 774         {
 775         int i;
 776         BN_ULONG aa,bb;
 777
 778         aa=a[n-1];
 779         bb=b[n-1];
 780         if (aa != bb) return((aa > bb)?1:-1);
 781         for (i=n-2; i>=0; i--)
 782                 {
 783                 aa=a[i];
 784                 bb=b[i];
 785                 if (aa != bb) return((aa > bb)?1:-1);
 786                 }
 787         return(0);
 788         }
 789