1 /* $OpenBSD: bn_lib.c,v 1.72 2023/01/14 15:12:27 jsing Exp $ */ 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 #include <assert.h> 60 #include <limits.h> 61 #include <stdio.h> 62 #include <string.h> 63 64 #include <openssl/opensslconf.h> 65 66 #include <openssl/err.h> 67 68 #include "bn_local.h" 69 70 BIGNUM * 71 BN_new(void) 72 { 73 BIGNUM *bn; 74 75 if ((bn = calloc(1, sizeof(BIGNUM))) == NULL) { 76 BNerror(ERR_R_MALLOC_FAILURE); 77 return NULL; 78 } 79 bn->flags = BN_FLG_MALLOCED; 80 81 return bn; 82 } 83 84 void 85 BN_init(BIGNUM *a) 86 { 87 memset(a, 0, sizeof(BIGNUM)); 88 } 89 90 void 91 BN_clear(BIGNUM *a) 92 { 93 if (a->d != NULL) 94 explicit_bzero(a->d, a->dmax * sizeof(a->d[0])); 95 a->top = 0; 96 a->neg = 0; 97 } 98 99 void 100 BN_free(BIGNUM *bn) 101 { 102 if (bn == NULL) 103 return; 104 105 if (!BN_get_flags(bn, BN_FLG_STATIC_DATA)) 106 freezero(bn->d, bn->dmax * sizeof(bn->d[0])); 107 108 if (!BN_get_flags(bn, BN_FLG_MALLOCED)) { 109 explicit_bzero(bn, sizeof(*bn)); 110 return; 111 } 112 113 freezero(bn, sizeof(*bn)); 114 } 115 116 void 117 BN_clear_free(BIGNUM *bn) 118 { 119 BN_free(bn); 120 } 121 122 /* This stuff appears to be completely unused, so is deprecated */ 123 #ifndef OPENSSL_NO_DEPRECATED 124 /* For a 32 bit machine 125 * 2 - 4 == 128 126 * 3 - 8 == 256 127 * 4 - 16 == 512 128 * 5 - 32 == 1024 129 * 6 - 64 == 2048 130 * 7 - 128 == 4096 131 * 8 - 256 == 8192 132 */ 133 static int bn_limit_bits = 0; 134 static int bn_limit_num = 8; /* (1<<bn_limit_bits) */ 135 static int bn_limit_bits_low = 0; 136 static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */ 137 static int bn_limit_bits_high = 0; 138 static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */ 139 static int bn_limit_bits_mont = 0; 140 static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */ 141 142 void 143 BN_set_params(int mult, int high, int low, int mont) 144 { 145 if (mult >= 0) { 146 if (mult > (int)(sizeof(int) * 8) - 1) 147 mult = sizeof(int) * 8 - 1; 148 bn_limit_bits = mult; 149 bn_limit_num = 1 << mult; 150 } 151 if (high >= 0) { 152 if (high > (int)(sizeof(int) * 8) - 1) 153 high = sizeof(int) * 8 - 1; 154 bn_limit_bits_high = high; 155 bn_limit_num_high = 1 << high; 156 } 157 if (low >= 0) { 158 if (low > (int)(sizeof(int) * 8) - 1) 159 low = sizeof(int) * 8 - 1; 160 bn_limit_bits_low = low; 161 bn_limit_num_low = 1 << low; 162 } 163 if (mont >= 0) { 164 if (mont > (int)(sizeof(int) * 8) - 1) 165 mont = sizeof(int) * 8 - 1; 166 bn_limit_bits_mont = mont; 167 bn_limit_num_mont = 1 << mont; 168 } 169 } 170 171 int 172 BN_get_params(int which) 173 { 174 if (which == 0) 175 return (bn_limit_bits); 176 else if (which == 1) 177 return (bn_limit_bits_high); 178 else if (which == 2) 179 return (bn_limit_bits_low); 180 else if (which == 3) 181 return (bn_limit_bits_mont); 182 else 183 return (0); 184 } 185 #endif 186 187 void 188 BN_set_flags(BIGNUM *b, int n) 189 { 190 b->flags |= n; 191 } 192 193 int 194 BN_get_flags(const BIGNUM *b, int n) 195 { 196 return b->flags & n; 197 } 198 199 void 200 BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags) 201 { 202 int dest_flags; 203 204 dest_flags = (dest->flags & BN_FLG_MALLOCED) | 205 (b->flags & ~BN_FLG_MALLOCED) | BN_FLG_STATIC_DATA | flags; 206 207 *dest = *b; 208 dest->flags = dest_flags; 209 } 210 211 const BIGNUM * 212 BN_value_one(void) 213 { 214 static const BN_ULONG data_one = 1L; 215 static const BIGNUM const_one = { 216 (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA 217 }; 218 219 return (&const_one); 220 } 221 222 int 223 BN_num_bits_word(BN_ULONG l) 224 { 225 BN_ULONG x, mask; 226 int bits; 227 unsigned int shift; 228 229 /* Constant time calculation of floor(log2(l)) + 1. */ 230 bits = (l != 0); 231 shift = BN_BITS4; /* On _LP64 this is 32, otherwise 16. */ 232 do { 233 x = l >> shift; 234 /* If x is 0, set mask to 0, otherwise set it to all 1s. */ 235 mask = ((~x & (x - 1)) >> (BN_BITS2 - 1)) - 1; 236 bits += shift & mask; 237 /* If x is 0, leave l alone, otherwise set l = x. */ 238 l ^= (x ^ l) & mask; 239 } while ((shift /= 2) != 0); 240 241 return bits; 242 } 243 244 int 245 BN_num_bits(const BIGNUM *a) 246 { 247 int i = a->top - 1; 248 249 250 if (BN_is_zero(a)) 251 return 0; 252 return ((i * BN_BITS2) + BN_num_bits_word(a->d[i])); 253 } 254 255 void 256 bn_correct_top(BIGNUM *a) 257 { 258 while (a->top > 0 && a->d[a->top - 1] == 0) 259 a->top--; 260 } 261 262 static int 263 bn_expand_internal(BIGNUM *bn, int words) 264 { 265 BN_ULONG *d; 266 267 if (words < 0) { 268 BNerror(BN_R_BIGNUM_TOO_LONG); // XXX 269 return 0; 270 } 271 272 if (words > INT_MAX / (4 * BN_BITS2)) { 273 BNerror(BN_R_BIGNUM_TOO_LONG); 274 return 0; 275 } 276 if (BN_get_flags(bn, BN_FLG_STATIC_DATA)) { 277 BNerror(BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 278 return 0; 279 } 280 281 d = recallocarray(bn->d, bn->dmax, words, sizeof(BN_ULONG)); 282 if (d == NULL) { 283 BNerror(ERR_R_MALLOC_FAILURE); 284 return 0; 285 } 286 bn->d = d; 287 bn->dmax = words; 288 289 return 1; 290 } 291 292 int 293 bn_expand(BIGNUM *bn, int bits) 294 { 295 int words; 296 297 if (bits < 0) 298 return 0; 299 300 if (bits > (INT_MAX - BN_BITS2 + 1)) 301 return 0; 302 303 words = (bits + BN_BITS2 - 1) / BN_BITS2; 304 305 return bn_wexpand(bn, words); 306 } 307 308 int 309 bn_wexpand(BIGNUM *bn, int words) 310 { 311 if (words < 0) 312 return 0; 313 314 if (words <= bn->dmax) 315 return 1; 316 317 return bn_expand_internal(bn, words); 318 } 319 320 BIGNUM * 321 BN_dup(const BIGNUM *a) 322 { 323 BIGNUM *t; 324 325 if (a == NULL) 326 return NULL; 327 328 t = BN_new(); 329 if (t == NULL) 330 return NULL; 331 if (!BN_copy(t, a)) { 332 BN_free(t); 333 return NULL; 334 } 335 return t; 336 } 337 338 BIGNUM * 339 BN_copy(BIGNUM *a, const BIGNUM *b) 340 { 341 int i; 342 BN_ULONG *A; 343 const BN_ULONG *B; 344 345 346 if (a == b) 347 return (a); 348 if (!bn_wexpand(a, b->top)) 349 return (NULL); 350 351 #if 1 352 A = a->d; 353 B = b->d; 354 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { 355 BN_ULONG a0, a1, a2, a3; 356 a0 = B[0]; 357 a1 = B[1]; 358 a2 = B[2]; 359 a3 = B[3]; 360 A[0] = a0; 361 A[1] = a1; 362 A[2] = a2; 363 A[3] = a3; 364 } 365 switch (b->top & 3) { 366 case 3: 367 A[2] = B[2]; 368 case 2: 369 A[1] = B[1]; 370 case 1: 371 A[0] = B[0]; 372 } 373 #else 374 memcpy(a->d, b->d, sizeof(b->d[0]) * b->top); 375 #endif 376 377 a->top = b->top; 378 a->neg = b->neg; 379 return (a); 380 } 381 382 void 383 BN_swap(BIGNUM *a, BIGNUM *b) 384 { 385 int flags_old_a, flags_old_b; 386 BN_ULONG *tmp_d; 387 int tmp_top, tmp_dmax, tmp_neg; 388 389 390 flags_old_a = a->flags; 391 flags_old_b = b->flags; 392 393 tmp_d = a->d; 394 tmp_top = a->top; 395 tmp_dmax = a->dmax; 396 tmp_neg = a->neg; 397 398 a->d = b->d; 399 a->top = b->top; 400 a->dmax = b->dmax; 401 a->neg = b->neg; 402 403 b->d = tmp_d; 404 b->top = tmp_top; 405 b->dmax = tmp_dmax; 406 b->neg = tmp_neg; 407 408 a->flags = (flags_old_a & BN_FLG_MALLOCED) | 409 (flags_old_b & BN_FLG_STATIC_DATA); 410 b->flags = (flags_old_b & BN_FLG_MALLOCED) | 411 (flags_old_a & BN_FLG_STATIC_DATA); 412 } 413 414 BN_ULONG 415 BN_get_word(const BIGNUM *a) 416 { 417 if (a->top > 1) 418 return BN_MASK2; 419 else if (a->top == 1) 420 return a->d[0]; 421 /* a->top == 0 */ 422 return 0; 423 } 424 425 int 426 BN_set_word(BIGNUM *a, BN_ULONG w) 427 { 428 if (!bn_wexpand(a, 1)) 429 return (0); 430 a->neg = 0; 431 a->d[0] = w; 432 a->top = (w ? 1 : 0); 433 return (1); 434 } 435 436 BIGNUM * 437 BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) 438 { 439 unsigned int i, m; 440 unsigned int n; 441 BN_ULONG l; 442 BIGNUM *bn = NULL; 443 444 if (len < 0) 445 return (NULL); 446 if (ret == NULL) 447 ret = bn = BN_new(); 448 if (ret == NULL) 449 return (NULL); 450 l = 0; 451 n = len; 452 if (n == 0) { 453 ret->top = 0; 454 return (ret); 455 } 456 i = ((n - 1) / BN_BYTES) + 1; 457 m = ((n - 1) % (BN_BYTES)); 458 if (!bn_wexpand(ret, (int)i)) { 459 BN_free(bn); 460 return NULL; 461 } 462 ret->top = i; 463 ret->neg = 0; 464 while (n--) { 465 l = (l << 8L) | *(s++); 466 if (m-- == 0) { 467 ret->d[--i] = l; 468 l = 0; 469 m = BN_BYTES - 1; 470 } 471 } 472 /* need to call this due to clear byte at top if avoiding 473 * having the top bit set (-ve number) */ 474 bn_correct_top(ret); 475 return (ret); 476 } 477 478 typedef enum { 479 big, 480 little, 481 } endianness_t; 482 483 /* ignore negative */ 484 static int 485 bn2binpad(const BIGNUM *a, unsigned char *to, int tolen, endianness_t endianness) 486 { 487 int n; 488 size_t i, lasti, j, atop, mask; 489 BN_ULONG l; 490 491 /* 492 * In case |a| is fixed-top, BN_num_bytes can return bogus length, 493 * but it's assumed that fixed-top inputs ought to be "nominated" 494 * even for padded output, so it works out... 495 */ 496 n = BN_num_bytes(a); 497 if (tolen == -1) 498 tolen = n; 499 else if (tolen < n) { /* uncommon/unlike case */ 500 BIGNUM temp = *a; 501 502 bn_correct_top(&temp); 503 504 n = BN_num_bytes(&temp); 505 if (tolen < n) 506 return -1; 507 } 508 509 /* Swipe through whole available data and don't give away padded zero. */ 510 atop = a->dmax * BN_BYTES; 511 if (atop == 0) { 512 explicit_bzero(to, tolen); 513 return tolen; 514 } 515 516 lasti = atop - 1; 517 atop = a->top * BN_BYTES; 518 519 if (endianness == big) 520 to += tolen; /* start from the end of the buffer */ 521 522 for (i = 0, j = 0; j < (size_t)tolen; j++) { 523 unsigned char val; 524 525 l = a->d[i / BN_BYTES]; 526 mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1)); 527 val = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask); 528 529 if (endianness == big) 530 *--to = val; 531 else 532 *to++ = val; 533 534 i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */ 535 } 536 537 return tolen; 538 } 539 540 int 541 BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) 542 { 543 if (tolen < 0) 544 return -1; 545 return bn2binpad(a, to, tolen, big); 546 } 547 548 int 549 BN_bn2bin(const BIGNUM *a, unsigned char *to) 550 { 551 return bn2binpad(a, to, -1, big); 552 } 553 554 BIGNUM * 555 BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret) 556 { 557 unsigned int i, m, n; 558 BN_ULONG l; 559 BIGNUM *bn = NULL; 560 561 if (ret == NULL) 562 ret = bn = BN_new(); 563 if (ret == NULL) 564 return NULL; 565 566 567 s += len; 568 /* Skip trailing zeroes. */ 569 for (; len > 0 && s[-1] == 0; s--, len--) 570 continue; 571 572 n = len; 573 if (n == 0) { 574 ret->top = 0; 575 return ret; 576 } 577 578 i = ((n - 1) / BN_BYTES) + 1; 579 m = (n - 1) % BN_BYTES; 580 if (!bn_wexpand(ret, (int)i)) { 581 BN_free(bn); 582 return NULL; 583 } 584 585 ret->top = i; 586 ret->neg = 0; 587 l = 0; 588 while (n-- > 0) { 589 s--; 590 l = (l << 8L) | *s; 591 if (m-- == 0) { 592 ret->d[--i] = l; 593 l = 0; 594 m = BN_BYTES - 1; 595 } 596 } 597 598 /* 599 * need to call this due to clear byte at top if avoiding having the 600 * top bit set (-ve number) 601 */ 602 bn_correct_top(ret); 603 604 return ret; 605 } 606 607 int 608 BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen) 609 { 610 if (tolen < 0) 611 return -1; 612 613 return bn2binpad(a, to, tolen, little); 614 } 615 616 int 617 BN_ucmp(const BIGNUM *a, const BIGNUM *b) 618 { 619 int i; 620 621 if (a->top < b->top) 622 return -1; 623 if (a->top > b->top) 624 return 1; 625 626 for (i = a->top - 1; i >= 0; i--) { 627 if (a->d[i] != b->d[i]) 628 return (a->d[i] > b->d[i] ? 1 : -1); 629 } 630 631 return 0; 632 } 633 634 int 635 BN_cmp(const BIGNUM *a, const BIGNUM *b) 636 { 637 if (a == NULL || b == NULL) { 638 if (a != NULL) 639 return -1; 640 if (b != NULL) 641 return 1; 642 return 0; 643 } 644 645 if (a->neg != b->neg) 646 return b->neg - a->neg; 647 648 if (a->neg) 649 return BN_ucmp(b, a); 650 651 return BN_ucmp(a, b); 652 } 653 654 int 655 BN_set_bit(BIGNUM *a, int n) 656 { 657 int i, j, k; 658 659 if (n < 0) 660 return 0; 661 662 i = n / BN_BITS2; 663 j = n % BN_BITS2; 664 if (a->top <= i) { 665 if (!bn_wexpand(a, i + 1)) 666 return (0); 667 for (k = a->top; k < i + 1; k++) 668 a->d[k] = 0; 669 a->top = i + 1; 670 } 671 672 a->d[i] |= (((BN_ULONG)1) << j); 673 return (1); 674 } 675 676 int 677 BN_clear_bit(BIGNUM *a, int n) 678 { 679 int i, j; 680 681 if (n < 0) 682 return 0; 683 684 i = n / BN_BITS2; 685 j = n % BN_BITS2; 686 if (a->top <= i) 687 return (0); 688 689 a->d[i] &= (~(((BN_ULONG)1) << j)); 690 bn_correct_top(a); 691 return (1); 692 } 693 694 int 695 BN_is_bit_set(const BIGNUM *a, int n) 696 { 697 int i, j; 698 699 if (n < 0) 700 return 0; 701 i = n / BN_BITS2; 702 j = n % BN_BITS2; 703 if (a->top <= i) 704 return 0; 705 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); 706 } 707 708 int 709 BN_mask_bits(BIGNUM *a, int n) 710 { 711 int b, w; 712 713 if (n < 0) 714 return 0; 715 716 w = n / BN_BITS2; 717 b = n % BN_BITS2; 718 if (w >= a->top) 719 return 0; 720 if (b == 0) 721 a->top = w; 722 else { 723 a->top = w + 1; 724 a->d[w] &= ~(BN_MASK2 << b); 725 } 726 bn_correct_top(a); 727 return (1); 728 } 729 730 void 731 BN_set_negative(BIGNUM *a, int b) 732 { 733 if (b && !BN_is_zero(a)) 734 a->neg = 1; 735 else 736 a->neg = 0; 737 } 738 739 int 740 bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) 741 { 742 int i; 743 BN_ULONG aa, bb; 744 745 aa = a[n - 1]; 746 bb = b[n - 1]; 747 if (aa != bb) 748 return ((aa > bb) ? 1 : -1); 749 for (i = n - 2; i >= 0; i--) { 750 aa = a[i]; 751 bb = b[i]; 752 if (aa != bb) 753 return ((aa > bb) ? 1 : -1); 754 } 755 return (0); 756 } 757 758 /* Here follows a specialised variants of bn_cmp_words(). It has the 759 property of performing the operation on arrays of different sizes. 760 The sizes of those arrays is expressed through cl, which is the 761 common length ( basicall, min(len(a),len(b)) ), and dl, which is the 762 delta between the two lengths, calculated as len(a)-len(b). 763 All lengths are the number of BN_ULONGs... */ 764 765 int 766 bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) 767 { 768 int n, i; 769 770 n = cl - 1; 771 772 if (dl < 0) { 773 for (i = dl; i < 0; i++) { 774 if (b[n - i] != 0) 775 return -1; /* a < b */ 776 } 777 } 778 if (dl > 0) { 779 for (i = dl; i > 0; i--) { 780 if (a[n + i] != 0) 781 return 1; /* a > b */ 782 } 783 } 784 return bn_cmp_words(a, b, cl); 785 } 786 787 /* 788 * Constant-time conditional swap of a and b. 789 * a and b are swapped if condition is not 0. 790 * The code assumes that at most one bit of condition is set. 791 * nwords is the number of words to swap. 792 * The code assumes that at least nwords are allocated in both a and b, 793 * and that no more than nwords are used by either a or b. 794 * a and b cannot be the same number 795 */ 796 void 797 BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) 798 { 799 BN_ULONG t; 800 int i; 801 802 assert(a != b); 803 assert((condition & (condition - 1)) == 0); 804 assert(sizeof(BN_ULONG) >= sizeof(int)); 805 806 condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1; 807 808 t = (a->top^b->top) & condition; 809 a->top ^= t; 810 b->top ^= t; 811 812 #define BN_CONSTTIME_SWAP(ind) \ 813 do { \ 814 t = (a->d[ind] ^ b->d[ind]) & condition; \ 815 a->d[ind] ^= t; \ 816 b->d[ind] ^= t; \ 817 } while (0) 818 819 820 switch (nwords) { 821 default: 822 for (i = 10; i < nwords; i++) 823 BN_CONSTTIME_SWAP(i); 824 /* Fallthrough */ 825 case 10: BN_CONSTTIME_SWAP(9); /* Fallthrough */ 826 case 9: BN_CONSTTIME_SWAP(8); /* Fallthrough */ 827 case 8: BN_CONSTTIME_SWAP(7); /* Fallthrough */ 828 case 7: BN_CONSTTIME_SWAP(6); /* Fallthrough */ 829 case 6: BN_CONSTTIME_SWAP(5); /* Fallthrough */ 830 case 5: BN_CONSTTIME_SWAP(4); /* Fallthrough */ 831 case 4: BN_CONSTTIME_SWAP(3); /* Fallthrough */ 832 case 3: BN_CONSTTIME_SWAP(2); /* Fallthrough */ 833 case 2: BN_CONSTTIME_SWAP(1); /* Fallthrough */ 834 case 1: 835 BN_CONSTTIME_SWAP(0); 836 } 837 #undef BN_CONSTTIME_SWAP 838 } 839 840 /* 841 * Constant-time conditional swap of a and b. 842 * a and b are swapped if condition is not 0. 843 * nwords is the number of words to swap. 844 */ 845 int 846 BN_swap_ct(BN_ULONG condition, BIGNUM *a, BIGNUM *b, size_t nwords) 847 { 848 BN_ULONG t; 849 int i, words; 850 851 if (a == b) 852 return 1; 853 if (nwords > INT_MAX) 854 return 0; 855 words = (int)nwords; 856 if (!bn_wexpand(a, words) || !bn_wexpand(b, words)) 857 return 0; 858 if (a->top > words || b->top > words) { 859 BNerror(BN_R_INVALID_LENGTH); 860 return 0; 861 } 862 863 /* Set condition to 0 (if it was zero) or all 1s otherwise. */ 864 condition = ((~condition & (condition - 1)) >> (BN_BITS2 - 1)) - 1; 865 866 /* swap top field */ 867 t = (a->top ^ b->top) & condition; 868 a->top ^= t; 869 b->top ^= t; 870 871 /* swap neg field */ 872 t = (a->neg ^ b->neg) & condition; 873 a->neg ^= t; 874 b->neg ^= t; 875 876 /* swap BN_FLG_CONSTTIME from flag field */ 877 t = ((a->flags ^ b->flags) & BN_FLG_CONSTTIME) & condition; 878 a->flags ^= t; 879 b->flags ^= t; 880 881 /* swap the data */ 882 for (i = 0; i < words; i++) { 883 t = (a->d[i] ^ b->d[i]) & condition; 884 a->d[i] ^= t; 885 b->d[i] ^= t; 886 } 887 888 return 1; 889 } 890 891 void 892 BN_zero(BIGNUM *a) 893 { 894 a->neg = 0; 895 a->top = 0; 896 } 897 898 void 899 BN_zero_ex(BIGNUM *a) 900 { 901 BN_zero(a); 902 } 903 904 int 905 BN_one(BIGNUM *a) 906 { 907 return BN_set_word(a, 1); 908 } 909 910 int 911 BN_abs_is_word(const BIGNUM *a, const BN_ULONG w) 912 { 913 return (a->top == 1 && a->d[0] == w) || (w == 0 && a->top == 0); 914 } 915 916 int 917 BN_is_zero(const BIGNUM *a) 918 { 919 return a->top == 0; 920 } 921 922 int 923 BN_is_one(const BIGNUM *a) 924 { 925 return BN_abs_is_word(a, 1) && !a->neg; 926 } 927 928 int 929 BN_is_word(const BIGNUM *a, const BN_ULONG w) 930 { 931 return BN_abs_is_word(a, w) && (w == 0 || !a->neg); 932 } 933 934 int 935 BN_is_odd(const BIGNUM *a) 936 { 937 return a->top > 0 && (a->d[0] & 1); 938 } 939 940 int 941 BN_is_negative(const BIGNUM *a) 942 { 943 return a->neg != 0; 944 } 945 946 /* 947 * Bits of security, see SP800-57, section 5.6.11, table 2. 948 */ 949 int 950 BN_security_bits(int L, int N) 951 { 952 int secbits, bits; 953 954 if (L >= 15360) 955 secbits = 256; 956 else if (L >= 7680) 957 secbits = 192; 958 else if (L >= 3072) 959 secbits = 128; 960 else if (L >= 2048) 961 secbits = 112; 962 else if (L >= 1024) 963 secbits = 80; 964 else 965 return 0; 966 967 if (N == -1) 968 return secbits; 969 970 bits = N / 2; 971 if (bits < 80) 972 return 0; 973 974 return bits >= secbits ? secbits : bits; 975 } 976 977 BN_GENCB * 978 BN_GENCB_new(void) 979 { 980 BN_GENCB *cb; 981 982 if ((cb = calloc(1, sizeof(*cb))) == NULL) 983 return NULL; 984 985 return cb; 986 } 987 988 void 989 BN_GENCB_free(BN_GENCB *cb) 990 { 991 if (cb == NULL) 992 return; 993 free(cb); 994 } 995 996 /* Populate a BN_GENCB structure with an "old"-style callback */ 997 void 998 BN_GENCB_set_old(BN_GENCB *gencb, void (*cb)(int, int, void *), void *cb_arg) 999 { 1000 gencb->ver = 1; 1001 gencb->cb.cb_1 = cb; 1002 gencb->arg = cb_arg; 1003 } 1004 1005 /* Populate a BN_GENCB structure with a "new"-style callback */ 1006 void 1007 BN_GENCB_set(BN_GENCB *gencb, int (*cb)(int, int, BN_GENCB *), void *cb_arg) 1008 { 1009 gencb->ver = 2; 1010 gencb->cb.cb_2 = cb; 1011 gencb->arg = cb_arg; 1012 } 1013 1014 void * 1015 BN_GENCB_get_arg(BN_GENCB *cb) 1016 { 1017 return cb->arg; 1018 } 1019