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