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