bn_lib.c revision 337982
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, inc, lasti, j; 621 BN_ULONG l; 622 623 n = BN_num_bytes(a); 624 if (tolen == -1) 625 tolen = n; 626 else if (tolen < n) 627 return -1; 628 629 if (n == 0) { 630 OPENSSL_cleanse(to, tolen); 631 return tolen; 632 } 633 634 lasti = n - 1; 635 for (i = 0, inc = 1, j = tolen; j > 0;) { 636 l = a->d[i / BN_BYTES]; 637 to[--j] = (unsigned char)(l >> (8 * (i % BN_BYTES)) & (0 - inc)); 638 inc = (i - lasti) >> (8 * sizeof(i) - 1); 639 i += inc; /* stay on top limb */ 640 } 641 642 return tolen; 643} 644 645int bn_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) 646{ 647 if (tolen < 0) 648 return -1; 649 return bn2binpad(a, to, tolen); 650} 651 652int BN_bn2bin(const BIGNUM *a, unsigned char *to) 653{ 654 int n, i; 655 BN_ULONG l; 656 657 bn_check_top(a); 658 n = i = BN_num_bytes(a); 659 while (i--) { 660 l = a->d[i / BN_BYTES]; 661 *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff; 662 } 663 return (n); 664} 665 666int BN_ucmp(const BIGNUM *a, const BIGNUM *b) 667{ 668 int i; 669 BN_ULONG t1, t2, *ap, *bp; 670 671 bn_check_top(a); 672 bn_check_top(b); 673 674 i = a->top - b->top; 675 if (i != 0) 676 return (i); 677 ap = a->d; 678 bp = b->d; 679 for (i = a->top - 1; i >= 0; i--) { 680 t1 = ap[i]; 681 t2 = bp[i]; 682 if (t1 != t2) 683 return ((t1 > t2) ? 1 : -1); 684 } 685 return (0); 686} 687 688int BN_cmp(const BIGNUM *a, const BIGNUM *b) 689{ 690 int i; 691 int gt, lt; 692 BN_ULONG t1, t2; 693 694 if ((a == NULL) || (b == NULL)) { 695 if (a != NULL) 696 return (-1); 697 else if (b != NULL) 698 return (1); 699 else 700 return (0); 701 } 702 703 bn_check_top(a); 704 bn_check_top(b); 705 706 if (a->neg != b->neg) { 707 if (a->neg) 708 return (-1); 709 else 710 return (1); 711 } 712 if (a->neg == 0) { 713 gt = 1; 714 lt = -1; 715 } else { 716 gt = -1; 717 lt = 1; 718 } 719 720 if (a->top > b->top) 721 return (gt); 722 if (a->top < b->top) 723 return (lt); 724 for (i = a->top - 1; i >= 0; i--) { 725 t1 = a->d[i]; 726 t2 = b->d[i]; 727 if (t1 > t2) 728 return (gt); 729 if (t1 < t2) 730 return (lt); 731 } 732 return (0); 733} 734 735int BN_set_bit(BIGNUM *a, int n) 736{ 737 int i, j, k; 738 739 if (n < 0) 740 return 0; 741 742 i = n / BN_BITS2; 743 j = n % BN_BITS2; 744 if (a->top <= i) { 745 if (bn_wexpand(a, i + 1) == NULL) 746 return (0); 747 for (k = a->top; k < i + 1; k++) 748 a->d[k] = 0; 749 a->top = i + 1; 750 a->flags &= ~BN_FLG_FIXED_TOP; 751 } 752 753 a->d[i] |= (((BN_ULONG)1) << j); 754 bn_check_top(a); 755 return (1); 756} 757 758int BN_clear_bit(BIGNUM *a, int n) 759{ 760 int i, j; 761 762 bn_check_top(a); 763 if (n < 0) 764 return 0; 765 766 i = n / BN_BITS2; 767 j = n % BN_BITS2; 768 if (a->top <= i) 769 return (0); 770 771 a->d[i] &= (~(((BN_ULONG)1) << j)); 772 bn_correct_top(a); 773 return (1); 774} 775 776int BN_is_bit_set(const BIGNUM *a, int n) 777{ 778 int i, j; 779 780 bn_check_top(a); 781 if (n < 0) 782 return 0; 783 i = n / BN_BITS2; 784 j = n % BN_BITS2; 785 if (a->top <= i) 786 return 0; 787 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); 788} 789 790int BN_mask_bits(BIGNUM *a, int n) 791{ 792 int b, w; 793 794 bn_check_top(a); 795 if (n < 0) 796 return 0; 797 798 w = n / BN_BITS2; 799 b = n % BN_BITS2; 800 if (w >= a->top) 801 return 0; 802 if (b == 0) 803 a->top = w; 804 else { 805 a->top = w + 1; 806 a->d[w] &= ~(BN_MASK2 << b); 807 } 808 bn_correct_top(a); 809 return (1); 810} 811 812void BN_set_negative(BIGNUM *a, int b) 813{ 814 if (b && !BN_is_zero(a)) 815 a->neg = 1; 816 else 817 a->neg = 0; 818} 819 820int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) 821{ 822 int i; 823 BN_ULONG aa, bb; 824 825 aa = a[n - 1]; 826 bb = b[n - 1]; 827 if (aa != bb) 828 return ((aa > bb) ? 1 : -1); 829 for (i = n - 2; i >= 0; i--) { 830 aa = a[i]; 831 bb = b[i]; 832 if (aa != bb) 833 return ((aa > bb) ? 1 : -1); 834 } 835 return (0); 836} 837 838/* 839 * Here follows a specialised variants of bn_cmp_words(). It has the 840 * property of performing the operation on arrays of different sizes. The 841 * sizes of those arrays is expressed through cl, which is the common length 842 * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the 843 * two lengths, calculated as len(a)-len(b). All lengths are the number of 844 * BN_ULONGs... 845 */ 846 847int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) 848{ 849 int n, i; 850 n = cl - 1; 851 852 if (dl < 0) { 853 for (i = dl; i < 0; i++) { 854 if (b[n - i] != 0) 855 return -1; /* a < b */ 856 } 857 } 858 if (dl > 0) { 859 for (i = dl; i > 0; i--) { 860 if (a[n + i] != 0) 861 return 1; /* a > b */ 862 } 863 } 864 return bn_cmp_words(a, b, cl); 865} 866 867/* 868 * Constant-time conditional swap of a and b. 869 * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set. 870 * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b, 871 * and that no more than nwords are used by either a or b. 872 * a and b cannot be the same number 873 */ 874void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) 875{ 876 BN_ULONG t; 877 int i; 878 879 bn_wcheck_size(a, nwords); 880 bn_wcheck_size(b, nwords); 881 882 assert(a != b); 883 assert((condition & (condition - 1)) == 0); 884 assert(sizeof(BN_ULONG) >= sizeof(int)); 885 886 condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1; 887 888 t = (a->top ^ b->top) & condition; 889 a->top ^= t; 890 b->top ^= t; 891 892#define BN_CONSTTIME_SWAP(ind) \ 893 do { \ 894 t = (a->d[ind] ^ b->d[ind]) & condition; \ 895 a->d[ind] ^= t; \ 896 b->d[ind] ^= t; \ 897 } while (0) 898 899 switch (nwords) { 900 default: 901 for (i = 10; i < nwords; i++) 902 BN_CONSTTIME_SWAP(i); 903 /* Fallthrough */ 904 case 10: 905 BN_CONSTTIME_SWAP(9); /* Fallthrough */ 906 case 9: 907 BN_CONSTTIME_SWAP(8); /* Fallthrough */ 908 case 8: 909 BN_CONSTTIME_SWAP(7); /* Fallthrough */ 910 case 7: 911 BN_CONSTTIME_SWAP(6); /* Fallthrough */ 912 case 6: 913 BN_CONSTTIME_SWAP(5); /* Fallthrough */ 914 case 5: 915 BN_CONSTTIME_SWAP(4); /* Fallthrough */ 916 case 4: 917 BN_CONSTTIME_SWAP(3); /* Fallthrough */ 918 case 3: 919 BN_CONSTTIME_SWAP(2); /* Fallthrough */ 920 case 2: 921 BN_CONSTTIME_SWAP(1); /* Fallthrough */ 922 case 1: 923 BN_CONSTTIME_SWAP(0); 924 } 925#undef BN_CONSTTIME_SWAP 926} 927