bn_lib.c revision 340704
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 if (words > (INT_MAX / (4 * BN_BITS2))) { 267 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG); 268 return NULL; 269 } 270 if (BN_get_flags(b, BN_FLG_STATIC_DATA)) { 271 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 272 return (NULL); 273 } 274 a = A = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG) * words); 275 if (A == NULL) { 276 BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE); 277 return (NULL); 278 } 279#ifdef PURIFY 280 /* 281 * Valgrind complains in BN_consttime_swap because we process the whole 282 * array even if it's not initialised yet. This doesn't matter in that 283 * function - what's important is constant time operation (we're not 284 * actually going to use the data) 285 */ 286 memset(a, 0, sizeof(BN_ULONG) * words); 287#endif 288 289#if 1 290 B = b->d; 291 /* Check if the previous number needs to be copied */ 292 if (B != NULL) { 293 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { 294 /* 295 * The fact that the loop is unrolled 296 * 4-wise is a tribute to Intel. It's 297 * the one that doesn't have enough 298 * registers to accomodate more data. 299 * I'd unroll it 8-wise otherwise:-) 300 * 301 * <appro@fy.chalmers.se> 302 */ 303 BN_ULONG a0, a1, a2, a3; 304 a0 = B[0]; 305 a1 = B[1]; 306 a2 = B[2]; 307 a3 = B[3]; 308 A[0] = a0; 309 A[1] = a1; 310 A[2] = a2; 311 A[3] = a3; 312 } 313 /* 314 * workaround for ultrix cc: without 'case 0', the optimizer does 315 * the switch table by doing a=top&3; a--; goto jump_table[a]; 316 * which fails for top== 0 317 */ 318 switch (b->top & 3) { 319 case 3: 320 A[2] = B[2]; 321 case 2: 322 A[1] = B[1]; 323 case 1: 324 A[0] = B[0]; 325 case 0: 326 ; 327 } 328 } 329#else 330 memset(A, 0, sizeof(BN_ULONG) * words); 331 memcpy(A, b->d, sizeof(b->d[0]) * b->top); 332#endif 333 334 return (a); 335} 336 337/* 338 * This is an internal function that can be used instead of bn_expand2() when 339 * there is a need to copy BIGNUMs instead of only expanding the data part, 340 * while still expanding them. Especially useful when needing to expand 341 * BIGNUMs that are declared 'const' and should therefore not be changed. The 342 * reason to use this instead of a BN_dup() followed by a bn_expand2() is 343 * memory allocation overhead. A BN_dup() followed by a bn_expand2() will 344 * allocate new memory for the BIGNUM data twice, and free it once, while 345 * bn_dup_expand() makes sure allocation is made only once. 346 */ 347 348#ifndef OPENSSL_NO_DEPRECATED 349BIGNUM *bn_dup_expand(const BIGNUM *b, int words) 350{ 351 BIGNUM *r = NULL; 352 353 bn_check_top(b); 354 355 /* 356 * This function does not work if words <= b->dmax && top < words because 357 * BN_dup() does not preserve 'dmax'! (But bn_dup_expand() is not used 358 * anywhere yet.) 359 */ 360 361 if (words > b->dmax) { 362 BN_ULONG *a = bn_expand_internal(b, words); 363 364 if (a) { 365 r = BN_new(); 366 if (r) { 367 r->top = b->top; 368 r->dmax = words; 369 r->neg = b->neg; 370 r->d = a; 371 } else { 372 /* r == NULL, BN_new failure */ 373 OPENSSL_free(a); 374 } 375 } 376 /* 377 * If a == NULL, there was an error in allocation in 378 * bn_expand_internal(), and NULL should be returned 379 */ 380 } else { 381 r = BN_dup(b); 382 } 383 384 bn_check_top(r); 385 return r; 386} 387#endif 388 389/* 390 * This is an internal function that should not be used in applications. It 391 * ensures that 'b' has enough room for a 'words' word number and initialises 392 * any unused part of b->d with leading zeros. It is mostly used by the 393 * various BIGNUM routines. If there is an error, NULL is returned. If not, 394 * 'b' is returned. 395 */ 396 397BIGNUM *bn_expand2(BIGNUM *b, int words) 398{ 399 if (words > b->dmax) { 400 BN_ULONG *a = bn_expand_internal(b, words); 401 if (!a) 402 return NULL; 403 if (b->d) 404 OPENSSL_free(b->d); 405 b->d = a; 406 b->dmax = words; 407 } 408 409/* None of this should be necessary because of what b->top means! */ 410#if 0 411 /* 412 * NB: bn_wexpand() calls this only if the BIGNUM really has to grow 413 */ 414 if (b->top < b->dmax) { 415 int i; 416 BN_ULONG *A = &(b->d[b->top]); 417 for (i = (b->dmax - b->top) >> 3; i > 0; i--, A += 8) { 418 A[0] = 0; 419 A[1] = 0; 420 A[2] = 0; 421 A[3] = 0; 422 A[4] = 0; 423 A[5] = 0; 424 A[6] = 0; 425 A[7] = 0; 426 } 427 for (i = (b->dmax - b->top) & 7; i > 0; i--, A++) 428 A[0] = 0; 429 assert(A == &(b->d[b->dmax])); 430 } 431#endif 432 return b; 433} 434 435BIGNUM *BN_dup(const BIGNUM *a) 436{ 437 BIGNUM *t; 438 439 if (a == NULL) 440 return NULL; 441 bn_check_top(a); 442 443 t = BN_new(); 444 if (t == NULL) 445 return NULL; 446 if (!BN_copy(t, a)) { 447 BN_free(t); 448 return NULL; 449 } 450 bn_check_top(t); 451 return t; 452} 453 454BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) 455{ 456 int i; 457 BN_ULONG *A; 458 const BN_ULONG *B; 459 460 bn_check_top(b); 461 462 if (a == b) 463 return (a); 464 if (bn_wexpand(a, b->top) == NULL) 465 return (NULL); 466 467#if 1 468 A = a->d; 469 B = b->d; 470 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { 471 BN_ULONG a0, a1, a2, a3; 472 a0 = B[0]; 473 a1 = B[1]; 474 a2 = B[2]; 475 a3 = B[3]; 476 A[0] = a0; 477 A[1] = a1; 478 A[2] = a2; 479 A[3] = a3; 480 } 481 /* ultrix cc workaround, see comments in bn_expand_internal */ 482 switch (b->top & 3) { 483 case 3: 484 A[2] = B[2]; 485 case 2: 486 A[1] = B[1]; 487 case 1: 488 A[0] = B[0]; 489 case 0:; 490 } 491#else 492 memcpy(a->d, b->d, sizeof(b->d[0]) * b->top); 493#endif 494 495 a->neg = b->neg; 496 a->top = b->top; 497 a->flags |= b->flags & BN_FLG_FIXED_TOP; 498 bn_check_top(a); 499 return (a); 500} 501 502#define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \ 503 | BN_FLG_CONSTTIME \ 504 | BN_FLG_FIXED_TOP)) 505#define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED)) 506 507void BN_swap(BIGNUM *a, BIGNUM *b) 508{ 509 int flags_old_a, flags_old_b; 510 BN_ULONG *tmp_d; 511 int tmp_top, tmp_dmax, tmp_neg; 512 513 bn_check_top(a); 514 bn_check_top(b); 515 516 flags_old_a = a->flags; 517 flags_old_b = b->flags; 518 519 tmp_d = a->d; 520 tmp_top = a->top; 521 tmp_dmax = a->dmax; 522 tmp_neg = a->neg; 523 524 a->d = b->d; 525 a->top = b->top; 526 a->dmax = b->dmax; 527 a->neg = b->neg; 528 529 b->d = tmp_d; 530 b->top = tmp_top; 531 b->dmax = tmp_dmax; 532 b->neg = tmp_neg; 533 534 a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b); 535 b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a); 536 bn_check_top(a); 537 bn_check_top(b); 538} 539 540void BN_clear(BIGNUM *a) 541{ 542 bn_check_top(a); 543 if (a->d != NULL) 544 OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0])); 545 a->top = 0; 546 a->neg = 0; 547 a->flags &= ~BN_FLG_FIXED_TOP; 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 a->flags &= ~BN_FLG_FIXED_TOP; 569 bn_check_top(a); 570 return (1); 571} 572 573BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) 574{ 575 unsigned int i, m; 576 unsigned int n; 577 BN_ULONG l; 578 BIGNUM *bn = NULL; 579 580 if (ret == NULL) 581 ret = bn = BN_new(); 582 if (ret == NULL) 583 return (NULL); 584 bn_check_top(ret); 585 l = 0; 586 n = len; 587 if (n == 0) { 588 ret->top = 0; 589 return (ret); 590 } 591 i = ((n - 1) / BN_BYTES) + 1; 592 m = ((n - 1) % (BN_BYTES)); 593 if (bn_wexpand(ret, (int)i) == NULL) { 594 if (bn) 595 BN_free(bn); 596 return NULL; 597 } 598 ret->top = i; 599 ret->neg = 0; 600 while (n--) { 601 l = (l << 8L) | *(s++); 602 if (m-- == 0) { 603 ret->d[--i] = l; 604 l = 0; 605 m = BN_BYTES - 1; 606 } 607 } 608 /* 609 * need to call this due to clear byte at top if avoiding having the top 610 * bit set (-ve number) 611 */ 612 bn_correct_top(ret); 613 return (ret); 614} 615 616/* ignore negative */ 617static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) 618{ 619 int n; 620 size_t i, lasti, j, atop, mask; 621 BN_ULONG l; 622 623 /* 624 * In case |a| is fixed-top, BN_num_bytes can return bogus length, 625 * but it's assumed that fixed-top inputs ought to be "nominated" 626 * even for padded output, so it works out... 627 */ 628 n = BN_num_bytes(a); 629 if (tolen == -1) { 630 tolen = n; 631 } else if (tolen < n) { /* uncommon/unlike case */ 632 BIGNUM temp = *a; 633 634 bn_correct_top(&temp); 635 n = BN_num_bytes(&temp); 636 if (tolen < n) 637 return -1; 638 } 639 640 /* Swipe through whole available data and don't give away padded zero. */ 641 atop = a->dmax * BN_BYTES; 642 if (atop == 0) { 643 OPENSSL_cleanse(to, tolen); 644 return tolen; 645 } 646 647 lasti = atop - 1; 648 atop = a->top * BN_BYTES; 649 for (i = 0, j = 0, to += tolen; j < (size_t)tolen; j++) { 650 l = a->d[i / BN_BYTES]; 651 mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1)); 652 *--to = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask); 653 i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */ 654 } 655 656 return tolen; 657} 658 659int bn_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) 660{ 661 if (tolen < 0) 662 return -1; 663 return bn2binpad(a, to, tolen); 664} 665 666int BN_bn2bin(const BIGNUM *a, unsigned char *to) 667{ 668 int n, i; 669 BN_ULONG l; 670 671 bn_check_top(a); 672 n = i = BN_num_bytes(a); 673 while (i--) { 674 l = a->d[i / BN_BYTES]; 675 *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff; 676 } 677 return (n); 678} 679 680int BN_ucmp(const BIGNUM *a, const BIGNUM *b) 681{ 682 int i; 683 BN_ULONG t1, t2, *ap, *bp; 684 685 bn_check_top(a); 686 bn_check_top(b); 687 688 i = a->top - b->top; 689 if (i != 0) 690 return (i); 691 ap = a->d; 692 bp = b->d; 693 for (i = a->top - 1; i >= 0; i--) { 694 t1 = ap[i]; 695 t2 = bp[i]; 696 if (t1 != t2) 697 return ((t1 > t2) ? 1 : -1); 698 } 699 return (0); 700} 701 702int BN_cmp(const BIGNUM *a, const BIGNUM *b) 703{ 704 int i; 705 int gt, lt; 706 BN_ULONG t1, t2; 707 708 if ((a == NULL) || (b == NULL)) { 709 if (a != NULL) 710 return (-1); 711 else if (b != NULL) 712 return (1); 713 else 714 return (0); 715 } 716 717 bn_check_top(a); 718 bn_check_top(b); 719 720 if (a->neg != b->neg) { 721 if (a->neg) 722 return (-1); 723 else 724 return (1); 725 } 726 if (a->neg == 0) { 727 gt = 1; 728 lt = -1; 729 } else { 730 gt = -1; 731 lt = 1; 732 } 733 734 if (a->top > b->top) 735 return (gt); 736 if (a->top < b->top) 737 return (lt); 738 for (i = a->top - 1; i >= 0; i--) { 739 t1 = a->d[i]; 740 t2 = b->d[i]; 741 if (t1 > t2) 742 return (gt); 743 if (t1 < t2) 744 return (lt); 745 } 746 return (0); 747} 748 749int BN_set_bit(BIGNUM *a, int n) 750{ 751 int i, j, k; 752 753 if (n < 0) 754 return 0; 755 756 i = n / BN_BITS2; 757 j = n % BN_BITS2; 758 if (a->top <= i) { 759 if (bn_wexpand(a, i + 1) == NULL) 760 return (0); 761 for (k = a->top; k < i + 1; k++) 762 a->d[k] = 0; 763 a->top = i + 1; 764 a->flags &= ~BN_FLG_FIXED_TOP; 765 } 766 767 a->d[i] |= (((BN_ULONG)1) << j); 768 bn_check_top(a); 769 return (1); 770} 771 772int BN_clear_bit(BIGNUM *a, int n) 773{ 774 int i, j; 775 776 bn_check_top(a); 777 if (n < 0) 778 return 0; 779 780 i = n / BN_BITS2; 781 j = n % BN_BITS2; 782 if (a->top <= i) 783 return (0); 784 785 a->d[i] &= (~(((BN_ULONG)1) << j)); 786 bn_correct_top(a); 787 return (1); 788} 789 790int BN_is_bit_set(const BIGNUM *a, int n) 791{ 792 int i, j; 793 794 bn_check_top(a); 795 if (n < 0) 796 return 0; 797 i = n / BN_BITS2; 798 j = n % BN_BITS2; 799 if (a->top <= i) 800 return 0; 801 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); 802} 803 804int BN_mask_bits(BIGNUM *a, int n) 805{ 806 int b, w; 807 808 bn_check_top(a); 809 if (n < 0) 810 return 0; 811 812 w = n / BN_BITS2; 813 b = n % BN_BITS2; 814 if (w >= a->top) 815 return 0; 816 if (b == 0) 817 a->top = w; 818 else { 819 a->top = w + 1; 820 a->d[w] &= ~(BN_MASK2 << b); 821 } 822 bn_correct_top(a); 823 return (1); 824} 825 826void BN_set_negative(BIGNUM *a, int b) 827{ 828 if (b && !BN_is_zero(a)) 829 a->neg = 1; 830 else 831 a->neg = 0; 832} 833 834int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) 835{ 836 int i; 837 BN_ULONG aa, bb; 838 839 aa = a[n - 1]; 840 bb = b[n - 1]; 841 if (aa != bb) 842 return ((aa > bb) ? 1 : -1); 843 for (i = n - 2; i >= 0; i--) { 844 aa = a[i]; 845 bb = b[i]; 846 if (aa != bb) 847 return ((aa > bb) ? 1 : -1); 848 } 849 return (0); 850} 851 852/* 853 * Here follows a specialised variants of bn_cmp_words(). It has the 854 * property of performing the operation on arrays of different sizes. The 855 * sizes of those arrays is expressed through cl, which is the common length 856 * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the 857 * two lengths, calculated as len(a)-len(b). All lengths are the number of 858 * BN_ULONGs... 859 */ 860 861int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) 862{ 863 int n, i; 864 n = cl - 1; 865 866 if (dl < 0) { 867 for (i = dl; i < 0; i++) { 868 if (b[n - i] != 0) 869 return -1; /* a < b */ 870 } 871 } 872 if (dl > 0) { 873 for (i = dl; i > 0; i--) { 874 if (a[n + i] != 0) 875 return 1; /* a > b */ 876 } 877 } 878 return bn_cmp_words(a, b, cl); 879} 880 881/* 882 * Constant-time conditional swap of a and b. 883 * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set. 884 * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b, 885 * and that no more than nwords are used by either a or b. 886 * a and b cannot be the same number 887 */ 888void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) 889{ 890 BN_ULONG t; 891 int i; 892 893 bn_wcheck_size(a, nwords); 894 bn_wcheck_size(b, nwords); 895 896 assert(a != b); 897 assert((condition & (condition - 1)) == 0); 898 assert(sizeof(BN_ULONG) >= sizeof(int)); 899 900 condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1; 901 902 t = (a->top ^ b->top) & condition; 903 a->top ^= t; 904 b->top ^= t; 905 906 t = (a->neg ^ b->neg) & condition; 907 a->neg ^= t; 908 b->neg ^= t; 909 910 /*- 911 * BN_FLG_STATIC_DATA: indicates that data may not be written to. Intention 912 * is actually to treat it as it's read-only data, and some (if not most) 913 * of it does reside in read-only segment. In other words observation of 914 * BN_FLG_STATIC_DATA in BN_consttime_swap should be treated as fatal 915 * condition. It would either cause SEGV or effectively cause data 916 * corruption. 917 * 918 * BN_FLG_MALLOCED: refers to BN structure itself, and hence must be 919 * preserved. 920 * 921 * BN_FLG_SECURE: must be preserved, because it determines how x->d was 922 * allocated and hence how to free it. 923 * 924 * BN_FLG_CONSTTIME: sufficient to mask and swap 925 * 926 * BN_FLG_FIXED_TOP: indicates that we haven't called bn_correct_top() on 927 * the data, so the d array may be padded with additional 0 values (i.e. 928 * top could be greater than the minimal value that it could be). We should 929 * be swapping it 930 */ 931 932#define BN_CONSTTIME_SWAP_FLAGS (BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP) 933 934 t = ((a->flags ^ b->flags) & BN_CONSTTIME_SWAP_FLAGS) & condition; 935 a->flags ^= t; 936 b->flags ^= t; 937 938#define BN_CONSTTIME_SWAP(ind) \ 939 do { \ 940 t = (a->d[ind] ^ b->d[ind]) & condition; \ 941 a->d[ind] ^= t; \ 942 b->d[ind] ^= t; \ 943 } while (0) 944 945 switch (nwords) { 946 default: 947 for (i = 10; i < nwords; i++) 948 BN_CONSTTIME_SWAP(i); 949 /* Fallthrough */ 950 case 10: 951 BN_CONSTTIME_SWAP(9); /* Fallthrough */ 952 case 9: 953 BN_CONSTTIME_SWAP(8); /* Fallthrough */ 954 case 8: 955 BN_CONSTTIME_SWAP(7); /* Fallthrough */ 956 case 7: 957 BN_CONSTTIME_SWAP(6); /* Fallthrough */ 958 case 6: 959 BN_CONSTTIME_SWAP(5); /* Fallthrough */ 960 case 5: 961 BN_CONSTTIME_SWAP(4); /* Fallthrough */ 962 case 4: 963 BN_CONSTTIME_SWAP(3); /* Fallthrough */ 964 case 3: 965 BN_CONSTTIME_SWAP(2); /* Fallthrough */ 966 case 2: 967 BN_CONSTTIME_SWAP(1); /* Fallthrough */ 968 case 1: 969 BN_CONSTTIME_SWAP(0); 970 } 971#undef BN_CONSTTIME_SWAP 972} 973