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     bn_check_top(b);
 267
 268     if (words > (INT_MAX / (4 * BN_BITS2))) {
 269         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
 270         return NULL;
 271     }
 272     if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
 273         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
 274         return (NULL);
 275     }
 276     a = A = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG) * words);
 277     if (A == NULL) {
 278         BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
 279         return (NULL);
 280     }
 281 #ifdef PURIFY
 282     /*
 283      * Valgrind complains in BN_consttime_swap because we process the whole
 284      * array even if it's not initialised yet. This doesn't matter in that
 285      * function - what's important is constant time operation (we're not
 286      * actually going to use the data)
 287      */
 288     memset(a, 0, sizeof(BN_ULONG) * words);
 289 #endif
 290
 291 #if 1
 292     B = b->d;
 293     /* Check if the previous number needs to be copied */
 294     if (B != NULL) {
 295         for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
 296             /*
 297              * The fact that the loop is unrolled
 298              * 4-wise is a tribute to Intel. It's
 299              * the one that doesn't have enough
 300              * registers to accomodate more data.
 301              * I'd unroll it 8-wise otherwise:-)
 302              *
 303              *              <appro@fy.chalmers.se>
 304              */
 305             BN_ULONG a0, a1, a2, a3;
 306             a0 = B[0];
 307             a1 = B[1];
 308             a2 = B[2];
 309             a3 = B[3];
 310             A[0] = a0;
 311             A[1] = a1;
 312             A[2] = a2;
 313             A[3] = a3;
 314         }
 315         /*
 316          * workaround for ultrix cc: without 'case 0', the optimizer does
 317          * the switch table by doing a=top&3; a--; goto jump_table[a];
 318          * which fails for top== 0
 319          */
 320         switch (b->top & 3) {
 321         case 3:
 322             A[2] = B[2];
 323         case 2:
 324             A[1] = B[1];
 325         case 1:
 326             A[0] = B[0];
 327         case 0:
 328             ;
 329         }
 330     }
 331 #else
 332     memset(A, 0, sizeof(BN_ULONG) * words);
 333     memcpy(A, b->d, sizeof(b->d[0]) * b->top);
 334 #endif
 335
 336     return (a);
 337 }
 338
 339 /*
 340  * This is an internal function that can be used instead of bn_expand2() when
 341  * there is a need to copy BIGNUMs instead of only expanding the data part,
 342  * while still expanding them. Especially useful when needing to expand
 343  * BIGNUMs that are declared 'const' and should therefore not be changed. The
 344  * reason to use this instead of a BN_dup() followed by a bn_expand2() is
 345  * memory allocation overhead.  A BN_dup() followed by a bn_expand2() will
 346  * allocate new memory for the BIGNUM data twice, and free it once, while
 347  * bn_dup_expand() makes sure allocation is made only once.
 348  */
 349
 350 #ifndef OPENSSL_NO_DEPRECATED
 351 BIGNUM *bn_dup_expand(const BIGNUM *b, int words)
 352 {
 353     BIGNUM *r = NULL;
 354
 355     bn_check_top(b);
 356
 357     /*
 358      * This function does not work if words <= b->dmax && top < words because
 359      * BN_dup() does not preserve 'dmax'! (But bn_dup_expand() is not used
 360      * anywhere yet.)
 361      */
 362
 363     if (words > b->dmax) {
 364         BN_ULONG *a = bn_expand_internal(b, words);
 365
 366         if (a) {
 367             r = BN_new();
 368             if (r) {
 369                 r->top = b->top;
 370                 r->dmax = words;
 371                 r->neg = b->neg;
 372                 r->d = a;
 373             } else {
 374                 /* r == NULL, BN_new failure */
 375                 OPENSSL_free(a);
 376             }
 377         }
 378         /*
 379          * If a == NULL, there was an error in allocation in
 380          * bn_expand_internal(), and NULL should be returned
 381          */
 382     } else {
 383         r = BN_dup(b);
 384     }
 385
 386     bn_check_top(r);
 387     return r;
 388 }
 389 #endif
 390
 391 /*
 392  * This is an internal function that should not be used in applications. It
 393  * ensures that 'b' has enough room for a 'words' word number and initialises
 394  * any unused part of b->d with leading zeros. It is mostly used by the
 395  * various BIGNUM routines. If there is an error, NULL is returned. If not,
 396  * 'b' is returned.
 397  */
 398
 399 BIGNUM *bn_expand2(BIGNUM *b, int words)
 400 {
 401     bn_check_top(b);
 402
 403     if (words > b->dmax) {
 404         BN_ULONG *a = bn_expand_internal(b, words);
 405         if (!a)
 406             return NULL;
 407         if (b->d)
 408             OPENSSL_free(b->d);
 409         b->d = a;
 410         b->dmax = words;
 411     }
 412
 413 /* None of this should be necessary because of what b->top means! */
 414 #if 0
 415     /*
 416      * NB: bn_wexpand() calls this only if the BIGNUM really has to grow
 417      */
 418     if (b->top < b->dmax) {
 419         int i;
 420         BN_ULONG *A = &(b->d[b->top]);
 421         for (i = (b->dmax - b->top) >> 3; i > 0; i--, A += 8) {
 422             A[0] = 0;
 423             A[1] = 0;
 424             A[2] = 0;
 425             A[3] = 0;
 426             A[4] = 0;
 427             A[5] = 0;
 428             A[6] = 0;
 429             A[7] = 0;
 430         }
 431         for (i = (b->dmax - b->top) & 7; i > 0; i--, A++)
 432             A[0] = 0;
 433         assert(A == &(b->d[b->dmax]));
 434     }
 435 #endif
 436     bn_check_top(b);
 437     return b;
 438 }
 439
 440 BIGNUM *BN_dup(const BIGNUM *a)
 441 {
 442     BIGNUM *t;
 443
 444     if (a == NULL)
 445         return NULL;
 446     bn_check_top(a);
 447
 448     t = BN_new();
 449     if (t == NULL)
 450         return NULL;
 451     if (!BN_copy(t, a)) {
 452         BN_free(t);
 453         return NULL;
 454     }
 455     bn_check_top(t);
 456     return t;
 457 }
 458
 459 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
 460 {
 461     int i;
 462     BN_ULONG *A;
 463     const BN_ULONG *B;
 464
 465     bn_check_top(b);
 466
 467     if (a == b)
 468         return (a);
 469     if (bn_wexpand(a, b->top) == NULL)
 470         return (NULL);
 471
 472 #if 1
 473     A = a->d;
 474     B = b->d;
 475     for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
 476         BN_ULONG a0, a1, a2, a3;
 477         a0 = B[0];
 478         a1 = B[1];
 479         a2 = B[2];
 480         a3 = B[3];
 481         A[0] = a0;
 482         A[1] = a1;
 483         A[2] = a2;
 484         A[3] = a3;
 485     }
 486     /* ultrix cc workaround, see comments in bn_expand_internal */
 487     switch (b->top & 3) {
 488     case 3:
 489         A[2] = B[2];
 490     case 2:
 491         A[1] = B[1];
 492     case 1:
 493         A[0] = B[0];
 494     case 0:;
 495     }
 496 #else
 497     memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
 498 #endif
 499
 500     a->top = b->top;
 501     a->neg = b->neg;
 502     bn_check_top(a);
 503     return (a);
 504 }
 505
 506 #define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \
 507                                     | BN_FLG_CONSTTIME))
 508 #define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED))
 509
 510 void BN_swap(BIGNUM *a, BIGNUM *b)
 511 {
 512     int flags_old_a, flags_old_b;
 513     BN_ULONG *tmp_d;
 514     int tmp_top, tmp_dmax, tmp_neg;
 515
 516     bn_check_top(a);
 517     bn_check_top(b);
 518
 519     flags_old_a = a->flags;
 520     flags_old_b = b->flags;
 521
 522     tmp_d = a->d;
 523     tmp_top = a->top;
 524     tmp_dmax = a->dmax;
 525     tmp_neg = a->neg;
 526
 527     a->d = b->d;
 528     a->top = b->top;
 529     a->dmax = b->dmax;
 530     a->neg = b->neg;
 531
 532     b->d = tmp_d;
 533     b->top = tmp_top;
 534     b->dmax = tmp_dmax;
 535     b->neg = tmp_neg;
 536
 537     a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b);
 538     b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a);
 539     bn_check_top(a);
 540     bn_check_top(b);
 541 }
 542
 543 void BN_clear(BIGNUM *a)
 544 {
 545     bn_check_top(a);
 546     if (a->d != NULL)
 547         OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
 548     a->top = 0;
 549     a->neg = 0;
 550 }
 551
 552 BN_ULONG BN_get_word(const BIGNUM *a)
 553 {
 554     if (a->top > 1)
 555         return BN_MASK2;
 556     else if (a->top == 1)
 557         return a->d[0];
 558     /* a->top == 0 */
 559     return 0;
 560 }
 561
 562 int BN_set_word(BIGNUM *a, BN_ULONG w)
 563 {
 564     bn_check_top(a);
 565     if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
 566         return (0);
 567     a->neg = 0;
 568     a->d[0] = w;
 569     a->top = (w ? 1 : 0);
 570     bn_check_top(a);
 571     return (1);
 572 }
 573
 574 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
 575 {
 576     unsigned int i, m;
 577     unsigned int n;
 578     BN_ULONG l;
 579     BIGNUM *bn = NULL;
 580
 581     if (ret == NULL)
 582         ret = bn = BN_new();
 583     if (ret == NULL)
 584         return (NULL);
 585     bn_check_top(ret);
 586     l = 0;
 587     n = len;
 588     if (n == 0) {
 589         ret->top = 0;
 590         return (ret);
 591     }
 592     i = ((n - 1) / BN_BYTES) + 1;
 593     m = ((n - 1) % (BN_BYTES));
 594     if (bn_wexpand(ret, (int)i) == NULL) {
 595         if (bn)
 596             BN_free(bn);
 597         return NULL;
 598     }
 599     ret->top = i;
 600     ret->neg = 0;
 601     while (n--) {
 602         l = (l << 8L) | *(s++);
 603         if (m-- == 0) {
 604             ret->d[--i] = l;
 605             l = 0;
 606             m = BN_BYTES - 1;
 607         }
 608     }
 609     /*
 610      * need to call this due to clear byte at top if avoiding having the top
 611      * bit set (-ve number)
 612      */
 613     bn_correct_top(ret);
 614     return (ret);
 615 }
 616
 617 /* ignore negative */
 618 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
 619 {
 620     int n, i;
 621     BN_ULONG l;
 622
 623     bn_check_top(a);
 624     n = i = BN_num_bytes(a);
 625     while (i--) {
 626         l = a->d[i / BN_BYTES];
 627         *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
 628     }
 629     return (n);
 630 }
 631
 632 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
 633 {
 634     int i;
 635     BN_ULONG t1, t2, *ap, *bp;
 636
 637     bn_check_top(a);
 638     bn_check_top(b);
 639
 640     i = a->top - b->top;
 641     if (i != 0)
 642         return (i);
 643     ap = a->d;
 644     bp = b->d;
 645     for (i = a->top - 1; i >= 0; i--) {
 646         t1 = ap[i];
 647         t2 = bp[i];
 648         if (t1 != t2)
 649             return ((t1 > t2) ? 1 : -1);
 650     }
 651     return (0);
 652 }
 653
 654 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
 655 {
 656     int i;
 657     int gt, lt;
 658     BN_ULONG t1, t2;
 659
 660     if ((a == NULL) || (b == NULL)) {
 661         if (a != NULL)
 662             return (-1);
 663         else if (b != NULL)
 664             return (1);
 665         else
 666             return (0);
 667     }
 668
 669     bn_check_top(a);
 670     bn_check_top(b);
 671
 672     if (a->neg != b->neg) {
 673         if (a->neg)
 674             return (-1);
 675         else
 676             return (1);
 677     }
 678     if (a->neg == 0) {
 679         gt = 1;
 680         lt = -1;
 681     } else {
 682         gt = -1;
 683         lt = 1;
 684     }
 685
 686     if (a->top > b->top)
 687         return (gt);
 688     if (a->top < b->top)
 689         return (lt);
 690     for (i = a->top - 1; i >= 0; i--) {
 691         t1 = a->d[i];
 692         t2 = b->d[i];
 693         if (t1 > t2)
 694             return (gt);
 695         if (t1 < t2)
 696             return (lt);
 697     }
 698     return (0);
 699 }
 700
 701 int BN_set_bit(BIGNUM *a, int n)
 702 {
 703     int i, j, k;
 704
 705     if (n < 0)
 706         return 0;
 707
 708     i = n / BN_BITS2;
 709     j = n % BN_BITS2;
 710     if (a->top <= i) {
 711         if (bn_wexpand(a, i + 1) == NULL)
 712             return (0);
 713         for (k = a->top; k < i + 1; k++)
 714             a->d[k] = 0;
 715         a->top = i + 1;
 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 }