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