crypto/openssl/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 BN_ULONG data_one = 1L;
 139     static BIGNUM const_one = { &data_one, 1, 1, 0, BN_FLG_STATIC_DATA };
 140
 141     return (&const_one);
 142 }
 143
 144 int BN_num_bits_word(BN_ULONG l)
 145 {
 146     static const char bits[256] = {
 147         0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
 148         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
 149         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 150         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
 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         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         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         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     };
 164
 165 #if defined(SIXTY_FOUR_BIT_LONG)
 166     if (l & 0xffffffff00000000L) {
 167         if (l & 0xffff000000000000L) {
 168             if (l & 0xff00000000000000L) {
 169                 return (bits[(int)(l >> 56)] + 56);
 170             } else
 171                 return (bits[(int)(l >> 48)] + 48);
 172         } else {
 173             if (l & 0x0000ff0000000000L) {
 174                 return (bits[(int)(l >> 40)] + 40);
 175             } else
 176                 return (bits[(int)(l >> 32)] + 32);
 177         }
 178     } else
 179 #else
 180 # ifdef SIXTY_FOUR_BIT
 181     if (l & 0xffffffff00000000LL) {
 182         if (l & 0xffff000000000000LL) {
 183             if (l & 0xff00000000000000LL) {
 184                 return (bits[(int)(l >> 56)] + 56);
 185             } else
 186                 return (bits[(int)(l >> 48)] + 48);
 187         } else {
 188             if (l & 0x0000ff0000000000LL) {
 189                 return (bits[(int)(l >> 40)] + 40);
 190             } else
 191                 return (bits[(int)(l >> 32)] + 32);
 192         }
 193     } else
 194 # endif
 195 #endif
 196     {
 197 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 198         if (l & 0xffff0000L) {
 199             if (l & 0xff000000L)
 200                 return (bits[(int)(l >> 24L)] + 24);
 201             else
 202                 return (bits[(int)(l >> 16L)] + 16);
 203         } else
 204 #endif
 205         {
 206 #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 207             if (l & 0xff00L)
 208                 return (bits[(int)(l >> 8)] + 8);
 209             else
 210 #endif
 211                 return (bits[(int)(l)]);
 212         }
 213     }
 214 }
 215
 216 int BN_num_bits(const BIGNUM *a)
 217 {
 218     int i = a->top - 1;
 219     bn_check_top(a);
 220
 221     if (BN_is_zero(a))
 222         return 0;
 223     return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
 224 }
 225
 226 void BN_clear_free(BIGNUM *a)
 227 {
 228     int i;
 229
 230     if (a == NULL)
 231         return;
 232     bn_check_top(a);
 233     if (a->d != NULL) {
 234         OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
 235         if (!(BN_get_flags(a, BN_FLG_STATIC_DATA)))
 236             OPENSSL_free(a->d);
 237     }
 238     i = BN_get_flags(a, BN_FLG_MALLOCED);
 239     OPENSSL_cleanse(a, sizeof(BIGNUM));
 240     if (i)
 241         OPENSSL_free(a);
 242 }
 243
 244 void BN_free(BIGNUM *a)
 245 {
 246     if (a == NULL)
 247         return;
 248     bn_check_top(a);
 249     if ((a->d != NULL) && !(BN_get_flags(a, BN_FLG_STATIC_DATA)))
 250         OPENSSL_free(a->d);
 251     if (a->flags & BN_FLG_MALLOCED)
 252         OPENSSL_free(a);
 253     else {
 254 #ifndef OPENSSL_NO_DEPRECATED
 255         a->flags |= BN_FLG_FREE;
 256 #endif
 257         a->d = NULL;
 258     }
 259 }
 260
 261 void BN_init(BIGNUM *a)
 262 {
 263     memset(a, 0, sizeof(BIGNUM));
 264     bn_check_top(a);
 265 }
 266
 267 BIGNUM *BN_new(void)
 268 {
 269     BIGNUM *ret;
 270
 271     if ((ret = (BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL) {
 272         BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
 273         return (NULL);
 274     }
 275     ret->flags = BN_FLG_MALLOCED;
 276     ret->top = 0;
 277     ret->neg = 0;
 278     ret->dmax = 0;
 279     ret->d = NULL;
 280     bn_check_top(ret);
 281     return (ret);
 282 }
 283
 284 /* This is used both by bn_expand2() and bn_dup_expand() */
 285 /* The caller MUST check that words > b->dmax before calling this */
 286 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
 287 {
 288     BN_ULONG *A, *a = NULL;
 289     const BN_ULONG *B;
 290     int i;
 291
 292     bn_check_top(b);
 293
 294     if (words > (INT_MAX / (4 * BN_BITS2))) {
 295         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
 296         return NULL;
 297     }
 298     if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
 299         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
 300         return (NULL);
 301     }
 302     a = A = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG) * words);
 303     if (A == NULL) {
 304         BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
 305         return (NULL);
 306     }
 307 #ifdef PURIFY
 308     /*
 309      * Valgrind complains in BN_consttime_swap because we process the whole
 310      * array even if it's not initialised yet. This doesn't matter in that
 311      * function - what's important is constant time operation (we're not
 312      * actually going to use the data)
 313      */
 314     memset(a, 0, sizeof(BN_ULONG) * words);
 315 #endif
 316
 317 #if 1
 318     B = b->d;
 319     /* Check if the previous number needs to be copied */
 320     if (B != NULL) {
 321         for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
 322             /*
 323              * The fact that the loop is unrolled
 324              * 4-wise is a tribute to Intel. It's
 325              * the one that doesn't have enough
 326              * registers to accomodate more data.
 327              * I'd unroll it 8-wise otherwise:-)
 328              *
 329              *              <appro@fy.chalmers.se>
 330              */
 331             BN_ULONG a0, a1, a2, a3;
 332             a0 = B[0];
 333             a1 = B[1];
 334             a2 = B[2];
 335             a3 = B[3];
 336             A[0] = a0;
 337             A[1] = a1;
 338             A[2] = a2;
 339             A[3] = a3;
 340         }
 341         /*
 342          * workaround for ultrix cc: without 'case 0', the optimizer does
 343          * the switch table by doing a=top&3; a--; goto jump_table[a];
 344          * which fails for top== 0
 345          */
 346         switch (b->top & 3) {
 347         case 3:
 348             A[2] = B[2];
 349         case 2:
 350             A[1] = B[1];
 351         case 1:
 352             A[0] = B[0];
 353         case 0:
 354             ;
 355         }
 356     }
 357 #else
 358     memset(A, 0, sizeof(BN_ULONG) * words);
 359     memcpy(A, b->d, sizeof(b->d[0]) * b->top);
 360 #endif
 361
 362     return (a);
 363 }
 364
 365 /*
 366  * This is an internal function that can be used instead of bn_expand2() when
 367  * there is a need to copy BIGNUMs instead of only expanding the data part,
 368  * while still expanding them. Especially useful when needing to expand
 369  * BIGNUMs that are declared 'const' and should therefore not be changed. The
 370  * reason to use this instead of a BN_dup() followed by a bn_expand2() is
 371  * memory allocation overhead.  A BN_dup() followed by a bn_expand2() will
 372  * allocate new memory for the BIGNUM data twice, and free it once, while
 373  * bn_dup_expand() makes sure allocation is made only once.
 374  */
 375
 376 #ifndef OPENSSL_NO_DEPRECATED
 377 BIGNUM *bn_dup_expand(const BIGNUM *b, int words)
 378 {
 379     BIGNUM *r = NULL;
 380
 381     bn_check_top(b);
 382
 383     /*
 384      * This function does not work if words <= b->dmax && top < words because
 385      * BN_dup() does not preserve 'dmax'! (But bn_dup_expand() is not used
 386      * anywhere yet.)
 387      */
 388
 389     if (words > b->dmax) {
 390         BN_ULONG *a = bn_expand_internal(b, words);
 391
 392         if (a) {
 393             r = BN_new();
 394             if (r) {
 395                 r->top = b->top;
 396                 r->dmax = words;
 397                 r->neg = b->neg;
 398                 r->d = a;
 399             } else {
 400                 /* r == NULL, BN_new failure */
 401                 OPENSSL_free(a);
 402             }
 403         }
 404         /*
 405          * If a == NULL, there was an error in allocation in
 406          * bn_expand_internal(), and NULL should be returned
 407          */
 408     } else {
 409         r = BN_dup(b);
 410     }
 411
 412     bn_check_top(r);
 413     return r;
 414 }
 415 #endif
 416
 417 /*
 418  * This is an internal function that should not be used in applications. It
 419  * ensures that 'b' has enough room for a 'words' word number and initialises
 420  * any unused part of b->d with leading zeros. It is mostly used by the
 421  * various BIGNUM routines. If there is an error, NULL is returned. If not,
 422  * 'b' is returned.
 423  */
 424
 425 BIGNUM *bn_expand2(BIGNUM *b, int words)
 426 {
 427     bn_check_top(b);
 428
 429     if (words > b->dmax) {
 430         BN_ULONG *a = bn_expand_internal(b, words);
 431         if (!a)
 432             return NULL;
 433         if (b->d)
 434             OPENSSL_free(b->d);
 435         b->d = a;
 436         b->dmax = words;
 437     }
 438
 439 /* None of this should be necessary because of what b->top means! */
 440 #if 0
 441     /*
 442      * NB: bn_wexpand() calls this only if the BIGNUM really has to grow
 443      */
 444     if (b->top < b->dmax) {
 445         int i;
 446         BN_ULONG *A = &(b->d[b->top]);
 447         for (i = (b->dmax - b->top) >> 3; i > 0; i--, A += 8) {
 448             A[0] = 0;
 449             A[1] = 0;
 450             A[2] = 0;
 451             A[3] = 0;
 452             A[4] = 0;
 453             A[5] = 0;
 454             A[6] = 0;
 455             A[7] = 0;
 456         }
 457         for (i = (b->dmax - b->top) & 7; i > 0; i--, A++)
 458             A[0] = 0;
 459         assert(A == &(b->d[b->dmax]));
 460     }
 461 #endif
 462     bn_check_top(b);
 463     return b;
 464 }
 465
 466 BIGNUM *BN_dup(const BIGNUM *a)
 467 {
 468     BIGNUM *t;
 469
 470     if (a == NULL)
 471         return NULL;
 472     bn_check_top(a);
 473
 474     t = BN_new();
 475     if (t == NULL)
 476         return NULL;
 477     if (!BN_copy(t, a)) {
 478         BN_free(t);
 479         return NULL;
 480     }
 481     bn_check_top(t);
 482     return t;
 483 }
 484
 485 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
 486 {
 487     int i;
 488     BN_ULONG *A;
 489     const BN_ULONG *B;
 490
 491     bn_check_top(b);
 492
 493     if (a == b)
 494         return (a);
 495     if (bn_wexpand(a, b->top) == NULL)
 496         return (NULL);
 497
 498 #if 1
 499     A = a->d;
 500     B = b->d;
 501     for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
 502         BN_ULONG a0, a1, a2, a3;
 503         a0 = B[0];
 504         a1 = B[1];
 505         a2 = B[2];
 506         a3 = B[3];
 507         A[0] = a0;
 508         A[1] = a1;
 509         A[2] = a2;
 510         A[3] = a3;
 511     }
 512     /* ultrix cc workaround, see comments in bn_expand_internal */
 513     switch (b->top & 3) {
 514     case 3:
 515         A[2] = B[2];
 516     case 2:
 517         A[1] = B[1];
 518     case 1:
 519         A[0] = B[0];
 520     case 0:;
 521     }
 522 #else
 523     memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
 524 #endif
 525
 526     a->top = b->top;
 527     a->neg = b->neg;
 528     bn_check_top(a);
 529     return (a);
 530 }
 531
 532 void BN_swap(BIGNUM *a, BIGNUM *b)
 533 {
 534     int flags_old_a, flags_old_b;
 535     BN_ULONG *tmp_d;
 536     int tmp_top, tmp_dmax, tmp_neg;
 537
 538     bn_check_top(a);
 539     bn_check_top(b);
 540
 541     flags_old_a = a->flags;
 542     flags_old_b = b->flags;
 543
 544     tmp_d = a->d;
 545     tmp_top = a->top;
 546     tmp_dmax = a->dmax;
 547     tmp_neg = a->neg;
 548
 549     a->d = b->d;
 550     a->top = b->top;
 551     a->dmax = b->dmax;
 552     a->neg = b->neg;
 553
 554     b->d = tmp_d;
 555     b->top = tmp_top;
 556     b->dmax = tmp_dmax;
 557     b->neg = tmp_neg;
 558
 559     a->flags =
 560         (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
 561     b->flags =
 562         (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
 563     bn_check_top(a);
 564     bn_check_top(b);
 565 }
 566
 567 void BN_clear(BIGNUM *a)
 568 {
 569     bn_check_top(a);
 570     if (a->d != NULL)
 571         memset(a->d, 0, a->dmax * sizeof(a->d[0]));
 572     a->top = 0;
 573     a->neg = 0;
 574 }
 575
 576 BN_ULONG BN_get_word(const BIGNUM *a)
 577 {
 578     if (a->top > 1)
 579         return BN_MASK2;
 580     else if (a->top == 1)
 581         return a->d[0];
 582     /* a->top == 0 */
 583     return 0;
 584 }
 585
 586 int BN_set_word(BIGNUM *a, BN_ULONG w)
 587 {
 588     bn_check_top(a);
 589     if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
 590         return (0);
 591     a->neg = 0;
 592     a->d[0] = w;
 593     a->top = (w ? 1 : 0);
 594     bn_check_top(a);
 595     return (1);
 596 }
 597
 598 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
 599 {
 600     unsigned int i, m;
 601     unsigned int n;
 602     BN_ULONG l;
 603     BIGNUM *bn = NULL;
 604
 605     if (ret == NULL)
 606         ret = bn = BN_new();
 607     if (ret == NULL)
 608         return (NULL);
 609     bn_check_top(ret);
 610     l = 0;
 611     n = len;
 612     if (n == 0) {
 613         ret->top = 0;
 614         return (ret);
 615     }
 616     i = ((n - 1) / BN_BYTES) + 1;
 617     m = ((n - 1) % (BN_BYTES));
 618     if (bn_wexpand(ret, (int)i) == NULL) {
 619         if (bn)
 620             BN_free(bn);
 621         return NULL;
 622     }
 623     ret->top = i;
 624     ret->neg = 0;
 625     while (n--) {
 626         l = (l << 8L) | *(s++);
 627         if (m-- == 0) {
 628             ret->d[--i] = l;
 629             l = 0;
 630             m = BN_BYTES - 1;
 631         }
 632     }
 633     /*
 634      * need to call this due to clear byte at top if avoiding having the top
 635      * bit set (-ve number)
 636      */
 637     bn_correct_top(ret);
 638     return (ret);
 639 }
 640
 641 /* ignore negative */
 642 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
 643 {
 644     int n, i;
 645     BN_ULONG l;
 646
 647     bn_check_top(a);
 648     n = i = BN_num_bytes(a);
 649     while (i--) {
 650         l = a->d[i / BN_BYTES];
 651         *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
 652     }
 653     return (n);
 654 }
 655
 656 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
 657 {
 658     int i;
 659     BN_ULONG t1, t2, *ap, *bp;
 660
 661     bn_check_top(a);
 662     bn_check_top(b);
 663
 664     i = a->top - b->top;
 665     if (i != 0)
 666         return (i);
 667     ap = a->d;
 668     bp = b->d;
 669     for (i = a->top - 1; i >= 0; i--) {
 670         t1 = ap[i];
 671         t2 = bp[i];
 672         if (t1 != t2)
 673             return ((t1 > t2) ? 1 : -1);
 674     }
 675     return (0);
 676 }
 677
 678 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
 679 {
 680     int i;
 681     int gt, lt;
 682     BN_ULONG t1, t2;
 683
 684     if ((a == NULL) || (b == NULL)) {
 685         if (a != NULL)
 686             return (-1);
 687         else if (b != NULL)
 688             return (1);
 689         else
 690             return (0);
 691     }
 692
 693     bn_check_top(a);
 694     bn_check_top(b);
 695
 696     if (a->neg != b->neg) {
 697         if (a->neg)
 698             return (-1);
 699         else
 700             return (1);
 701     }
 702     if (a->neg == 0) {
 703         gt = 1;
 704         lt = -1;
 705     } else {
 706         gt = -1;
 707         lt = 1;
 708     }
 709
 710     if (a->top > b->top)
 711         return (gt);
 712     if (a->top < b->top)
 713         return (lt);
 714     for (i = a->top - 1; i >= 0; i--) {
 715         t1 = a->d[i];
 716         t2 = b->d[i];
 717         if (t1 > t2)
 718             return (gt);
 719         if (t1 < t2)
 720             return (lt);
 721     }
 722     return (0);
 723 }
 724
 725 int BN_set_bit(BIGNUM *a, int n)
 726 {
 727     int i, j, k;
 728
 729     if (n < 0)
 730         return 0;
 731
 732     i = n / BN_BITS2;
 733     j = n % BN_BITS2;
 734     if (a->top <= i) {
 735         if (bn_wexpand(a, i + 1) == NULL)
 736             return (0);
 737         for (k = a->top; k < i + 1; k++)
 738             a->d[k] = 0;
 739         a->top = i + 1;
 740     }
 741
 742     a->d[i] |= (((BN_ULONG)1) << j);
 743     bn_check_top(a);
 744     return (1);
 745 }
 746
 747 int BN_clear_bit(BIGNUM *a, int n)
 748 {
 749     int i, j;
 750
 751     bn_check_top(a);
 752     if (n < 0)
 753         return 0;
 754
 755     i = n / BN_BITS2;
 756     j = n % BN_BITS2;
 757     if (a->top <= i)
 758         return (0);
 759
 760     a->d[i] &= (~(((BN_ULONG)1) << j));
 761     bn_correct_top(a);
 762     return (1);
 763 }
 764
 765 int BN_is_bit_set(const BIGNUM *a, int n)
 766 {
 767     int i, j;
 768
 769     bn_check_top(a);
 770     if (n < 0)
 771         return 0;
 772     i = n / BN_BITS2;
 773     j = n % BN_BITS2;
 774     if (a->top <= i)
 775         return 0;
 776     return (((a->d[i]) >> j) & ((BN_ULONG)1));
 777 }
 778
 779 int BN_mask_bits(BIGNUM *a, int n)
 780 {
 781     int b, w;
 782
 783     bn_check_top(a);
 784     if (n < 0)
 785         return 0;
 786
 787     w = n / BN_BITS2;
 788     b = n % BN_BITS2;
 789     if (w >= a->top)
 790         return 0;
 791     if (b == 0)
 792         a->top = w;
 793     else {
 794         a->top = w + 1;
 795         a->d[w] &= ~(BN_MASK2 << b);
 796     }
 797     bn_correct_top(a);
 798     return (1);
 799 }
 800
 801 void BN_set_negative(BIGNUM *a, int b)
 802 {
 803     if (b && !BN_is_zero(a))
 804         a->neg = 1;
 805     else
 806         a->neg = 0;
 807 }
 808
 809 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
 810 {
 811     int i;
 812     BN_ULONG aa, bb;
 813
 814     aa = a[n - 1];
 815     bb = b[n - 1];
 816     if (aa != bb)
 817         return ((aa > bb) ? 1 : -1);
 818     for (i = n - 2; i >= 0; i--) {
 819         aa = a[i];
 820         bb = b[i];
 821         if (aa != bb)
 822             return ((aa > bb) ? 1 : -1);
 823     }
 824     return (0);
 825 }
 826
 827 /*
 828  * Here follows a specialised variants of bn_cmp_words().  It has the
 829  * property of performing the operation on arrays of different sizes. The
 830  * sizes of those arrays is expressed through cl, which is the common length
 831  * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the
 832  * two lengths, calculated as len(a)-len(b). All lengths are the number of
 833  * BN_ULONGs...
 834  */
 835
 836 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
 837 {
 838     int n, i;
 839     n = cl - 1;
 840
 841     if (dl < 0) {
 842         for (i = dl; i < 0; i++) {
 843             if (b[n - i] != 0)
 844                 return -1;      /* a < b */
 845         }
 846     }
 847     if (dl > 0) {
 848         for (i = dl; i > 0; i--) {
 849             if (a[n + i] != 0)
 850                 return 1;       /* a > b */
 851         }
 852     }
 853     return bn_cmp_words(a, b, cl);
 854 }