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