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