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