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