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