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                 /*
 355                  * workaround for ultrix cc: without 'case 0', the optimizer does
 356                  * the switch table by doing a=top&3; a--; goto jump_table[a];
 357                  * which fails for top== 0
 358                  */
 359                 switch (b->top&3)
 360                         {
 361                 case 3: A[2]=B[2];
 362                 case 2: A[1]=B[1];
 363                 case 1: A[0]=B[0];
 364                 case 0:
 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         /* ultrix cc workaround, see comments in bn_expand_internal */
 456         switch (b->top&3)
 457                 {
 458                 case 3: A[2]=B[2];
 459                 case 2: A[1]=B[1];
 460                 case 1: A[0]=B[0];
 461                 case 0: ;
 462                 }
 463 #else
 464         memcpy(a->d,b->d,sizeof(b->d[0])*b->top);
 465 #endif
 466
 467         a->top=b->top;
 468         a->neg=b->neg;
 469         bn_check_top(a);
 470         return(a);
 471         }
 472
 473 void BN_swap(BIGNUM *a, BIGNUM *b)
 474         {
 475         int flags_old_a, flags_old_b;
 476         BN_ULONG *tmp_d;
 477         int tmp_top, tmp_dmax, tmp_neg;
 478
 479         bn_check_top(a);
 480         bn_check_top(b);
 481
 482         flags_old_a = a->flags;
 483         flags_old_b = b->flags;
 484
 485         tmp_d = a->d;
 486         tmp_top = a->top;
 487         tmp_dmax = a->dmax;
 488         tmp_neg = a->neg;
 489
 490         a->d = b->d;
 491         a->top = b->top;
 492         a->dmax = b->dmax;
 493         a->neg = b->neg;
 494
 495         b->d = tmp_d;
 496         b->top = tmp_top;
 497         b->dmax = tmp_dmax;
 498         b->neg = tmp_neg;
 499
 500         a->flags = (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
 501         b->flags = (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
 502         bn_check_top(a);
 503         bn_check_top(b);
 504         }
 505
 506 void BN_clear(BIGNUM *a)
 507         {
 508         bn_check_top(a);
 509         if (a->d != NULL)
 510                 memset(a->d,0,a->dmax*sizeof(a->d[0]));
 511         a->top=0;
 512         a->neg=0;
 513         }
 514
 515 BN_ULONG BN_get_word(const BIGNUM *a)
 516         {
 517         if (a->top > 1)
 518                 return BN_MASK2;
 519         else if (a->top == 1)
 520                 return a->d[0];
 521         /* a->top == 0 */
 522         return 0;
 523         }
 524
 525 int BN_set_word(BIGNUM *a, BN_ULONG w)
 526         {
 527         bn_check_top(a);
 528         if (bn_expand(a,(int)sizeof(BN_ULONG)*8) == NULL) return(0);
 529         a->neg = 0;
 530         a->d[0] = w;
 531         a->top = (w ? 1 : 0);
 532         bn_check_top(a);
 533         return(1);
 534         }
 535
 536 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
 537         {
 538         unsigned int i,m;
 539         unsigned int n;
 540         BN_ULONG l;
 541         BIGNUM  *bn = NULL;
 542
 543         if (ret == NULL)
 544                 ret = bn = BN_new();
 545         if (ret == NULL) return(NULL);
 546         bn_check_top(ret);
 547         l=0;
 548         n=len;
 549         if (n == 0)
 550                 {
 551                 ret->top=0;
 552                 return(ret);
 553                 }
 554         i=((n-1)/BN_BYTES)+1;
 555         m=((n-1)%(BN_BYTES));
 556         if (bn_wexpand(ret, (int)i) == NULL)
 557                 {
 558                 if (bn) BN_free(bn);
 559                 return NULL;
 560                 }
 561         ret->top=i;
 562         ret->neg=0;
 563         while (n--)
 564                 {
 565                 l=(l<<8L)| *(s++);
 566                 if (m-- == 0)
 567                         {
 568                         ret->d[--i]=l;
 569                         l=0;
 570                         m=BN_BYTES-1;
 571                         }
 572                 }
 573         /* need to call this due to clear byte at top if avoiding
 574          * having the top bit set (-ve number) */
 575         bn_correct_top(ret);
 576         return(ret);
 577         }
 578
 579 /* ignore negative */
 580 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
 581         {
 582         int n,i;
 583         BN_ULONG l;
 584
 585         bn_check_top(a);
 586         n=i=BN_num_bytes(a);
 587         while (i--)
 588                 {
 589                 l=a->d[i/BN_BYTES];
 590                 *(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
 591                 }
 592         return(n);
 593         }
 594
 595 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
 596         {
 597         int i;
 598         BN_ULONG t1,t2,*ap,*bp;
 599
 600         bn_check_top(a);
 601         bn_check_top(b);
 602
 603         i=a->top-b->top;
 604         if (i != 0) return(i);
 605         ap=a->d;
 606         bp=b->d;
 607         for (i=a->top-1; i>=0; i--)
 608                 {
 609                 t1= ap[i];
 610                 t2= bp[i];
 611                 if (t1 != t2)
 612                         return((t1 > t2) ? 1 : -1);
 613                 }
 614         return(0);
 615         }
 616
 617 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
 618         {
 619         int i;
 620         int gt,lt;
 621         BN_ULONG t1,t2;
 622
 623         if ((a == NULL) || (b == NULL))
 624                 {
 625                 if (a != NULL)
 626                         return(-1);
 627                 else if (b != NULL)
 628                         return(1);
 629                 else
 630                         return(0);
 631                 }
 632
 633         bn_check_top(a);
 634         bn_check_top(b);
 635
 636         if (a->neg != b->neg)
 637                 {
 638                 if (a->neg)
 639                         return(-1);
 640                 else    return(1);
 641                 }
 642         if (a->neg == 0)
 643                 { gt=1; lt= -1; }
 644         else    { gt= -1; lt=1; }
 645
 646         if (a->top > b->top) return(gt);
 647         if (a->top < b->top) return(lt);
 648         for (i=a->top-1; i>=0; i--)
 649                 {
 650                 t1=a->d[i];
 651                 t2=b->d[i];
 652                 if (t1 > t2) return(gt);
 653                 if (t1 < t2) return(lt);
 654                 }
 655         return(0);
 656         }
 657
 658 int BN_set_bit(BIGNUM *a, int n)
 659         {
 660         int i,j,k;
 661
 662         if (n < 0)
 663                 return 0;
 664
 665         i=n/BN_BITS2;
 666         j=n%BN_BITS2;
 667         if (a->top <= i)
 668                 {
 669                 if (bn_wexpand(a,i+1) == NULL) return(0);
 670                 for(k=a->top; k<i+1; k++)
 671                         a->d[k]=0;
 672                 a->top=i+1;
 673                 }
 674
 675         a->d[i]|=(((BN_ULONG)1)<<j);
 676         bn_check_top(a);
 677         return(1);
 678         }
 679
 680 int BN_clear_bit(BIGNUM *a, int n)
 681         {
 682         int i,j;
 683
 684         bn_check_top(a);
 685         if (n < 0) return 0;
 686
 687         i=n/BN_BITS2;
 688         j=n%BN_BITS2;
 689         if (a->top <= i) return(0);
 690
 691         a->d[i]&=(~(((BN_ULONG)1)<<j));
 692         bn_correct_top(a);
 693         return(1);
 694         }
 695
 696 int BN_is_bit_set(const BIGNUM *a, int n)
 697         {
 698         int i,j;
 699
 700         bn_check_top(a);
 701         if (n < 0) return 0;
 702         i=n/BN_BITS2;
 703         j=n%BN_BITS2;
 704         if (a->top <= i) return 0;
 705         return (int)(((a->d[i])>>j)&((BN_ULONG)1));
 706         }
 707
 708 int BN_mask_bits(BIGNUM *a, int n)
 709         {
 710         int b,w;
 711
 712         bn_check_top(a);
 713         if (n < 0) return 0;
 714
 715         w=n/BN_BITS2;
 716         b=n%BN_BITS2;
 717         if (w >= a->top) return 0;
 718         if (b == 0)
 719                 a->top=w;
 720         else
 721                 {
 722                 a->top=w+1;
 723                 a->d[w]&= ~(BN_MASK2<<b);
 724                 }
 725         bn_correct_top(a);
 726         return(1);
 727         }
 728
 729 void BN_set_negative(BIGNUM *a, int b)
 730         {
 731         if (b && !BN_is_zero(a))
 732                 a->neg = 1;
 733         else
 734                 a->neg = 0;
 735         }
 736
 737 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
 738         {
 739         int i;
 740         BN_ULONG aa,bb;
 741
 742         aa=a[n-1];
 743         bb=b[n-1];
 744         if (aa != bb) return((aa > bb)?1:-1);
 745         for (i=n-2; i>=0; i--)
 746                 {
 747                 aa=a[i];
 748                 bb=b[i];
 749                 if (aa != bb) return((aa > bb)?1:-1);
 750                 }
 751         return(0);
 752         }
 753
 754 /* Here follows a specialised variants of bn_cmp_words().  It has the
 755    property of performing the operation on arrays of different sizes.
 756    The sizes of those arrays is expressed through cl, which is the
 757    common length ( basicall, min(len(a),len(b)) ), and dl, which is the
 758    delta between the two lengths, calculated as len(a)-len(b).
 759    All lengths are the number of BN_ULONGs...  */
 760
 761 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b,
 762         int cl, int dl)
 763         {
 764         int n,i;
 765         n = cl-1;
 766
 767         if (dl < 0)
 768                 {
 769                 for (i=dl; i<0; i++)
 770                         {
 771                         if (b[n-i] != 0)
 772                                 return -1; /* a < b */
 773                         }
 774                 }
 775         if (dl > 0)
 776                 {
 777                 for (i=dl; i>0; i--)
 778                         {
 779                         if (a[n+i] != 0)
 780                                 return 1; /* a > b */
 781                         }
 782                 }
 783         return bn_cmp_words(a,b,cl);
 784         }
 785
 786 /*
 787  * Constant-time conditional swap of a and b.
 788  * a and b are swapped if condition is not 0.  The code assumes that at most one bit of condition is set.
 789  * nwords is the number of words to swap.  The code assumes that at least nwords are allocated in both a and b,
 790  * and that no more than nwords are used by either a or b.
 791  * a and b cannot be the same number
 792  */
 793 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
 794         {
 795         BN_ULONG t;
 796         int i;
 797
 798         bn_wcheck_size(a, nwords);
 799         bn_wcheck_size(b, nwords);
 800
 801         assert(a != b);
 802         assert((condition & (condition - 1)) == 0);
 803         assert(sizeof(BN_ULONG) >= sizeof(int));
 804
 805         condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
 806
 807         t = (a->top^b->top) & condition;
 808         a->top ^= t;
 809         b->top ^= t;
 810
 811 #define BN_CONSTTIME_SWAP(ind) \
 812         do { \
 813                 t = (a->d[ind] ^ b->d[ind]) & condition; \
 814                 a->d[ind] ^= t; \
 815                 b->d[ind] ^= t; \
 816         } while (0)
 817
 818
 819         switch (nwords) {
 820         default:
 821                 for (i = 10; i < nwords; i++)
 822                         BN_CONSTTIME_SWAP(i);
 823                 /* Fallthrough */
 824         case 10: BN_CONSTTIME_SWAP(9); /* Fallthrough */
 825         case 9: BN_CONSTTIME_SWAP(8); /* Fallthrough */
 826         case 8: BN_CONSTTIME_SWAP(7); /* Fallthrough */
 827         case 7: BN_CONSTTIME_SWAP(6); /* Fallthrough */
 828         case 6: BN_CONSTTIME_SWAP(5); /* Fallthrough */
 829         case 5: BN_CONSTTIME_SWAP(4); /* Fallthrough */
 830         case 4: BN_CONSTTIME_SWAP(3); /* Fallthrough */
 831         case 3: BN_CONSTTIME_SWAP(2); /* Fallthrough */
 832         case 2: BN_CONSTTIME_SWAP(1); /* Fallthrough */
 833         case 1: BN_CONSTTIME_SWAP(0);
 834         }
 835 #undef BN_CONSTTIME_SWAP
 836 }
 837
 838 /* Bits of security, see SP800-57 */
 839
 840 int BN_security_bits(int L, int N)
 841         {
 842         int secbits, bits;
 843         if (L >= 15360)
 844                 secbits = 256;
 845         else if (L >= 7690)
 846                 secbits = 192;
 847         else if (L >= 3072)
 848                 secbits = 128;
 849         else if (L >= 2048)
 850                 secbits = 112;
 851         else if (L >= 1024)
 852                 secbits = 80;
 853         else
 854                 return 0;
 855         if (N == -1)
 856                 return secbits;
 857         bits = N / 2;
 858         if (bits < 80)
 859                 return 0;
 860         return bits >= secbits ? secbits : bits;
 861         }
 862
 863
 864 void BN_zero_ex(BIGNUM *a)
 865         {
 866         a->top = 0;
 867         a->neg = 0;
 868         }
 869
 870 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
 871         {
 872         return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
 873         }
 874
 875 int BN_is_zero(const BIGNUM *a)
 876         {
 877         return a->top == 0;
 878         }
 879
 880 int BN_is_one(const BIGNUM *a)
 881         {
 882         return BN_abs_is_word(a, 1) && !a->neg;
 883         }
 884
 885 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
 886         {
 887         return BN_abs_is_word(a, w) && (!w || !a->neg);
 888         }
 889
 890 int BN_is_odd(const BIGNUM *a)
 891         {
 892         return (a->top > 0) && (a->d[0] & 1);
 893         }
 894
 895 int BN_is_negative(const BIGNUM *a)
 896         {
 897         return (a->neg != 0);
 898         }
 899
 900 int BN_to_montgomery(BIGNUM *r,const BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx)
 901         {
 902         return BN_mod_mul_montgomery(r,a,&(mont->RR),mont,ctx);
 903         }
 904
 905 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int n)
 906         {
 907         dest->d=b->d;
 908         dest->top=b->top;
 909         dest->dmax=b->dmax;
 910         dest->neg=b->neg;
 911         dest->flags=((dest->flags & BN_FLG_MALLOCED)
 912                 |  (b->flags & ~BN_FLG_MALLOCED)
 913                 |  BN_FLG_STATIC_DATA
 914                 |  n);
 915         }
 916
 917 BN_GENCB *BN_GENCB_new(void)
 918         {
 919         BN_GENCB *ret;
 920
 921         if ((ret=(BN_GENCB *)OPENSSL_malloc(sizeof(BN_GENCB))) == NULL)
 922                 {
 923                 BNerr(BN_F_BN_GENCB_NEW,ERR_R_MALLOC_FAILURE);
 924                 return(NULL);
 925                 }
 926
 927         return ret;
 928         }
 929
 930 void BN_GENCB_free(BN_GENCB *cb)
 931         {
 932         if (cb == NULL) return;
 933         OPENSSL_free(cb);
 934         }
 935
 936 void BN_set_flags(BIGNUM *b, int n)
 937         {
 938         b->flags|=n;
 939         }
 940
 941 int BN_get_flags(const BIGNUM *b, int n)
 942         {
 943         return b->flags&n;
 944         }
 945
 946 /* Populate a BN_GENCB structure with an "old"-style callback */
 947 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback)(int, int, void *), void *cb_arg)
 948         {
 949         BN_GENCB *tmp_gencb = gencb;
 950         tmp_gencb->ver = 1;
 951         tmp_gencb->arg = cb_arg;
 952         tmp_gencb->cb.cb_1 = callback;
 953         }
 954
 955 /* Populate a BN_GENCB structure with a "new"-style callback */
 956 void BN_GENCB_set(BN_GENCB *gencb, int (*callback)(int, int, BN_GENCB *), void *cb_arg)
 957         {
 958         BN_GENCB *tmp_gencb = gencb;
 959         tmp_gencb->ver = 2;
 960         tmp_gencb->arg = cb_arg;
 961         tmp_gencb->cb.cb_2 = callback;
 962         }
 963
 964 void *BN_GENCB_get_arg(BN_GENCB *cb)
 965         {
 966         return cb->arg;
 967         }
 968
 969
 970 BIGNUM *bn_wexpand(BIGNUM *a, int words)
 971         {
 972         return (words <= a->dmax)?a:bn_expand2(a,words);
 973         }
 974
 975 void bn_correct_top(BIGNUM *a)
 976         {
 977         BN_ULONG *ftl;
 978         int tmp_top = a->top;
 979
 980         if (tmp_top > 0)
 981                 {
 982                 for (ftl= &(a->d[tmp_top-1]); tmp_top > 0; tmp_top--)
 983                         if (*(ftl--)) break;
 984                 a->top = tmp_top;
 985                 }
 986         bn_pollute(a);
 987         }