crypto/bn/bn_lib.c

   1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   2  * All rights reserved.
   3  *
   4  * This package is an SSL implementation written
   5  * by Eric Young (eay@cryptsoft.com).
   6  * The implementation was written so as to conform with Netscapes SSL.
   7  *
   8  * This library is free for commercial and non-commercial use as long as
   9  * the following conditions are aheared to.  The following conditions
  10  * apply to all code found in this distribution, be it the RC4, RSA,
  11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  12  * included with this distribution is covered by the same copyright terms
  13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  14  *
  15  * Copyright remains Eric Young's, and as such any Copyright notices in
  16  * the code are not to be removed.
  17  * If this package is used in a product, Eric Young should be given attribution
  18  * as the author of the parts of the library used.
  19  * This can be in the form of a textual message at program startup or
  20  * in documentation (online or textual) provided with the package.
  21  *
  22  * Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions
  24  * are met:
  25  * 1. Redistributions of source code must retain the copyright
  26  *    notice, this list of conditions and the following disclaimer.
  27  * 2. Redistributions in binary form must reproduce the above copyright
  28  *    notice, this list of conditions and the following disclaimer in the
  29  *    documentation and/or other materials provided with the distribution.
  30  * 3. All advertising materials mentioning features or use of this software
  31  *    must display the following acknowledgement:
  32  *    "This product includes cryptographic software written by
  33  *     Eric Young (eay@cryptsoft.com)"
  34  *    The word 'cryptographic' can be left out if the rouines from the library
  35  *    being used are not cryptographic related :-).
  36  * 4. If you include any Windows specific code (or a derivative thereof) from
  37  *    the apps directory (application code) you must include an acknowledgement:
  38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  50  * SUCH DAMAGE.
  51  *
  52  * The licence and distribution terms for any publically available version or
  53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  54  * copied and put under another distribution licence
  55  * [including the GNU Public Licence.]
  56  */
  57
  58 #ifndef BN_DEBUG
  59 # undef NDEBUG                  /* avoid conflicting definitions */
  60 # define NDEBUG
  61 #endif
  62
  63 #include <assert.h>
  64 #include <limits.h>
  65 #include "internal/cryptlib.h"
  66 #include "bn_lcl.h"
  67 #include <openssl/opensslconf.h>
  68
  69 /* This stuff appears to be completely unused, so is deprecated */
  70 #if OPENSSL_API_COMPAT < 0x00908000L
  71 /*-
  72  * For a 32 bit machine
  73  * 2 -   4 ==  128
  74  * 3 -   8 ==  256
  75  * 4 -  16 ==  512
  76  * 5 -  32 == 1024
  77  * 6 -  64 == 2048
  78  * 7 - 128 == 4096
  79  * 8 - 256 == 8192
  80  */
  81 static int bn_limit_bits = 0;
  82 static int bn_limit_num = 8;    /* (1<<bn_limit_bits) */
  83 static int bn_limit_bits_low = 0;
  84 static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */
  85 static int bn_limit_bits_high = 0;
  86 static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */
  87 static int bn_limit_bits_mont = 0;
  88 static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */
  89
  90 void BN_set_params(int mult, int high, int low, int mont)
  91 {
  92     if (mult >= 0) {
  93         if (mult > (int)(sizeof(int) * 8) - 1)
  94             mult = sizeof(int) * 8 - 1;
  95         bn_limit_bits = mult;
  96         bn_limit_num = 1 << mult;
  97     }
  98     if (high >= 0) {
  99         if (high > (int)(sizeof(int) * 8) - 1)
 100             high = sizeof(int) * 8 - 1;
 101         bn_limit_bits_high = high;
 102         bn_limit_num_high = 1 << high;
 103     }
 104     if (low >= 0) {
 105         if (low > (int)(sizeof(int) * 8) - 1)
 106             low = sizeof(int) * 8 - 1;
 107         bn_limit_bits_low = low;
 108         bn_limit_num_low = 1 << low;
 109     }
 110     if (mont >= 0) {
 111         if (mont > (int)(sizeof(int) * 8) - 1)
 112             mont = sizeof(int) * 8 - 1;
 113         bn_limit_bits_mont = mont;
 114         bn_limit_num_mont = 1 << mont;
 115     }
 116 }
 117
 118 int BN_get_params(int which)
 119 {
 120     if (which == 0)
 121         return (bn_limit_bits);
 122     else if (which == 1)
 123         return (bn_limit_bits_high);
 124     else if (which == 2)
 125         return (bn_limit_bits_low);
 126     else if (which == 3)
 127         return (bn_limit_bits_mont);
 128     else
 129         return (0);
 130 }
 131 #endif
 132
 133 const BIGNUM *BN_value_one(void)
 134 {
 135     static const BN_ULONG data_one = 1L;
 136     static const BIGNUM const_one =
 137         { (BN_ULONG *)&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 unsigned 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         if (l & 0xffff000000000000L) {
 166             if (l & 0xff00000000000000L) {
 167                 return (bits[(int)(l >> 56)] + 56);
 168             } else
 169                 return (bits[(int)(l >> 48)] + 48);
 170         } else {
 171             if (l & 0x0000ff0000000000L) {
 172                 return (bits[(int)(l >> 40)] + 40);
 173             } else
 174                 return (bits[(int)(l >> 32)] + 32);
 175         }
 176     } else
 177 #else
 178 # ifdef SIXTY_FOUR_BIT
 179     if (l & 0xffffffff00000000LL) {
 180         if (l & 0xffff000000000000LL) {
 181             if (l & 0xff00000000000000LL) {
 182                 return (bits[(int)(l >> 56)] + 56);
 183             } else
 184                 return (bits[(int)(l >> 48)] + 48);
 185         } else {
 186             if (l & 0x0000ff0000000000LL) {
 187                 return (bits[(int)(l >> 40)] + 40);
 188             } else
 189                 return (bits[(int)(l >> 32)] + 32);
 190         }
 191     } else
 192 # endif
 193 #endif
 194     {
 195 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 196         if (l & 0xffff0000L) {
 197             if (l & 0xff000000L)
 198                 return (bits[(int)(l >> 24L)] + 24);
 199             else
 200                 return (bits[(int)(l >> 16L)] + 16);
 201         } else
 202 #endif
 203         {
 204 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 205             if (l & 0xff00L)
 206                 return (bits[(int)(l >> 8)] + 8);
 207             else
 208 #endif
 209                 return (bits[(int)(l)]);
 210         }
 211     }
 212 }
 213
 214 int BN_num_bits(const BIGNUM *a)
 215 {
 216     int i = a->top - 1;
 217     bn_check_top(a);
 218
 219     if (BN_is_zero(a))
 220         return 0;
 221     return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
 222 }
 223
 224 static void bn_free_d(BIGNUM *a)
 225 {
 226     if (BN_get_flags(a,BN_FLG_SECURE))
 227         OPENSSL_secure_free(a->d);
 228     else
 229         OPENSSL_free(a->d);
 230 }
 231
 232
 233 void BN_clear_free(BIGNUM *a)
 234 {
 235     int i;
 236
 237     if (a == NULL)
 238         return;
 239     bn_check_top(a);
 240     if (a->d != NULL) {
 241         OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
 242         if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
 243             bn_free_d(a);
 244     }
 245     i = BN_get_flags(a, BN_FLG_MALLOCED);
 246     OPENSSL_cleanse(a, sizeof(*a));
 247     if (i)
 248         OPENSSL_free(a);
 249 }
 250
 251 void BN_free(BIGNUM *a)
 252 {
 253     if (a == NULL)
 254         return;
 255     bn_check_top(a);
 256     if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
 257         bn_free_d(a);
 258     if (a->flags & BN_FLG_MALLOCED)
 259         OPENSSL_free(a);
 260     else {
 261 #if OPENSSL_API_COMPAT < 0x00908000L
 262         a->flags |= BN_FLG_FREE;
 263 #endif
 264         a->d = NULL;
 265     }
 266 }
 267
 268 void bn_init(BIGNUM *a)
 269 {
 270     static BIGNUM nilbn;
 271
 272     *a = nilbn;
 273     bn_check_top(a);
 274 }
 275
 276 BIGNUM *BN_new(void)
 277 {
 278     BIGNUM *ret;
 279
 280     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
 281         BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
 282         return (NULL);
 283     }
 284     ret->flags = BN_FLG_MALLOCED;
 285     bn_check_top(ret);
 286     return (ret);
 287 }
 288
 289  BIGNUM *BN_secure_new(void)
 290  {
 291      BIGNUM *ret = BN_new();
 292      if (ret != NULL)
 293          ret->flags |= BN_FLG_SECURE;
 294      return (ret);
 295  }
 296
 297 /* This is used by bn_expand2() */
 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         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
 309         return NULL;
 310     }
 311     if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
 312         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
 313         return (NULL);
 314     }
 315     if (BN_get_flags(b,BN_FLG_SECURE))
 316         a = A = OPENSSL_secure_zalloc(words * sizeof(*a));
 317     else
 318         a = A = OPENSSL_zalloc(words * sizeof(*a));
 319     if (A == NULL) {
 320         BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
 321         return (NULL);
 322     }
 323
 324 #if 1
 325     B = b->d;
 326     /* Check if the previous number needs to be copied */
 327     if (B != NULL) {
 328         for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
 329             /*
 330              * The fact that the loop is unrolled
 331              * 4-wise is a tribute to Intel. It's
 332              * the one that doesn't have enough
 333              * registers to accomodate more data.
 334              * I'd unroll it 8-wise otherwise:-)
 335              *
 336              *              <appro@fy.chalmers.se>
 337              */
 338             BN_ULONG a0, a1, a2, a3;
 339             a0 = B[0];
 340             a1 = B[1];
 341             a2 = B[2];
 342             a3 = B[3];
 343             A[0] = a0;
 344             A[1] = a1;
 345             A[2] = a2;
 346             A[3] = a3;
 347         }
 348         /*
 349          * workaround for ultrix cc: without 'case 0', the optimizer does
 350          * the switch table by doing a=top&3; a--; goto jump_table[a];
 351          * which fails for top== 0
 352          */
 353         switch (b->top & 3) {
 354         case 3:
 355             A[2] = B[2];
 356         case 2:
 357             A[1] = B[1];
 358         case 1:
 359             A[0] = B[0];
 360         case 0:
 361             ;
 362         }
 363     }
 364 #else
 365     memset(A, 0, sizeof(*A) * words);
 366     memcpy(A, b->d, sizeof(b->d[0]) * b->top);
 367 #endif
 368
 369     return (a);
 370 }
 371
 372 /*
 373  * This is an internal function that should not be used in applications. It
 374  * ensures that 'b' has enough room for a 'words' word number and initialises
 375  * any unused part of b->d with leading zeros. It is mostly used by the
 376  * various BIGNUM routines. If there is an error, NULL is returned. If not,
 377  * 'b' is returned.
 378  */
 379
 380 BIGNUM *bn_expand2(BIGNUM *b, int words)
 381 {
 382     bn_check_top(b);
 383
 384     if (words > b->dmax) {
 385         BN_ULONG *a = bn_expand_internal(b, words);
 386         if (!a)
 387             return NULL;
 388         if (b->d) {
 389             OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0]));
 390             bn_free_d(b);
 391         }
 392         b->d = a;
 393         b->dmax = words;
 394     }
 395
 396     bn_check_top(b);
 397     return b;
 398 }
 399
 400 BIGNUM *BN_dup(const BIGNUM *a)
 401 {
 402     BIGNUM *t;
 403
 404     if (a == NULL)
 405         return NULL;
 406     bn_check_top(a);
 407
 408     t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
 409     if (t == NULL)
 410         return NULL;
 411     if (!BN_copy(t, a)) {
 412         BN_free(t);
 413         return NULL;
 414     }
 415     bn_check_top(t);
 416     return t;
 417 }
 418
 419 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
 420 {
 421     int i;
 422     BN_ULONG *A;
 423     const BN_ULONG *B;
 424
 425     bn_check_top(b);
 426
 427     if (a == b)
 428         return (a);
 429     if (bn_wexpand(a, b->top) == NULL)
 430         return (NULL);
 431
 432 #if 1
 433     A = a->d;
 434     B = b->d;
 435     for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
 436         BN_ULONG a0, a1, a2, a3;
 437         a0 = B[0];
 438         a1 = B[1];
 439         a2 = B[2];
 440         a3 = B[3];
 441         A[0] = a0;
 442         A[1] = a1;
 443         A[2] = a2;
 444         A[3] = a3;
 445     }
 446     /* ultrix cc workaround, see comments in bn_expand_internal */
 447     switch (b->top & 3) {
 448     case 3:
 449         A[2] = B[2];
 450     case 2:
 451         A[1] = B[1];
 452     case 1:
 453         A[0] = B[0];
 454     case 0:;
 455     }
 456 #else
 457     memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
 458 #endif
 459
 460     a->top = b->top;
 461     a->neg = b->neg;
 462     bn_check_top(a);
 463     return (a);
 464 }
 465
 466 void BN_swap(BIGNUM *a, BIGNUM *b)
 467 {
 468     int flags_old_a, flags_old_b;
 469     BN_ULONG *tmp_d;
 470     int tmp_top, tmp_dmax, tmp_neg;
 471
 472     bn_check_top(a);
 473     bn_check_top(b);
 474
 475     flags_old_a = a->flags;
 476     flags_old_b = b->flags;
 477
 478     tmp_d = a->d;
 479     tmp_top = a->top;
 480     tmp_dmax = a->dmax;
 481     tmp_neg = a->neg;
 482
 483     a->d = b->d;
 484     a->top = b->top;
 485     a->dmax = b->dmax;
 486     a->neg = b->neg;
 487
 488     b->d = tmp_d;
 489     b->top = tmp_top;
 490     b->dmax = tmp_dmax;
 491     b->neg = tmp_neg;
 492
 493     a->flags =
 494         (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
 495     b->flags =
 496         (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
 497     bn_check_top(a);
 498     bn_check_top(b);
 499 }
 500
 501 void BN_clear(BIGNUM *a)
 502 {
 503     bn_check_top(a);
 504     if (a->d != NULL)
 505         memset(a->d, 0, sizeof(*a->d) * a->dmax);
 506     a->top = 0;
 507     a->neg = 0;
 508 }
 509
 510 BN_ULONG BN_get_word(const BIGNUM *a)
 511 {
 512     if (a->top > 1)
 513         return BN_MASK2;
 514     else if (a->top == 1)
 515         return a->d[0];
 516     /* a->top == 0 */
 517     return 0;
 518 }
 519
 520 int BN_set_word(BIGNUM *a, BN_ULONG w)
 521 {
 522     bn_check_top(a);
 523     if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
 524         return (0);
 525     a->neg = 0;
 526     a->d[0] = w;
 527     a->top = (w ? 1 : 0);
 528     bn_check_top(a);
 529     return (1);
 530 }
 531
 532 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
 533 {
 534     unsigned int i, m;
 535     unsigned int n;
 536     BN_ULONG l;
 537     BIGNUM *bn = NULL;
 538
 539     if (ret == NULL)
 540         ret = bn = BN_new();
 541     if (ret == NULL)
 542         return (NULL);
 543     bn_check_top(ret);
 544     /* Skip leading zero's. */
 545     for ( ; len > 0 && *s == 0; s++, len--)
 546         continue;
 547     n = len;
 548     if (n == 0) {
 549         ret->top = 0;
 550         return (ret);
 551     }
 552     i = ((n - 1) / BN_BYTES) + 1;
 553     m = ((n - 1) % (BN_BYTES));
 554     if (bn_wexpand(ret, (int)i) == NULL) {
 555         BN_free(bn);
 556         return NULL;
 557     }
 558     ret->top = i;
 559     ret->neg = 0;
 560     l = 0;
 561     while (n--) {
 562         l = (l << 8L) | *(s++);
 563         if (m-- == 0) {
 564             ret->d[--i] = l;
 565             l = 0;
 566             m = BN_BYTES - 1;
 567         }
 568     }
 569     /*
 570      * need to call this due to clear byte at top if avoiding having the top
 571      * bit set (-ve number)
 572      */
 573     bn_correct_top(ret);
 574     return (ret);
 575 }
 576
 577 /* ignore negative */
 578 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
 579 {
 580     int n, i;
 581     BN_ULONG l;
 582
 583     bn_check_top(a);
 584     n = i = BN_num_bytes(a);
 585     while (i--) {
 586         l = a->d[i / BN_BYTES];
 587         *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
 588     }
 589     return (n);
 590 }
 591
 592 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
 593 {
 594     int i;
 595     BN_ULONG t1, t2, *ap, *bp;
 596
 597     bn_check_top(a);
 598     bn_check_top(b);
 599
 600     i = a->top - b->top;
 601     if (i != 0)
 602         return (i);
 603     ap = a->d;
 604     bp = b->d;
 605     for (i = a->top - 1; i >= 0; i--) {
 606         t1 = ap[i];
 607         t2 = bp[i];
 608         if (t1 != t2)
 609             return ((t1 > t2) ? 1 : -1);
 610     }
 611     return (0);
 612 }
 613
 614 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
 615 {
 616     int i;
 617     int gt, lt;
 618     BN_ULONG t1, t2;
 619
 620     if ((a == NULL) || (b == NULL)) {
 621         if (a != NULL)
 622             return (-1);
 623         else if (b != NULL)
 624             return (1);
 625         else
 626             return (0);
 627     }
 628
 629     bn_check_top(a);
 630     bn_check_top(b);
 631
 632     if (a->neg != b->neg) {
 633         if (a->neg)
 634             return (-1);
 635         else
 636             return (1);
 637     }
 638     if (a->neg == 0) {
 639         gt = 1;
 640         lt = -1;
 641     } else {
 642         gt = -1;
 643         lt = 1;
 644     }
 645
 646     if (a->top > b->top)
 647         return (gt);
 648     if (a->top < b->top)
 649         return (lt);
 650     for (i = a->top - 1; i >= 0; i--) {
 651         t1 = a->d[i];
 652         t2 = b->d[i];
 653         if (t1 > t2)
 654             return (gt);
 655         if (t1 < t2)
 656             return (lt);
 657     }
 658     return (0);
 659 }
 660
 661 int BN_set_bit(BIGNUM *a, int n)
 662 {
 663     int i, j, k;
 664
 665     if (n < 0)
 666         return 0;
 667
 668     i = n / BN_BITS2;
 669     j = n % BN_BITS2;
 670     if (a->top <= i) {
 671         if (bn_wexpand(a, i + 1) == NULL)
 672             return (0);
 673         for (k = a->top; k < i + 1; k++)
 674             a->d[k] = 0;
 675         a->top = i + 1;
 676     }
 677
 678     a->d[i] |= (((BN_ULONG)1) << j);
 679     bn_check_top(a);
 680     return (1);
 681 }
 682
 683 int BN_clear_bit(BIGNUM *a, int n)
 684 {
 685     int i, j;
 686
 687     bn_check_top(a);
 688     if (n < 0)
 689         return 0;
 690
 691     i = n / BN_BITS2;
 692     j = n % BN_BITS2;
 693     if (a->top <= i)
 694         return (0);
 695
 696     a->d[i] &= (~(((BN_ULONG)1) << j));
 697     bn_correct_top(a);
 698     return (1);
 699 }
 700
 701 int BN_is_bit_set(const BIGNUM *a, int n)
 702 {
 703     int i, j;
 704
 705     bn_check_top(a);
 706     if (n < 0)
 707         return 0;
 708     i = n / BN_BITS2;
 709     j = n % BN_BITS2;
 710     if (a->top <= i)
 711         return 0;
 712     return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
 713 }
 714
 715 int BN_mask_bits(BIGNUM *a, int n)
 716 {
 717     int b, w;
 718
 719     bn_check_top(a);
 720     if (n < 0)
 721         return 0;
 722
 723     w = n / BN_BITS2;
 724     b = n % BN_BITS2;
 725     if (w >= a->top)
 726         return 0;
 727     if (b == 0)
 728         a->top = w;
 729     else {
 730         a->top = w + 1;
 731         a->d[w] &= ~(BN_MASK2 << b);
 732     }
 733     bn_correct_top(a);
 734     return (1);
 735 }
 736
 737 void BN_set_negative(BIGNUM *a, int b)
 738 {
 739     if (b && !BN_is_zero(a))
 740         a->neg = 1;
 741     else
 742         a->neg = 0;
 743 }
 744
 745 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
 746 {
 747     int i;
 748     BN_ULONG aa, bb;
 749
 750     aa = a[n - 1];
 751     bb = b[n - 1];
 752     if (aa != bb)
 753         return ((aa > bb) ? 1 : -1);
 754     for (i = n - 2; i >= 0; i--) {
 755         aa = a[i];
 756         bb = b[i];
 757         if (aa != bb)
 758             return ((aa > bb) ? 1 : -1);
 759     }
 760     return (0);
 761 }
 762
 763 /*
 764  * Here follows a specialised variants of bn_cmp_words().  It has the
 765  * property of performing the operation on arrays of different sizes. The
 766  * sizes of those arrays is expressed through cl, which is the common length
 767  * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the
 768  * two lengths, calculated as len(a)-len(b). All lengths are the number of
 769  * BN_ULONGs...
 770  */
 771
 772 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
 773 {
 774     int n, i;
 775     n = cl - 1;
 776
 777     if (dl < 0) {
 778         for (i = dl; i < 0; i++) {
 779             if (b[n - i] != 0)
 780                 return -1;      /* a < b */
 781         }
 782     }
 783     if (dl > 0) {
 784         for (i = dl; i > 0; i--) {
 785             if (a[n + i] != 0)
 786                 return 1;       /* a > b */
 787         }
 788     }
 789     return bn_cmp_words(a, b, cl);
 790 }
 791
 792 /*
 793  * Constant-time conditional swap of a and b.
 794  * a and b are swapped if condition is not 0.  The code assumes that at most one bit of condition is set.
 795  * nwords is the number of words to swap.  The code assumes that at least nwords are allocated in both a and b,
 796  * and that no more than nwords are used by either a or b.
 797  * a and b cannot be the same number
 798  */
 799 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
 800 {
 801     BN_ULONG t;
 802     int i;
 803
 804     bn_wcheck_size(a, nwords);
 805     bn_wcheck_size(b, nwords);
 806
 807     assert(a != b);
 808     assert((condition & (condition - 1)) == 0);
 809     assert(sizeof(BN_ULONG) >= sizeof(int));
 810
 811     condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
 812
 813     t = (a->top ^ b->top) & condition;
 814     a->top ^= t;
 815     b->top ^= t;
 816
 817 #define BN_CONSTTIME_SWAP(ind) \
 818         do { \
 819                 t = (a->d[ind] ^ b->d[ind]) & condition; \
 820                 a->d[ind] ^= t; \
 821                 b->d[ind] ^= t; \
 822         } while (0)
 823
 824     switch (nwords) {
 825     default:
 826         for (i = 10; i < nwords; i++)
 827             BN_CONSTTIME_SWAP(i);
 828         /* Fallthrough */
 829     case 10:
 830         BN_CONSTTIME_SWAP(9);   /* Fallthrough */
 831     case 9:
 832         BN_CONSTTIME_SWAP(8);   /* Fallthrough */
 833     case 8:
 834         BN_CONSTTIME_SWAP(7);   /* Fallthrough */
 835     case 7:
 836         BN_CONSTTIME_SWAP(6);   /* Fallthrough */
 837     case 6:
 838         BN_CONSTTIME_SWAP(5);   /* Fallthrough */
 839     case 5:
 840         BN_CONSTTIME_SWAP(4);   /* Fallthrough */
 841     case 4:
 842         BN_CONSTTIME_SWAP(3);   /* Fallthrough */
 843     case 3:
 844         BN_CONSTTIME_SWAP(2);   /* Fallthrough */
 845     case 2:
 846         BN_CONSTTIME_SWAP(1);   /* Fallthrough */
 847     case 1:
 848         BN_CONSTTIME_SWAP(0);
 849     }
 850 #undef BN_CONSTTIME_SWAP
 851 }
 852
 853 /* Bits of security, see SP800-57 */
 854
 855 int BN_security_bits(int L, int N)
 856 {
 857     int secbits, bits;
 858     if (L >= 15360)
 859         secbits = 256;
 860     else if (L >= 7690)
 861         secbits = 192;
 862     else if (L >= 3072)
 863         secbits = 128;
 864     else if (L >= 2048)
 865         secbits = 112;
 866     else if (L >= 1024)
 867         secbits = 80;
 868     else
 869         return 0;
 870     if (N == -1)
 871         return secbits;
 872     bits = N / 2;
 873     if (bits < 80)
 874         return 0;
 875     return bits >= secbits ? secbits : bits;
 876 }
 877
 878 void BN_zero_ex(BIGNUM *a)
 879 {
 880     a->top = 0;
 881     a->neg = 0;
 882 }
 883
 884 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
 885 {
 886     return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
 887 }
 888
 889 int BN_is_zero(const BIGNUM *a)
 890 {
 891     return a->top == 0;
 892 }
 893
 894 int BN_is_one(const BIGNUM *a)
 895 {
 896     return BN_abs_is_word(a, 1) && !a->neg;
 897 }
 898
 899 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
 900 {
 901     return BN_abs_is_word(a, w) && (!w || !a->neg);
 902 }
 903
 904 int BN_is_odd(const BIGNUM *a)
 905 {
 906     return (a->top > 0) && (a->d[0] & 1);
 907 }
 908
 909 int BN_is_negative(const BIGNUM *a)
 910 {
 911     return (a->neg != 0);
 912 }
 913
 914 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
 915                      BN_CTX *ctx)
 916 {
 917     return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
 918 }
 919
 920 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
 921 {
 922     dest->d = b->d;
 923     dest->top = b->top;
 924     dest->dmax = b->dmax;
 925     dest->neg = b->neg;
 926     dest->flags = ((dest->flags & BN_FLG_MALLOCED)
 927                    | (b->flags & ~BN_FLG_MALLOCED)
 928                    | BN_FLG_STATIC_DATA | flags);
 929 }
 930
 931 BN_GENCB *BN_GENCB_new(void)
 932 {
 933     BN_GENCB *ret;
 934
 935     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
 936         BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
 937         return (NULL);
 938     }
 939
 940     return ret;
 941 }
 942
 943 void BN_GENCB_free(BN_GENCB *cb)
 944 {
 945     if (cb == NULL)
 946         return;
 947     OPENSSL_free(cb);
 948 }
 949
 950 void BN_set_flags(BIGNUM *b, int n)
 951 {
 952     b->flags |= n;
 953 }
 954
 955 int BN_get_flags(const BIGNUM *b, int n)
 956 {
 957     return b->flags & n;
 958 }
 959
 960 /* Populate a BN_GENCB structure with an "old"-style callback */
 961 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
 962                       void *cb_arg)
 963 {
 964     BN_GENCB *tmp_gencb = gencb;
 965     tmp_gencb->ver = 1;
 966     tmp_gencb->arg = cb_arg;
 967     tmp_gencb->cb.cb_1 = callback;
 968 }
 969
 970 /* Populate a BN_GENCB structure with a "new"-style callback */
 971 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
 972                   void *cb_arg)
 973 {
 974     BN_GENCB *tmp_gencb = gencb;
 975     tmp_gencb->ver = 2;
 976     tmp_gencb->arg = cb_arg;
 977     tmp_gencb->cb.cb_2 = callback;
 978 }
 979
 980 void *BN_GENCB_get_arg(BN_GENCB *cb)
 981 {
 982     return cb->arg;
 983 }
 984
 985 BIGNUM *bn_wexpand(BIGNUM *a, int words)
 986 {
 987     return (words <= a->dmax) ? a : bn_expand2(a, words);
 988 }
 989
 990 void bn_correct_top(BIGNUM *a)
 991 {
 992     BN_ULONG *ftl;
 993     int tmp_top = a->top;
 994
 995     if (tmp_top > 0) {
 996         for (ftl = &(a->d[tmp_top - 1]); tmp_top > 0; tmp_top--)
 997             if (*(ftl--))
 998                 break;
 999         a->top = tmp_top;
1000     }
1001     bn_pollute(a);
1002 }