crypto/bn/bn_lib.c

   1 /* crypto/bn/bn_lib.c */
   2 /* Copyright (C) 1995-1997 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.8.1b 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 #ifndef 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, bits)
 283 BIGNUM *b;
 284 int bits;
 285         {
 286         BN_ULONG *p;
 287         register int n;
 288
 289         while (bits > b->max*BN_BITS2)
 290                 {
 291                 n=((bits+BN_BITS2-1)/BN_BITS2)*2;
 292                 p=b->d=(BN_ULONG *)Realloc(b->d,sizeof(BN_ULONG)*(n+1));
 293                 if (p == NULL)
 294                         {
 295                         BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE);
 296                         return(NULL);
 297                         }
 298                 memset(&(p[b->max]),0,((n+1)-b->max)*sizeof(BN_ULONG));
 299                 b->max=n;
 300                 }
 301         return(b);
 302         }
 303
 304 BIGNUM *BN_dup(a)
 305 BIGNUM *a;
 306         {
 307         BIGNUM *r;
 308
 309         r=BN_new();
 310         if (r == NULL) return(NULL);
 311         return((BIGNUM *)BN_copy(r,a));
 312         }
 313
 314 BIGNUM *BN_copy(a, b)
 315 BIGNUM *a;
 316 BIGNUM *b;
 317         {
 318         if (bn_expand(a,b->top*BN_BITS2) == NULL) return(NULL);
 319         memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
 320 /*      memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/
 321         a->top=b->top;
 322         a->neg=b->neg;
 323         return(a);
 324         }
 325
 326 void BN_clear(a)
 327 BIGNUM *a;
 328         {
 329         memset(a->d,0,a->max*sizeof(a->d[0]));
 330         a->top=0;
 331         a->neg=0;
 332         }
 333
 334 unsigned long BN_get_word(a)
 335 BIGNUM *a;
 336         {
 337         int i,n;
 338         unsigned long ret=0;
 339
 340         n=BN_num_bytes(a);
 341         if (n > sizeof(unsigned long))
 342 #ifdef SIXTY_FOUR_BIT_LONG
 343                 return(BN_MASK2);
 344 #else
 345                 return(0xFFFFFFFFL);
 346 #endif
 347         for (i=a->top-1; i>=0; i--)
 348                 {
 349 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
 350                 ret<<=BN_BITS4; /* stops the compiler complaining */
 351                 ret<<=BN_BITS4;
 352 #endif
 353                 ret|=a->d[i];
 354                 }
 355         return(ret);
 356         }
 357
 358 int BN_set_word(a,w)
 359 BIGNUM *a;
 360 unsigned long w;
 361         {
 362         int i,n;
 363         if (bn_expand(a,sizeof(unsigned long)*8) == NULL) return(0);
 364
 365         n=sizeof(unsigned long)/BN_BYTES;
 366         a->neg=0;
 367         a->top=0;
 368         a->d[0]=(BN_ULONG)w&BN_MASK2;
 369         if (a->d[0] != 0) a->top=1;
 370         for (i=1; i<n; i++)
 371                 {
 372                 /* the following is done instead of
 373                  * w>>=BN_BITS2 so compilers don't complain
 374                  * on builds where sizeof(long) == BN_TYPES */
 375 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
 376                 w>>=BN_BITS4;
 377                 w>>=BN_BITS4;
 378 #endif
 379                 a->d[i]=(BN_ULONG)w&BN_MASK2;
 380                 if (a->d[i] != 0) a->top=i+1;
 381                 }
 382         return(1);
 383         }
 384
 385 /* ignore negative */
 386 BIGNUM *BN_bin2bn(s, len, ret)
 387 unsigned char *s;
 388 int len;
 389 BIGNUM *ret;
 390         {
 391         unsigned int i,m;
 392         unsigned int n;
 393         BN_ULONG l;
 394
 395         if (ret == NULL) ret=BN_new();
 396         if (ret == NULL) return(NULL);
 397         l=0;
 398         n=len;
 399         if (n == 0)
 400                 {
 401                 ret->top=0;
 402                 return(ret);
 403                 }
 404         if (bn_expand(ret,(int)(n+2)*8) == NULL)
 405                 return(NULL);
 406         i=((n-1)/BN_BYTES)+1;
 407         m=((n-1)%(BN_BYTES));
 408         ret->top=i;
 409         while (n-- > 0)
 410                 {
 411                 l=(l<<8L)| *(s++);
 412                 if (m-- == 0)
 413                         {
 414                         ret->d[--i]=l;
 415                         l=0;
 416                         m=BN_BYTES-1;
 417                         }
 418                 }
 419         /* need to call this due to clear byte at top if avoiding
 420          * having the top bit set (-ve number) */
 421         bn_fix_top(ret);
 422         return(ret);
 423         }
 424
 425 /* ignore negative */
 426 int BN_bn2bin(a, to)
 427 BIGNUM *a;
 428 unsigned char *to;
 429         {
 430         int n,i;
 431         BN_ULONG l;
 432
 433         n=i=BN_num_bytes(a);
 434         while (i-- > 0)
 435                 {
 436                 l=a->d[i/BN_BYTES];
 437                 *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
 438                 }
 439         return(n);
 440         }
 441
 442 int BN_ucmp(a, b)
 443 BIGNUM *a;
 444 BIGNUM *b;
 445         {
 446         int i;
 447         BN_ULONG t1,t2,*ap,*bp;
 448
 449         i=a->top-b->top;
 450         if (i != 0) return(i);
 451         ap=a->d;
 452         bp=b->d;
 453         for (i=a->top-1; i>=0; i--)
 454                 {
 455                 t1= ap[i];
 456                 t2= bp[i];
 457                 if (t1 != t2)
 458                         return(t1 > t2?1:-1);
 459                 }
 460         return(0);
 461         }
 462
 463 int BN_cmp(a, b)
 464 BIGNUM *a;
 465 BIGNUM *b;
 466         {
 467         int i;
 468         int gt,lt;
 469         BN_ULONG t1,t2;
 470
 471         if ((a == NULL) || (b == NULL))
 472                 {
 473                 if (a != NULL)
 474                         return(-1);
 475                 else if (b != NULL)
 476                         return(1);
 477                 else
 478                         return(0);
 479                 }
 480         if (a->neg != b->neg)
 481                 {
 482                 if (a->neg)
 483                         return(-1);
 484                 else    return(1);
 485                 }
 486         if (a->neg == 0)
 487                 { gt=1; lt= -1; }
 488         else    { gt= -1; lt=1; }
 489
 490         if (a->top > b->top) return(gt);
 491         if (a->top < b->top) return(lt);
 492         for (i=a->top-1; i>=0; i--)
 493                 {
 494                 t1=a->d[i];
 495                 t2=b->d[i];
 496                 if (t1 > t2) return(gt);
 497                 if (t1 < t2) return(lt);
 498                 }
 499         return(0);
 500         }
 501
 502 int BN_set_bit(a, n)
 503 BIGNUM *a;
 504 int n;
 505         {
 506         int i,j;
 507
 508         i=n/BN_BITS2;
 509         j=n%BN_BITS2;
 510         if (a->top <= i) return(0);
 511
 512         a->d[i]|=(1L<<j);
 513         return(1);
 514         }
 515
 516 int BN_clear_bit(a, n)
 517 BIGNUM *a;
 518 int n;
 519         {
 520         int i,j;
 521
 522         i=n/BN_BITS2;
 523         j=n%BN_BITS2;
 524         if (a->top <= i) return(0);
 525
 526         a->d[i]&=(~(1L<<j));
 527         return(1);
 528         }
 529
 530 int BN_is_bit_set(a, n)
 531 BIGNUM *a;
 532 int n;
 533         {
 534         int i,j;
 535
 536         if (n < 0) return(0);
 537         i=n/BN_BITS2;
 538         j=n%BN_BITS2;
 539         if (a->top <= i) return(0);
 540         return((a->d[i]&(((BN_ULONG)1)<<j))?1:0);
 541         }
 542
 543 int BN_mask_bits(a,n)
 544 BIGNUM *a;
 545 int n;
 546         {
 547         int b,w;
 548
 549         w=n/BN_BITS2;
 550         b=n%BN_BITS2;
 551         if (w >= a->top) return(0);
 552         if (b == 0)
 553                 a->top=w;
 554         else
 555                 {
 556                 a->top=w+1;
 557                 a->d[w]&= ~(BN_MASK2<<b);
 558                 while ((w >= 0) && (a->d[w] == 0))
 559                         {
 560                         a->top--;
 561                         w--;
 562                         }
 563                 }
 564         return(1);
 565         }