crypto/bn/bn_lib.c

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