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     a->top = b->top;
 528     a->neg = b->neg;
 529     bn_check_top(a);
 530     return (a);
 531 }
 532
 533 void BN_swap(BIGNUM *a, BIGNUM *b)
 534 {
 535     int flags_old_a, flags_old_b;
 536     BN_ULONG *tmp_d;
 537     int tmp_top, tmp_dmax, tmp_neg;
 538
 539     bn_check_top(a);
 540     bn_check_top(b);
 541
 542     flags_old_a = a->flags;
 543     flags_old_b = b->flags;
 544
 545     tmp_d = a->d;
 546     tmp_top = a->top;
 547     tmp_dmax = a->dmax;
 548     tmp_neg = a->neg;
 549
 550     a->d = b->d;
 551     a->top = b->top;
 552     a->dmax = b->dmax;
 553     a->neg = b->neg;
 554
 555     b->d = tmp_d;
 556     b->top = tmp_top;
 557     b->dmax = tmp_dmax;
 558     b->neg = tmp_neg;
 559
 560     a->flags =
 561         (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
 562     b->flags =
 563         (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
 564     bn_check_top(a);
 565     bn_check_top(b);
 566 }
 567
 568 void BN_clear(BIGNUM *a)
 569 {
 570     bn_check_top(a);
 571     if (a->d != NULL)
 572         OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
 573     a->top = 0;
 574     a->neg = 0;
 575 }
 576
 577 BN_ULONG BN_get_word(const BIGNUM *a)
 578 {
 579     if (a->top > 1)
 580         return BN_MASK2;
 581     else if (a->top == 1)
 582         return a->d[0];
 583     /* a->top == 0 */
 584     return 0;
 585 }
 586
 587 int BN_set_word(BIGNUM *a, BN_ULONG w)
 588 {
 589     bn_check_top(a);
 590     if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
 591         return (0);
 592     a->neg = 0;
 593     a->d[0] = w;
 594     a->top = (w ? 1 : 0);
 595     bn_check_top(a);
 596     return (1);
 597 }
 598
 599 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
 600 {
 601     unsigned int i, m;
 602     unsigned int n;
 603     BN_ULONG l;
 604     BIGNUM *bn = NULL;
 605
 606     if (ret == NULL)
 607         ret = bn = BN_new();
 608     if (ret == NULL)
 609         return (NULL);
 610     bn_check_top(ret);
 611     l = 0;
 612     n = len;
 613     if (n == 0) {
 614         ret->top = 0;
 615         return (ret);
 616     }
 617     i = ((n - 1) / BN_BYTES) + 1;
 618     m = ((n - 1) % (BN_BYTES));
 619     if (bn_wexpand(ret, (int)i) == NULL) {
 620         if (bn)
 621             BN_free(bn);
 622         return NULL;
 623     }
 624     ret->top = i;
 625     ret->neg = 0;
 626     while (n--) {
 627         l = (l << 8L) | *(s++);
 628         if (m-- == 0) {
 629             ret->d[--i] = l;
 630             l = 0;
 631             m = BN_BYTES - 1;
 632         }
 633     }
 634     /*
 635      * need to call this due to clear byte at top if avoiding having the top
 636      * bit set (-ve number)
 637      */
 638     bn_correct_top(ret);
 639     return (ret);
 640 }
 641
 642 /* ignore negative */
 643 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
 644 {
 645     int n, i;
 646     BN_ULONG l;
 647
 648     bn_check_top(a);
 649     n = i = BN_num_bytes(a);
 650     while (i--) {
 651         l = a->d[i / BN_BYTES];
 652         *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
 653     }
 654     return (n);
 655 }
 656
 657 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
 658 {
 659     int i;
 660     BN_ULONG t1, t2, *ap, *bp;
 661
 662     bn_check_top(a);
 663     bn_check_top(b);
 664
 665     i = a->top - b->top;
 666     if (i != 0)
 667         return (i);
 668     ap = a->d;
 669     bp = b->d;
 670     for (i = a->top - 1; i >= 0; i--) {
 671         t1 = ap[i];
 672         t2 = bp[i];
 673         if (t1 != t2)
 674             return ((t1 > t2) ? 1 : -1);
 675     }
 676     return (0);
 677 }
 678
 679 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
 680 {
 681     int i;
 682     int gt, lt;
 683     BN_ULONG t1, t2;
 684
 685     if ((a == NULL) || (b == NULL)) {
 686         if (a != NULL)
 687             return (-1);
 688         else if (b != NULL)
 689             return (1);
 690         else
 691             return (0);
 692     }
 693
 694     bn_check_top(a);
 695     bn_check_top(b);
 696
 697     if (a->neg != b->neg) {
 698         if (a->neg)
 699             return (-1);
 700         else
 701             return (1);
 702     }
 703     if (a->neg == 0) {
 704         gt = 1;
 705         lt = -1;
 706     } else {
 707         gt = -1;
 708         lt = 1;
 709     }
 710
 711     if (a->top > b->top)
 712         return (gt);
 713     if (a->top < b->top)
 714         return (lt);
 715     for (i = a->top - 1; i >= 0; i--) {
 716         t1 = a->d[i];
 717         t2 = b->d[i];
 718         if (t1 > t2)
 719             return (gt);
 720         if (t1 < t2)
 721             return (lt);
 722     }
 723     return (0);
 724 }
 725
 726 int BN_set_bit(BIGNUM *a, int n)
 727 {
 728     int i, j, k;
 729
 730     if (n < 0)
 731         return 0;
 732
 733     i = n / BN_BITS2;
 734     j = n % BN_BITS2;
 735     if (a->top <= i) {
 736         if (bn_wexpand(a, i + 1) == NULL)
 737             return (0);
 738         for (k = a->top; k < i + 1; k++)
 739             a->d[k] = 0;
 740         a->top = i + 1;
 741     }
 742
 743     a->d[i] |= (((BN_ULONG)1) << j);
 744     bn_check_top(a);
 745     return (1);
 746 }
 747
 748 int BN_clear_bit(BIGNUM *a, int n)
 749 {
 750     int i, j;
 751
 752     bn_check_top(a);
 753     if (n < 0)
 754         return 0;
 755
 756     i = n / BN_BITS2;
 757     j = n % BN_BITS2;
 758     if (a->top <= i)
 759         return (0);
 760
 761     a->d[i] &= (~(((BN_ULONG)1) << j));
 762     bn_correct_top(a);
 763     return (1);
 764 }
 765
 766 int BN_is_bit_set(const BIGNUM *a, int n)
 767 {
 768     int i, j;
 769
 770     bn_check_top(a);
 771     if (n < 0)
 772         return 0;
 773     i = n / BN_BITS2;
 774     j = n % BN_BITS2;
 775     if (a->top <= i)
 776         return 0;
 777     return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
 778 }
 779
 780 int BN_mask_bits(BIGNUM *a, int n)
 781 {
 782     int b, w;
 783
 784     bn_check_top(a);
 785     if (n < 0)
 786         return 0;
 787
 788     w = n / BN_BITS2;
 789     b = n % BN_BITS2;
 790     if (w >= a->top)
 791         return 0;
 792     if (b == 0)
 793         a->top = w;
 794     else {
 795         a->top = w + 1;
 796         a->d[w] &= ~(BN_MASK2 << b);
 797     }
 798     bn_correct_top(a);
 799     return (1);
 800 }
 801
 802 void BN_set_negative(BIGNUM *a, int b)
 803 {
 804     if (b && !BN_is_zero(a))
 805         a->neg = 1;
 806     else
 807         a->neg = 0;
 808 }
 809
 810 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
 811 {
 812     int i;
 813     BN_ULONG aa, bb;
 814
 815     aa = a[n - 1];
 816     bb = b[n - 1];
 817     if (aa != bb)
 818         return ((aa > bb) ? 1 : -1);
 819     for (i = n - 2; i >= 0; i--) {
 820         aa = a[i];
 821         bb = b[i];
 822         if (aa != bb)
 823             return ((aa > bb) ? 1 : -1);
 824     }
 825     return (0);
 826 }
 827
 828 /*
 829  * Here follows a specialised variants of bn_cmp_words().  It has the
 830  * property of performing the operation on arrays of different sizes. The
 831  * sizes of those arrays is expressed through cl, which is the common length
 832  * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the
 833  * two lengths, calculated as len(a)-len(b). All lengths are the number of
 834  * BN_ULONGs...
 835  */
 836
 837 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
 838 {
 839     int n, i;
 840     n = cl - 1;
 841
 842     if (dl < 0) {
 843         for (i = dl; i < 0; i++) {
 844             if (b[n - i] != 0)
 845                 return -1;      /* a < b */
 846         }
 847     }
 848     if (dl > 0) {
 849         for (i = dl; i > 0; i--) {
 850             if (a[n + i] != 0)
 851                 return 1;       /* a > b */
 852         }
 853     }
 854     return bn_cmp_words(a, b, cl);
 855 }
 856
 857 /*
 858  * Constant-time conditional swap of a and b.
 859  * a and b are swapped if condition is not 0.  The code assumes that at most one bit of condition is set.
 860  * nwords is the number of words to swap.  The code assumes that at least nwords are allocated in both a and b,
 861  * and that no more than nwords are used by either a or b.
 862  * a and b cannot be the same number
 863  */
 864 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
 865 {
 866     BN_ULONG t;
 867     int i;
 868
 869     bn_wcheck_size(a, nwords);
 870     bn_wcheck_size(b, nwords);
 871
 872     assert(a != b);
 873     assert((condition & (condition - 1)) == 0);
 874     assert(sizeof(BN_ULONG) >= sizeof(int));
 875
 876     condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
 877
 878     t = (a->top ^ b->top) & condition;
 879     a->top ^= t;
 880     b->top ^= t;
 881
 882 #define BN_CONSTTIME_SWAP(ind) \
 883         do { \
 884                 t = (a->d[ind] ^ b->d[ind]) & condition; \
 885                 a->d[ind] ^= t; \
 886                 b->d[ind] ^= t; \
 887         } while (0)
 888
 889     switch (nwords) {
 890     default:
 891         for (i = 10; i < nwords; i++)
 892             BN_CONSTTIME_SWAP(i);
 893         /* Fallthrough */
 894     case 10:
 895         BN_CONSTTIME_SWAP(9);   /* Fallthrough */
 896     case 9:
 897         BN_CONSTTIME_SWAP(8);   /* Fallthrough */
 898     case 8:
 899         BN_CONSTTIME_SWAP(7);   /* Fallthrough */
 900     case 7:
 901         BN_CONSTTIME_SWAP(6);   /* Fallthrough */
 902     case 6:
 903         BN_CONSTTIME_SWAP(5);   /* Fallthrough */
 904     case 5:
 905         BN_CONSTTIME_SWAP(4);   /* Fallthrough */
 906     case 4:
 907         BN_CONSTTIME_SWAP(3);   /* Fallthrough */
 908     case 3:
 909         BN_CONSTTIME_SWAP(2);   /* Fallthrough */
 910     case 2:
 911         BN_CONSTTIME_SWAP(1);   /* Fallthrough */
 912     case 1:
 913         BN_CONSTTIME_SWAP(0);
 914     }
 915 #undef BN_CONSTTIME_SWAP
 916 }