1/* 2 * Copyright 1995-2023 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the Apache License 2.0 (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10#include <assert.h> 11#include <limits.h> 12#include "internal/cryptlib.h" 13#include "internal/endian.h" 14#include "bn_local.h" 15#include <openssl/opensslconf.h> 16#include "internal/constant_time.h" 17 18/* This stuff appears to be completely unused, so is deprecated */ 19#ifndef OPENSSL_NO_DEPRECATED_0_9_8 20/*- 21 * For a 32 bit machine 22 * 2 - 4 == 128 23 * 3 - 8 == 256 24 * 4 - 16 == 512 25 * 5 - 32 == 1024 26 * 6 - 64 == 2048 27 * 7 - 128 == 4096 28 * 8 - 256 == 8192 29 */ 30static int bn_limit_bits = 0; 31static int bn_limit_num = 8; /* (1<<bn_limit_bits) */ 32static int bn_limit_bits_low = 0; 33static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */ 34static int bn_limit_bits_high = 0; 35static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */ 36static int bn_limit_bits_mont = 0; 37static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */ 38 39void BN_set_params(int mult, int high, int low, int mont) 40{ 41 if (mult >= 0) { 42 if (mult > (int)(sizeof(int) * 8) - 1) 43 mult = sizeof(int) * 8 - 1; 44 bn_limit_bits = mult; 45 bn_limit_num = 1 << mult; 46 } 47 if (high >= 0) { 48 if (high > (int)(sizeof(int) * 8) - 1) 49 high = sizeof(int) * 8 - 1; 50 bn_limit_bits_high = high; 51 bn_limit_num_high = 1 << high; 52 } 53 if (low >= 0) { 54 if (low > (int)(sizeof(int) * 8) - 1) 55 low = sizeof(int) * 8 - 1; 56 bn_limit_bits_low = low; 57 bn_limit_num_low = 1 << low; 58 } 59 if (mont >= 0) { 60 if (mont > (int)(sizeof(int) * 8) - 1) 61 mont = sizeof(int) * 8 - 1; 62 bn_limit_bits_mont = mont; 63 bn_limit_num_mont = 1 << mont; 64 } 65} 66 67int BN_get_params(int which) 68{ 69 if (which == 0) 70 return bn_limit_bits; 71 else if (which == 1) 72 return bn_limit_bits_high; 73 else if (which == 2) 74 return bn_limit_bits_low; 75 else if (which == 3) 76 return bn_limit_bits_mont; 77 else 78 return 0; 79} 80#endif 81 82const BIGNUM *BN_value_one(void) 83{ 84 static const BN_ULONG data_one = 1L; 85 static const BIGNUM const_one = 86 { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA }; 87 88 return &const_one; 89} 90 91/* 92 * Old Visual Studio ARM compiler miscompiles BN_num_bits_word() 93 * https://mta.openssl.org/pipermail/openssl-users/2018-August/008465.html 94 */ 95#if defined(_MSC_VER) && defined(_ARM_) && defined(_WIN32_WCE) \ 96 && _MSC_VER>=1400 && _MSC_VER<1501 97# define MS_BROKEN_BN_num_bits_word 98# pragma optimize("", off) 99#endif 100int BN_num_bits_word(BN_ULONG l) 101{ 102 BN_ULONG x, mask; 103 int bits = (l != 0); 104 105#if BN_BITS2 > 32 106 x = l >> 32; 107 mask = (0 - x) & BN_MASK2; 108 mask = (0 - (mask >> (BN_BITS2 - 1))); 109 bits += 32 & mask; 110 l ^= (x ^ l) & mask; 111#endif 112 113 x = l >> 16; 114 mask = (0 - x) & BN_MASK2; 115 mask = (0 - (mask >> (BN_BITS2 - 1))); 116 bits += 16 & mask; 117 l ^= (x ^ l) & mask; 118 119 x = l >> 8; 120 mask = (0 - x) & BN_MASK2; 121 mask = (0 - (mask >> (BN_BITS2 - 1))); 122 bits += 8 & mask; 123 l ^= (x ^ l) & mask; 124 125 x = l >> 4; 126 mask = (0 - x) & BN_MASK2; 127 mask = (0 - (mask >> (BN_BITS2 - 1))); 128 bits += 4 & mask; 129 l ^= (x ^ l) & mask; 130 131 x = l >> 2; 132 mask = (0 - x) & BN_MASK2; 133 mask = (0 - (mask >> (BN_BITS2 - 1))); 134 bits += 2 & mask; 135 l ^= (x ^ l) & mask; 136 137 x = l >> 1; 138 mask = (0 - x) & BN_MASK2; 139 mask = (0 - (mask >> (BN_BITS2 - 1))); 140 bits += 1 & mask; 141 142 return bits; 143} 144#ifdef MS_BROKEN_BN_num_bits_word 145# pragma optimize("", on) 146#endif 147 148/* 149 * This function still leaks `a->dmax`: it's caller's responsibility to 150 * expand the input `a` in advance to a public length. 151 */ 152static ossl_inline 153int bn_num_bits_consttime(const BIGNUM *a) 154{ 155 int j, ret; 156 unsigned int mask, past_i; 157 int i = a->top - 1; 158 bn_check_top(a); 159 160 for (j = 0, past_i = 0, ret = 0; j < a->dmax; j++) { 161 mask = constant_time_eq_int(i, j); /* 0xff..ff if i==j, 0x0 otherwise */ 162 163 ret += BN_BITS2 & (~mask & ~past_i); 164 ret += BN_num_bits_word(a->d[j]) & mask; 165 166 past_i |= mask; /* past_i will become 0xff..ff after i==j */ 167 } 168 169 /* 170 * if BN_is_zero(a) => i is -1 and ret contains garbage, so we mask the 171 * final result. 172 */ 173 mask = ~(constant_time_eq_int(i, ((int)-1))); 174 175 return ret & mask; 176} 177 178int BN_num_bits(const BIGNUM *a) 179{ 180 int i = a->top - 1; 181 bn_check_top(a); 182 183 if (a->flags & BN_FLG_CONSTTIME) { 184 /* 185 * We assume that BIGNUMs flagged as CONSTTIME have also been expanded 186 * so that a->dmax is not leaking secret information. 187 * 188 * In other words, it's the caller's responsibility to ensure `a` has 189 * been preallocated in advance to a public length if we hit this 190 * branch. 191 * 192 */ 193 return bn_num_bits_consttime(a); 194 } 195 196 if (BN_is_zero(a)) 197 return 0; 198 199 return ((i * BN_BITS2) + BN_num_bits_word(a->d[i])); 200} 201 202static void bn_free_d(BIGNUM *a, int clear) 203{ 204 if (BN_get_flags(a, BN_FLG_SECURE)) 205 OPENSSL_secure_clear_free(a->d, a->dmax * sizeof(a->d[0])); 206 else if (clear != 0) 207 OPENSSL_clear_free(a->d, a->dmax * sizeof(a->d[0])); 208 else 209 OPENSSL_free(a->d); 210} 211 212 213void BN_clear_free(BIGNUM *a) 214{ 215 if (a == NULL) 216 return; 217 if (a->d != NULL && !BN_get_flags(a, BN_FLG_STATIC_DATA)) 218 bn_free_d(a, 1); 219 if (BN_get_flags(a, BN_FLG_MALLOCED)) { 220 OPENSSL_cleanse(a, sizeof(*a)); 221 OPENSSL_free(a); 222 } 223} 224 225void BN_free(BIGNUM *a) 226{ 227 if (a == NULL) 228 return; 229 if (!BN_get_flags(a, BN_FLG_STATIC_DATA)) 230 bn_free_d(a, 0); 231 if (a->flags & BN_FLG_MALLOCED) 232 OPENSSL_free(a); 233} 234 235void bn_init(BIGNUM *a) 236{ 237 static BIGNUM nilbn; 238 239 *a = nilbn; 240 bn_check_top(a); 241} 242 243BIGNUM *BN_new(void) 244{ 245 BIGNUM *ret; 246 247 if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) { 248 ERR_raise(ERR_LIB_BN, ERR_R_MALLOC_FAILURE); 249 return NULL; 250 } 251 ret->flags = BN_FLG_MALLOCED; 252 bn_check_top(ret); 253 return ret; 254} 255 256 BIGNUM *BN_secure_new(void) 257 { 258 BIGNUM *ret = BN_new(); 259 if (ret != NULL) 260 ret->flags |= BN_FLG_SECURE; 261 return ret; 262 } 263 264/* This is used by bn_expand2() */ 265/* The caller MUST check that words > b->dmax before calling this */ 266static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) 267{ 268 BN_ULONG *a = NULL; 269 270 if (words > (INT_MAX / (4 * BN_BITS2))) { 271 ERR_raise(ERR_LIB_BN, BN_R_BIGNUM_TOO_LONG); 272 return NULL; 273 } 274 if (BN_get_flags(b, BN_FLG_STATIC_DATA)) { 275 ERR_raise(ERR_LIB_BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 276 return NULL; 277 } 278 if (BN_get_flags(b, BN_FLG_SECURE)) 279 a = OPENSSL_secure_zalloc(words * sizeof(*a)); 280 else 281 a = OPENSSL_zalloc(words * sizeof(*a)); 282 if (a == NULL) { 283 ERR_raise(ERR_LIB_BN, ERR_R_MALLOC_FAILURE); 284 return NULL; 285 } 286 287 assert(b->top <= words); 288 if (b->top > 0) 289 memcpy(a, b->d, sizeof(*a) * b->top); 290 291 return a; 292} 293 294/* 295 * This is an internal function that should not be used in applications. It 296 * ensures that 'b' has enough room for a 'words' word number and initialises 297 * any unused part of b->d with leading zeros. It is mostly used by the 298 * various BIGNUM routines. If there is an error, NULL is returned. If not, 299 * 'b' is returned. 300 */ 301 302BIGNUM *bn_expand2(BIGNUM *b, int words) 303{ 304 if (words > b->dmax) { 305 BN_ULONG *a = bn_expand_internal(b, words); 306 if (!a) 307 return NULL; 308 if (b->d != NULL) 309 bn_free_d(b, 1); 310 b->d = a; 311 b->dmax = words; 312 } 313 314 return b; 315} 316 317BIGNUM *BN_dup(const BIGNUM *a) 318{ 319 BIGNUM *t; 320 321 if (a == NULL) 322 return NULL; 323 bn_check_top(a); 324 325 t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new(); 326 if (t == NULL) 327 return NULL; 328 if (!BN_copy(t, a)) { 329 BN_free(t); 330 return NULL; 331 } 332 bn_check_top(t); 333 return t; 334} 335 336BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) 337{ 338 int bn_words; 339 340 bn_check_top(b); 341 342 bn_words = BN_get_flags(b, BN_FLG_CONSTTIME) ? b->dmax : b->top; 343 344 if (a == b) 345 return a; 346 if (bn_wexpand(a, bn_words) == NULL) 347 return NULL; 348 349 if (b->top > 0) 350 memcpy(a->d, b->d, sizeof(b->d[0]) * bn_words); 351 352 a->neg = b->neg; 353 a->top = b->top; 354 a->flags |= b->flags & BN_FLG_FIXED_TOP; 355 bn_check_top(a); 356 return a; 357} 358 359#define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \ 360 | BN_FLG_CONSTTIME \ 361 | BN_FLG_SECURE \ 362 | BN_FLG_FIXED_TOP)) 363#define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED)) 364 365void BN_swap(BIGNUM *a, BIGNUM *b) 366{ 367 int flags_old_a, flags_old_b; 368 BN_ULONG *tmp_d; 369 int tmp_top, tmp_dmax, tmp_neg; 370 371 bn_check_top(a); 372 bn_check_top(b); 373 374 flags_old_a = a->flags; 375 flags_old_b = b->flags; 376 377 tmp_d = a->d; 378 tmp_top = a->top; 379 tmp_dmax = a->dmax; 380 tmp_neg = a->neg; 381 382 a->d = b->d; 383 a->top = b->top; 384 a->dmax = b->dmax; 385 a->neg = b->neg; 386 387 b->d = tmp_d; 388 b->top = tmp_top; 389 b->dmax = tmp_dmax; 390 b->neg = tmp_neg; 391 392 a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b); 393 b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a); 394 bn_check_top(a); 395 bn_check_top(b); 396} 397 398void BN_clear(BIGNUM *a) 399{ 400 if (a == NULL) 401 return; 402 bn_check_top(a); 403 if (a->d != NULL) 404 OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax); 405 a->neg = 0; 406 a->top = 0; 407 a->flags &= ~BN_FLG_FIXED_TOP; 408} 409 410BN_ULONG BN_get_word(const BIGNUM *a) 411{ 412 if (a->top > 1) 413 return BN_MASK2; 414 else if (a->top == 1) 415 return a->d[0]; 416 /* a->top == 0 */ 417 return 0; 418} 419 420int BN_set_word(BIGNUM *a, BN_ULONG w) 421{ 422 bn_check_top(a); 423 if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL) 424 return 0; 425 a->neg = 0; 426 a->d[0] = w; 427 a->top = (w ? 1 : 0); 428 a->flags &= ~BN_FLG_FIXED_TOP; 429 bn_check_top(a); 430 return 1; 431} 432 433BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) 434{ 435 unsigned int i, m; 436 unsigned int n; 437 BN_ULONG l; 438 BIGNUM *bn = NULL; 439 440 if (ret == NULL) 441 ret = bn = BN_new(); 442 if (ret == NULL) 443 return NULL; 444 bn_check_top(ret); 445 /* Skip leading zero's. */ 446 for ( ; len > 0 && *s == 0; s++, len--) 447 continue; 448 n = len; 449 if (n == 0) { 450 ret->top = 0; 451 return ret; 452 } 453 i = ((n - 1) / BN_BYTES) + 1; 454 m = ((n - 1) % (BN_BYTES)); 455 if (bn_wexpand(ret, (int)i) == NULL) { 456 BN_free(bn); 457 return NULL; 458 } 459 ret->top = i; 460 ret->neg = 0; 461 l = 0; 462 while (n--) { 463 l = (l << 8L) | *(s++); 464 if (m-- == 0) { 465 ret->d[--i] = l; 466 l = 0; 467 m = BN_BYTES - 1; 468 } 469 } 470 /* 471 * need to call this due to clear byte at top if avoiding having the top 472 * bit set (-ve number) 473 */ 474 bn_correct_top(ret); 475 return ret; 476} 477 478typedef enum {big, little} endianess_t; 479 480/* ignore negative */ 481static 482int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen, endianess_t endianess) 483{ 484 int n; 485 size_t i, lasti, j, atop, mask; 486 BN_ULONG l; 487 488 /* 489 * In case |a| is fixed-top, BN_num_bytes can return bogus length, 490 * but it's assumed that fixed-top inputs ought to be "nominated" 491 * even for padded output, so it works out... 492 */ 493 n = BN_num_bytes(a); 494 if (tolen == -1) { 495 tolen = n; 496 } else if (tolen < n) { /* uncommon/unlike case */ 497 BIGNUM temp = *a; 498 499 bn_correct_top(&temp); 500 n = BN_num_bytes(&temp); 501 if (tolen < n) 502 return -1; 503 } 504 505 /* Swipe through whole available data and don't give away padded zero. */ 506 atop = a->dmax * BN_BYTES; 507 if (atop == 0) { 508 if (tolen != 0) 509 memset(to, '\0', tolen); 510 return tolen; 511 } 512 513 lasti = atop - 1; 514 atop = a->top * BN_BYTES; 515 if (endianess == big) 516 to += tolen; /* start from the end of the buffer */ 517 for (i = 0, j = 0; j < (size_t)tolen; j++) { 518 unsigned char val; 519 l = a->d[i / BN_BYTES]; 520 mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1)); 521 val = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask); 522 if (endianess == big) 523 *--to = val; 524 else 525 *to++ = val; 526 i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */ 527 } 528 529 return tolen; 530} 531 532int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) 533{ 534 if (tolen < 0) 535 return -1; 536 return bn2binpad(a, to, tolen, big); 537} 538 539int BN_bn2bin(const BIGNUM *a, unsigned char *to) 540{ 541 return bn2binpad(a, to, -1, big); 542} 543 544BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret) 545{ 546 unsigned int i, m; 547 unsigned int n; 548 BN_ULONG l; 549 BIGNUM *bn = NULL; 550 551 if (ret == NULL) 552 ret = bn = BN_new(); 553 if (ret == NULL) 554 return NULL; 555 bn_check_top(ret); 556 s += len; 557 /* Skip trailing zeroes. */ 558 for ( ; len > 0 && s[-1] == 0; s--, len--) 559 continue; 560 n = len; 561 if (n == 0) { 562 ret->top = 0; 563 return ret; 564 } 565 i = ((n - 1) / BN_BYTES) + 1; 566 m = ((n - 1) % (BN_BYTES)); 567 if (bn_wexpand(ret, (int)i) == NULL) { 568 BN_free(bn); 569 return NULL; 570 } 571 ret->top = i; 572 ret->neg = 0; 573 l = 0; 574 while (n--) { 575 s--; 576 l = (l << 8L) | *s; 577 if (m-- == 0) { 578 ret->d[--i] = l; 579 l = 0; 580 m = BN_BYTES - 1; 581 } 582 } 583 /* 584 * need to call this due to clear byte at top if avoiding having the top 585 * bit set (-ve number) 586 */ 587 bn_correct_top(ret); 588 return ret; 589} 590 591int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen) 592{ 593 if (tolen < 0) 594 return -1; 595 return bn2binpad(a, to, tolen, little); 596} 597 598BIGNUM *BN_native2bn(const unsigned char *s, int len, BIGNUM *ret) 599{ 600 DECLARE_IS_ENDIAN; 601 602 if (IS_LITTLE_ENDIAN) 603 return BN_lebin2bn(s, len, ret); 604 return BN_bin2bn(s, len, ret); 605} 606 607int BN_bn2nativepad(const BIGNUM *a, unsigned char *to, int tolen) 608{ 609 DECLARE_IS_ENDIAN; 610 611 if (IS_LITTLE_ENDIAN) 612 return BN_bn2lebinpad(a, to, tolen); 613 return BN_bn2binpad(a, to, tolen); 614} 615 616int BN_ucmp(const BIGNUM *a, const BIGNUM *b) 617{ 618 int i; 619 BN_ULONG t1, t2, *ap, *bp; 620 621 bn_check_top(a); 622 bn_check_top(b); 623 624 i = a->top - b->top; 625 if (i != 0) 626 return i; 627 ap = a->d; 628 bp = b->d; 629 for (i = a->top - 1; i >= 0; i--) { 630 t1 = ap[i]; 631 t2 = bp[i]; 632 if (t1 != t2) 633 return ((t1 > t2) ? 1 : -1); 634 } 635 return 0; 636} 637 638int BN_cmp(const BIGNUM *a, const BIGNUM *b) 639{ 640 int i; 641 int gt, lt; 642 BN_ULONG t1, t2; 643 644 if ((a == NULL) || (b == NULL)) { 645 if (a != NULL) 646 return -1; 647 else if (b != NULL) 648 return 1; 649 else 650 return 0; 651 } 652 653 bn_check_top(a); 654 bn_check_top(b); 655 656 if (a->neg != b->neg) { 657 if (a->neg) 658 return -1; 659 else 660 return 1; 661 } 662 if (a->neg == 0) { 663 gt = 1; 664 lt = -1; 665 } else { 666 gt = -1; 667 lt = 1; 668 } 669 670 if (a->top > b->top) 671 return gt; 672 if (a->top < b->top) 673 return lt; 674 for (i = a->top - 1; i >= 0; i--) { 675 t1 = a->d[i]; 676 t2 = b->d[i]; 677 if (t1 > t2) 678 return gt; 679 if (t1 < t2) 680 return lt; 681 } 682 return 0; 683} 684 685int BN_set_bit(BIGNUM *a, int n) 686{ 687 int i, j, k; 688 689 if (n < 0) 690 return 0; 691 692 i = n / BN_BITS2; 693 j = n % BN_BITS2; 694 if (a->top <= i) { 695 if (bn_wexpand(a, i + 1) == NULL) 696 return 0; 697 for (k = a->top; k < i + 1; k++) 698 a->d[k] = 0; 699 a->top = i + 1; 700 a->flags &= ~BN_FLG_FIXED_TOP; 701 } 702 703 a->d[i] |= (((BN_ULONG)1) << j); 704 bn_check_top(a); 705 return 1; 706} 707 708int BN_clear_bit(BIGNUM *a, int n) 709{ 710 int i, j; 711 712 bn_check_top(a); 713 if (n < 0) 714 return 0; 715 716 i = n / BN_BITS2; 717 j = n % BN_BITS2; 718 if (a->top <= i) 719 return 0; 720 721 a->d[i] &= (~(((BN_ULONG)1) << j)); 722 bn_correct_top(a); 723 return 1; 724} 725 726int BN_is_bit_set(const BIGNUM *a, int n) 727{ 728 int i, j; 729 730 bn_check_top(a); 731 if (n < 0) 732 return 0; 733 i = n / BN_BITS2; 734 j = n % BN_BITS2; 735 if (a->top <= i) 736 return 0; 737 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); 738} 739 740int BN_mask_bits(BIGNUM *a, int n) 741{ 742 int b, w; 743 744 bn_check_top(a); 745 if (n < 0) 746 return 0; 747 748 w = n / BN_BITS2; 749 b = n % BN_BITS2; 750 if (w >= a->top) 751 return 0; 752 if (b == 0) 753 a->top = w; 754 else { 755 a->top = w + 1; 756 a->d[w] &= ~(BN_MASK2 << b); 757 } 758 bn_correct_top(a); 759 return 1; 760} 761 762void BN_set_negative(BIGNUM *a, int b) 763{ 764 if (b && !BN_is_zero(a)) 765 a->neg = 1; 766 else 767 a->neg = 0; 768} 769 770int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) 771{ 772 int i; 773 BN_ULONG aa, bb; 774 775 if (n == 0) 776 return 0; 777 778 aa = a[n - 1]; 779 bb = b[n - 1]; 780 if (aa != bb) 781 return ((aa > bb) ? 1 : -1); 782 for (i = n - 2; i >= 0; i--) { 783 aa = a[i]; 784 bb = b[i]; 785 if (aa != bb) 786 return ((aa > bb) ? 1 : -1); 787 } 788 return 0; 789} 790 791/* 792 * Here follows a specialised variants of bn_cmp_words(). It has the 793 * capability of performing the operation on arrays of different sizes. The 794 * sizes of those arrays is expressed through cl, which is the common length 795 * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the 796 * two lengths, calculated as len(a)-len(b). All lengths are the number of 797 * BN_ULONGs... 798 */ 799 800int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) 801{ 802 int n, i; 803 n = cl - 1; 804 805 if (dl < 0) { 806 for (i = dl; i < 0; i++) { 807 if (b[n - i] != 0) 808 return -1; /* a < b */ 809 } 810 } 811 if (dl > 0) { 812 for (i = dl; i > 0; i--) { 813 if (a[n + i] != 0) 814 return 1; /* a > b */ 815 } 816 } 817 return bn_cmp_words(a, b, cl); 818} 819 820/*- 821 * Constant-time conditional swap of a and b. 822 * a and b are swapped if condition is not 0. 823 * nwords is the number of words to swap. 824 * Assumes that at least nwords are allocated in both a and b. 825 * Assumes that no more than nwords are used by either a or b. 826 */ 827void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) 828{ 829 BN_ULONG t; 830 int i; 831 832 if (a == b) 833 return; 834 835 bn_wcheck_size(a, nwords); 836 bn_wcheck_size(b, nwords); 837 838 condition = ((~condition & ((condition - 1))) >> (BN_BITS2 - 1)) - 1; 839 840 t = (a->top ^ b->top) & condition; 841 a->top ^= t; 842 b->top ^= t; 843 844 t = (a->neg ^ b->neg) & condition; 845 a->neg ^= t; 846 b->neg ^= t; 847 848 /*- 849 * BN_FLG_STATIC_DATA: indicates that data may not be written to. Intention 850 * is actually to treat it as it's read-only data, and some (if not most) 851 * of it does reside in read-only segment. In other words observation of 852 * BN_FLG_STATIC_DATA in BN_consttime_swap should be treated as fatal 853 * condition. It would either cause SEGV or effectively cause data 854 * corruption. 855 * 856 * BN_FLG_MALLOCED: refers to BN structure itself, and hence must be 857 * preserved. 858 * 859 * BN_FLG_SECURE: must be preserved, because it determines how x->d was 860 * allocated and hence how to free it. 861 * 862 * BN_FLG_CONSTTIME: sufficient to mask and swap 863 * 864 * BN_FLG_FIXED_TOP: indicates that we haven't called bn_correct_top() on 865 * the data, so the d array may be padded with additional 0 values (i.e. 866 * top could be greater than the minimal value that it could be). We should 867 * be swapping it 868 */ 869 870#define BN_CONSTTIME_SWAP_FLAGS (BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP) 871 872 t = ((a->flags ^ b->flags) & BN_CONSTTIME_SWAP_FLAGS) & condition; 873 a->flags ^= t; 874 b->flags ^= t; 875 876 /* conditionally swap the data */ 877 for (i = 0; i < nwords; i++) { 878 t = (a->d[i] ^ b->d[i]) & condition; 879 a->d[i] ^= t; 880 b->d[i] ^= t; 881 } 882} 883 884#undef BN_CONSTTIME_SWAP_FLAGS 885 886/* Bits of security, see SP800-57 */ 887 888int BN_security_bits(int L, int N) 889{ 890 int secbits, bits; 891 if (L >= 15360) 892 secbits = 256; 893 else if (L >= 7680) 894 secbits = 192; 895 else if (L >= 3072) 896 secbits = 128; 897 else if (L >= 2048) 898 secbits = 112; 899 else if (L >= 1024) 900 secbits = 80; 901 else 902 return 0; 903 if (N == -1) 904 return secbits; 905 bits = N / 2; 906 if (bits < 80) 907 return 0; 908 return bits >= secbits ? secbits : bits; 909} 910 911void BN_zero_ex(BIGNUM *a) 912{ 913 a->neg = 0; 914 a->top = 0; 915 a->flags &= ~BN_FLG_FIXED_TOP; 916} 917 918int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w) 919{ 920 return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0)); 921} 922 923int BN_is_zero(const BIGNUM *a) 924{ 925 return a->top == 0; 926} 927 928int BN_is_one(const BIGNUM *a) 929{ 930 return BN_abs_is_word(a, 1) && !a->neg; 931} 932 933int BN_is_word(const BIGNUM *a, const BN_ULONG w) 934{ 935 return BN_abs_is_word(a, w) && (!w || !a->neg); 936} 937 938int BN_is_odd(const BIGNUM *a) 939{ 940 return (a->top > 0) && (a->d[0] & 1); 941} 942 943int BN_is_negative(const BIGNUM *a) 944{ 945 return (a->neg != 0); 946} 947 948int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont, 949 BN_CTX *ctx) 950{ 951 return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx); 952} 953 954void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags) 955{ 956 dest->d = b->d; 957 dest->top = b->top; 958 dest->dmax = b->dmax; 959 dest->neg = b->neg; 960 dest->flags = ((dest->flags & BN_FLG_MALLOCED) 961 | (b->flags & ~BN_FLG_MALLOCED) 962 | BN_FLG_STATIC_DATA | flags); 963} 964 965BN_GENCB *BN_GENCB_new(void) 966{ 967 BN_GENCB *ret; 968 969 if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) { 970 ERR_raise(ERR_LIB_BN, ERR_R_MALLOC_FAILURE); 971 return NULL; 972 } 973 974 return ret; 975} 976 977void BN_GENCB_free(BN_GENCB *cb) 978{ 979 if (cb == NULL) 980 return; 981 OPENSSL_free(cb); 982} 983 984void BN_set_flags(BIGNUM *b, int n) 985{ 986 b->flags |= n; 987} 988 989int BN_get_flags(const BIGNUM *b, int n) 990{ 991 return b->flags & n; 992} 993 994/* Populate a BN_GENCB structure with an "old"-style callback */ 995void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *), 996 void *cb_arg) 997{ 998 BN_GENCB *tmp_gencb = gencb; 999 tmp_gencb->ver = 1; 1000 tmp_gencb->arg = cb_arg; 1001 tmp_gencb->cb.cb_1 = callback; 1002} 1003 1004/* Populate a BN_GENCB structure with a "new"-style callback */ 1005void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *), 1006 void *cb_arg) 1007{ 1008 BN_GENCB *tmp_gencb = gencb; 1009 tmp_gencb->ver = 2; 1010 tmp_gencb->arg = cb_arg; 1011 tmp_gencb->cb.cb_2 = callback; 1012} 1013 1014void *BN_GENCB_get_arg(BN_GENCB *cb) 1015{ 1016 return cb->arg; 1017} 1018 1019BIGNUM *bn_wexpand(BIGNUM *a, int words) 1020{ 1021 return (words <= a->dmax) ? a : bn_expand2(a, words); 1022} 1023 1024void bn_correct_top_consttime(BIGNUM *a) 1025{ 1026 int j, atop; 1027 BN_ULONG limb; 1028 unsigned int mask; 1029 1030 for (j = 0, atop = 0; j < a->dmax; j++) { 1031 limb = a->d[j]; 1032 limb |= 0 - limb; 1033 limb >>= BN_BITS2 - 1; 1034 limb = 0 - limb; 1035 mask = (unsigned int)limb; 1036 mask &= constant_time_msb(j - a->top); 1037 atop = constant_time_select_int(mask, j + 1, atop); 1038 } 1039 1040 mask = constant_time_eq_int(atop, 0); 1041 a->top = atop; 1042 a->neg = constant_time_select_int(mask, 0, a->neg); 1043 a->flags &= ~BN_FLG_FIXED_TOP; 1044} 1045 1046void bn_correct_top(BIGNUM *a) 1047{ 1048 BN_ULONG *ftl; 1049 int tmp_top = a->top; 1050 1051 if (tmp_top > 0) { 1052 for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) { 1053 ftl--; 1054 if (*ftl != 0) 1055 break; 1056 } 1057 a->top = tmp_top; 1058 } 1059 if (a->top == 0) 1060 a->neg = 0; 1061 a->flags &= ~BN_FLG_FIXED_TOP; 1062 bn_pollute(a); 1063} 1064