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