crypto/bn/bn_lib.c

   1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   2  * All rights reserved.
   3  *
   4  * This package is an SSL implementation written
   5  * by Eric Young (eay@cryptsoft.com).
   6  * The implementation was written so as to conform with Netscapes SSL.
   7  *
   8  * This library is free for commercial and non-commercial use as long as
   9  * the following conditions are aheared to.  The following conditions
  10  * apply to all code found in this distribution, be it the RC4, RSA,
  11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  12  * included with this distribution is covered by the same copyright terms
  13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  14  *
  15  * Copyright remains Eric Young's, and as such any Copyright notices in
  16  * the code are not to be removed.
  17  * If this package is used in a product, Eric Young should be given attribution
  18  * as the author of the parts of the library used.
  19  * This can be in the form of a textual message at program startup or
  20  * in documentation (online or textual) provided with the package.
  21  *
  22  * Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions
  24  * are met:
  25  * 1. Redistributions of source code must retain the copyright
  26  *    notice, this list of conditions and the following disclaimer.
  27  * 2. Redistributions in binary form must reproduce the above copyright
  28  *    notice, this list of conditions and the following disclaimer in the
  29  *    documentation and/or other materials provided with the distribution.
  30  * 3. All advertising materials mentioning features or use of this software
  31  *    must display the following acknowledgement:
  32  *    "This product includes cryptographic software written by
  33  *     Eric Young (eay@cryptsoft.com)"
  34  *    The word 'cryptographic' can be left out if the rouines from the library
  35  *    being used are not cryptographic related :-).
  36  * 4. If you include any Windows specific code (or a derivative thereof) from
  37  *    the apps directory (application code) you must include an acknowledgement:
  38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  50  * SUCH DAMAGE.
  51  *
  52  * The licence and distribution terms for any publically available version or
  53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  54  * copied and put under another distribution licence
  55  * [including the GNU Public Licence.]
  56  */
  57
  58 #include <assert.h>
  59 #include <limits.h>
  60 #include "internal/cryptlib.h"
  61 #include "bn_lcl.h"
  62 #include <openssl/opensslconf.h>
  63
  64 /* This stuff appears to be completely unused, so is deprecated */
  65 #if OPENSSL_API_COMPAT < 0x00908000L
  66 /*-
  67  * For a 32 bit machine
  68  * 2 -   4 ==  128
  69  * 3 -   8 ==  256
  70  * 4 -  16 ==  512
  71  * 5 -  32 == 1024
  72  * 6 -  64 == 2048
  73  * 7 - 128 == 4096
  74  * 8 - 256 == 8192
  75  */
  76 static int bn_limit_bits = 0;
  77 static int bn_limit_num = 8;    /* (1<<bn_limit_bits) */
  78 static int bn_limit_bits_low = 0;
  79 static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */
  80 static int bn_limit_bits_high = 0;
  81 static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */
  82 static int bn_limit_bits_mont = 0;
  83 static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */
  84
  85 void BN_set_params(int mult, int high, int low, int mont)
  86 {
  87     if (mult >= 0) {
  88         if (mult > (int)(sizeof(int) * 8) - 1)
  89             mult = sizeof(int) * 8 - 1;
  90         bn_limit_bits = mult;
  91         bn_limit_num = 1 << mult;
  92     }
  93     if (high >= 0) {
  94         if (high > (int)(sizeof(int) * 8) - 1)
  95             high = sizeof(int) * 8 - 1;
  96         bn_limit_bits_high = high;
  97         bn_limit_num_high = 1 << high;
  98     }
  99     if (low >= 0) {
 100         if (low > (int)(sizeof(int) * 8) - 1)
 101             low = sizeof(int) * 8 - 1;
 102         bn_limit_bits_low = low;
 103         bn_limit_num_low = 1 << low;
 104     }
 105     if (mont >= 0) {
 106         if (mont > (int)(sizeof(int) * 8) - 1)
 107             mont = sizeof(int) * 8 - 1;
 108         bn_limit_bits_mont = mont;
 109         bn_limit_num_mont = 1 << mont;
 110     }
 111 }
 112
 113 int BN_get_params(int which)
 114 {
 115     if (which == 0)
 116         return (bn_limit_bits);
 117     else if (which == 1)
 118         return (bn_limit_bits_high);
 119     else if (which == 2)
 120         return (bn_limit_bits_low);
 121     else if (which == 3)
 122         return (bn_limit_bits_mont);
 123     else
 124         return (0);
 125 }
 126 #endif
 127
 128 const BIGNUM *BN_value_one(void)
 129 {
 130     static const BN_ULONG data_one = 1L;
 131     static const BIGNUM const_one =
 132         { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA };
 133
 134     return (&const_one);
 135 }
 136
 137 int BN_num_bits_word(BN_ULONG l)
 138 {
 139     static const unsigned char bits[256] = {
 140         0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
 141         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 142         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 143         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 144         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 145         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 146         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 147         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
 148         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 149         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 150         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 151         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 152         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
 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     };
 157
 158 #if defined(SIXTY_FOUR_BIT_LONG)
 159     if (l & 0xffffffff00000000L) {
 160         if (l & 0xffff000000000000L) {
 161             if (l & 0xff00000000000000L) {
 162                 return (bits[(int)(l >> 56)] + 56);
 163             } else
 164                 return (bits[(int)(l >> 48)] + 48);
 165         } else {
 166             if (l & 0x0000ff0000000000L) {
 167                 return (bits[(int)(l >> 40)] + 40);
 168             } else
 169                 return (bits[(int)(l >> 32)] + 32);
 170         }
 171     } else
 172 #else
 173 # ifdef SIXTY_FOUR_BIT
 174     if (l & 0xffffffff00000000LL) {
 175         if (l & 0xffff000000000000LL) {
 176             if (l & 0xff00000000000000LL) {
 177                 return (bits[(int)(l >> 56)] + 56);
 178             } else
 179                 return (bits[(int)(l >> 48)] + 48);
 180         } else {
 181             if (l & 0x0000ff0000000000LL) {
 182                 return (bits[(int)(l >> 40)] + 40);
 183             } else
 184                 return (bits[(int)(l >> 32)] + 32);
 185         }
 186     } else
 187 # endif
 188 #endif
 189     {
 190 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 191         if (l & 0xffff0000L) {
 192             if (l & 0xff000000L)
 193                 return (bits[(int)(l >> 24L)] + 24);
 194             else
 195                 return (bits[(int)(l >> 16L)] + 16);
 196         } else
 197 #endif
 198         {
 199 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 200             if (l & 0xff00L)
 201                 return (bits[(int)(l >> 8)] + 8);
 202             else
 203 #endif
 204                 return (bits[(int)(l)]);
 205         }
 206     }
 207 }
 208
 209 int BN_num_bits(const BIGNUM *a)
 210 {
 211     int i = a->top - 1;
 212     bn_check_top(a);
 213
 214     if (BN_is_zero(a))
 215         return 0;
 216     return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
 217 }
 218
 219 static void bn_free_d(BIGNUM *a)
 220 {
 221     if (BN_get_flags(a,BN_FLG_SECURE))
 222         OPENSSL_secure_free(a->d);
 223     else
 224         OPENSSL_free(a->d);
 225 }
 226
 227
 228 void BN_clear_free(BIGNUM *a)
 229 {
 230     int i;
 231
 232     if (a == NULL)
 233         return;
 234     bn_check_top(a);
 235     if (a->d != NULL) {
 236         OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
 237         if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
 238             bn_free_d(a);
 239     }
 240     i = BN_get_flags(a, BN_FLG_MALLOCED);
 241     OPENSSL_cleanse(a, sizeof(*a));
 242     if (i)
 243         OPENSSL_free(a);
 244 }
 245
 246 void BN_free(BIGNUM *a)
 247 {
 248     if (a == NULL)
 249         return;
 250     bn_check_top(a);
 251     if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
 252         bn_free_d(a);
 253     if (a->flags & BN_FLG_MALLOCED)
 254         OPENSSL_free(a);
 255     else {
 256 #if OPENSSL_API_COMPAT < 0x00908000L
 257         a->flags |= BN_FLG_FREE;
 258 #endif
 259         a->d = NULL;
 260     }
 261 }
 262
 263 void bn_init(BIGNUM *a)
 264 {
 265     static BIGNUM nilbn;
 266
 267     *a = nilbn;
 268     bn_check_top(a);
 269 }
 270
 271 BIGNUM *BN_new(void)
 272 {
 273     BIGNUM *ret;
 274
 275     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
 276         BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
 277         return (NULL);
 278     }
 279     ret->flags = BN_FLG_MALLOCED;
 280     bn_check_top(ret);
 281     return (ret);
 282 }
 283
 284  BIGNUM *BN_secure_new(void)
 285  {
 286      BIGNUM *ret = BN_new();
 287      if (ret != NULL)
 288          ret->flags |= BN_FLG_SECURE;
 289      return (ret);
 290  }
 291
 292 /* This is used by bn_expand2() */
 293 /* The caller MUST check that words > b->dmax before calling this */
 294 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
 295 {
 296     BN_ULONG *A, *a = NULL;
 297     const BN_ULONG *B;
 298     int i;
 299
 300     bn_check_top(b);
 301
 302     if (words > (INT_MAX / (4 * BN_BITS2))) {
 303         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
 304         return NULL;
 305     }
 306     if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
 307         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
 308         return (NULL);
 309     }
 310     if (BN_get_flags(b,BN_FLG_SECURE))
 311         a = A = OPENSSL_secure_zalloc(words * sizeof(*a));
 312     else
 313         a = A = OPENSSL_zalloc(words * sizeof(*a));
 314     if (A == NULL) {
 315         BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
 316         return (NULL);
 317     }
 318
 319 #if 1
 320     B = b->d;
 321     /* Check if the previous number needs to be copied */
 322     if (B != NULL) {
 323         for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
 324             /*
 325              * The fact that the loop is unrolled
 326              * 4-wise is a tribute to Intel. It's
 327              * the one that doesn't have enough
 328              * registers to accommodate more data.
 329              * I'd unroll it 8-wise otherwise:-)
 330              *
 331              *              <appro@fy.chalmers.se>
 332              */
 333             BN_ULONG a0, a1, a2, a3;
 334             a0 = B[0];
 335             a1 = B[1];
 336             a2 = B[2];
 337             a3 = B[3];
 338             A[0] = a0;
 339             A[1] = a1;
 340             A[2] = a2;
 341             A[3] = a3;
 342         }
 343         switch (b->top & 3) {
 344         case 3:
 345             A[2] = B[2];
 346         case 2:
 347             A[1] = B[1];
 348         case 1:
 349             A[0] = B[0];
 350         case 0:
 351             /* Without the "case 0" some old optimizers got this wrong. */
 352             ;
 353         }
 354     }
 355 #else
 356     memset(A, 0, sizeof(*A) * words);
 357     memcpy(A, b->d, sizeof(b->d[0]) * b->top);
 358 #endif
 359
 360     return (a);
 361 }
 362
 363 /*
 364  * This is an internal function that should not be used in applications. It
 365  * ensures that 'b' has enough room for a 'words' word number and initialises
 366  * any unused part of b->d with leading zeros. It is mostly used by the
 367  * various BIGNUM routines. If there is an error, NULL is returned. If not,
 368  * 'b' is returned.
 369  */
 370
 371 BIGNUM *bn_expand2(BIGNUM *b, int words)
 372 {
 373     bn_check_top(b);
 374
 375     if (words > b->dmax) {
 376         BN_ULONG *a = bn_expand_internal(b, words);
 377         if (!a)
 378             return NULL;
 379         if (b->d) {
 380             OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0]));
 381             bn_free_d(b);
 382         }
 383         b->d = a;
 384         b->dmax = words;
 385     }
 386
 387     bn_check_top(b);
 388     return b;
 389 }
 390
 391 BIGNUM *BN_dup(const BIGNUM *a)
 392 {
 393     BIGNUM *t;
 394
 395     if (a == NULL)
 396         return NULL;
 397     bn_check_top(a);
 398
 399     t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
 400     if (t == NULL)
 401         return NULL;
 402     if (!BN_copy(t, a)) {
 403         BN_free(t);
 404         return NULL;
 405     }
 406     bn_check_top(t);
 407     return t;
 408 }
 409
 410 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
 411 {
 412     int i;
 413     BN_ULONG *A;
 414     const BN_ULONG *B;
 415
 416     bn_check_top(b);
 417
 418     if (a == b)
 419         return (a);
 420     if (bn_wexpand(a, b->top) == NULL)
 421         return (NULL);
 422
 423 #if 1
 424     A = a->d;
 425     B = b->d;
 426     for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
 427         BN_ULONG a0, a1, a2, a3;
 428         a0 = B[0];
 429         a1 = B[1];
 430         a2 = B[2];
 431         a3 = B[3];
 432         A[0] = a0;
 433         A[1] = a1;
 434         A[2] = a2;
 435         A[3] = a3;
 436     }
 437     /* ultrix cc workaround, see comments in bn_expand_internal */
 438     switch (b->top & 3) {
 439     case 3:
 440         A[2] = B[2];
 441     case 2:
 442         A[1] = B[1];
 443     case 1:
 444         A[0] = B[0];
 445     case 0:;
 446     }
 447 #else
 448     memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
 449 #endif
 450
 451     a->top = b->top;
 452     a->neg = b->neg;
 453     bn_check_top(a);
 454     return (a);
 455 }
 456
 457 void BN_swap(BIGNUM *a, BIGNUM *b)
 458 {
 459     int flags_old_a, flags_old_b;
 460     BN_ULONG *tmp_d;
 461     int tmp_top, tmp_dmax, tmp_neg;
 462
 463     bn_check_top(a);
 464     bn_check_top(b);
 465
 466     flags_old_a = a->flags;
 467     flags_old_b = b->flags;
 468
 469     tmp_d = a->d;
 470     tmp_top = a->top;
 471     tmp_dmax = a->dmax;
 472     tmp_neg = a->neg;
 473
 474     a->d = b->d;
 475     a->top = b->top;
 476     a->dmax = b->dmax;
 477     a->neg = b->neg;
 478
 479     b->d = tmp_d;
 480     b->top = tmp_top;
 481     b->dmax = tmp_dmax;
 482     b->neg = tmp_neg;
 483
 484     a->flags =
 485         (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
 486     b->flags =
 487         (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
 488     bn_check_top(a);
 489     bn_check_top(b);
 490 }
 491
 492 void BN_clear(BIGNUM *a)
 493 {
 494     bn_check_top(a);
 495     if (a->d != NULL)
 496         memset(a->d, 0, sizeof(*a->d) * a->dmax);
 497     a->top = 0;
 498     a->neg = 0;
 499 }
 500
 501 BN_ULONG BN_get_word(const BIGNUM *a)
 502 {
 503     if (a->top > 1)
 504         return BN_MASK2;
 505     else if (a->top == 1)
 506         return a->d[0];
 507     /* a->top == 0 */
 508     return 0;
 509 }
 510
 511 int BN_set_word(BIGNUM *a, BN_ULONG w)
 512 {
 513     bn_check_top(a);
 514     if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
 515         return (0);
 516     a->neg = 0;
 517     a->d[0] = w;
 518     a->top = (w ? 1 : 0);
 519     bn_check_top(a);
 520     return (1);
 521 }
 522
 523 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
 524 {
 525     unsigned int i, m;
 526     unsigned int n;
 527     BN_ULONG l;
 528     BIGNUM *bn = NULL;
 529
 530     if (ret == NULL)
 531         ret = bn = BN_new();
 532     if (ret == NULL)
 533         return (NULL);
 534     bn_check_top(ret);
 535     /* Skip leading zero's. */
 536     for ( ; len > 0 && *s == 0; s++, len--)
 537         continue;
 538     n = len;
 539     if (n == 0) {
 540         ret->top = 0;
 541         return (ret);
 542     }
 543     i = ((n - 1) / BN_BYTES) + 1;
 544     m = ((n - 1) % (BN_BYTES));
 545     if (bn_wexpand(ret, (int)i) == NULL) {
 546         BN_free(bn);
 547         return NULL;
 548     }
 549     ret->top = i;
 550     ret->neg = 0;
 551     l = 0;
 552     while (n--) {
 553         l = (l << 8L) | *(s++);
 554         if (m-- == 0) {
 555             ret->d[--i] = l;
 556             l = 0;
 557             m = BN_BYTES - 1;
 558         }
 559     }
 560     /*
 561      * need to call this due to clear byte at top if avoiding having the top
 562      * bit set (-ve number)
 563      */
 564     bn_correct_top(ret);
 565     return (ret);
 566 }
 567
 568 /* ignore negative */
 569 static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
 570 {
 571     int i;
 572     BN_ULONG l;
 573
 574     bn_check_top(a);
 575     i = BN_num_bytes(a);
 576     if (tolen == -1)
 577         tolen = i;
 578     else if (tolen < i)
 579         return -1;
 580     /* Add leading zeroes if necessary */
 581     if (tolen > i) {
 582         memset(to, 0, tolen - i);
 583         to += tolen - i;
 584     }
 585     while (i--) {
 586         l = a->d[i / BN_BYTES];
 587         *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
 588     }
 589     return tolen;
 590 }
 591
 592 int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
 593 {
 594     if (tolen < 0)
 595         return -1;
 596     return bn2binpad(a, to, tolen);
 597 }
 598
 599 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
 600 {
 601     return bn2binpad(a, to, -1);
 602 }
 603
 604 BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
 605 {
 606     unsigned int i, m;
 607     unsigned int n;
 608     BN_ULONG l;
 609     BIGNUM *bn = NULL;
 610
 611     if (ret == NULL)
 612         ret = bn = BN_new();
 613     if (ret == NULL)
 614         return (NULL);
 615     bn_check_top(ret);
 616     s += len - 1;
 617     /* Skip trailing zeroes. */
 618     for ( ; len > 0 && *s == 0; s--, len--)
 619         continue;
 620     n = len;
 621     if (n == 0) {
 622         ret->top = 0;
 623         return ret;
 624     }
 625     i = ((n - 1) / BN_BYTES) + 1;
 626     m = ((n - 1) % (BN_BYTES));
 627     if (bn_wexpand(ret, (int)i) == NULL) {
 628         BN_free(bn);
 629         return NULL;
 630     }
 631     ret->top = i;
 632     ret->neg = 0;
 633     l = 0;
 634     while (n--) {
 635         l = (l << 8L) | *(s--);
 636         if (m-- == 0) {
 637             ret->d[--i] = l;
 638             l = 0;
 639             m = BN_BYTES - 1;
 640         }
 641     }
 642     /*
 643      * need to call this due to clear byte at top if avoiding having the top
 644      * bit set (-ve number)
 645      */
 646     bn_correct_top(ret);
 647     return ret;
 648 }
 649
 650 int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
 651 {
 652     int i;
 653     BN_ULONG l;
 654     bn_check_top(a);
 655     i = BN_num_bytes(a);
 656     if (tolen < i)
 657         return -1;
 658     /* Add trailing zeroes if necessary */
 659     if (tolen > i)
 660         memset(to + i, 0, tolen - i);
 661     to += i - 1;
 662     while (i--) {
 663         l = a->d[i / BN_BYTES];
 664         *(to--) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
 665     }
 666     return tolen;
 667 }
 668
 669 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
 670 {
 671     int i;
 672     BN_ULONG t1, t2, *ap, *bp;
 673
 674     bn_check_top(a);
 675     bn_check_top(b);
 676
 677     i = a->top - b->top;
 678     if (i != 0)
 679         return (i);
 680     ap = a->d;
 681     bp = b->d;
 682     for (i = a->top - 1; i >= 0; i--) {
 683         t1 = ap[i];
 684         t2 = bp[i];
 685         if (t1 != t2)
 686             return ((t1 > t2) ? 1 : -1);
 687     }
 688     return (0);
 689 }
 690
 691 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
 692 {
 693     int i;
 694     int gt, lt;
 695     BN_ULONG t1, t2;
 696
 697     if ((a == NULL) || (b == NULL)) {
 698         if (a != NULL)
 699             return (-1);
 700         else if (b != NULL)
 701             return (1);
 702         else
 703             return (0);
 704     }
 705
 706     bn_check_top(a);
 707     bn_check_top(b);
 708
 709     if (a->neg != b->neg) {
 710         if (a->neg)
 711             return (-1);
 712         else
 713             return (1);
 714     }
 715     if (a->neg == 0) {
 716         gt = 1;
 717         lt = -1;
 718     } else {
 719         gt = -1;
 720         lt = 1;
 721     }
 722
 723     if (a->top > b->top)
 724         return (gt);
 725     if (a->top < b->top)
 726         return (lt);
 727     for (i = a->top - 1; i >= 0; i--) {
 728         t1 = a->d[i];
 729         t2 = b->d[i];
 730         if (t1 > t2)
 731             return (gt);
 732         if (t1 < t2)
 733             return (lt);
 734     }
 735     return (0);
 736 }
 737
 738 int BN_set_bit(BIGNUM *a, int n)
 739 {
 740     int i, j, k;
 741
 742     if (n < 0)
 743         return 0;
 744
 745     i = n / BN_BITS2;
 746     j = n % BN_BITS2;
 747     if (a->top <= i) {
 748         if (bn_wexpand(a, i + 1) == NULL)
 749             return (0);
 750         for (k = a->top; k < i + 1; k++)
 751             a->d[k] = 0;
 752         a->top = i + 1;
 753     }
 754
 755     a->d[i] |= (((BN_ULONG)1) << j);
 756     bn_check_top(a);
 757     return (1);
 758 }
 759
 760 int BN_clear_bit(BIGNUM *a, int n)
 761 {
 762     int i, j;
 763
 764     bn_check_top(a);
 765     if (n < 0)
 766         return 0;
 767
 768     i = n / BN_BITS2;
 769     j = n % BN_BITS2;
 770     if (a->top <= i)
 771         return (0);
 772
 773     a->d[i] &= (~(((BN_ULONG)1) << j));
 774     bn_correct_top(a);
 775     return (1);
 776 }
 777
 778 int BN_is_bit_set(const BIGNUM *a, int n)
 779 {
 780     int i, j;
 781
 782     bn_check_top(a);
 783     if (n < 0)
 784         return 0;
 785     i = n / BN_BITS2;
 786     j = n % BN_BITS2;
 787     if (a->top <= i)
 788         return 0;
 789     return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
 790 }
 791
 792 int BN_mask_bits(BIGNUM *a, int n)
 793 {
 794     int b, w;
 795
 796     bn_check_top(a);
 797     if (n < 0)
 798         return 0;
 799
 800     w = n / BN_BITS2;
 801     b = n % BN_BITS2;
 802     if (w >= a->top)
 803         return 0;
 804     if (b == 0)
 805         a->top = w;
 806     else {
 807         a->top = w + 1;
 808         a->d[w] &= ~(BN_MASK2 << b);
 809     }
 810     bn_correct_top(a);
 811     return (1);
 812 }
 813
 814 void BN_set_negative(BIGNUM *a, int b)
 815 {
 816     if (b && !BN_is_zero(a))
 817         a->neg = 1;
 818     else
 819         a->neg = 0;
 820 }
 821
 822 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
 823 {
 824     int i;
 825     BN_ULONG aa, bb;
 826
 827     aa = a[n - 1];
 828     bb = b[n - 1];
 829     if (aa != bb)
 830         return ((aa > bb) ? 1 : -1);
 831     for (i = n - 2; i >= 0; i--) {
 832         aa = a[i];
 833         bb = b[i];
 834         if (aa != bb)
 835             return ((aa > bb) ? 1 : -1);
 836     }
 837     return (0);
 838 }
 839
 840 /*
 841  * Here follows a specialised variants of bn_cmp_words().  It has the
 842  * property of performing the operation on arrays of different sizes. The
 843  * sizes of those arrays is expressed through cl, which is the common length
 844  * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the
 845  * two lengths, calculated as len(a)-len(b). All lengths are the number of
 846  * BN_ULONGs...
 847  */
 848
 849 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
 850 {
 851     int n, i;
 852     n = cl - 1;
 853
 854     if (dl < 0) {
 855         for (i = dl; i < 0; i++) {
 856             if (b[n - i] != 0)
 857                 return -1;      /* a < b */
 858         }
 859     }
 860     if (dl > 0) {
 861         for (i = dl; i > 0; i--) {
 862             if (a[n + i] != 0)
 863                 return 1;       /* a > b */
 864         }
 865     }
 866     return bn_cmp_words(a, b, cl);
 867 }
 868
 869 /*
 870  * Constant-time conditional swap of a and b.
 871  * a and b are swapped if condition is not 0.  The code assumes that at most one bit of condition is set.
 872  * nwords is the number of words to swap.  The code assumes that at least nwords are allocated in both a and b,
 873  * and that no more than nwords are used by either a or b.
 874  * a and b cannot be the same number
 875  */
 876 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
 877 {
 878     BN_ULONG t;
 879     int i;
 880
 881     bn_wcheck_size(a, nwords);
 882     bn_wcheck_size(b, nwords);
 883
 884     assert(a != b);
 885     assert((condition & (condition - 1)) == 0);
 886     assert(sizeof(BN_ULONG) >= sizeof(int));
 887
 888     condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
 889
 890     t = (a->top ^ b->top) & condition;
 891     a->top ^= t;
 892     b->top ^= t;
 893
 894 #define BN_CONSTTIME_SWAP(ind) \
 895         do { \
 896                 t = (a->d[ind] ^ b->d[ind]) & condition; \
 897                 a->d[ind] ^= t; \
 898                 b->d[ind] ^= t; \
 899         } while (0)
 900
 901     switch (nwords) {
 902     default:
 903         for (i = 10; i < nwords; i++)
 904             BN_CONSTTIME_SWAP(i);
 905         /* Fallthrough */
 906     case 10:
 907         BN_CONSTTIME_SWAP(9);   /* Fallthrough */
 908     case 9:
 909         BN_CONSTTIME_SWAP(8);   /* Fallthrough */
 910     case 8:
 911         BN_CONSTTIME_SWAP(7);   /* Fallthrough */
 912     case 7:
 913         BN_CONSTTIME_SWAP(6);   /* Fallthrough */
 914     case 6:
 915         BN_CONSTTIME_SWAP(5);   /* Fallthrough */
 916     case 5:
 917         BN_CONSTTIME_SWAP(4);   /* Fallthrough */
 918     case 4:
 919         BN_CONSTTIME_SWAP(3);   /* Fallthrough */
 920     case 3:
 921         BN_CONSTTIME_SWAP(2);   /* Fallthrough */
 922     case 2:
 923         BN_CONSTTIME_SWAP(1);   /* Fallthrough */
 924     case 1:
 925         BN_CONSTTIME_SWAP(0);
 926     }
 927 #undef BN_CONSTTIME_SWAP
 928 }
 929
 930 /* Bits of security, see SP800-57 */
 931
 932 int BN_security_bits(int L, int N)
 933 {
 934     int secbits, bits;
 935     if (L >= 15360)
 936         secbits = 256;
 937     else if (L >= 7690)
 938         secbits = 192;
 939     else if (L >= 3072)
 940         secbits = 128;
 941     else if (L >= 2048)
 942         secbits = 112;
 943     else if (L >= 1024)
 944         secbits = 80;
 945     else
 946         return 0;
 947     if (N == -1)
 948         return secbits;
 949     bits = N / 2;
 950     if (bits < 80)
 951         return 0;
 952     return bits >= secbits ? secbits : bits;
 953 }
 954
 955 void BN_zero_ex(BIGNUM *a)
 956 {
 957     a->top = 0;
 958     a->neg = 0;
 959 }
 960
 961 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
 962 {
 963     return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
 964 }
 965
 966 int BN_is_zero(const BIGNUM *a)
 967 {
 968     return a->top == 0;
 969 }
 970
 971 int BN_is_one(const BIGNUM *a)
 972 {
 973     return BN_abs_is_word(a, 1) && !a->neg;
 974 }
 975
 976 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
 977 {
 978     return BN_abs_is_word(a, w) && (!w || !a->neg);
 979 }
 980
 981 int BN_is_odd(const BIGNUM *a)
 982 {
 983     return (a->top > 0) && (a->d[0] & 1);
 984 }
 985
 986 int BN_is_negative(const BIGNUM *a)
 987 {
 988     return (a->neg != 0);
 989 }
 990
 991 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
 992                      BN_CTX *ctx)
 993 {
 994     return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
 995 }
 996
 997 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
 998 {
 999     dest->d = b->d;
1000     dest->top = b->top;
1001     dest->dmax = b->dmax;
1002     dest->neg = b->neg;
1003     dest->flags = ((dest->flags & BN_FLG_MALLOCED)
1004                    | (b->flags & ~BN_FLG_MALLOCED)
1005                    | BN_FLG_STATIC_DATA | flags);
1006 }
1007
1008 BN_GENCB *BN_GENCB_new(void)
1009 {
1010     BN_GENCB *ret;
1011
1012     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
1013         BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
1014         return (NULL);
1015     }
1016
1017     return ret;
1018 }
1019
1020 void BN_GENCB_free(BN_GENCB *cb)
1021 {
1022     if (cb == NULL)
1023         return;
1024     OPENSSL_free(cb);
1025 }
1026
1027 void BN_set_flags(BIGNUM *b, int n)
1028 {
1029     b->flags |= n;
1030 }
1031
1032 int BN_get_flags(const BIGNUM *b, int n)
1033 {
1034     return b->flags & n;
1035 }
1036
1037 /* Populate a BN_GENCB structure with an "old"-style callback */
1038 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
1039                       void *cb_arg)
1040 {
1041     BN_GENCB *tmp_gencb = gencb;
1042     tmp_gencb->ver = 1;
1043     tmp_gencb->arg = cb_arg;
1044     tmp_gencb->cb.cb_1 = callback;
1045 }
1046
1047 /* Populate a BN_GENCB structure with a "new"-style callback */
1048 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
1049                   void *cb_arg)
1050 {
1051     BN_GENCB *tmp_gencb = gencb;
1052     tmp_gencb->ver = 2;
1053     tmp_gencb->arg = cb_arg;
1054     tmp_gencb->cb.cb_2 = callback;
1055 }
1056
1057 void *BN_GENCB_get_arg(BN_GENCB *cb)
1058 {
1059     return cb->arg;
1060 }
1061
1062 BIGNUM *bn_wexpand(BIGNUM *a, int words)
1063 {
1064     return (words <= a->dmax) ? a : bn_expand2(a, words);
1065 }
1066
1067 void bn_correct_top(BIGNUM *a)
1068 {
1069     BN_ULONG *ftl;
1070     int tmp_top = a->top;
1071
1072     if (tmp_top > 0) {
1073         for (ftl = &(a->d[tmp_top - 1]); tmp_top > 0; tmp_top--)
1074             if (*(ftl--))
1075                 break;
1076         a->top = tmp_top;
1077     }
1078     bn_pollute(a);
1079 }