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