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