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