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 #include <openssl/opensslconf.h>
  69
  70 /* This stuff appears to be completely unused, so is deprecated */
  71 #if OPENSSL_API_COMPAT < 0x00908000L
  72 /*-
  73  * For a 32 bit machine
  74  * 2 -   4 ==  128
  75  * 3 -   8 ==  256
  76  * 4 -  16 ==  512
  77  * 5 -  32 == 1024
  78  * 6 -  64 == 2048
  79  * 7 - 128 == 4096
  80  * 8 - 256 == 8192
  81  */
  82 static int bn_limit_bits = 0;
  83 static int bn_limit_num = 8;    /* (1<<bn_limit_bits) */
  84 static int bn_limit_bits_low = 0;
  85 static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */
  86 static int bn_limit_bits_high = 0;
  87 static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */
  88 static int bn_limit_bits_mont = 0;
  89 static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */
  90
  91 void BN_set_params(int mult, int high, int low, int mont)
  92 {
  93     if (mult >= 0) {
  94         if (mult > (int)(sizeof(int) * 8) - 1)
  95             mult = sizeof(int) * 8 - 1;
  96         bn_limit_bits = mult;
  97         bn_limit_num = 1 << mult;
  98     }
  99     if (high >= 0) {
 100         if (high > (int)(sizeof(int) * 8) - 1)
 101             high = sizeof(int) * 8 - 1;
 102         bn_limit_bits_high = high;
 103         bn_limit_num_high = 1 << high;
 104     }
 105     if (low >= 0) {
 106         if (low > (int)(sizeof(int) * 8) - 1)
 107             low = sizeof(int) * 8 - 1;
 108         bn_limit_bits_low = low;
 109         bn_limit_num_low = 1 << low;
 110     }
 111     if (mont >= 0) {
 112         if (mont > (int)(sizeof(int) * 8) - 1)
 113             mont = sizeof(int) * 8 - 1;
 114         bn_limit_bits_mont = mont;
 115         bn_limit_num_mont = 1 << mont;
 116     }
 117 }
 118
 119 int BN_get_params(int which)
 120 {
 121     if (which == 0)
 122         return (bn_limit_bits);
 123     else if (which == 1)
 124         return (bn_limit_bits_high);
 125     else if (which == 2)
 126         return (bn_limit_bits_low);
 127     else if (which == 3)
 128         return (bn_limit_bits_mont);
 129     else
 130         return (0);
 131 }
 132 #endif
 133
 134 const BIGNUM *BN_value_one(void)
 135 {
 136     static const BN_ULONG data_one = 1L;
 137     static const BIGNUM const_one =
 138         { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA };
 139
 140     return (&const_one);
 141 }
 142
 143 int BN_num_bits_word(BN_ULONG l)
 144 {
 145     static const unsigned char bits[256] = {
 146         0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
 147         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 148         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 149         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 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         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 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         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 162     };
 163
 164 #if defined(SIXTY_FOUR_BIT_LONG)
 165     if (l & 0xffffffff00000000L) {
 166         if (l & 0xffff000000000000L) {
 167             if (l & 0xff00000000000000L) {
 168                 return (bits[(int)(l >> 56)] + 56);
 169             } else
 170                 return (bits[(int)(l >> 48)] + 48);
 171         } else {
 172             if (l & 0x0000ff0000000000L) {
 173                 return (bits[(int)(l >> 40)] + 40);
 174             } else
 175                 return (bits[(int)(l >> 32)] + 32);
 176         }
 177     } else
 178 #else
 179 # ifdef SIXTY_FOUR_BIT
 180     if (l & 0xffffffff00000000LL) {
 181         if (l & 0xffff000000000000LL) {
 182             if (l & 0xff00000000000000LL) {
 183                 return (bits[(int)(l >> 56)] + 56);
 184             } else
 185                 return (bits[(int)(l >> 48)] + 48);
 186         } else {
 187             if (l & 0x0000ff0000000000LL) {
 188                 return (bits[(int)(l >> 40)] + 40);
 189             } else
 190                 return (bits[(int)(l >> 32)] + 32);
 191         }
 192     } else
 193 # endif
 194 #endif
 195     {
 196 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 197         if (l & 0xffff0000L) {
 198             if (l & 0xff000000L)
 199                 return (bits[(int)(l >> 24L)] + 24);
 200             else
 201                 return (bits[(int)(l >> 16L)] + 16);
 202         } else
 203 #endif
 204         {
 205 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 206             if (l & 0xff00L)
 207                 return (bits[(int)(l >> 8)] + 8);
 208             else
 209 #endif
 210                 return (bits[(int)(l)]);
 211         }
 212     }
 213 }
 214
 215 int BN_num_bits(const BIGNUM *a)
 216 {
 217     int i = a->top - 1;
 218     bn_check_top(a);
 219
 220     if (BN_is_zero(a))
 221         return 0;
 222     return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
 223 }
 224
 225 static void bn_free_d(BIGNUM *a)
 226 {
 227     if (BN_get_flags(a,BN_FLG_SECURE))
 228         OPENSSL_secure_free(a->d);
 229     else
 230         OPENSSL_free(a->d);
 231 }
 232
 233
 234 void BN_clear_free(BIGNUM *a)
 235 {
 236     int i;
 237
 238     if (a == NULL)
 239         return;
 240     bn_check_top(a);
 241     if (a->d != NULL) {
 242         OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
 243         if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
 244             bn_free_d(a);
 245     }
 246     i = BN_get_flags(a, BN_FLG_MALLOCED);
 247     OPENSSL_cleanse(a, sizeof(*a));
 248     if (i)
 249         OPENSSL_free(a);
 250 }
 251
 252 void BN_free(BIGNUM *a)
 253 {
 254     if (a == NULL)
 255         return;
 256     bn_check_top(a);
 257     if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
 258         bn_free_d(a);
 259     if (a->flags & BN_FLG_MALLOCED)
 260         OPENSSL_free(a);
 261     else {
 262 #if OPENSSL_API_COMPAT < 0x00908000L
 263         a->flags |= BN_FLG_FREE;
 264 #endif
 265         a->d = NULL;
 266     }
 267 }
 268
 269 void bn_init(BIGNUM *a)
 270 {
 271     static BIGNUM nilbn;
 272
 273     *a = nilbn;
 274     bn_check_top(a);
 275 }
 276
 277 BIGNUM *BN_new(void)
 278 {
 279     BIGNUM *ret;
 280
 281     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
 282         BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
 283         return (NULL);
 284     }
 285     ret->flags = BN_FLG_MALLOCED;
 286     bn_check_top(ret);
 287     return (ret);
 288 }
 289
 290  BIGNUM *BN_secure_new(void)
 291  {
 292      BIGNUM *ret = BN_new();
 293      if (ret != NULL)
 294          ret->flags |= BN_FLG_SECURE;
 295      return (ret);
 296  }
 297
 298 /* This is used both by bn_expand2() and bn_dup_expand() */
 299 /* The caller MUST check that words > b->dmax before calling this */
 300 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
 301 {
 302     BN_ULONG *A, *a = NULL;
 303     const BN_ULONG *B;
 304     int i;
 305
 306     bn_check_top(b);
 307
 308     if (words > (INT_MAX / (4 * BN_BITS2))) {
 309         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
 310         return NULL;
 311     }
 312     if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
 313         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
 314         return (NULL);
 315     }
 316     if (BN_get_flags(b,BN_FLG_SECURE))
 317         a = A = OPENSSL_secure_malloc(words * sizeof(*a));
 318     else
 319         a = A = OPENSSL_malloc(words * sizeof(*a));
 320     if (A == NULL) {
 321         BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
 322         return (NULL);
 323     }
 324 #ifdef PURIFY
 325     /*
 326      * Valgrind complains in BN_consttime_swap because we process the whole
 327      * array even if it's not initialised yet. This doesn't matter in that
 328      * function - what's important is constant time operation (we're not
 329      * actually going to use the data)
 330      */
 331     memset(a, 0, sizeof(*a) * words);
 332 #endif
 333
 334 #if 1
 335     B = b->d;
 336     /* Check if the previous number needs to be copied */
 337     if (B != NULL) {
 338         for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
 339             /*
 340              * The fact that the loop is unrolled
 341              * 4-wise is a tribute to Intel. It's
 342              * the one that doesn't have enough
 343              * registers to accomodate more data.
 344              * I'd unroll it 8-wise otherwise:-)
 345              *
 346              *              <appro@fy.chalmers.se>
 347              */
 348             BN_ULONG a0, a1, a2, a3;
 349             a0 = B[0];
 350             a1 = B[1];
 351             a2 = B[2];
 352             a3 = B[3];
 353             A[0] = a0;
 354             A[1] = a1;
 355             A[2] = a2;
 356             A[3] = a3;
 357         }
 358         /*
 359          * workaround for ultrix cc: without 'case 0', the optimizer does
 360          * the switch table by doing a=top&3; a--; goto jump_table[a];
 361          * which fails for top== 0
 362          */
 363         switch (b->top & 3) {
 364         case 3:
 365             A[2] = B[2];
 366         case 2:
 367             A[1] = B[1];
 368         case 1:
 369             A[0] = B[0];
 370         case 0:
 371             ;
 372         }
 373     }
 374 #else
 375     memset(A, 0, sizeof(*A) * words);
 376     memcpy(A, b->d, sizeof(b->d[0]) * b->top);
 377 #endif
 378
 379     return (a);
 380 }
 381
 382 /*
 383  * This is an internal function that should not be used in applications. It
 384  * ensures that 'b' has enough room for a 'words' word number and initialises
 385  * any unused part of b->d with leading zeros. It is mostly used by the
 386  * various BIGNUM routines. If there is an error, NULL is returned. If not,
 387  * 'b' is returned.
 388  */
 389
 390 BIGNUM *bn_expand2(BIGNUM *b, int words)
 391 {
 392     bn_check_top(b);
 393
 394     if (words > b->dmax) {
 395         BN_ULONG *a = bn_expand_internal(b, words);
 396         if (!a)
 397             return NULL;
 398         if (b->d) {
 399             OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0]));
 400             bn_free_d(b);
 401         }
 402         b->d = a;
 403         b->dmax = words;
 404     }
 405
 406     bn_check_top(b);
 407     return b;
 408 }
 409
 410 BIGNUM *BN_dup(const BIGNUM *a)
 411 {
 412     BIGNUM *t;
 413
 414     if (a == NULL)
 415         return NULL;
 416     bn_check_top(a);
 417
 418     t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
 419     if (t == NULL)
 420         return NULL;
 421     if (!BN_copy(t, a)) {
 422         BN_free(t);
 423         return NULL;
 424     }
 425     bn_check_top(t);
 426     return t;
 427 }
 428
 429 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
 430 {
 431     int i;
 432     BN_ULONG *A;
 433     const BN_ULONG *B;
 434
 435     bn_check_top(b);
 436
 437     if (a == b)
 438         return (a);
 439     if (bn_wexpand(a, b->top) == NULL)
 440         return (NULL);
 441
 442 #if 1
 443     A = a->d;
 444     B = b->d;
 445     for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
 446         BN_ULONG a0, a1, a2, a3;
 447         a0 = B[0];
 448         a1 = B[1];
 449         a2 = B[2];
 450         a3 = B[3];
 451         A[0] = a0;
 452         A[1] = a1;
 453         A[2] = a2;
 454         A[3] = a3;
 455     }
 456     /* ultrix cc workaround, see comments in bn_expand_internal */
 457     switch (b->top & 3) {
 458     case 3:
 459         A[2] = B[2];
 460     case 2:
 461         A[1] = B[1];
 462     case 1:
 463         A[0] = B[0];
 464     case 0:;
 465     }
 466 #else
 467     memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
 468 #endif
 469
 470     a->top = b->top;
 471     a->neg = b->neg;
 472     bn_check_top(a);
 473     return (a);
 474 }
 475
 476 void BN_swap(BIGNUM *a, BIGNUM *b)
 477 {
 478     int flags_old_a, flags_old_b;
 479     BN_ULONG *tmp_d;
 480     int tmp_top, tmp_dmax, tmp_neg;
 481
 482     bn_check_top(a);
 483     bn_check_top(b);
 484
 485     flags_old_a = a->flags;
 486     flags_old_b = b->flags;
 487
 488     tmp_d = a->d;
 489     tmp_top = a->top;
 490     tmp_dmax = a->dmax;
 491     tmp_neg = a->neg;
 492
 493     a->d = b->d;
 494     a->top = b->top;
 495     a->dmax = b->dmax;
 496     a->neg = b->neg;
 497
 498     b->d = tmp_d;
 499     b->top = tmp_top;
 500     b->dmax = tmp_dmax;
 501     b->neg = tmp_neg;
 502
 503     a->flags =
 504         (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
 505     b->flags =
 506         (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
 507     bn_check_top(a);
 508     bn_check_top(b);
 509 }
 510
 511 void BN_clear(BIGNUM *a)
 512 {
 513     bn_check_top(a);
 514     if (a->d != NULL)
 515         memset(a->d, 0, sizeof(*a->d) * a->dmax);
 516     a->top = 0;
 517     a->neg = 0;
 518 }
 519
 520 BN_ULONG BN_get_word(const BIGNUM *a)
 521 {
 522     if (a->top > 1)
 523         return BN_MASK2;
 524     else if (a->top == 1)
 525         return a->d[0];
 526     /* a->top == 0 */
 527     return 0;
 528 }
 529
 530 int BN_set_word(BIGNUM *a, BN_ULONG w)
 531 {
 532     bn_check_top(a);
 533     if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
 534         return (0);
 535     a->neg = 0;
 536     a->d[0] = w;
 537     a->top = (w ? 1 : 0);
 538     bn_check_top(a);
 539     return (1);
 540 }
 541
 542 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
 543 {
 544     unsigned int i, m;
 545     unsigned int n;
 546     BN_ULONG l;
 547     BIGNUM *bn = NULL;
 548
 549     if (ret == NULL)
 550         ret = bn = BN_new();
 551     if (ret == NULL)
 552         return (NULL);
 553     bn_check_top(ret);
 554     /* Skip leading zero's. */
 555     for ( ; len > 0 && *s == 0; s++, len--)
 556         continue;
 557     n = len;
 558     if (n == 0) {
 559         ret->top = 0;
 560         return (ret);
 561     }
 562     i = ((n - 1) / BN_BYTES) + 1;
 563     m = ((n - 1) % (BN_BYTES));
 564     if (bn_wexpand(ret, (int)i) == NULL) {
 565         BN_free(bn);
 566         return NULL;
 567     }
 568     ret->top = i;
 569     ret->neg = 0;
 570     l = 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 flags)
 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 | flags);
 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 }