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         memset(a->d, 0, 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 - 1;
 569     /* Skip trailing zeroes. */
 570     for ( ; len > 0 && *s == 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         l = (l << 8L) | *(s--);
 588         if (m-- == 0) {
 589             ret->d[--i] = l;
 590             l = 0;
 591             m = BN_BYTES - 1;
 592         }
 593     }
 594     /*
 595      * need to call this due to clear byte at top if avoiding having the top
 596      * bit set (-ve number)
 597      */
 598     bn_correct_top(ret);
 599     return ret;
 600 }
 601
 602 int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
 603 {
 604     int i;
 605     BN_ULONG l;
 606     bn_check_top(a);
 607     i = BN_num_bytes(a);
 608     if (tolen < i)
 609         return -1;
 610     /* Add trailing zeroes if necessary */
 611     if (tolen > i)
 612         memset(to + i, 0, tolen - i);
 613     to += i - 1;
 614     while (i--) {
 615         l = a->d[i / BN_BYTES];
 616         *(to--) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
 617     }
 618     return tolen;
 619 }
 620
 621 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
 622 {
 623     int i;
 624     BN_ULONG t1, t2, *ap, *bp;
 625
 626     bn_check_top(a);
 627     bn_check_top(b);
 628
 629     i = a->top - b->top;
 630     if (i != 0)
 631         return (i);
 632     ap = a->d;
 633     bp = b->d;
 634     for (i = a->top - 1; i >= 0; i--) {
 635         t1 = ap[i];
 636         t2 = bp[i];
 637         if (t1 != t2)
 638             return ((t1 > t2) ? 1 : -1);
 639     }
 640     return (0);
 641 }
 642
 643 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
 644 {
 645     int i;
 646     int gt, lt;
 647     BN_ULONG t1, t2;
 648
 649     if ((a == NULL) || (b == NULL)) {
 650         if (a != NULL)
 651             return (-1);
 652         else if (b != NULL)
 653             return (1);
 654         else
 655             return (0);
 656     }
 657
 658     bn_check_top(a);
 659     bn_check_top(b);
 660
 661     if (a->neg != b->neg) {
 662         if (a->neg)
 663             return (-1);
 664         else
 665             return (1);
 666     }
 667     if (a->neg == 0) {
 668         gt = 1;
 669         lt = -1;
 670     } else {
 671         gt = -1;
 672         lt = 1;
 673     }
 674
 675     if (a->top > b->top)
 676         return (gt);
 677     if (a->top < b->top)
 678         return (lt);
 679     for (i = a->top - 1; i >= 0; i--) {
 680         t1 = a->d[i];
 681         t2 = b->d[i];
 682         if (t1 > t2)
 683             return (gt);
 684         if (t1 < t2)
 685             return (lt);
 686     }
 687     return (0);
 688 }
 689
 690 int BN_set_bit(BIGNUM *a, int n)
 691 {
 692     int i, j, k;
 693
 694     if (n < 0)
 695         return 0;
 696
 697     i = n / BN_BITS2;
 698     j = n % BN_BITS2;
 699     if (a->top <= i) {
 700         if (bn_wexpand(a, i + 1) == NULL)
 701             return (0);
 702         for (k = a->top; k < i + 1; k++)
 703             a->d[k] = 0;
 704         a->top = i + 1;
 705     }
 706
 707     a->d[i] |= (((BN_ULONG)1) << j);
 708     bn_check_top(a);
 709     return (1);
 710 }
 711
 712 int BN_clear_bit(BIGNUM *a, int n)
 713 {
 714     int i, j;
 715
 716     bn_check_top(a);
 717     if (n < 0)
 718         return 0;
 719
 720     i = n / BN_BITS2;
 721     j = n % BN_BITS2;
 722     if (a->top <= i)
 723         return (0);
 724
 725     a->d[i] &= (~(((BN_ULONG)1) << j));
 726     bn_correct_top(a);
 727     return (1);
 728 }
 729
 730 int BN_is_bit_set(const BIGNUM *a, int n)
 731 {
 732     int i, j;
 733
 734     bn_check_top(a);
 735     if (n < 0)
 736         return 0;
 737     i = n / BN_BITS2;
 738     j = n % BN_BITS2;
 739     if (a->top <= i)
 740         return 0;
 741     return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
 742 }
 743
 744 int BN_mask_bits(BIGNUM *a, int n)
 745 {
 746     int b, w;
 747
 748     bn_check_top(a);
 749     if (n < 0)
 750         return 0;
 751
 752     w = n / BN_BITS2;
 753     b = n % BN_BITS2;
 754     if (w >= a->top)
 755         return 0;
 756     if (b == 0)
 757         a->top = w;
 758     else {
 759         a->top = w + 1;
 760         a->d[w] &= ~(BN_MASK2 << b);
 761     }
 762     bn_correct_top(a);
 763     return (1);
 764 }
 765
 766 void BN_set_negative(BIGNUM *a, int b)
 767 {
 768     if (b && !BN_is_zero(a))
 769         a->neg = 1;
 770     else
 771         a->neg = 0;
 772 }
 773
 774 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
 775 {
 776     int i;
 777     BN_ULONG aa, bb;
 778
 779     aa = a[n - 1];
 780     bb = b[n - 1];
 781     if (aa != bb)
 782         return ((aa > bb) ? 1 : -1);
 783     for (i = n - 2; i >= 0; i--) {
 784         aa = a[i];
 785         bb = b[i];
 786         if (aa != bb)
 787             return ((aa > bb) ? 1 : -1);
 788     }
 789     return (0);
 790 }
 791
 792 /*
 793  * Here follows a specialised variants of bn_cmp_words().  It has the
 794  * capability of performing the operation on arrays of different sizes. The
 795  * sizes of those arrays is expressed through cl, which is the common length
 796  * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the
 797  * two lengths, calculated as len(a)-len(b). All lengths are the number of
 798  * BN_ULONGs...
 799  */
 800
 801 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
 802 {
 803     int n, i;
 804     n = cl - 1;
 805
 806     if (dl < 0) {
 807         for (i = dl; i < 0; i++) {
 808             if (b[n - i] != 0)
 809                 return -1;      /* a < b */
 810         }
 811     }
 812     if (dl > 0) {
 813         for (i = dl; i > 0; i--) {
 814             if (a[n + i] != 0)
 815                 return 1;       /* a > b */
 816         }
 817     }
 818     return bn_cmp_words(a, b, cl);
 819 }
 820
 821 /*
 822  * Constant-time conditional swap of a and b.
 823  * a and b are swapped if condition is not 0.  The code assumes that at most one bit of condition is set.
 824  * nwords is the number of words to swap.  The code assumes that at least nwords are allocated in both a and b,
 825  * and that no more than nwords are used by either a or b.
 826  * a and b cannot be the same number
 827  */
 828 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
 829 {
 830     BN_ULONG t;
 831     int i;
 832
 833     bn_wcheck_size(a, nwords);
 834     bn_wcheck_size(b, nwords);
 835
 836     assert(a != b);
 837     assert((condition & (condition - 1)) == 0);
 838     assert(sizeof(BN_ULONG) >= sizeof(int));
 839
 840     condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
 841
 842     t = (a->top ^ b->top) & condition;
 843     a->top ^= t;
 844     b->top ^= t;
 845
 846 #define BN_CONSTTIME_SWAP(ind) \
 847         do { \
 848                 t = (a->d[ind] ^ b->d[ind]) & condition; \
 849                 a->d[ind] ^= t; \
 850                 b->d[ind] ^= t; \
 851         } while (0)
 852
 853     switch (nwords) {
 854     default:
 855         for (i = 10; i < nwords; i++)
 856             BN_CONSTTIME_SWAP(i);
 857         /* Fallthrough */
 858     case 10:
 859         BN_CONSTTIME_SWAP(9);   /* Fallthrough */
 860     case 9:
 861         BN_CONSTTIME_SWAP(8);   /* Fallthrough */
 862     case 8:
 863         BN_CONSTTIME_SWAP(7);   /* Fallthrough */
 864     case 7:
 865         BN_CONSTTIME_SWAP(6);   /* Fallthrough */
 866     case 6:
 867         BN_CONSTTIME_SWAP(5);   /* Fallthrough */
 868     case 5:
 869         BN_CONSTTIME_SWAP(4);   /* Fallthrough */
 870     case 4:
 871         BN_CONSTTIME_SWAP(3);   /* Fallthrough */
 872     case 3:
 873         BN_CONSTTIME_SWAP(2);   /* Fallthrough */
 874     case 2:
 875         BN_CONSTTIME_SWAP(1);   /* Fallthrough */
 876     case 1:
 877         BN_CONSTTIME_SWAP(0);
 878     }
 879 #undef BN_CONSTTIME_SWAP
 880 }
 881
 882 /* Bits of security, see SP800-57 */
 883
 884 int BN_security_bits(int L, int N)
 885 {
 886     int secbits, bits;
 887     if (L >= 15360)
 888         secbits = 256;
 889     else if (L >= 7690)
 890         secbits = 192;
 891     else if (L >= 3072)
 892         secbits = 128;
 893     else if (L >= 2048)
 894         secbits = 112;
 895     else if (L >= 1024)
 896         secbits = 80;
 897     else
 898         return 0;
 899     if (N == -1)
 900         return secbits;
 901     bits = N / 2;
 902     if (bits < 80)
 903         return 0;
 904     return bits >= secbits ? secbits : bits;
 905 }
 906
 907 void BN_zero_ex(BIGNUM *a)
 908 {
 909     a->top = 0;
 910     a->neg = 0;
 911 }
 912
 913 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
 914 {
 915     return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
 916 }
 917
 918 int BN_is_zero(const BIGNUM *a)
 919 {
 920     return a->top == 0;
 921 }
 922
 923 int BN_is_one(const BIGNUM *a)
 924 {
 925     return BN_abs_is_word(a, 1) && !a->neg;
 926 }
 927
 928 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
 929 {
 930     return BN_abs_is_word(a, w) && (!w || !a->neg);
 931 }
 932
 933 int BN_is_odd(const BIGNUM *a)
 934 {
 935     return (a->top > 0) && (a->d[0] & 1);
 936 }
 937
 938 int BN_is_negative(const BIGNUM *a)
 939 {
 940     return (a->neg != 0);
 941 }
 942
 943 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
 944                      BN_CTX *ctx)
 945 {
 946     return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
 947 }
 948
 949 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
 950 {
 951     dest->d = b->d;
 952     dest->top = b->top;
 953     dest->dmax = b->dmax;
 954     dest->neg = b->neg;
 955     dest->flags = ((dest->flags & BN_FLG_MALLOCED)
 956                    | (b->flags & ~BN_FLG_MALLOCED)
 957                    | BN_FLG_STATIC_DATA | flags);
 958 }
 959
 960 BN_GENCB *BN_GENCB_new(void)
 961 {
 962     BN_GENCB *ret;
 963
 964     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
 965         BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
 966         return (NULL);
 967     }
 968
 969     return ret;
 970 }
 971
 972 void BN_GENCB_free(BN_GENCB *cb)
 973 {
 974     if (cb == NULL)
 975         return;
 976     OPENSSL_free(cb);
 977 }
 978
 979 void BN_set_flags(BIGNUM *b, int n)
 980 {
 981     b->flags |= n;
 982 }
 983
 984 int BN_get_flags(const BIGNUM *b, int n)
 985 {
 986     return b->flags & n;
 987 }
 988
 989 /* Populate a BN_GENCB structure with an "old"-style callback */
 990 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
 991                       void *cb_arg)
 992 {
 993     BN_GENCB *tmp_gencb = gencb;
 994     tmp_gencb->ver = 1;
 995     tmp_gencb->arg = cb_arg;
 996     tmp_gencb->cb.cb_1 = callback;
 997 }
 998
 999 /* Populate a BN_GENCB structure with a "new"-style callback */
1000 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
1001                   void *cb_arg)
1002 {
1003     BN_GENCB *tmp_gencb = gencb;
1004     tmp_gencb->ver = 2;
1005     tmp_gencb->arg = cb_arg;
1006     tmp_gencb->cb.cb_2 = callback;
1007 }
1008
1009 void *BN_GENCB_get_arg(BN_GENCB *cb)
1010 {
1011     return cb->arg;
1012 }
1013
1014 BIGNUM *bn_wexpand(BIGNUM *a, int words)
1015 {
1016     return (words <= a->dmax) ? a : bn_expand2(a, words);
1017 }
1018
1019 void bn_correct_top(BIGNUM *a)
1020 {
1021     BN_ULONG *ftl;
1022     int tmp_top = a->top;
1023
1024     if (tmp_top > 0) {
1025         for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) {
1026             ftl--;
1027             if (*ftl != 0)
1028                 break;
1029         }
1030         a->top = tmp_top;
1031     }
1032     bn_pollute(a);
1033 }