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