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