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