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