crypto/bn/bn_lib.c

   1 /*
   2  * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include <assert.h>
  11 #include <limits.h>
  12 #include "internal/cryptlib.h"
  13 #include "bn_lcl.h"
  14 #include <openssl/opensslconf.h>
  15
  16 /* This stuff appears to be completely unused, so is deprecated */
  17 #if OPENSSL_API_COMPAT < 0x00908000L
  18 /*-
  19  * For a 32 bit machine
  20  * 2 -   4 ==  128
  21  * 3 -   8 ==  256
  22  * 4 -  16 ==  512
  23  * 5 -  32 == 1024
  24  * 6 -  64 == 2048
  25  * 7 - 128 == 4096
  26  * 8 - 256 == 8192
  27  */
  28 static int bn_limit_bits = 0;
  29 static int bn_limit_num = 8;    /* (1<<bn_limit_bits) */
  30 static int bn_limit_bits_low = 0;
  31 static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */
  32 static int bn_limit_bits_high = 0;
  33 static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */
  34 static int bn_limit_bits_mont = 0;
  35 static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */
  36
  37 void BN_set_params(int mult, int high, int low, int mont)
  38 {
  39     if (mult >= 0) {
  40         if (mult > (int)(sizeof(int) * 8) - 1)
  41             mult = sizeof(int) * 8 - 1;
  42         bn_limit_bits = mult;
  43         bn_limit_num = 1 << mult;
  44     }
  45     if (high >= 0) {
  46         if (high > (int)(sizeof(int) * 8) - 1)
  47             high = sizeof(int) * 8 - 1;
  48         bn_limit_bits_high = high;
  49         bn_limit_num_high = 1 << high;
  50     }
  51     if (low >= 0) {
  52         if (low > (int)(sizeof(int) * 8) - 1)
  53             low = sizeof(int) * 8 - 1;
  54         bn_limit_bits_low = low;
  55         bn_limit_num_low = 1 << low;
  56     }
  57     if (mont >= 0) {
  58         if (mont > (int)(sizeof(int) * 8) - 1)
  59             mont = sizeof(int) * 8 - 1;
  60         bn_limit_bits_mont = mont;
  61         bn_limit_num_mont = 1 << mont;
  62     }
  63 }
  64
  65 int BN_get_params(int which)
  66 {
  67     if (which == 0)
  68         return bn_limit_bits;
  69     else if (which == 1)
  70         return bn_limit_bits_high;
  71     else if (which == 2)
  72         return bn_limit_bits_low;
  73     else if (which == 3)
  74         return bn_limit_bits_mont;
  75     else
  76         return 0;
  77 }
  78 #endif
  79
  80 const BIGNUM *BN_value_one(void)
  81 {
  82     static const BN_ULONG data_one = 1L;
  83     static const BIGNUM const_one =
  84         { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA };
  85
  86     return &const_one;
  87 }
  88
  89 int BN_num_bits_word(BN_ULONG l)
  90 {
  91     BN_ULONG x, mask;
  92     int bits = (l != 0);
  93
  94 #if BN_BITS2 > 32
  95     x = l >> 32;
  96     mask = (0 - x) & BN_MASK2;
  97     mask = (0 - (mask >> (BN_BITS2 - 1)));
  98     bits += 32 & mask;
  99     l ^= (x ^ l) & mask;
 100 #endif
 101
 102     x = l >> 16;
 103     mask = (0 - x) & BN_MASK2;
 104     mask = (0 - (mask >> (BN_BITS2 - 1)));
 105     bits += 16 & mask;
 106     l ^= (x ^ l) & mask;
 107
 108     x = l >> 8;
 109     mask = (0 - x) & BN_MASK2;
 110     mask = (0 - (mask >> (BN_BITS2 - 1)));
 111     bits += 8 & mask;
 112     l ^= (x ^ l) & mask;
 113
 114     x = l >> 4;
 115     mask = (0 - x) & BN_MASK2;
 116     mask = (0 - (mask >> (BN_BITS2 - 1)));
 117     bits += 4 & mask;
 118     l ^= (x ^ l) & mask;
 119
 120     x = l >> 2;
 121     mask = (0 - x) & BN_MASK2;
 122     mask = (0 - (mask >> (BN_BITS2 - 1)));
 123     bits += 2 & mask;
 124     l ^= (x ^ l) & mask;
 125
 126     x = l >> 1;
 127     mask = (0 - x) & BN_MASK2;
 128     mask = (0 - (mask >> (BN_BITS2 - 1)));
 129     bits += 1 & mask;
 130
 131     return bits;
 132 }
 133
 134 int BN_num_bits(const BIGNUM *a)
 135 {
 136     int i = a->top - 1;
 137     bn_check_top(a);
 138
 139     if (BN_is_zero(a))
 140         return 0;
 141     return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
 142 }
 143
 144 static void bn_free_d(BIGNUM *a)
 145 {
 146     if (BN_get_flags(a, BN_FLG_SECURE))
 147         OPENSSL_secure_free(a->d);
 148     else
 149         OPENSSL_free(a->d);
 150 }
 151
 152
 153 void BN_clear_free(BIGNUM *a)
 154 {
 155     if (a == NULL)
 156         return;
 157     if (a->d != NULL && !BN_get_flags(a, BN_FLG_STATIC_DATA)) {
 158         OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
 159         bn_free_d(a);
 160     }
 161     if (BN_get_flags(a, BN_FLG_MALLOCED)) {
 162         OPENSSL_cleanse(a, sizeof(*a));
 163         OPENSSL_free(a);
 164     }
 165 }
 166
 167 void BN_free(BIGNUM *a)
 168 {
 169     if (a == NULL)
 170         return;
 171     if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
 172         bn_free_d(a);
 173     if (a->flags & BN_FLG_MALLOCED)
 174         OPENSSL_free(a);
 175 }
 176
 177 void bn_init(BIGNUM *a)
 178 {
 179     static BIGNUM nilbn;
 180
 181     *a = nilbn;
 182     bn_check_top(a);
 183 }
 184
 185 BIGNUM *BN_new(void)
 186 {
 187     BIGNUM *ret;
 188
 189     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
 190         BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
 191         return NULL;
 192     }
 193     ret->flags = BN_FLG_MALLOCED;
 194     bn_check_top(ret);
 195     return ret;
 196 }
 197
 198  BIGNUM *BN_secure_new(void)
 199  {
 200      BIGNUM *ret = BN_new();
 201      if (ret != NULL)
 202          ret->flags |= BN_FLG_SECURE;
 203      return ret;
 204  }
 205
 206 /* This is used by bn_expand2() */
 207 /* The caller MUST check that words > b->dmax before calling this */
 208 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
 209 {
 210     BN_ULONG *a = NULL;
 211
 212     bn_check_top(b);
 213
 214     if (words > (INT_MAX / (4 * BN_BITS2))) {
 215         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
 216         return NULL;
 217     }
 218     if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
 219         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
 220         return NULL;
 221     }
 222     if (BN_get_flags(b, BN_FLG_SECURE))
 223         a = OPENSSL_secure_zalloc(words * sizeof(*a));
 224     else
 225         a = OPENSSL_zalloc(words * sizeof(*a));
 226     if (a == NULL) {
 227         BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
 228         return NULL;
 229     }
 230
 231     assert(b->top <= words);
 232     if (b->top > 0)
 233         memcpy(a, b->d, sizeof(*a) * b->top);
 234
 235     return a;
 236 }
 237
 238 /*
 239  * This is an internal function that should not be used in applications. It
 240  * ensures that 'b' has enough room for a 'words' word number and initialises
 241  * any unused part of b->d with leading zeros. It is mostly used by the
 242  * various BIGNUM routines. If there is an error, NULL is returned. If not,
 243  * 'b' is returned.
 244  */
 245
 246 BIGNUM *bn_expand2(BIGNUM *b, int words)
 247 {
 248     bn_check_top(b);
 249
 250     if (words > b->dmax) {
 251         BN_ULONG *a = bn_expand_internal(b, words);
 252         if (!a)
 253             return NULL;
 254         if (b->d) {
 255             OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0]));
 256             bn_free_d(b);
 257         }
 258         b->d = a;
 259         b->dmax = words;
 260     }
 261
 262     bn_check_top(b);
 263     return b;
 264 }
 265
 266 BIGNUM *BN_dup(const BIGNUM *a)
 267 {
 268     BIGNUM *t;
 269
 270     if (a == NULL)
 271         return NULL;
 272     bn_check_top(a);
 273
 274     t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
 275     if (t == NULL)
 276         return NULL;
 277     if (!BN_copy(t, a)) {
 278         BN_free(t);
 279         return NULL;
 280     }
 281     bn_check_top(t);
 282     return t;
 283 }
 284
 285 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
 286 {
 287     bn_check_top(b);
 288
 289     if (a == b)
 290         return a;
 291     if (bn_wexpand(a, b->top) == NULL)
 292         return NULL;
 293
 294     if (b->top > 0)
 295         memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
 296
 297     a->top = b->top;
 298     a->neg = b->neg;
 299     bn_check_top(a);
 300     return a;
 301 }
 302
 303 void BN_swap(BIGNUM *a, BIGNUM *b)
 304 {
 305     int flags_old_a, flags_old_b;
 306     BN_ULONG *tmp_d;
 307     int tmp_top, tmp_dmax, tmp_neg;
 308
 309     bn_check_top(a);
 310     bn_check_top(b);
 311
 312     flags_old_a = a->flags;
 313     flags_old_b = b->flags;
 314
 315     tmp_d = a->d;
 316     tmp_top = a->top;
 317     tmp_dmax = a->dmax;
 318     tmp_neg = a->neg;
 319
 320     a->d = b->d;
 321     a->top = b->top;
 322     a->dmax = b->dmax;
 323     a->neg = b->neg;
 324
 325     b->d = tmp_d;
 326     b->top = tmp_top;
 327     b->dmax = tmp_dmax;
 328     b->neg = tmp_neg;
 329
 330     a->flags =
 331         (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
 332     b->flags =
 333         (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
 334     bn_check_top(a);
 335     bn_check_top(b);
 336 }
 337
 338 void BN_clear(BIGNUM *a)
 339 {
 340     bn_check_top(a);
 341     if (a->d != NULL)
 342         OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax);
 343     a->top = 0;
 344     a->neg = 0;
 345 }
 346
 347 BN_ULONG BN_get_word(const BIGNUM *a)
 348 {
 349     if (a->top > 1)
 350         return BN_MASK2;
 351     else if (a->top == 1)
 352         return a->d[0];
 353     /* a->top == 0 */
 354     return 0;
 355 }
 356
 357 int BN_set_word(BIGNUM *a, BN_ULONG w)
 358 {
 359     bn_check_top(a);
 360     if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
 361         return 0;
 362     a->neg = 0;
 363     a->d[0] = w;
 364     a->top = (w ? 1 : 0);
 365     bn_check_top(a);
 366     return 1;
 367 }
 368
 369 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
 370 {
 371     unsigned int i, m;
 372     unsigned int n;
 373     BN_ULONG l;
 374     BIGNUM *bn = NULL;
 375
 376     if (ret == NULL)
 377         ret = bn = BN_new();
 378     if (ret == NULL)
 379         return NULL;
 380     bn_check_top(ret);
 381     /* Skip leading zero's. */
 382     for ( ; len > 0 && *s == 0; s++, len--)
 383         continue;
 384     n = len;
 385     if (n == 0) {
 386         ret->top = 0;
 387         return ret;
 388     }
 389     i = ((n - 1) / BN_BYTES) + 1;
 390     m = ((n - 1) % (BN_BYTES));
 391     if (bn_wexpand(ret, (int)i) == NULL) {
 392         BN_free(bn);
 393         return NULL;
 394     }
 395     ret->top = i;
 396     ret->neg = 0;
 397     l = 0;
 398     while (n--) {
 399         l = (l << 8L) | *(s++);
 400         if (m-- == 0) {
 401             ret->d[--i] = l;
 402             l = 0;
 403             m = BN_BYTES - 1;
 404         }
 405     }
 406     /*
 407      * need to call this due to clear byte at top if avoiding having the top
 408      * bit set (-ve number)
 409      */
 410     bn_correct_top(ret);
 411     return ret;
 412 }
 413
 414 /* ignore negative */
 415 static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
 416 {
 417     int i;
 418     BN_ULONG l;
 419
 420     bn_check_top(a);
 421     i = BN_num_bytes(a);
 422     if (tolen == -1)
 423         tolen = i;
 424     else if (tolen < i)
 425         return -1;
 426     /* Add leading zeroes if necessary */
 427     if (tolen > i) {
 428         memset(to, 0, tolen - i);
 429         to += tolen - i;
 430     }
 431     while (i--) {
 432         l = a->d[i / BN_BYTES];
 433         *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
 434     }
 435     return tolen;
 436 }
 437
 438 int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
 439 {
 440     if (tolen < 0)
 441         return -1;
 442     return bn2binpad(a, to, tolen);
 443 }
 444
 445 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
 446 {
 447     return bn2binpad(a, to, -1);
 448 }
 449
 450 BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
 451 {
 452     unsigned int i, m;
 453     unsigned int n;
 454     BN_ULONG l;
 455     BIGNUM *bn = NULL;
 456
 457     if (ret == NULL)
 458         ret = bn = BN_new();
 459     if (ret == NULL)
 460         return NULL;
 461     bn_check_top(ret);
 462     s += len;
 463     /* Skip trailing zeroes. */
 464     for ( ; len > 0 && s[-1] == 0; s--, len--)
 465         continue;
 466     n = len;
 467     if (n == 0) {
 468         ret->top = 0;
 469         return ret;
 470     }
 471     i = ((n - 1) / BN_BYTES) + 1;
 472     m = ((n - 1) % (BN_BYTES));
 473     if (bn_wexpand(ret, (int)i) == NULL) {
 474         BN_free(bn);
 475         return NULL;
 476     }
 477     ret->top = i;
 478     ret->neg = 0;
 479     l = 0;
 480     while (n--) {
 481         s--;
 482         l = (l << 8L) | *s;
 483         if (m-- == 0) {
 484             ret->d[--i] = l;
 485             l = 0;
 486             m = BN_BYTES - 1;
 487         }
 488     }
 489     /*
 490      * need to call this due to clear byte at top if avoiding having the top
 491      * bit set (-ve number)
 492      */
 493     bn_correct_top(ret);
 494     return ret;
 495 }
 496
 497 int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
 498 {
 499     int i;
 500     BN_ULONG l;
 501     bn_check_top(a);
 502     i = BN_num_bytes(a);
 503     if (tolen < i)
 504         return -1;
 505     /* Add trailing zeroes if necessary */
 506     if (tolen > i)
 507         memset(to + i, 0, tolen - i);
 508     to += i;
 509     while (i--) {
 510         l = a->d[i / BN_BYTES];
 511         to--;
 512         *to = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
 513     }
 514     return tolen;
 515 }
 516
 517 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
 518 {
 519     int i;
 520     BN_ULONG t1, t2, *ap, *bp;
 521
 522     bn_check_top(a);
 523     bn_check_top(b);
 524
 525     i = a->top - b->top;
 526     if (i != 0)
 527         return i;
 528     ap = a->d;
 529     bp = b->d;
 530     for (i = a->top - 1; i >= 0; i--) {
 531         t1 = ap[i];
 532         t2 = bp[i];
 533         if (t1 != t2)
 534             return ((t1 > t2) ? 1 : -1);
 535     }
 536     return 0;
 537 }
 538
 539 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
 540 {
 541     int i;
 542     int gt, lt;
 543     BN_ULONG t1, t2;
 544
 545     if ((a == NULL) || (b == NULL)) {
 546         if (a != NULL)
 547             return -1;
 548         else if (b != NULL)
 549             return 1;
 550         else
 551             return 0;
 552     }
 553
 554     bn_check_top(a);
 555     bn_check_top(b);
 556
 557     if (a->neg != b->neg) {
 558         if (a->neg)
 559             return -1;
 560         else
 561             return 1;
 562     }
 563     if (a->neg == 0) {
 564         gt = 1;
 565         lt = -1;
 566     } else {
 567         gt = -1;
 568         lt = 1;
 569     }
 570
 571     if (a->top > b->top)
 572         return gt;
 573     if (a->top < b->top)
 574         return lt;
 575     for (i = a->top - 1; i >= 0; i--) {
 576         t1 = a->d[i];
 577         t2 = b->d[i];
 578         if (t1 > t2)
 579             return gt;
 580         if (t1 < t2)
 581             return lt;
 582     }
 583     return 0;
 584 }
 585
 586 int BN_set_bit(BIGNUM *a, int n)
 587 {
 588     int i, j, k;
 589
 590     if (n < 0)
 591         return 0;
 592
 593     i = n / BN_BITS2;
 594     j = n % BN_BITS2;
 595     if (a->top <= i) {
 596         if (bn_wexpand(a, i + 1) == NULL)
 597             return 0;
 598         for (k = a->top; k < i + 1; k++)
 599             a->d[k] = 0;
 600         a->top = i + 1;
 601     }
 602
 603     a->d[i] |= (((BN_ULONG)1) << j);
 604     bn_check_top(a);
 605     return 1;
 606 }
 607
 608 int BN_clear_bit(BIGNUM *a, int n)
 609 {
 610     int i, j;
 611
 612     bn_check_top(a);
 613     if (n < 0)
 614         return 0;
 615
 616     i = n / BN_BITS2;
 617     j = n % BN_BITS2;
 618     if (a->top <= i)
 619         return 0;
 620
 621     a->d[i] &= (~(((BN_ULONG)1) << j));
 622     bn_correct_top(a);
 623     return 1;
 624 }
 625
 626 int BN_is_bit_set(const BIGNUM *a, int n)
 627 {
 628     int i, j;
 629
 630     bn_check_top(a);
 631     if (n < 0)
 632         return 0;
 633     i = n / BN_BITS2;
 634     j = n % BN_BITS2;
 635     if (a->top <= i)
 636         return 0;
 637     return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
 638 }
 639
 640 int BN_mask_bits(BIGNUM *a, int n)
 641 {
 642     int b, w;
 643
 644     bn_check_top(a);
 645     if (n < 0)
 646         return 0;
 647
 648     w = n / BN_BITS2;
 649     b = n % BN_BITS2;
 650     if (w >= a->top)
 651         return 0;
 652     if (b == 0)
 653         a->top = w;
 654     else {
 655         a->top = w + 1;
 656         a->d[w] &= ~(BN_MASK2 << b);
 657     }
 658     bn_correct_top(a);
 659     return 1;
 660 }
 661
 662 void BN_set_negative(BIGNUM *a, int b)
 663 {
 664     if (b && !BN_is_zero(a))
 665         a->neg = 1;
 666     else
 667         a->neg = 0;
 668 }
 669
 670 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
 671 {
 672     int i;
 673     BN_ULONG aa, bb;
 674
 675     aa = a[n - 1];
 676     bb = b[n - 1];
 677     if (aa != bb)
 678         return ((aa > bb) ? 1 : -1);
 679     for (i = n - 2; i >= 0; i--) {
 680         aa = a[i];
 681         bb = b[i];
 682         if (aa != bb)
 683             return ((aa > bb) ? 1 : -1);
 684     }
 685     return 0;
 686 }
 687
 688 /*
 689  * Here follows a specialised variants of bn_cmp_words().  It has the
 690  * capability of performing the operation on arrays of different sizes. The
 691  * sizes of those arrays is expressed through cl, which is the common length
 692  * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the
 693  * two lengths, calculated as len(a)-len(b). All lengths are the number of
 694  * BN_ULONGs...
 695  */
 696
 697 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
 698 {
 699     int n, i;
 700     n = cl - 1;
 701
 702     if (dl < 0) {
 703         for (i = dl; i < 0; i++) {
 704             if (b[n - i] != 0)
 705                 return -1;      /* a < b */
 706         }
 707     }
 708     if (dl > 0) {
 709         for (i = dl; i > 0; i--) {
 710             if (a[n + i] != 0)
 711                 return 1;       /* a > b */
 712         }
 713     }
 714     return bn_cmp_words(a, b, cl);
 715 }
 716
 717 /*
 718  * Constant-time conditional swap of a and b.
 719  * a and b are swapped if condition is not 0.  The code assumes that at most one bit of condition is set.
 720  * nwords is the number of words to swap.  The code assumes that at least nwords are allocated in both a and b,
 721  * and that no more than nwords are used by either a or b.
 722  * a and b cannot be the same number
 723  */
 724 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
 725 {
 726     BN_ULONG t;
 727     int i;
 728
 729     bn_wcheck_size(a, nwords);
 730     bn_wcheck_size(b, nwords);
 731
 732     assert(a != b);
 733     assert((condition & (condition - 1)) == 0);
 734     assert(sizeof(BN_ULONG) >= sizeof(int));
 735
 736     condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
 737
 738     t = (a->top ^ b->top) & condition;
 739     a->top ^= t;
 740     b->top ^= t;
 741
 742 #define BN_CONSTTIME_SWAP(ind) \
 743         do { \
 744                 t = (a->d[ind] ^ b->d[ind]) & condition; \
 745                 a->d[ind] ^= t; \
 746                 b->d[ind] ^= t; \
 747         } while (0)
 748
 749     switch (nwords) {
 750     default:
 751         for (i = 10; i < nwords; i++)
 752             BN_CONSTTIME_SWAP(i);
 753         /* Fallthrough */
 754     case 10:
 755         BN_CONSTTIME_SWAP(9);   /* Fallthrough */
 756     case 9:
 757         BN_CONSTTIME_SWAP(8);   /* Fallthrough */
 758     case 8:
 759         BN_CONSTTIME_SWAP(7);   /* Fallthrough */
 760     case 7:
 761         BN_CONSTTIME_SWAP(6);   /* Fallthrough */
 762     case 6:
 763         BN_CONSTTIME_SWAP(5);   /* Fallthrough */
 764     case 5:
 765         BN_CONSTTIME_SWAP(4);   /* Fallthrough */
 766     case 4:
 767         BN_CONSTTIME_SWAP(3);   /* Fallthrough */
 768     case 3:
 769         BN_CONSTTIME_SWAP(2);   /* Fallthrough */
 770     case 2:
 771         BN_CONSTTIME_SWAP(1);   /* Fallthrough */
 772     case 1:
 773         BN_CONSTTIME_SWAP(0);
 774     }
 775 #undef BN_CONSTTIME_SWAP
 776 }
 777
 778 /* Bits of security, see SP800-57 */
 779
 780 int BN_security_bits(int L, int N)
 781 {
 782     int secbits, bits;
 783     if (L >= 15360)
 784         secbits = 256;
 785     else if (L >= 7680)
 786         secbits = 192;
 787     else if (L >= 3072)
 788         secbits = 128;
 789     else if (L >= 2048)
 790         secbits = 112;
 791     else if (L >= 1024)
 792         secbits = 80;
 793     else
 794         return 0;
 795     if (N == -1)
 796         return secbits;
 797     bits = N / 2;
 798     if (bits < 80)
 799         return 0;
 800     return bits >= secbits ? secbits : bits;
 801 }
 802
 803 void BN_zero_ex(BIGNUM *a)
 804 {
 805     a->top = 0;
 806     a->neg = 0;
 807 }
 808
 809 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
 810 {
 811     return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
 812 }
 813
 814 int BN_is_zero(const BIGNUM *a)
 815 {
 816     return a->top == 0;
 817 }
 818
 819 int BN_is_one(const BIGNUM *a)
 820 {
 821     return BN_abs_is_word(a, 1) && !a->neg;
 822 }
 823
 824 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
 825 {
 826     return BN_abs_is_word(a, w) && (!w || !a->neg);
 827 }
 828
 829 int BN_is_odd(const BIGNUM *a)
 830 {
 831     return (a->top > 0) && (a->d[0] & 1);
 832 }
 833
 834 int BN_is_negative(const BIGNUM *a)
 835 {
 836     return (a->neg != 0);
 837 }
 838
 839 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
 840                      BN_CTX *ctx)
 841 {
 842     return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
 843 }
 844
 845 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
 846 {
 847     dest->d = b->d;
 848     dest->top = b->top;
 849     dest->dmax = b->dmax;
 850     dest->neg = b->neg;
 851     dest->flags = ((dest->flags & BN_FLG_MALLOCED)
 852                    | (b->flags & ~BN_FLG_MALLOCED)
 853                    | BN_FLG_STATIC_DATA | flags);
 854 }
 855
 856 BN_GENCB *BN_GENCB_new(void)
 857 {
 858     BN_GENCB *ret;
 859
 860     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
 861         BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
 862         return NULL;
 863     }
 864
 865     return ret;
 866 }
 867
 868 void BN_GENCB_free(BN_GENCB *cb)
 869 {
 870     if (cb == NULL)
 871         return;
 872     OPENSSL_free(cb);
 873 }
 874
 875 void BN_set_flags(BIGNUM *b, int n)
 876 {
 877     b->flags |= n;
 878 }
 879
 880 int BN_get_flags(const BIGNUM *b, int n)
 881 {
 882     return b->flags & n;
 883 }
 884
 885 /* Populate a BN_GENCB structure with an "old"-style callback */
 886 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
 887                       void *cb_arg)
 888 {
 889     BN_GENCB *tmp_gencb = gencb;
 890     tmp_gencb->ver = 1;
 891     tmp_gencb->arg = cb_arg;
 892     tmp_gencb->cb.cb_1 = callback;
 893 }
 894
 895 /* Populate a BN_GENCB structure with a "new"-style callback */
 896 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
 897                   void *cb_arg)
 898 {
 899     BN_GENCB *tmp_gencb = gencb;
 900     tmp_gencb->ver = 2;
 901     tmp_gencb->arg = cb_arg;
 902     tmp_gencb->cb.cb_2 = callback;
 903 }
 904
 905 void *BN_GENCB_get_arg(BN_GENCB *cb)
 906 {
 907     return cb->arg;
 908 }
 909
 910 BIGNUM *bn_wexpand(BIGNUM *a, int words)
 911 {
 912     return (words <= a->dmax) ? a : bn_expand2(a, words);
 913 }
 914
 915 void bn_correct_top(BIGNUM *a)
 916 {
 917     BN_ULONG *ftl;
 918     int tmp_top = a->top;
 919
 920     if (tmp_top > 0) {
 921         for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) {
 922             ftl--;
 923             if (*ftl != 0)
 924                 break;
 925         }
 926         a->top = tmp_top;
 927     }
 928     if (a->top == 0)
 929         a->neg = 0;
 930     bn_pollute(a);
 931 }