crypto/bn/bn_lib.c

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