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     /* Skip leading zero's. */
 556     for ( ; len > 0 && *s == 0; s++, len--)
 557         continue;
 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     l = 0;
 572     while (n--) {
 573         l = (l << 8L) | *(s++);
 574         if (m-- == 0) {
 575             ret->d[--i] = l;
 576             l = 0;
 577             m = BN_BYTES - 1;
 578         }
 579     }
 580     /*
 581      * need to call this due to clear byte at top if avoiding having the top
 582      * bit set (-ve number)
 583      */
 584     bn_correct_top(ret);
 585     return (ret);
 586 }
 587
 588 /* ignore negative */
 589 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
 590 {
 591     int n, i;
 592     BN_ULONG l;
 593
 594     bn_check_top(a);
 595     n = i = BN_num_bytes(a);
 596     while (i--) {
 597         l = a->d[i / BN_BYTES];
 598         *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
 599     }
 600     return (n);
 601 }
 602
 603 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
 604 {
 605     int i;
 606     BN_ULONG t1, t2, *ap, *bp;
 607
 608     bn_check_top(a);
 609     bn_check_top(b);
 610
 611     i = a->top - b->top;
 612     if (i != 0)
 613         return (i);
 614     ap = a->d;
 615     bp = b->d;
 616     for (i = a->top - 1; i >= 0; i--) {
 617         t1 = ap[i];
 618         t2 = bp[i];
 619         if (t1 != t2)
 620             return ((t1 > t2) ? 1 : -1);
 621     }
 622     return (0);
 623 }
 624
 625 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
 626 {
 627     int i;
 628     int gt, lt;
 629     BN_ULONG t1, t2;
 630
 631     if ((a == NULL) || (b == NULL)) {
 632         if (a != NULL)
 633             return (-1);
 634         else if (b != NULL)
 635             return (1);
 636         else
 637             return (0);
 638     }
 639
 640     bn_check_top(a);
 641     bn_check_top(b);
 642
 643     if (a->neg != b->neg) {
 644         if (a->neg)
 645             return (-1);
 646         else
 647             return (1);
 648     }
 649     if (a->neg == 0) {
 650         gt = 1;
 651         lt = -1;
 652     } else {
 653         gt = -1;
 654         lt = 1;
 655     }
 656
 657     if (a->top > b->top)
 658         return (gt);
 659     if (a->top < b->top)
 660         return (lt);
 661     for (i = a->top - 1; i >= 0; i--) {
 662         t1 = a->d[i];
 663         t2 = b->d[i];
 664         if (t1 > t2)
 665             return (gt);
 666         if (t1 < t2)
 667             return (lt);
 668     }
 669     return (0);
 670 }
 671
 672 int BN_set_bit(BIGNUM *a, int n)
 673 {
 674     int i, j, k;
 675
 676     if (n < 0)
 677         return 0;
 678
 679     i = n / BN_BITS2;
 680     j = n % BN_BITS2;
 681     if (a->top <= i) {
 682         if (bn_wexpand(a, i + 1) == NULL)
 683             return (0);
 684         for (k = a->top; k < i + 1; k++)
 685             a->d[k] = 0;
 686         a->top = i + 1;
 687     }
 688
 689     a->d[i] |= (((BN_ULONG)1) << j);
 690     bn_check_top(a);
 691     return (1);
 692 }
 693
 694 int BN_clear_bit(BIGNUM *a, int n)
 695 {
 696     int i, j;
 697
 698     bn_check_top(a);
 699     if (n < 0)
 700         return 0;
 701
 702     i = n / BN_BITS2;
 703     j = n % BN_BITS2;
 704     if (a->top <= i)
 705         return (0);
 706
 707     a->d[i] &= (~(((BN_ULONG)1) << j));
 708     bn_correct_top(a);
 709     return (1);
 710 }
 711
 712 int BN_is_bit_set(const BIGNUM *a, int n)
 713 {
 714     int i, j;
 715
 716     bn_check_top(a);
 717     if (n < 0)
 718         return 0;
 719     i = n / BN_BITS2;
 720     j = n % BN_BITS2;
 721     if (a->top <= i)
 722         return 0;
 723     return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
 724 }
 725
 726 int BN_mask_bits(BIGNUM *a, int n)
 727 {
 728     int b, w;
 729
 730     bn_check_top(a);
 731     if (n < 0)
 732         return 0;
 733
 734     w = n / BN_BITS2;
 735     b = n % BN_BITS2;
 736     if (w >= a->top)
 737         return 0;
 738     if (b == 0)
 739         a->top = w;
 740     else {
 741         a->top = w + 1;
 742         a->d[w] &= ~(BN_MASK2 << b);
 743     }
 744     bn_correct_top(a);
 745     return (1);
 746 }
 747
 748 void BN_set_negative(BIGNUM *a, int b)
 749 {
 750     if (b && !BN_is_zero(a))
 751         a->neg = 1;
 752     else
 753         a->neg = 0;
 754 }
 755
 756 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
 757 {
 758     int i;
 759     BN_ULONG aa, bb;
 760
 761     aa = a[n - 1];
 762     bb = b[n - 1];
 763     if (aa != bb)
 764         return ((aa > bb) ? 1 : -1);
 765     for (i = n - 2; i >= 0; i--) {
 766         aa = a[i];
 767         bb = b[i];
 768         if (aa != bb)
 769             return ((aa > bb) ? 1 : -1);
 770     }
 771     return (0);
 772 }
 773
 774 /*
 775  * Here follows a specialised variants of bn_cmp_words().  It has the
 776  * property of performing the operation on arrays of different sizes. The
 777  * sizes of those arrays is expressed through cl, which is the common length
 778  * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the
 779  * two lengths, calculated as len(a)-len(b). All lengths are the number of
 780  * BN_ULONGs...
 781  */
 782
 783 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
 784 {
 785     int n, i;
 786     n = cl - 1;
 787
 788     if (dl < 0) {
 789         for (i = dl; i < 0; i++) {
 790             if (b[n - i] != 0)
 791                 return -1;      /* a < b */
 792         }
 793     }
 794     if (dl > 0) {
 795         for (i = dl; i > 0; i--) {
 796             if (a[n + i] != 0)
 797                 return 1;       /* a > b */
 798         }
 799     }
 800     return bn_cmp_words(a, b, cl);
 801 }
 802
 803 /*
 804  * Constant-time conditional swap of a and b.
 805  * a and b are swapped if condition is not 0.  The code assumes that at most one bit of condition is set.
 806  * nwords is the number of words to swap.  The code assumes that at least nwords are allocated in both a and b,
 807  * and that no more than nwords are used by either a or b.
 808  * a and b cannot be the same number
 809  */
 810 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
 811 {
 812     BN_ULONG t;
 813     int i;
 814
 815     bn_wcheck_size(a, nwords);
 816     bn_wcheck_size(b, nwords);
 817
 818     assert(a != b);
 819     assert((condition & (condition - 1)) == 0);
 820     assert(sizeof(BN_ULONG) >= sizeof(int));
 821
 822     condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
 823
 824     t = (a->top ^ b->top) & condition;
 825     a->top ^= t;
 826     b->top ^= t;
 827
 828 #define BN_CONSTTIME_SWAP(ind) \
 829         do { \
 830                 t = (a->d[ind] ^ b->d[ind]) & condition; \
 831                 a->d[ind] ^= t; \
 832                 b->d[ind] ^= t; \
 833         } while (0)
 834
 835     switch (nwords) {
 836     default:
 837         for (i = 10; i < nwords; i++)
 838             BN_CONSTTIME_SWAP(i);
 839         /* Fallthrough */
 840     case 10:
 841         BN_CONSTTIME_SWAP(9);   /* Fallthrough */
 842     case 9:
 843         BN_CONSTTIME_SWAP(8);   /* Fallthrough */
 844     case 8:
 845         BN_CONSTTIME_SWAP(7);   /* Fallthrough */
 846     case 7:
 847         BN_CONSTTIME_SWAP(6);   /* Fallthrough */
 848     case 6:
 849         BN_CONSTTIME_SWAP(5);   /* Fallthrough */
 850     case 5:
 851         BN_CONSTTIME_SWAP(4);   /* Fallthrough */
 852     case 4:
 853         BN_CONSTTIME_SWAP(3);   /* Fallthrough */
 854     case 3:
 855         BN_CONSTTIME_SWAP(2);   /* Fallthrough */
 856     case 2:
 857         BN_CONSTTIME_SWAP(1);   /* Fallthrough */
 858     case 1:
 859         BN_CONSTTIME_SWAP(0);
 860     }
 861 #undef BN_CONSTTIME_SWAP
 862 }
 863
 864 /* Bits of security, see SP800-57 */
 865
 866 int BN_security_bits(int L, int N)
 867 {
 868     int secbits, bits;
 869     if (L >= 15360)
 870         secbits = 256;
 871     else if (L >= 7690)
 872         secbits = 192;
 873     else if (L >= 3072)
 874         secbits = 128;
 875     else if (L >= 2048)
 876         secbits = 112;
 877     else if (L >= 1024)
 878         secbits = 80;
 879     else
 880         return 0;
 881     if (N == -1)
 882         return secbits;
 883     bits = N / 2;
 884     if (bits < 80)
 885         return 0;
 886     return bits >= secbits ? secbits : bits;
 887 }
 888
 889 void BN_zero_ex(BIGNUM *a)
 890 {
 891     a->top = 0;
 892     a->neg = 0;
 893 }
 894
 895 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
 896 {
 897     return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
 898 }
 899
 900 int BN_is_zero(const BIGNUM *a)
 901 {
 902     return a->top == 0;
 903 }
 904
 905 int BN_is_one(const BIGNUM *a)
 906 {
 907     return BN_abs_is_word(a, 1) && !a->neg;
 908 }
 909
 910 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
 911 {
 912     return BN_abs_is_word(a, w) && (!w || !a->neg);
 913 }
 914
 915 int BN_is_odd(const BIGNUM *a)
 916 {
 917     return (a->top > 0) && (a->d[0] & 1);
 918 }
 919
 920 int BN_is_negative(const BIGNUM *a)
 921 {
 922     return (a->neg != 0);
 923 }
 924
 925 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
 926                      BN_CTX *ctx)
 927 {
 928     return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
 929 }
 930
 931 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int n)
 932 {
 933     dest->d = b->d;
 934     dest->top = b->top;
 935     dest->dmax = b->dmax;
 936     dest->neg = b->neg;
 937     dest->flags = ((dest->flags & BN_FLG_MALLOCED)
 938                    | (b->flags & ~BN_FLG_MALLOCED)
 939                    | BN_FLG_STATIC_DATA | n);
 940 }
 941
 942 BN_GENCB *BN_GENCB_new(void)
 943 {
 944     BN_GENCB *ret;
 945
 946     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
 947         BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
 948         return (NULL);
 949     }
 950
 951     return ret;
 952 }
 953
 954 void BN_GENCB_free(BN_GENCB *cb)
 955 {
 956     if (cb == NULL)
 957         return;
 958     OPENSSL_free(cb);
 959 }
 960
 961 void BN_set_flags(BIGNUM *b, int n)
 962 {
 963     b->flags |= n;
 964 }
 965
 966 int BN_get_flags(const BIGNUM *b, int n)
 967 {
 968     return b->flags & n;
 969 }
 970
 971 /* Populate a BN_GENCB structure with an "old"-style callback */
 972 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
 973                       void *cb_arg)
 974 {
 975     BN_GENCB *tmp_gencb = gencb;
 976     tmp_gencb->ver = 1;
 977     tmp_gencb->arg = cb_arg;
 978     tmp_gencb->cb.cb_1 = callback;
 979 }
 980
 981 /* Populate a BN_GENCB structure with a "new"-style callback */
 982 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
 983                   void *cb_arg)
 984 {
 985     BN_GENCB *tmp_gencb = gencb;
 986     tmp_gencb->ver = 2;
 987     tmp_gencb->arg = cb_arg;
 988     tmp_gencb->cb.cb_2 = callback;
 989 }
 990
 991 void *BN_GENCB_get_arg(BN_GENCB *cb)
 992 {
 993     return cb->arg;
 994 }
 995
 996 BIGNUM *bn_wexpand(BIGNUM *a, int words)
 997 {
 998     return (words <= a->dmax) ? a : bn_expand2(a, words);
 999 }
1000
1001 void bn_correct_top(BIGNUM *a)
1002 {
1003     BN_ULONG *ftl;
1004     int tmp_top = a->top;
1005
1006     if (tmp_top > 0) {
1007         for (ftl = &(a->d[tmp_top - 1]); tmp_top > 0; tmp_top--)
1008             if (*(ftl--))
1009                 break;
1010         a->top = tmp_top;
1011     }
1012     bn_pollute(a);
1013 }