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