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