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 #include <stdio.h>
  60 #include "cryptlib.h"
  61 #include "bn_lcl.h"
  62
  63 char *BN_version="Big Number part of SSLeay 0.9.0b 29-Jun-1998";
  64
  65 BIGNUM *BN_value_one()
  66         {
  67         static BN_ULONG data_one=1L;
  68         static BIGNUM const_one={&data_one,1,1,0};
  69
  70         return(&const_one);
  71         }
  72
  73 char *BN_options()
  74         {
  75         static int init=0;
  76         static char data[16];
  77
  78         if (!init)
  79                 {
  80                 init++;
  81 #ifdef BN_LLONG
  82                 sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULLONG)*8,
  83                         (int)sizeof(BN_ULONG)*8);
  84 #else
  85                 sprintf(data,"bn(%d,%d)",(int)sizeof(BN_ULONG)*8,
  86                         (int)sizeof(BN_ULONG)*8);
  87 #endif
  88                 }
  89         return(data);
  90         }
  91
  92 int BN_num_bits_word(l)
  93 BN_ULONG l;
  94         {
  95         static char bits[256]={
  96                 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
  97                 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
  98                 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
  99                 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
 100                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 101                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 102                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 103                 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 104                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 105                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 106                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 107                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 108                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 109                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 110                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 111                 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
 112                 };
 113
 114 #ifdef SIXTY_FOUR_BIT_LONG
 115         if (l & 0xffffffff00000000L)
 116                 {
 117                 if (l & 0xffff000000000000L)
 118                         {
 119                         if (l & 0xff00000000000000L)
 120                                 {
 121                                 return(bits[l>>56]+56);
 122                                 }
 123                         else    return(bits[l>>48]+48);
 124                         }
 125                 else
 126                         {
 127                         if (l & 0x0000ff0000000000L)
 128                                 {
 129                                 return(bits[l>>40]+40);
 130                                 }
 131                         else    return(bits[l>>32]+32);
 132                         }
 133                 }
 134         else
 135 #else
 136 #ifdef SIXTY_FOUR_BIT
 137         if (l & 0xffffffff00000000LL)
 138                 {
 139                 if (l & 0xffff000000000000LL)
 140                         {
 141                         if (l & 0xff00000000000000LL)
 142                                 {
 143                                 return(bits[l>>56]+56);
 144                                 }
 145                         else    return(bits[l>>48]+48);
 146                         }
 147                 else
 148                         {
 149                         if (l & 0x0000ff0000000000LL)
 150                                 {
 151                                 return(bits[l>>40]+40);
 152                                 }
 153                         else    return(bits[l>>32]+32);
 154                         }
 155                 }
 156         else
 157 #endif
 158 #endif
 159                 {
 160 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 161                 if (l & 0xffff0000L)
 162                         {
 163                         if (l & 0xff000000L)
 164                                 return(bits[l>>24L]+24);
 165                         else    return(bits[l>>16L]+16);
 166                         }
 167                 else
 168 #endif
 169                         {
 170 #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 171                         if (l & 0xff00L)
 172                                 return(bits[l>>8]+8);
 173                         else
 174 #endif
 175                                 return(bits[l   ]  );
 176                         }
 177                 }
 178         }
 179
 180 int BN_num_bits(a)
 181 BIGNUM *a;
 182         {
 183         BN_ULONG l;
 184         int i;
 185
 186         if (a->top == 0) return(0);
 187         l=a->d[a->top-1];
 188         i=(a->top-1)*BN_BITS2;
 189         if (l == 0)
 190                 {
 191 #if !defined(NO_STDIO) && !defined(WIN16)
 192                 fprintf(stderr,"BAD TOP VALUE\n");
 193 #endif
 194                 abort();
 195                 }
 196         return(i+BN_num_bits_word(l));
 197         }
 198
 199 void BN_clear_free(a)
 200 BIGNUM *a;
 201         {
 202         if (a == NULL) return;
 203         if (a->d != NULL)
 204                 {
 205                 memset(a->d,0,a->max*sizeof(a->d[0]));
 206                 Free(a->d);
 207                 }
 208         memset(a,0,sizeof(BIGNUM));
 209         Free(a);
 210         }
 211
 212 void BN_free(a)
 213 BIGNUM *a;
 214         {
 215         if (a == NULL) return;
 216         if (a->d != NULL) Free(a->d);
 217         Free(a);
 218         }
 219
 220 BIGNUM *BN_new()
 221         {
 222         BIGNUM *ret;
 223         BN_ULONG *p;
 224
 225         ret=(BIGNUM *)Malloc(sizeof(BIGNUM));
 226         if (ret == NULL) goto err;
 227         ret->top=0;
 228         ret->neg=0;
 229         ret->max=(BN_DEFAULT_BITS/BN_BITS2);
 230         p=(BN_ULONG *)Malloc(sizeof(BN_ULONG)*(ret->max+1));
 231         if (p == NULL) goto err;
 232         ret->d=p;
 233
 234         memset(p,0,(ret->max+1)*sizeof(p[0]));
 235         return(ret);
 236 err:
 237         BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE);
 238         return(NULL);
 239         }
 240
 241 BN_CTX *BN_CTX_new()
 242         {
 243         BN_CTX *ret;
 244         BIGNUM *n;
 245         int i,j;
 246
 247         ret=(BN_CTX *)Malloc(sizeof(BN_CTX));
 248         if (ret == NULL) goto err2;
 249
 250         for (i=0; i<BN_CTX_NUM; i++)
 251                 {
 252                 n=BN_new();
 253                 if (n == NULL) goto err;
 254                 ret->bn[i]=n;
 255                 }
 256
 257         /* There is actually an extra one, this is for debugging my
 258          * stuff */
 259         ret->bn[BN_CTX_NUM]=NULL;
 260
 261         ret->tos=0;
 262         return(ret);
 263 err:
 264         for (j=0; j<i; j++)
 265                 BN_free(ret->bn[j]);
 266         Free(ret);
 267 err2:
 268         BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE);
 269         return(NULL);
 270         }
 271
 272 void BN_CTX_free(c)
 273 BN_CTX *c;
 274         {
 275         int i;
 276
 277         for (i=0; i<BN_CTX_NUM; i++)
 278                 BN_clear_free(c->bn[i]);
 279         Free(c);
 280         }
 281
 282 BIGNUM *bn_expand2(b, words)
 283 BIGNUM *b;
 284 int words;
 285         {
 286         BN_ULONG *p;
 287
 288         if (words > b->max)
 289                 {
 290                 p=(BN_ULONG *)Realloc(b->d,sizeof(BN_ULONG)*(words+1));
 291                 if (p == NULL)
 292                         {
 293                         BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE);
 294                         return(NULL);
 295                         }
 296                 b->d=p;
 297                 memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG));
 298                 b->max=words;
 299                 }
 300         return(b);
 301         }
 302
 303 BIGNUM *BN_dup(a)
 304 BIGNUM *a;
 305         {
 306         BIGNUM *r;
 307
 308         r=BN_new();
 309         if (r == NULL) return(NULL);
 310         return((BIGNUM *)BN_copy(r,a));
 311         }
 312
 313 BIGNUM *BN_copy(a, b)
 314 BIGNUM *a;
 315 BIGNUM *b;
 316         {
 317         int i;
 318         BN_ULONG *A,*B;
 319
 320         if (a == b) return(a);
 321         if (bn_wexpand(a,b->top) == NULL) return(NULL);
 322
 323 #if 1
 324         A=a->d;
 325         B=b->d;
 326         for (i=b->top&(~7); i>0; i-=8)
 327                 {
 328                 A[0]=B[0];
 329                 A[1]=B[1];
 330                 A[2]=B[2];
 331                 A[3]=B[3];
 332                 A[4]=B[4];
 333                 A[5]=B[5];
 334                 A[6]=B[6];
 335                 A[7]=B[7];
 336                 A+=8;
 337                 B+=8;
 338                 }
 339         switch (b->top&7)
 340                 {
 341         case 7:
 342                 A[6]=B[6];
 343         case 6:
 344                 A[5]=B[5];
 345         case 5:
 346                 A[4]=B[4];
 347         case 4:
 348                 A[3]=B[3];
 349         case 3:
 350                 A[2]=B[2];
 351         case 2:
 352                 A[1]=B[1];
 353         case 1:
 354                 A[0]=B[0];
 355                 }
 356 #else
 357         memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
 358 #endif
 359
 360 /*      memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/
 361         a->top=b->top;
 362         if (a->top == 0)
 363                 a->d[0]=0;
 364         a->neg=b->neg;
 365         return(a);
 366         }
 367
 368 void BN_clear(a)
 369 BIGNUM *a;
 370         {
 371         memset(a->d,0,a->max*sizeof(a->d[0]));
 372         a->top=0;
 373         a->neg=0;
 374         }
 375
 376 unsigned long BN_get_word(a)
 377 BIGNUM *a;
 378         {
 379         int i,n;
 380         unsigned long ret=0;
 381
 382         n=BN_num_bytes(a);
 383         if (n > sizeof(unsigned long))
 384 #ifdef SIXTY_FOUR_BIT_LONG
 385                 return(BN_MASK2);
 386 #else
 387                 return(0xFFFFFFFFL);
 388 #endif
 389         for (i=a->top-1; i>=0; i--)
 390                 {
 391 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
 392                 ret<<=BN_BITS4; /* stops the compiler complaining */
 393                 ret<<=BN_BITS4;
 394 #endif
 395                 ret|=a->d[i];
 396                 }
 397         return(ret);
 398         }
 399
 400 int BN_set_word(a,w)
 401 BIGNUM *a;
 402 unsigned long w;
 403         {
 404         int i,n;
 405         if (bn_expand(a,sizeof(unsigned long)*8) == NULL) return(0);
 406
 407         n=sizeof(unsigned long)/BN_BYTES;
 408         a->neg=0;
 409         a->top=0;
 410         a->d[0]=(BN_ULONG)w&BN_MASK2;
 411         if (a->d[0] != 0) a->top=1;
 412         for (i=1; i<n; i++)
 413                 {
 414                 /* the following is done instead of
 415                  * w>>=BN_BITS2 so compilers don't complain
 416                  * on builds where sizeof(long) == BN_TYPES */
 417 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
 418                 w>>=BN_BITS4;
 419                 w>>=BN_BITS4;
 420 #endif
 421                 a->d[i]=(BN_ULONG)w&BN_MASK2;
 422                 if (a->d[i] != 0) a->top=i+1;
 423                 }
 424         return(1);
 425         }
 426
 427 /* ignore negative */
 428 BIGNUM *BN_bin2bn(s, len, ret)
 429 unsigned char *s;
 430 int len;
 431 BIGNUM *ret;
 432         {
 433         unsigned int i,m;
 434         unsigned int n;
 435         BN_ULONG l;
 436
 437         if (ret == NULL) ret=BN_new();
 438         if (ret == NULL) return(NULL);
 439         l=0;
 440         n=len;
 441         if (n == 0)
 442                 {
 443                 ret->top=0;
 444                 return(ret);
 445                 }
 446         if (bn_expand(ret,(int)(n+2)*8) == NULL)
 447                 return(NULL);
 448         i=((n-1)/BN_BYTES)+1;
 449         m=((n-1)%(BN_BYTES));
 450         ret->top=i;
 451         while (n-- > 0)
 452                 {
 453                 l=(l<<8L)| *(s++);
 454                 if (m-- == 0)
 455                         {
 456                         ret->d[--i]=l;
 457                         l=0;
 458                         m=BN_BYTES-1;
 459                         }
 460                 }
 461         /* need to call this due to clear byte at top if avoiding
 462          * having the top bit set (-ve number) */
 463         bn_fix_top(ret);
 464         return(ret);
 465         }
 466
 467 /* ignore negative */
 468 int BN_bn2bin(a, to)
 469 BIGNUM *a;
 470 unsigned char *to;
 471         {
 472         int n,i;
 473         BN_ULONG l;
 474
 475         n=i=BN_num_bytes(a);
 476         while (i-- > 0)
 477                 {
 478                 l=a->d[i/BN_BYTES];
 479                 *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
 480                 }
 481         return(n);
 482         }
 483
 484 int BN_ucmp(a, b)
 485 BIGNUM *a;
 486 BIGNUM *b;
 487         {
 488         int i;
 489         BN_ULONG t1,t2,*ap,*bp;
 490
 491         i=a->top-b->top;
 492         if (i != 0) return(i);
 493         ap=a->d;
 494         bp=b->d;
 495         for (i=a->top-1; i>=0; i--)
 496                 {
 497                 t1= ap[i];
 498                 t2= bp[i];
 499                 if (t1 != t2)
 500                         return(t1 > t2?1:-1);
 501                 }
 502         return(0);
 503         }
 504
 505 int BN_cmp(a, b)
 506 BIGNUM *a;
 507 BIGNUM *b;
 508         {
 509         int i;
 510         int gt,lt;
 511         BN_ULONG t1,t2;
 512
 513         if ((a == NULL) || (b == NULL))
 514                 {
 515                 if (a != NULL)
 516                         return(-1);
 517                 else if (b != NULL)
 518                         return(1);
 519                 else
 520                         return(0);
 521                 }
 522         if (a->neg != b->neg)
 523                 {
 524                 if (a->neg)
 525                         return(-1);
 526                 else    return(1);
 527                 }
 528         if (a->neg == 0)
 529                 { gt=1; lt= -1; }
 530         else    { gt= -1; lt=1; }
 531
 532         if (a->top > b->top) return(gt);
 533         if (a->top < b->top) return(lt);
 534         for (i=a->top-1; i>=0; i--)
 535                 {
 536                 t1=a->d[i];
 537                 t2=b->d[i];
 538                 if (t1 > t2) return(gt);
 539                 if (t1 < t2) return(lt);
 540                 }
 541         return(0);
 542         }
 543
 544 int BN_set_bit(a, n)
 545 BIGNUM *a;
 546 int n;
 547         {
 548         int i,j;
 549
 550         i=n/BN_BITS2;
 551         j=n%BN_BITS2;
 552         if (a->top <= i)
 553                 {
 554                 if (bn_expand(a,n) == NULL) return(0);
 555                 a->top=i+1;
 556                 }
 557
 558         a->d[i]|=(1L<<j);
 559         return(1);
 560         }
 561
 562 int BN_clear_bit(a, n)
 563 BIGNUM *a;
 564 int n;
 565         {
 566         int i,j;
 567
 568         i=n/BN_BITS2;
 569         j=n%BN_BITS2;
 570         if (a->top <= i) return(0);
 571
 572         a->d[i]&=(~(1L<<j));
 573         return(1);
 574         }
 575
 576 int BN_is_bit_set(a, n)
 577 BIGNUM *a;
 578 int n;
 579         {
 580         int i,j;
 581
 582         if (n < 0) return(0);
 583         i=n/BN_BITS2;
 584         j=n%BN_BITS2;
 585         if (a->top <= i) return(0);
 586         return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
 587         }
 588
 589 int BN_mask_bits(a,n)
 590 BIGNUM *a;
 591 int n;
 592         {
 593         int b,w;
 594
 595         w=n/BN_BITS2;
 596         b=n%BN_BITS2;
 597         if (w >= a->top) return(0);
 598         if (b == 0)
 599                 a->top=w;
 600         else
 601                 {
 602                 a->top=w+1;
 603                 a->d[w]&= ~(BN_MASK2<<b);
 604                 while ((w >= 0) && (a->d[w] == 0))
 605                         {
 606                         a->top--;
 607                         w--;
 608                         }
 609                 }
 610         return(1);
 611         }