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