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