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