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