1 /* $OpenBSD: bn_lib.c,v 1.93 2024/04/16 13:07:14 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 #include "bn_internal.h" 70 71 BIGNUM * 72 BN_new(void) 73 { 74 BIGNUM *bn; 75 76 if ((bn = calloc(1, sizeof(BIGNUM))) == NULL) { 77 BNerror(ERR_R_MALLOC_FAILURE); 78 return NULL; 79 } 80 bn->flags = BN_FLG_MALLOCED; 81 82 return bn; 83 } 84 LCRYPTO_ALIAS(BN_new); 85 86 void 87 BN_init(BIGNUM *a) 88 { 89 memset(a, 0, sizeof(BIGNUM)); 90 } 91 92 void 93 BN_clear(BIGNUM *a) 94 { 95 if (a->d != NULL) 96 explicit_bzero(a->d, a->dmax * sizeof(a->d[0])); 97 a->top = 0; 98 a->neg = 0; 99 } 100 LCRYPTO_ALIAS(BN_clear); 101 102 void 103 BN_free(BIGNUM *bn) 104 { 105 if (bn == NULL) 106 return; 107 108 if (!BN_get_flags(bn, BN_FLG_STATIC_DATA)) 109 freezero(bn->d, bn->dmax * sizeof(bn->d[0])); 110 111 if (!BN_get_flags(bn, BN_FLG_MALLOCED)) { 112 explicit_bzero(bn, sizeof(*bn)); 113 return; 114 } 115 116 freezero(bn, sizeof(*bn)); 117 } 118 LCRYPTO_ALIAS(BN_free); 119 120 void 121 BN_clear_free(BIGNUM *bn) 122 { 123 BN_free(bn); 124 } 125 LCRYPTO_ALIAS(BN_clear_free); 126 127 void 128 BN_set_flags(BIGNUM *b, int n) 129 { 130 b->flags |= n; 131 } 132 LCRYPTO_ALIAS(BN_set_flags); 133 134 int 135 BN_get_flags(const BIGNUM *b, int n) 136 { 137 return b->flags & n; 138 } 139 LCRYPTO_ALIAS(BN_get_flags); 140 141 void 142 BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags) 143 { 144 int dest_flags; 145 146 dest_flags = (dest->flags & BN_FLG_MALLOCED) | 147 (b->flags & ~BN_FLG_MALLOCED) | BN_FLG_STATIC_DATA | flags; 148 149 *dest = *b; 150 dest->flags = dest_flags; 151 } 152 LCRYPTO_ALIAS(BN_with_flags); 153 154 static const BN_ULONG bn_value_one_data = 1; 155 static const BIGNUM bn_value_one = { 156 .d = (BN_ULONG *)&bn_value_one_data, 157 .top = 1, 158 .dmax = 1, 159 .neg = 0, 160 .flags = BN_FLG_STATIC_DATA, 161 }; 162 163 const BIGNUM * 164 BN_value_one(void) 165 { 166 return &bn_value_one; 167 } 168 LCRYPTO_ALIAS(BN_value_one); 169 170 int 171 BN_num_bits_word(BN_ULONG w) 172 { 173 return BN_BITS2 - bn_clzw(w); 174 } 175 LCRYPTO_ALIAS(BN_num_bits_word); 176 177 int 178 BN_num_bits(const BIGNUM *bn) 179 { 180 return bn_bitsize(bn); 181 } 182 LCRYPTO_ALIAS(BN_num_bits); 183 184 void 185 bn_correct_top(BIGNUM *a) 186 { 187 while (a->top > 0 && a->d[a->top - 1] == 0) 188 a->top--; 189 } 190 191 static int 192 bn_expand_internal(BIGNUM *bn, int words) 193 { 194 BN_ULONG *d; 195 196 if (words < 0) { 197 BNerror(BN_R_BIGNUM_TOO_LONG); // XXX 198 return 0; 199 } 200 201 if (words > INT_MAX / (4 * BN_BITS2)) { 202 BNerror(BN_R_BIGNUM_TOO_LONG); 203 return 0; 204 } 205 if (BN_get_flags(bn, BN_FLG_STATIC_DATA)) { 206 BNerror(BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 207 return 0; 208 } 209 210 d = recallocarray(bn->d, bn->dmax, words, sizeof(BN_ULONG)); 211 if (d == NULL) { 212 BNerror(ERR_R_MALLOC_FAILURE); 213 return 0; 214 } 215 bn->d = d; 216 bn->dmax = words; 217 218 return 1; 219 } 220 221 int 222 bn_expand_bits(BIGNUM *bn, size_t bits) 223 { 224 int words; 225 226 if (bits > (INT_MAX - BN_BITS2 + 1)) 227 return 0; 228 229 words = (bits + BN_BITS2 - 1) / BN_BITS2; 230 231 return bn_wexpand(bn, words); 232 } 233 234 int 235 bn_expand_bytes(BIGNUM *bn, size_t bytes) 236 { 237 int words; 238 239 if (bytes > (INT_MAX - BN_BYTES + 1)) 240 return 0; 241 242 words = (bytes + BN_BYTES - 1) / BN_BYTES; 243 244 return bn_wexpand(bn, words); 245 } 246 247 int 248 bn_wexpand(BIGNUM *bn, int words) 249 { 250 if (words < 0) 251 return 0; 252 253 if (words <= bn->dmax) 254 return 1; 255 256 return bn_expand_internal(bn, words); 257 } 258 259 BIGNUM * 260 BN_dup(const BIGNUM *a) 261 { 262 BIGNUM *t; 263 264 if (a == NULL) 265 return NULL; 266 267 t = BN_new(); 268 if (t == NULL) 269 return NULL; 270 if (!bn_copy(t, a)) { 271 BN_free(t); 272 return NULL; 273 } 274 return t; 275 } 276 LCRYPTO_ALIAS(BN_dup); 277 278 static inline void 279 bn_copy_words(BN_ULONG *ap, const BN_ULONG *bp, int n) 280 { 281 while (n > 0) { 282 ap[0] = bp[0]; 283 ap++; 284 bp++; 285 n--; 286 } 287 } 288 289 BIGNUM * 290 BN_copy(BIGNUM *a, const BIGNUM *b) 291 { 292 if (a == b) 293 return (a); 294 295 if (!bn_wexpand(a, b->top)) 296 return (NULL); 297 298 bn_copy_words(a->d, b->d, b->top); 299 300 /* Copy constant time flag from b, but make it sticky on a. */ 301 a->flags |= b->flags & BN_FLG_CONSTTIME; 302 303 a->top = b->top; 304 a->neg = b->neg; 305 306 return (a); 307 } 308 LCRYPTO_ALIAS(BN_copy); 309 310 int 311 bn_copy(BIGNUM *dst, const BIGNUM *src) 312 { 313 return BN_copy(dst, src) != NULL; 314 } 315 316 void 317 BN_swap(BIGNUM *a, BIGNUM *b) 318 { 319 int flags_old_a, flags_old_b; 320 BN_ULONG *tmp_d; 321 int tmp_top, tmp_dmax, tmp_neg; 322 323 324 flags_old_a = a->flags; 325 flags_old_b = b->flags; 326 327 tmp_d = a->d; 328 tmp_top = a->top; 329 tmp_dmax = a->dmax; 330 tmp_neg = a->neg; 331 332 a->d = b->d; 333 a->top = b->top; 334 a->dmax = b->dmax; 335 a->neg = b->neg; 336 337 b->d = tmp_d; 338 b->top = tmp_top; 339 b->dmax = tmp_dmax; 340 b->neg = tmp_neg; 341 342 a->flags = (flags_old_a & BN_FLG_MALLOCED) | 343 (flags_old_b & BN_FLG_STATIC_DATA); 344 b->flags = (flags_old_b & BN_FLG_MALLOCED) | 345 (flags_old_a & BN_FLG_STATIC_DATA); 346 } 347 LCRYPTO_ALIAS(BN_swap); 348 349 BN_ULONG 350 BN_get_word(const BIGNUM *a) 351 { 352 if (a->top > 1) 353 return BN_MASK2; 354 else if (a->top == 1) 355 return a->d[0]; 356 /* a->top == 0 */ 357 return 0; 358 } 359 LCRYPTO_ALIAS(BN_get_word); 360 361 int 362 BN_set_word(BIGNUM *a, BN_ULONG w) 363 { 364 if (!bn_wexpand(a, 1)) 365 return (0); 366 a->neg = 0; 367 a->d[0] = w; 368 a->top = (w ? 1 : 0); 369 return (1); 370 } 371 LCRYPTO_ALIAS(BN_set_word); 372 373 int 374 BN_ucmp(const BIGNUM *a, const BIGNUM *b) 375 { 376 int i; 377 378 if (a->top < b->top) 379 return -1; 380 if (a->top > b->top) 381 return 1; 382 383 for (i = a->top - 1; i >= 0; i--) { 384 if (a->d[i] != b->d[i]) 385 return (a->d[i] > b->d[i] ? 1 : -1); 386 } 387 388 return 0; 389 } 390 LCRYPTO_ALIAS(BN_ucmp); 391 392 int 393 BN_cmp(const BIGNUM *a, const BIGNUM *b) 394 { 395 if (a == NULL || b == NULL) { 396 if (a != NULL) 397 return -1; 398 if (b != NULL) 399 return 1; 400 return 0; 401 } 402 403 if (a->neg != b->neg) 404 return b->neg - a->neg; 405 406 if (a->neg) 407 return BN_ucmp(b, a); 408 409 return BN_ucmp(a, b); 410 } 411 LCRYPTO_ALIAS(BN_cmp); 412 413 int 414 BN_set_bit(BIGNUM *a, int n) 415 { 416 int i, j, k; 417 418 if (n < 0) 419 return 0; 420 421 i = n / BN_BITS2; 422 j = n % BN_BITS2; 423 if (a->top <= i) { 424 if (!bn_wexpand(a, i + 1)) 425 return (0); 426 for (k = a->top; k < i + 1; k++) 427 a->d[k] = 0; 428 a->top = i + 1; 429 } 430 431 a->d[i] |= (((BN_ULONG)1) << j); 432 return (1); 433 } 434 LCRYPTO_ALIAS(BN_set_bit); 435 436 int 437 BN_clear_bit(BIGNUM *a, int n) 438 { 439 int i, j; 440 441 if (n < 0) 442 return 0; 443 444 i = n / BN_BITS2; 445 j = n % BN_BITS2; 446 if (a->top <= i) 447 return (0); 448 449 a->d[i] &= (~(((BN_ULONG)1) << j)); 450 bn_correct_top(a); 451 452 BN_set_negative(a, a->neg); 453 454 return (1); 455 } 456 LCRYPTO_ALIAS(BN_clear_bit); 457 458 int 459 BN_is_bit_set(const BIGNUM *a, int n) 460 { 461 int i, j; 462 463 if (n < 0) 464 return 0; 465 i = n / BN_BITS2; 466 j = n % BN_BITS2; 467 if (a->top <= i) 468 return 0; 469 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); 470 } 471 LCRYPTO_ALIAS(BN_is_bit_set); 472 473 int 474 BN_mask_bits(BIGNUM *a, int n) 475 { 476 int b, w; 477 478 if (n < 0) 479 return 0; 480 481 w = n / BN_BITS2; 482 b = n % BN_BITS2; 483 if (w >= a->top) 484 return 0; 485 if (b == 0) 486 a->top = w; 487 else { 488 a->top = w + 1; 489 a->d[w] &= ~(BN_MASK2 << b); 490 } 491 bn_correct_top(a); 492 493 BN_set_negative(a, a->neg); 494 495 return (1); 496 } 497 LCRYPTO_ALIAS(BN_mask_bits); 498 499 void 500 BN_set_negative(BIGNUM *bn, int neg) 501 { 502 bn->neg = ~BN_is_zero(bn) & bn_ct_ne_zero(neg); 503 } 504 LCRYPTO_ALIAS(BN_set_negative); 505 506 /* 507 * Constant-time conditional swap of a and b. 508 * a and b are swapped if condition is not 0. 509 * The code assumes that at most one bit of condition is set. 510 * nwords is the number of words to swap. 511 * The code assumes that at least nwords are allocated in both a and b, 512 * and that no more than nwords are used by either a or b. 513 * a and b cannot be the same number 514 */ 515 void 516 BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) 517 { 518 BN_ULONG t; 519 int i; 520 521 assert(a != b); 522 assert((condition & (condition - 1)) == 0); 523 assert(sizeof(BN_ULONG) >= sizeof(int)); 524 525 condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1; 526 527 t = (a->top^b->top) & condition; 528 a->top ^= t; 529 b->top ^= t; 530 531 #define BN_CONSTTIME_SWAP(ind) \ 532 do { \ 533 t = (a->d[ind] ^ b->d[ind]) & condition; \ 534 a->d[ind] ^= t; \ 535 b->d[ind] ^= t; \ 536 } while (0) 537 538 539 switch (nwords) { 540 default: 541 for (i = 10; i < nwords; i++) 542 BN_CONSTTIME_SWAP(i); 543 /* Fallthrough */ 544 case 10: BN_CONSTTIME_SWAP(9); /* Fallthrough */ 545 case 9: BN_CONSTTIME_SWAP(8); /* Fallthrough */ 546 case 8: BN_CONSTTIME_SWAP(7); /* Fallthrough */ 547 case 7: BN_CONSTTIME_SWAP(6); /* Fallthrough */ 548 case 6: BN_CONSTTIME_SWAP(5); /* Fallthrough */ 549 case 5: BN_CONSTTIME_SWAP(4); /* Fallthrough */ 550 case 4: BN_CONSTTIME_SWAP(3); /* Fallthrough */ 551 case 3: BN_CONSTTIME_SWAP(2); /* Fallthrough */ 552 case 2: BN_CONSTTIME_SWAP(1); /* Fallthrough */ 553 case 1: 554 BN_CONSTTIME_SWAP(0); 555 } 556 #undef BN_CONSTTIME_SWAP 557 } 558 LCRYPTO_ALIAS(BN_consttime_swap); 559 560 /* 561 * Constant-time conditional swap of a and b. 562 * a and b are swapped if condition is not 0. 563 * nwords is the number of words to swap. 564 */ 565 int 566 BN_swap_ct(BN_ULONG condition, BIGNUM *a, BIGNUM *b, size_t nwords) 567 { 568 BN_ULONG t; 569 int i, words; 570 571 if (a == b) 572 return 1; 573 if (nwords > INT_MAX) 574 return 0; 575 words = (int)nwords; 576 if (!bn_wexpand(a, words) || !bn_wexpand(b, words)) 577 return 0; 578 if (a->top > words || b->top > words) { 579 BNerror(BN_R_INVALID_LENGTH); 580 return 0; 581 } 582 583 /* Set condition to 0 (if it was zero) or all 1s otherwise. */ 584 condition = ((~condition & (condition - 1)) >> (BN_BITS2 - 1)) - 1; 585 586 /* swap top field */ 587 t = (a->top ^ b->top) & condition; 588 a->top ^= t; 589 b->top ^= t; 590 591 /* swap neg field */ 592 t = (a->neg ^ b->neg) & condition; 593 a->neg ^= t; 594 b->neg ^= t; 595 596 /* swap BN_FLG_CONSTTIME from flag field */ 597 t = ((a->flags ^ b->flags) & BN_FLG_CONSTTIME) & condition; 598 a->flags ^= t; 599 b->flags ^= t; 600 601 /* swap the data */ 602 for (i = 0; i < words; i++) { 603 t = (a->d[i] ^ b->d[i]) & condition; 604 a->d[i] ^= t; 605 b->d[i] ^= t; 606 } 607 608 return 1; 609 } 610 611 void 612 BN_zero(BIGNUM *a) 613 { 614 a->neg = 0; 615 a->top = 0; 616 } 617 LCRYPTO_ALIAS(BN_zero); 618 619 int 620 BN_one(BIGNUM *a) 621 { 622 return BN_set_word(a, 1); 623 } 624 LCRYPTO_ALIAS(BN_one); 625 626 int 627 BN_abs_is_word(const BIGNUM *a, const BN_ULONG w) 628 { 629 return (a->top == 1 && a->d[0] == w) || (w == 0 && a->top == 0); 630 } 631 LCRYPTO_ALIAS(BN_abs_is_word); 632 633 int 634 BN_is_zero(const BIGNUM *bn) 635 { 636 BN_ULONG bits = 0; 637 int i; 638 639 for (i = 0; i < bn->top; i++) 640 bits |= bn->d[i]; 641 642 return bits == 0; 643 } 644 LCRYPTO_ALIAS(BN_is_zero); 645 646 int 647 BN_is_one(const BIGNUM *a) 648 { 649 return BN_abs_is_word(a, 1) && !a->neg; 650 } 651 LCRYPTO_ALIAS(BN_is_one); 652 653 int 654 BN_is_word(const BIGNUM *a, const BN_ULONG w) 655 { 656 return BN_abs_is_word(a, w) && (w == 0 || !a->neg); 657 } 658 LCRYPTO_ALIAS(BN_is_word); 659 660 int 661 BN_is_odd(const BIGNUM *a) 662 { 663 return a->top > 0 && (a->d[0] & 1); 664 } 665 LCRYPTO_ALIAS(BN_is_odd); 666 667 int 668 BN_is_negative(const BIGNUM *a) 669 { 670 return a->neg != 0; 671 } 672 LCRYPTO_ALIAS(BN_is_negative); 673 674 /* 675 * Bits of security, see SP800-57, section 5.6.11, table 2. 676 */ 677 int 678 BN_security_bits(int L, int N) 679 { 680 int secbits, bits; 681 682 if (L >= 15360) 683 secbits = 256; 684 else if (L >= 7680) 685 secbits = 192; 686 else if (L >= 3072) 687 secbits = 128; 688 else if (L >= 2048) 689 secbits = 112; 690 else if (L >= 1024) 691 secbits = 80; 692 else 693 return 0; 694 695 if (N == -1) 696 return secbits; 697 698 bits = N / 2; 699 if (bits < 80) 700 return 0; 701 702 return bits >= secbits ? secbits : bits; 703 } 704 LCRYPTO_ALIAS(BN_security_bits); 705 706 BN_GENCB * 707 BN_GENCB_new(void) 708 { 709 BN_GENCB *cb; 710 711 if ((cb = calloc(1, sizeof(*cb))) == NULL) 712 return NULL; 713 714 return cb; 715 } 716 LCRYPTO_ALIAS(BN_GENCB_new); 717 718 void 719 BN_GENCB_free(BN_GENCB *cb) 720 { 721 if (cb == NULL) 722 return; 723 free(cb); 724 } 725 LCRYPTO_ALIAS(BN_GENCB_free); 726 727 /* Populate a BN_GENCB structure with an "old"-style callback */ 728 void 729 BN_GENCB_set_old(BN_GENCB *gencb, void (*cb)(int, int, void *), void *cb_arg) 730 { 731 gencb->ver = 1; 732 gencb->cb.cb_1 = cb; 733 gencb->arg = cb_arg; 734 } 735 LCRYPTO_ALIAS(BN_GENCB_set_old); 736 737 /* Populate a BN_GENCB structure with a "new"-style callback */ 738 void 739 BN_GENCB_set(BN_GENCB *gencb, int (*cb)(int, int, BN_GENCB *), void *cb_arg) 740 { 741 gencb->ver = 2; 742 gencb->cb.cb_2 = cb; 743 gencb->arg = cb_arg; 744 } 745 LCRYPTO_ALIAS(BN_GENCB_set); 746 747 void * 748 BN_GENCB_get_arg(BN_GENCB *cb) 749 { 750 return cb->arg; 751 } 752 LCRYPTO_ALIAS(BN_GENCB_get_arg); 753