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