crypto/bn/bn_lib.c

   1 /* crypto/bn/bn_lib.c */
   2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   3  * All rights reserved.
   4  *
   5  * This package is an SSL implementation written
   6  * by Eric Young (eay@cryptsoft.com).
   7  * The implementation was written so as to conform with Netscapes SSL.
   8  *
   9  * This library is free for commercial and non-commercial use as long as
  10  * the following conditions are aheared to.  The following conditions
  11  * apply to all code found in this distribution, be it the RC4, RSA,
  12  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  13  * included with this distribution is covered by the same copyright terms
  14  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  15  *
  16  * Copyright remains Eric Young's, and as such any Copyright notices in
  17  * the code are not to be removed.
  18  * If this package is used in a product, Eric Young should be given attribution
  19  * as the author of the parts of the library used.
  20  * This can be in the form of a textual message at program startup or
  21  * in documentation (online or textual) provided with the package.
  22  *
  23  * Redistribution and use in source and binary forms, with or without
  24  * modification, are permitted provided that the following conditions
  25  * are met:
  26  * 1. Redistributions of source code must retain the copyright
  27  *    notice, this list of conditions and the following disclaimer.
  28  * 2. Redistributions in binary form must reproduce the above copyright
  29  *    notice, this list of conditions and the following disclaimer in the
  30  *    documentation and/or other materials provided with the distribution.
  31  * 3. All advertising materials mentioning features or use of this software
  32  *    must display the following acknowledgement:
  33  *    "This product includes cryptographic software written by
  34  *     Eric Young (eay@cryptsoft.com)"
  35  *    The word 'cryptographic' can be left out if the rouines from the library
  36  *    being used are not cryptographic related :-).
  37  * 4. If you include any Windows specific code (or a derivative thereof) from
  38  *    the apps directory (application code) you must include an acknowledgement:
  39  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  40  *
  41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  44  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  51  * SUCH DAMAGE.
  52  *
  53  * The licence and distribution terms for any publically available version or
  54  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  55  * copied and put under another distribution licence
  56  * [including the GNU Public Licence.]
  57  */
  58
  59 #ifndef BN_DEBUG
  60 # undef NDEBUG                  /* avoid conflicting definitions */
  61 # define NDEBUG
  62 #endif
  63
  64 #include <assert.h>
  65 #include <limits.h>
  66 #include "cryptlib.h"
  67 #include "bn_lcl.h"
  68
  69 const char BN_version[] = "Big Number" OPENSSL_VERSION_PTEXT;
  70
  71 /* This stuff appears to be completely unused, so is deprecated */
  72 #ifndef OPENSSL_NO_DEPRECATED
  73 /*-
  74  * For a 32 bit machine
  75  * 2 -   4 ==  128
  76  * 3 -   8 ==  256
  77  * 4 -  16 ==  512
  78  * 5 -  32 == 1024
  79  * 6 -  64 == 2048
  80  * 7 - 128 == 4096
  81  * 8 - 256 == 8192
  82  */
  83 static int bn_limit_bits = 0;
  84 static int bn_limit_num = 8;    /* (1<<bn_limit_bits) */
  85 static int bn_limit_bits_low = 0;
  86 static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */
  87 static int bn_limit_bits_high = 0;
  88 static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */
  89 static int bn_limit_bits_mont = 0;
  90 static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */
  91
  92 void BN_set_params(int mult, int high, int low, int mont)
  93 {
  94     if (mult >= 0) {
  95         if (mult > (int)(sizeof(int) * 8) - 1)
  96             mult = sizeof(int) * 8 - 1;
  97         bn_limit_bits = mult;
  98         bn_limit_num = 1 << mult;
  99     }
 100     if (high >= 0) {
 101         if (high > (int)(sizeof(int) * 8) - 1)
 102             high = sizeof(int) * 8 - 1;
 103         bn_limit_bits_high = high;
 104         bn_limit_num_high = 1 << high;
 105     }
 106     if (low >= 0) {
 107         if (low > (int)(sizeof(int) * 8) - 1)
 108             low = sizeof(int) * 8 - 1;
 109         bn_limit_bits_low = low;
 110         bn_limit_num_low = 1 << low;
 111     }
 112     if (mont >= 0) {
 113         if (mont > (int)(sizeof(int) * 8) - 1)
 114             mont = sizeof(int) * 8 - 1;
 115         bn_limit_bits_mont = mont;
 116         bn_limit_num_mont = 1 << mont;
 117     }
 118 }
 119
 120 int BN_get_params(int which)
 121 {
 122     if (which == 0)
 123         return (bn_limit_bits);
 124     else if (which == 1)
 125         return (bn_limit_bits_high);
 126     else if (which == 2)
 127         return (bn_limit_bits_low);
 128     else if (which == 3)
 129         return (bn_limit_bits_mont);
 130     else
 131         return (0);
 132 }
 133 #endif
 134
 135 const BIGNUM *BN_value_one(void)
 136 {
 137     static const BN_ULONG data_one = 1L;
 138     static const BIGNUM const_one =
 139         { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA };
 140
 141     return (&const_one);
 142 }
 143
 144 int BN_num_bits_word(BN_ULONG l)
 145 {
 146     static const unsigned char bits[256] = {
 147         0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
 148         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 149         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 150         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 151         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 152         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 153         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 154         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 155         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 156         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 157         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 158         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 159         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 160         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 161         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 162         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 163     };
 164
 165 #if defined(SIXTY_FOUR_BIT_LONG)
 166     if (l & 0xffffffff00000000L) {
 167         if (l & 0xffff000000000000L) {
 168             if (l & 0xff00000000000000L) {
 169                 return (bits[(int)(l >> 56)] + 56);
 170             } else
 171                 return (bits[(int)(l >> 48)] + 48);
 172         } else {
 173             if (l & 0x0000ff0000000000L) {
 174                 return (bits[(int)(l >> 40)] + 40);
 175             } else
 176                 return (bits[(int)(l >> 32)] + 32);
 177         }
 178     } else
 179 #else
 180 # ifdef SIXTY_FOUR_BIT
 181     if (l & 0xffffffff00000000LL) {
 182         if (l & 0xffff000000000000LL) {
 183             if (l & 0xff00000000000000LL) {
 184                 return (bits[(int)(l >> 56)] + 56);
 185             } else
 186                 return (bits[(int)(l >> 48)] + 48);
 187         } else {
 188             if (l & 0x0000ff0000000000LL) {
 189                 return (bits[(int)(l >> 40)] + 40);
 190             } else
 191                 return (bits[(int)(l >> 32)] + 32);
 192         }
 193     } else
 194 # endif
 195 #endif
 196     {
 197 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 198         if (l & 0xffff0000L) {
 199             if (l & 0xff000000L)
 200                 return (bits[(int)(l >> 24L)] + 24);
 201             else
 202                 return (bits[(int)(l >> 16L)] + 16);
 203         } else
 204 #endif
 205         {
 206 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 207             if (l & 0xff00L)
 208                 return (bits[(int)(l >> 8)] + 8);
 209             else
 210 #endif
 211                 return (bits[(int)(l)]);
 212         }
 213     }
 214 }
 215
 216 int BN_num_bits(const BIGNUM *a)
 217 {
 218     int i = a->top - 1;
 219     bn_check_top(a);
 220
 221     if (BN_is_zero(a))
 222         return 0;
 223     return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
 224 }
 225
 226 void BN_clear_free(BIGNUM *a)
 227 {
 228     int i;
 229
 230     if (a == NULL)
 231         return;
 232     bn_check_top(a);
 233     if (a->d != NULL) {
 234         OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
 235         if (!(BN_get_flags(a, BN_FLG_STATIC_DATA)))
 236             OPENSSL_free(a->d);
 237     }
 238     i = BN_get_flags(a, BN_FLG_MALLOCED);
 239     OPENSSL_cleanse(a, sizeof(BIGNUM));
 240     if (i)
 241         OPENSSL_free(a);
 242 }
 243
 244 void BN_free(BIGNUM *a)
 245 {
 246     if (a == NULL)
 247         return;
 248     bn_check_top(a);
 249     if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
 250         OPENSSL_free(a->d);
 251     if (a->flags & BN_FLG_MALLOCED)
 252         OPENSSL_free(a);
 253     else {
 254 #ifndef OPENSSL_NO_DEPRECATED
 255         a->flags |= BN_FLG_FREE;
 256 #endif
 257         a->d = NULL;
 258     }
 259 }
 260
 261 void BN_init(BIGNUM *a)
 262 {
 263     memset(a, 0, sizeof(BIGNUM));
 264     bn_check_top(a);
 265 }
 266
 267 BIGNUM *BN_new(void)
 268 {
 269     BIGNUM *ret;
 270
 271     if ((ret = OPENSSL_malloc(sizeof(BIGNUM))) == NULL) {
 272         BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
 273         return (NULL);
 274     }
 275     ret->flags = BN_FLG_MALLOCED;
 276     ret->top = 0;
 277     ret->neg = 0;
 278     ret->dmax = 0;
 279     ret->d = NULL;
 280     bn_check_top(ret);
 281     return (ret);
 282 }
 283
 284 /* This is used both by bn_expand2() and bn_dup_expand() */
 285 /* The caller MUST check that words > b->dmax before calling this */
 286 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
 287 {
 288     BN_ULONG *A, *a = NULL;
 289     const BN_ULONG *B;
 290     int i;
 291
 292     bn_check_top(b);
 293
 294     if (words > (INT_MAX / (4 * BN_BITS2))) {
 295         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
 296         return NULL;
 297     }
 298     if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
 299         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
 300         return (NULL);
 301     }
 302     a = A = OPENSSL_malloc(sizeof(BN_ULONG) * words);
 303     if (A == NULL) {
 304         BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
 305         return (NULL);
 306     }
 307 #ifdef PURIFY
 308     /*
 309      * Valgrind complains in BN_consttime_swap because we process the whole
 310      * array even if it's not initialised yet. This doesn't matter in that
 311      * function - what's important is constant time operation (we're not
 312      * actually going to use the data)
 313      */
 314     memset(a, 0, sizeof(BN_ULONG) * words);
 315 #endif
 316
 317 #if 1
 318     B = b->d;
 319     /* Check if the previous number needs to be copied */
 320     if (B != NULL) {
 321         for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
 322             /*
 323              * The fact that the loop is unrolled
 324              * 4-wise is a tribute to Intel. It's
 325              * the one that doesn't have enough
 326              * registers to accomodate more data.
 327              * I'd unroll it 8-wise otherwise:-)
 328              *
 329              *              <appro@fy.chalmers.se>
 330              */
 331             BN_ULONG a0, a1, a2, a3;
 332             a0 = B[0];
 333             a1 = B[1];
 334             a2 = B[2];
 335             a3 = B[3];
 336             A[0] = a0;
 337             A[1] = a1;
 338             A[2] = a2;
 339             A[3] = a3;
 340         }
 341         /*
 342          * workaround for ultrix cc: without 'case 0', the optimizer does
 343          * the switch table by doing a=top&3; a--; goto jump_table[a];
 344          * which fails for top== 0
 345          */
 346         switch (b->top & 3) {
 347         case 3:
 348             A[2] = B[2];
 349         case 2:
 350             A[1] = B[1];
 351         case 1:
 352             A[0] = B[0];
 353         case 0:
 354             ;
 355         }
 356     }
 357 #else
 358     memset(A, 0, sizeof(BN_ULONG) * words);
 359     memcpy(A, b->d, sizeof(b->d[0]) * b->top);
 360 #endif
 361
 362     return (a);
 363 }
 364
 365 /*
 366  * This is an internal function that should not be used in applications. It
 367  * ensures that 'b' has enough room for a 'words' word number and initialises
 368  * any unused part of b->d with leading zeros. It is mostly used by the
 369  * various BIGNUM routines. If there is an error, NULL is returned. If not,
 370  * 'b' is returned.
 371  */
 372
 373 BIGNUM *bn_expand2(BIGNUM *b, int words)
 374 {
 375     bn_check_top(b);
 376
 377     if (words > b->dmax) {
 378         BN_ULONG *a = bn_expand_internal(b, words);
 379         if (!a)
 380             return NULL;
 381         OPENSSL_free(b->d);
 382         b->d = a;
 383         b->dmax = words;
 384     }
 385
 386     bn_check_top(b);
 387     return b;
 388 }
 389
 390 BIGNUM *BN_dup(const BIGNUM *a)
 391 {
 392     BIGNUM *t;
 393
 394     if (a == NULL)
 395         return NULL;
 396     bn_check_top(a);
 397
 398     t = BN_new();
 399     if (t == NULL)
 400         return NULL;
 401     if (!BN_copy(t, a)) {
 402         BN_free(t);
 403         return NULL;
 404     }
 405     bn_check_top(t);
 406     return t;
 407 }
 408
 409 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
 410 {
 411     int i;
 412     BN_ULONG *A;
 413     const BN_ULONG *B;
 414
 415     bn_check_top(b);
 416
 417     if (a == b)
 418         return (a);
 419     if (bn_wexpand(a, b->top) == NULL)
 420         return (NULL);
 421
 422 #if 1
 423     A = a->d;
 424     B = b->d;
 425     for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
 426         BN_ULONG a0, a1, a2, a3;
 427         a0 = B[0];
 428         a1 = B[1];
 429         a2 = B[2];
 430         a3 = B[3];
 431         A[0] = a0;
 432         A[1] = a1;
 433         A[2] = a2;
 434         A[3] = a3;
 435     }
 436     /* ultrix cc workaround, see comments in bn_expand_internal */
 437     switch (b->top & 3) {
 438     case 3:
 439         A[2] = B[2];
 440     case 2:
 441         A[1] = B[1];
 442     case 1:
 443         A[0] = B[0];
 444     case 0:;
 445     }
 446 #else
 447     memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
 448 #endif
 449
 450     a->top = b->top;
 451     a->neg = b->neg;
 452     bn_check_top(a);
 453     return (a);
 454 }
 455
 456 void BN_swap(BIGNUM *a, BIGNUM *b)
 457 {
 458     int flags_old_a, flags_old_b;
 459     BN_ULONG *tmp_d;
 460     int tmp_top, tmp_dmax, tmp_neg;
 461
 462     bn_check_top(a);
 463     bn_check_top(b);
 464
 465     flags_old_a = a->flags;
 466     flags_old_b = b->flags;
 467
 468     tmp_d = a->d;
 469     tmp_top = a->top;
 470     tmp_dmax = a->dmax;
 471     tmp_neg = a->neg;
 472
 473     a->d = b->d;
 474     a->top = b->top;
 475     a->dmax = b->dmax;
 476     a->neg = b->neg;
 477
 478     b->d = tmp_d;
 479     b->top = tmp_top;
 480     b->dmax = tmp_dmax;
 481     b->neg = tmp_neg;
 482
 483     a->flags =
 484         (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
 485     b->flags =
 486         (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
 487     bn_check_top(a);
 488     bn_check_top(b);
 489 }
 490
 491 void BN_clear(BIGNUM *a)
 492 {
 493     bn_check_top(a);
 494     if (a->d != NULL)
 495         memset(a->d, 0, a->dmax * sizeof(a->d[0]));
 496     a->top = 0;
 497     a->neg = 0;
 498 }
 499
 500 BN_ULONG BN_get_word(const BIGNUM *a)
 501 {
 502     if (a->top > 1)
 503         return BN_MASK2;
 504     else if (a->top == 1)
 505         return a->d[0];
 506     /* a->top == 0 */
 507     return 0;
 508 }
 509
 510 int BN_set_word(BIGNUM *a, BN_ULONG w)
 511 {
 512     bn_check_top(a);
 513     if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
 514         return (0);
 515     a->neg = 0;
 516     a->d[0] = w;
 517     a->top = (w ? 1 : 0);
 518     bn_check_top(a);
 519     return (1);
 520 }
 521
 522 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
 523 {
 524     unsigned int i, m;
 525     unsigned int n;
 526     BN_ULONG l;
 527     BIGNUM *bn = NULL;
 528
 529     if (ret == NULL)
 530         ret = bn = BN_new();
 531     if (ret == NULL)
 532         return (NULL);
 533     bn_check_top(ret);
 534     l = 0;
 535     n = len;
 536     if (n == 0) {
 537         ret->top = 0;
 538         return (ret);
 539     }
 540     i = ((n - 1) / BN_BYTES) + 1;
 541     m = ((n - 1) % (BN_BYTES));
 542     if (bn_wexpand(ret, (int)i) == NULL) {
 543         BN_free(bn);
 544         return NULL;
 545     }
 546     ret->top = i;
 547     ret->neg = 0;
 548     while (n--) {
 549         l = (l << 8L) | *(s++);
 550         if (m-- == 0) {
 551             ret->d[--i] = l;
 552             l = 0;
 553             m = BN_BYTES - 1;
 554         }
 555     }
 556     /*
 557      * need to call this due to clear byte at top if avoiding having the top
 558      * bit set (-ve number)
 559      */
 560     bn_correct_top(ret);
 561     return (ret);
 562 }
 563
 564 /* ignore negative */
 565 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
 566 {
 567     int n, i;
 568     BN_ULONG l;
 569
 570     bn_check_top(a);
 571     n = i = BN_num_bytes(a);
 572     while (i--) {
 573         l = a->d[i / BN_BYTES];
 574         *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
 575     }
 576     return (n);
 577 }
 578
 579 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
 580 {
 581     int i;
 582     BN_ULONG t1, t2, *ap, *bp;
 583
 584     bn_check_top(a);
 585     bn_check_top(b);
 586
 587     i = a->top - b->top;
 588     if (i != 0)
 589         return (i);
 590     ap = a->d;
 591     bp = b->d;
 592     for (i = a->top - 1; i >= 0; i--) {
 593         t1 = ap[i];
 594         t2 = bp[i];
 595         if (t1 != t2)
 596             return ((t1 > t2) ? 1 : -1);
 597     }
 598     return (0);
 599 }
 600
 601 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
 602 {
 603     int i;
 604     int gt, lt;
 605     BN_ULONG t1, t2;
 606
 607     if ((a == NULL) || (b == NULL)) {
 608         if (a != NULL)
 609             return (-1);
 610         else if (b != NULL)
 611             return (1);
 612         else
 613             return (0);
 614     }
 615
 616     bn_check_top(a);
 617     bn_check_top(b);
 618
 619     if (a->neg != b->neg) {
 620         if (a->neg)
 621             return (-1);
 622         else
 623             return (1);
 624     }
 625     if (a->neg == 0) {
 626         gt = 1;
 627         lt = -1;
 628     } else {
 629         gt = -1;
 630         lt = 1;
 631     }
 632
 633     if (a->top > b->top)
 634         return (gt);
 635     if (a->top < b->top)
 636         return (lt);
 637     for (i = a->top - 1; i >= 0; i--) {
 638         t1 = a->d[i];
 639         t2 = b->d[i];
 640         if (t1 > t2)
 641             return (gt);
 642         if (t1 < t2)
 643             return (lt);
 644     }
 645     return (0);
 646 }
 647
 648 int BN_set_bit(BIGNUM *a, int n)
 649 {
 650     int i, j, k;
 651
 652     if (n < 0)
 653         return 0;
 654
 655     i = n / BN_BITS2;
 656     j = n % BN_BITS2;
 657     if (a->top <= i) {
 658         if (bn_wexpand(a, i + 1) == NULL)
 659             return (0);
 660         for (k = a->top; k < i + 1; k++)
 661             a->d[k] = 0;
 662         a->top = i + 1;
 663     }
 664
 665     a->d[i] |= (((BN_ULONG)1) << j);
 666     bn_check_top(a);
 667     return (1);
 668 }
 669
 670 int BN_clear_bit(BIGNUM *a, int n)
 671 {
 672     int i, j;
 673
 674     bn_check_top(a);
 675     if (n < 0)
 676         return 0;
 677
 678     i = n / BN_BITS2;
 679     j = n % BN_BITS2;
 680     if (a->top <= i)
 681         return (0);
 682
 683     a->d[i] &= (~(((BN_ULONG)1) << j));
 684     bn_correct_top(a);
 685     return (1);
 686 }
 687
 688 int BN_is_bit_set(const BIGNUM *a, int n)
 689 {
 690     int i, j;
 691
 692     bn_check_top(a);
 693     if (n < 0)
 694         return 0;
 695     i = n / BN_BITS2;
 696     j = n % BN_BITS2;
 697     if (a->top <= i)
 698         return 0;
 699     return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
 700 }
 701
 702 int BN_mask_bits(BIGNUM *a, int n)
 703 {
 704     int b, w;
 705
 706     bn_check_top(a);
 707     if (n < 0)
 708         return 0;
 709
 710     w = n / BN_BITS2;
 711     b = n % BN_BITS2;
 712     if (w >= a->top)
 713         return 0;
 714     if (b == 0)
 715         a->top = w;
 716     else {
 717         a->top = w + 1;
 718         a->d[w] &= ~(BN_MASK2 << b);
 719     }
 720     bn_correct_top(a);
 721     return (1);
 722 }
 723
 724 void BN_set_negative(BIGNUM *a, int b)
 725 {
 726     if (b && !BN_is_zero(a))
 727         a->neg = 1;
 728     else
 729         a->neg = 0;
 730 }
 731
 732 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
 733 {
 734     int i;
 735     BN_ULONG aa, bb;
 736
 737     aa = a[n - 1];
 738     bb = b[n - 1];
 739     if (aa != bb)
 740         return ((aa > bb) ? 1 : -1);
 741     for (i = n - 2; i >= 0; i--) {
 742         aa = a[i];
 743         bb = b[i];
 744         if (aa != bb)
 745             return ((aa > bb) ? 1 : -1);
 746     }
 747     return (0);
 748 }
 749
 750 /*
 751  * Here follows a specialised variants of bn_cmp_words().  It has the
 752  * property of performing the operation on arrays of different sizes. The
 753  * sizes of those arrays is expressed through cl, which is the common length
 754  * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the
 755  * two lengths, calculated as len(a)-len(b). All lengths are the number of
 756  * BN_ULONGs...
 757  */
 758
 759 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
 760 {
 761     int n, i;
 762     n = cl - 1;
 763
 764     if (dl < 0) {
 765         for (i = dl; i < 0; i++) {
 766             if (b[n - i] != 0)
 767                 return -1;      /* a < b */
 768         }
 769     }
 770     if (dl > 0) {
 771         for (i = dl; i > 0; i--) {
 772             if (a[n + i] != 0)
 773                 return 1;       /* a > b */
 774         }
 775     }
 776     return bn_cmp_words(a, b, cl);
 777 }
 778
 779 /*
 780  * Constant-time conditional swap of a and b.
 781  * a and b are swapped if condition is not 0.  The code assumes that at most one bit of condition is set.
 782  * nwords is the number of words to swap.  The code assumes that at least nwords are allocated in both a and b,
 783  * and that no more than nwords are used by either a or b.
 784  * a and b cannot be the same number
 785  */
 786 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
 787 {
 788     BN_ULONG t;
 789     int i;
 790
 791     bn_wcheck_size(a, nwords);
 792     bn_wcheck_size(b, nwords);
 793
 794     assert(a != b);
 795     assert((condition & (condition - 1)) == 0);
 796     assert(sizeof(BN_ULONG) >= sizeof(int));
 797
 798     condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
 799
 800     t = (a->top ^ b->top) & condition;
 801     a->top ^= t;
 802     b->top ^= t;
 803
 804 #define BN_CONSTTIME_SWAP(ind) \
 805         do { \
 806                 t = (a->d[ind] ^ b->d[ind]) & condition; \
 807                 a->d[ind] ^= t; \
 808                 b->d[ind] ^= t; \
 809         } while (0)
 810
 811     switch (nwords) {
 812     default:
 813         for (i = 10; i < nwords; i++)
 814             BN_CONSTTIME_SWAP(i);
 815         /* Fallthrough */
 816     case 10:
 817         BN_CONSTTIME_SWAP(9);   /* Fallthrough */
 818     case 9:
 819         BN_CONSTTIME_SWAP(8);   /* Fallthrough */
 820     case 8:
 821         BN_CONSTTIME_SWAP(7);   /* Fallthrough */
 822     case 7:
 823         BN_CONSTTIME_SWAP(6);   /* Fallthrough */
 824     case 6:
 825         BN_CONSTTIME_SWAP(5);   /* Fallthrough */
 826     case 5:
 827         BN_CONSTTIME_SWAP(4);   /* Fallthrough */
 828     case 4:
 829         BN_CONSTTIME_SWAP(3);   /* Fallthrough */
 830     case 3:
 831         BN_CONSTTIME_SWAP(2);   /* Fallthrough */
 832     case 2:
 833         BN_CONSTTIME_SWAP(1);   /* Fallthrough */
 834     case 1:
 835         BN_CONSTTIME_SWAP(0);
 836     }
 837 #undef BN_CONSTTIME_SWAP
 838 }
 839
 840 /* Bits of security, see SP800-57 */
 841
 842 int BN_security_bits(int L, int N)
 843 {
 844     int secbits, bits;
 845     if (L >= 15360)
 846         secbits = 256;
 847     else if (L >= 7690)
 848         secbits = 192;
 849     else if (L >= 3072)
 850         secbits = 128;
 851     else if (L >= 2048)
 852         secbits = 112;
 853     else if (L >= 1024)
 854         secbits = 80;
 855     else
 856         return 0;
 857     if (N == -1)
 858         return secbits;
 859     bits = N / 2;
 860     if (bits < 80)
 861         return 0;
 862     return bits >= secbits ? secbits : bits;
 863 }
 864
 865 void BN_zero_ex(BIGNUM *a)
 866 {
 867     a->top = 0;
 868     a->neg = 0;
 869 }
 870
 871 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
 872 {
 873     return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
 874 }
 875
 876 int BN_is_zero(const BIGNUM *a)
 877 {
 878     return a->top == 0;
 879 }
 880
 881 int BN_is_one(const BIGNUM *a)
 882 {
 883     return BN_abs_is_word(a, 1) && !a->neg;
 884 }
 885
 886 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
 887 {
 888     return BN_abs_is_word(a, w) && (!w || !a->neg);
 889 }
 890
 891 int BN_is_odd(const BIGNUM *a)
 892 {
 893     return (a->top > 0) && (a->d[0] & 1);
 894 }
 895
 896 int BN_is_negative(const BIGNUM *a)
 897 {
 898     return (a->neg != 0);
 899 }
 900
 901 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
 902                      BN_CTX *ctx)
 903 {
 904     return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
 905 }
 906
 907 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int n)
 908 {
 909     dest->d = b->d;
 910     dest->top = b->top;
 911     dest->dmax = b->dmax;
 912     dest->neg = b->neg;
 913     dest->flags = ((dest->flags & BN_FLG_MALLOCED)
 914                    | (b->flags & ~BN_FLG_MALLOCED)
 915                    | BN_FLG_STATIC_DATA | n);
 916 }
 917
 918 BN_GENCB *BN_GENCB_new(void)
 919 {
 920     BN_GENCB *ret;
 921
 922     if ((ret = OPENSSL_malloc(sizeof(BN_GENCB))) == NULL) {
 923         BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
 924         return (NULL);
 925     }
 926
 927     return ret;
 928 }
 929
 930 void BN_GENCB_free(BN_GENCB *cb)
 931 {
 932     if (cb == NULL)
 933         return;
 934     OPENSSL_free(cb);
 935 }
 936
 937 void BN_set_flags(BIGNUM *b, int n)
 938 {
 939     b->flags |= n;
 940 }
 941
 942 int BN_get_flags(const BIGNUM *b, int n)
 943 {
 944     return b->flags & n;
 945 }
 946
 947 /* Populate a BN_GENCB structure with an "old"-style callback */
 948 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
 949                       void *cb_arg)
 950 {
 951     BN_GENCB *tmp_gencb = gencb;
 952     tmp_gencb->ver = 1;
 953     tmp_gencb->arg = cb_arg;
 954     tmp_gencb->cb.cb_1 = callback;
 955 }
 956
 957 /* Populate a BN_GENCB structure with a "new"-style callback */
 958 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
 959                   void *cb_arg)
 960 {
 961     BN_GENCB *tmp_gencb = gencb;
 962     tmp_gencb->ver = 2;
 963     tmp_gencb->arg = cb_arg;
 964     tmp_gencb->cb.cb_2 = callback;
 965 }
 966
 967 void *BN_GENCB_get_arg(BN_GENCB *cb)
 968 {
 969     return cb->arg;
 970 }
 971
 972 BIGNUM *bn_wexpand(BIGNUM *a, int words)
 973 {
 974     return (words <= a->dmax) ? a : bn_expand2(a, words);
 975 }
 976
 977 void bn_correct_top(BIGNUM *a)
 978 {
 979     BN_ULONG *ftl;
 980     int tmp_top = a->top;
 981
 982     if (tmp_top > 0) {
 983         for (ftl = &(a->d[tmp_top - 1]); tmp_top > 0; tmp_top--)
 984             if (*(ftl--))
 985                 break;
 986         a->top = tmp_top;
 987     }
 988     bn_pollute(a);
 989 }