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