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