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