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