bn_gcd.c revision 296341
1/* crypto/bn/bn_gcd.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 * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. 60 * 61 * Redistribution and use in source and binary forms, with or without 62 * modification, are permitted provided that the following conditions 63 * are met: 64 * 65 * 1. Redistributions of source code must retain the above copyright 66 * notice, this list of conditions and the following disclaimer. 67 * 68 * 2. Redistributions in binary form must reproduce the above copyright 69 * notice, this list of conditions and the following disclaimer in 70 * the documentation and/or other materials provided with the 71 * distribution. 72 * 73 * 3. All advertising materials mentioning features or use of this 74 * software must display the following acknowledgment: 75 * "This product includes software developed by the OpenSSL Project 76 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 77 * 78 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 79 * endorse or promote products derived from this software without 80 * prior written permission. For written permission, please contact 81 * openssl-core@openssl.org. 82 * 83 * 5. Products derived from this software may not be called "OpenSSL" 84 * nor may "OpenSSL" appear in their names without prior written 85 * permission of the OpenSSL Project. 86 * 87 * 6. Redistributions of any form whatsoever must retain the following 88 * acknowledgment: 89 * "This product includes software developed by the OpenSSL Project 90 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 91 * 92 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 93 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 94 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 95 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 96 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 97 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 98 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 99 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 100 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 101 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 102 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 103 * OF THE POSSIBILITY OF SUCH DAMAGE. 104 * ==================================================================== 105 * 106 * This product includes cryptographic software written by Eric Young 107 * (eay@cryptsoft.com). This product includes software written by Tim 108 * Hudson (tjh@cryptsoft.com). 109 * 110 */ 111 112#include "cryptlib.h" 113#include "bn_lcl.h" 114 115static BIGNUM *euclid(BIGNUM *a, BIGNUM *b); 116 117int BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) 118{ 119 BIGNUM *a, *b, *t; 120 int ret = 0; 121 122 bn_check_top(in_a); 123 bn_check_top(in_b); 124 125 BN_CTX_start(ctx); 126 a = BN_CTX_get(ctx); 127 b = BN_CTX_get(ctx); 128 if (a == NULL || b == NULL) 129 goto err; 130 131 if (BN_copy(a, in_a) == NULL) 132 goto err; 133 if (BN_copy(b, in_b) == NULL) 134 goto err; 135 a->neg = 0; 136 b->neg = 0; 137 138 if (BN_cmp(a, b) < 0) { 139 t = a; 140 a = b; 141 b = t; 142 } 143 t = euclid(a, b); 144 if (t == NULL) 145 goto err; 146 147 if (BN_copy(r, t) == NULL) 148 goto err; 149 ret = 1; 150 err: 151 BN_CTX_end(ctx); 152 bn_check_top(r); 153 return (ret); 154} 155 156static BIGNUM *euclid(BIGNUM *a, BIGNUM *b) 157{ 158 BIGNUM *t; 159 int shifts = 0; 160 161 bn_check_top(a); 162 bn_check_top(b); 163 164 /* 0 <= b <= a */ 165 while (!BN_is_zero(b)) { 166 /* 0 < b <= a */ 167 168 if (BN_is_odd(a)) { 169 if (BN_is_odd(b)) { 170 if (!BN_sub(a, a, b)) 171 goto err; 172 if (!BN_rshift1(a, a)) 173 goto err; 174 if (BN_cmp(a, b) < 0) { 175 t = a; 176 a = b; 177 b = t; 178 } 179 } else { /* a odd - b even */ 180 181 if (!BN_rshift1(b, b)) 182 goto err; 183 if (BN_cmp(a, b) < 0) { 184 t = a; 185 a = b; 186 b = t; 187 } 188 } 189 } else { /* a is even */ 190 191 if (BN_is_odd(b)) { 192 if (!BN_rshift1(a, a)) 193 goto err; 194 if (BN_cmp(a, b) < 0) { 195 t = a; 196 a = b; 197 b = t; 198 } 199 } else { /* a even - b even */ 200 201 if (!BN_rshift1(a, a)) 202 goto err; 203 if (!BN_rshift1(b, b)) 204 goto err; 205 shifts++; 206 } 207 } 208 /* 0 <= b <= a */ 209 } 210 211 if (shifts) { 212 if (!BN_lshift(a, a, shifts)) 213 goto err; 214 } 215 bn_check_top(a); 216 return (a); 217 err: 218 return (NULL); 219} 220 221/* solves ax == 1 (mod n) */ 222static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, 223 const BIGNUM *a, const BIGNUM *n, 224 BN_CTX *ctx); 225 226BIGNUM *BN_mod_inverse(BIGNUM *in, 227 const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) 228{ 229 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL; 230 BIGNUM *ret = NULL; 231 int sign; 232 233 if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0) 234 || (BN_get_flags(n, BN_FLG_CONSTTIME) != 0)) { 235 return BN_mod_inverse_no_branch(in, a, n, ctx); 236 } 237 238 bn_check_top(a); 239 bn_check_top(n); 240 241 BN_CTX_start(ctx); 242 A = BN_CTX_get(ctx); 243 B = BN_CTX_get(ctx); 244 X = BN_CTX_get(ctx); 245 D = BN_CTX_get(ctx); 246 M = BN_CTX_get(ctx); 247 Y = BN_CTX_get(ctx); 248 T = BN_CTX_get(ctx); 249 if (T == NULL) 250 goto err; 251 252 if (in == NULL) 253 R = BN_new(); 254 else 255 R = in; 256 if (R == NULL) 257 goto err; 258 259 BN_one(X); 260 BN_zero(Y); 261 if (BN_copy(B, a) == NULL) 262 goto err; 263 if (BN_copy(A, n) == NULL) 264 goto err; 265 A->neg = 0; 266 if (B->neg || (BN_ucmp(B, A) >= 0)) { 267 if (!BN_nnmod(B, B, A, ctx)) 268 goto err; 269 } 270 sign = -1; 271 /*- 272 * From B = a mod |n|, A = |n| it follows that 273 * 274 * 0 <= B < A, 275 * -sign*X*a == B (mod |n|), 276 * sign*Y*a == A (mod |n|). 277 */ 278 279 if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048))) { 280 /* 281 * Binary inversion algorithm; requires odd modulus. This is faster 282 * than the general algorithm if the modulus is sufficiently small 283 * (about 400 .. 500 bits on 32-bit sytems, but much more on 64-bit 284 * systems) 285 */ 286 int shift; 287 288 while (!BN_is_zero(B)) { 289 /*- 290 * 0 < B < |n|, 291 * 0 < A <= |n|, 292 * (1) -sign*X*a == B (mod |n|), 293 * (2) sign*Y*a == A (mod |n|) 294 */ 295 296 /* 297 * Now divide B by the maximum possible power of two in the 298 * integers, and divide X by the same value mod |n|. When we're 299 * done, (1) still holds. 300 */ 301 shift = 0; 302 while (!BN_is_bit_set(B, shift)) { /* note that 0 < B */ 303 shift++; 304 305 if (BN_is_odd(X)) { 306 if (!BN_uadd(X, X, n)) 307 goto err; 308 } 309 /* 310 * now X is even, so we can easily divide it by two 311 */ 312 if (!BN_rshift1(X, X)) 313 goto err; 314 } 315 if (shift > 0) { 316 if (!BN_rshift(B, B, shift)) 317 goto err; 318 } 319 320 /* 321 * Same for A and Y. Afterwards, (2) still holds. 322 */ 323 shift = 0; 324 while (!BN_is_bit_set(A, shift)) { /* note that 0 < A */ 325 shift++; 326 327 if (BN_is_odd(Y)) { 328 if (!BN_uadd(Y, Y, n)) 329 goto err; 330 } 331 /* now Y is even */ 332 if (!BN_rshift1(Y, Y)) 333 goto err; 334 } 335 if (shift > 0) { 336 if (!BN_rshift(A, A, shift)) 337 goto err; 338 } 339 340 /*- 341 * We still have (1) and (2). 342 * Both A and B are odd. 343 * The following computations ensure that 344 * 345 * 0 <= B < |n|, 346 * 0 < A < |n|, 347 * (1) -sign*X*a == B (mod |n|), 348 * (2) sign*Y*a == A (mod |n|), 349 * 350 * and that either A or B is even in the next iteration. 351 */ 352 if (BN_ucmp(B, A) >= 0) { 353 /* -sign*(X + Y)*a == B - A (mod |n|) */ 354 if (!BN_uadd(X, X, Y)) 355 goto err; 356 /* 357 * NB: we could use BN_mod_add_quick(X, X, Y, n), but that 358 * actually makes the algorithm slower 359 */ 360 if (!BN_usub(B, B, A)) 361 goto err; 362 } else { 363 /* sign*(X + Y)*a == A - B (mod |n|) */ 364 if (!BN_uadd(Y, Y, X)) 365 goto err; 366 /* 367 * as above, BN_mod_add_quick(Y, Y, X, n) would slow things 368 * down 369 */ 370 if (!BN_usub(A, A, B)) 371 goto err; 372 } 373 } 374 } else { 375 /* general inversion algorithm */ 376 377 while (!BN_is_zero(B)) { 378 BIGNUM *tmp; 379 380 /*- 381 * 0 < B < A, 382 * (*) -sign*X*a == B (mod |n|), 383 * sign*Y*a == A (mod |n|) 384 */ 385 386 /* (D, M) := (A/B, A%B) ... */ 387 if (BN_num_bits(A) == BN_num_bits(B)) { 388 if (!BN_one(D)) 389 goto err; 390 if (!BN_sub(M, A, B)) 391 goto err; 392 } else if (BN_num_bits(A) == BN_num_bits(B) + 1) { 393 /* A/B is 1, 2, or 3 */ 394 if (!BN_lshift1(T, B)) 395 goto err; 396 if (BN_ucmp(A, T) < 0) { 397 /* A < 2*B, so D=1 */ 398 if (!BN_one(D)) 399 goto err; 400 if (!BN_sub(M, A, B)) 401 goto err; 402 } else { 403 /* A >= 2*B, so D=2 or D=3 */ 404 if (!BN_sub(M, A, T)) 405 goto err; 406 if (!BN_add(D, T, B)) 407 goto err; /* use D (:= 3*B) as temp */ 408 if (BN_ucmp(A, D) < 0) { 409 /* A < 3*B, so D=2 */ 410 if (!BN_set_word(D, 2)) 411 goto err; 412 /* 413 * M (= A - 2*B) already has the correct value 414 */ 415 } else { 416 /* only D=3 remains */ 417 if (!BN_set_word(D, 3)) 418 goto err; 419 /* 420 * currently M = A - 2*B, but we need M = A - 3*B 421 */ 422 if (!BN_sub(M, M, B)) 423 goto err; 424 } 425 } 426 } else { 427 if (!BN_div(D, M, A, B, ctx)) 428 goto err; 429 } 430 431 /*- 432 * Now 433 * A = D*B + M; 434 * thus we have 435 * (**) sign*Y*a == D*B + M (mod |n|). 436 */ 437 438 tmp = A; /* keep the BIGNUM object, the value does not 439 * matter */ 440 441 /* (A, B) := (B, A mod B) ... */ 442 A = B; 443 B = M; 444 /* ... so we have 0 <= B < A again */ 445 446 /*- 447 * Since the former M is now B and the former B is now A, 448 * (**) translates into 449 * sign*Y*a == D*A + B (mod |n|), 450 * i.e. 451 * sign*Y*a - D*A == B (mod |n|). 452 * Similarly, (*) translates into 453 * -sign*X*a == A (mod |n|). 454 * 455 * Thus, 456 * sign*Y*a + D*sign*X*a == B (mod |n|), 457 * i.e. 458 * sign*(Y + D*X)*a == B (mod |n|). 459 * 460 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at 461 * -sign*X*a == B (mod |n|), 462 * sign*Y*a == A (mod |n|). 463 * Note that X and Y stay non-negative all the time. 464 */ 465 466 /* 467 * most of the time D is very small, so we can optimize tmp := 468 * D*X+Y 469 */ 470 if (BN_is_one(D)) { 471 if (!BN_add(tmp, X, Y)) 472 goto err; 473 } else { 474 if (BN_is_word(D, 2)) { 475 if (!BN_lshift1(tmp, X)) 476 goto err; 477 } else if (BN_is_word(D, 4)) { 478 if (!BN_lshift(tmp, X, 2)) 479 goto err; 480 } else if (D->top == 1) { 481 if (!BN_copy(tmp, X)) 482 goto err; 483 if (!BN_mul_word(tmp, D->d[0])) 484 goto err; 485 } else { 486 if (!BN_mul(tmp, D, X, ctx)) 487 goto err; 488 } 489 if (!BN_add(tmp, tmp, Y)) 490 goto err; 491 } 492 493 M = Y; /* keep the BIGNUM object, the value does not 494 * matter */ 495 Y = X; 496 X = tmp; 497 sign = -sign; 498 } 499 } 500 501 /*- 502 * The while loop (Euclid's algorithm) ends when 503 * A == gcd(a,n); 504 * we have 505 * sign*Y*a == A (mod |n|), 506 * where Y is non-negative. 507 */ 508 509 if (sign < 0) { 510 if (!BN_sub(Y, n, Y)) 511 goto err; 512 } 513 /* Now Y*a == A (mod |n|). */ 514 515 if (BN_is_one(A)) { 516 /* Y*a == 1 (mod |n|) */ 517 if (!Y->neg && BN_ucmp(Y, n) < 0) { 518 if (!BN_copy(R, Y)) 519 goto err; 520 } else { 521 if (!BN_nnmod(R, Y, n, ctx)) 522 goto err; 523 } 524 } else { 525 BNerr(BN_F_BN_MOD_INVERSE, BN_R_NO_INVERSE); 526 goto err; 527 } 528 ret = R; 529 err: 530 if ((ret == NULL) && (in == NULL)) 531 BN_free(R); 532 BN_CTX_end(ctx); 533 bn_check_top(ret); 534 return (ret); 535} 536 537/* 538 * BN_mod_inverse_no_branch is a special version of BN_mod_inverse. It does 539 * not contain branches that may leak sensitive information. 540 */ 541static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, 542 const BIGNUM *a, const BIGNUM *n, 543 BN_CTX *ctx) 544{ 545 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL; 546 BIGNUM local_A, local_B; 547 BIGNUM *pA, *pB; 548 BIGNUM *ret = NULL; 549 int sign; 550 551 bn_check_top(a); 552 bn_check_top(n); 553 554 BN_CTX_start(ctx); 555 A = BN_CTX_get(ctx); 556 B = BN_CTX_get(ctx); 557 X = BN_CTX_get(ctx); 558 D = BN_CTX_get(ctx); 559 M = BN_CTX_get(ctx); 560 Y = BN_CTX_get(ctx); 561 T = BN_CTX_get(ctx); 562 if (T == NULL) 563 goto err; 564 565 if (in == NULL) 566 R = BN_new(); 567 else 568 R = in; 569 if (R == NULL) 570 goto err; 571 572 BN_one(X); 573 BN_zero(Y); 574 if (BN_copy(B, a) == NULL) 575 goto err; 576 if (BN_copy(A, n) == NULL) 577 goto err; 578 A->neg = 0; 579 580 if (B->neg || (BN_ucmp(B, A) >= 0)) { 581 /* 582 * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, 583 * BN_div_no_branch will be called eventually. 584 */ 585 pB = &local_B; 586 BN_with_flags(pB, B, BN_FLG_CONSTTIME); 587 if (!BN_nnmod(B, pB, A, ctx)) 588 goto err; 589 } 590 sign = -1; 591 /*- 592 * From B = a mod |n|, A = |n| it follows that 593 * 594 * 0 <= B < A, 595 * -sign*X*a == B (mod |n|), 596 * sign*Y*a == A (mod |n|). 597 */ 598 599 while (!BN_is_zero(B)) { 600 BIGNUM *tmp; 601 602 /*- 603 * 0 < B < A, 604 * (*) -sign*X*a == B (mod |n|), 605 * sign*Y*a == A (mod |n|) 606 */ 607 608 /* 609 * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, 610 * BN_div_no_branch will be called eventually. 611 */ 612 pA = &local_A; 613 BN_with_flags(pA, A, BN_FLG_CONSTTIME); 614 615 /* (D, M) := (A/B, A%B) ... */ 616 if (!BN_div(D, M, pA, B, ctx)) 617 goto err; 618 619 /*- 620 * Now 621 * A = D*B + M; 622 * thus we have 623 * (**) sign*Y*a == D*B + M (mod |n|). 624 */ 625 626 tmp = A; /* keep the BIGNUM object, the value does not 627 * matter */ 628 629 /* (A, B) := (B, A mod B) ... */ 630 A = B; 631 B = M; 632 /* ... so we have 0 <= B < A again */ 633 634 /*- 635 * Since the former M is now B and the former B is now A, 636 * (**) translates into 637 * sign*Y*a == D*A + B (mod |n|), 638 * i.e. 639 * sign*Y*a - D*A == B (mod |n|). 640 * Similarly, (*) translates into 641 * -sign*X*a == A (mod |n|). 642 * 643 * Thus, 644 * sign*Y*a + D*sign*X*a == B (mod |n|), 645 * i.e. 646 * sign*(Y + D*X)*a == B (mod |n|). 647 * 648 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at 649 * -sign*X*a == B (mod |n|), 650 * sign*Y*a == A (mod |n|). 651 * Note that X and Y stay non-negative all the time. 652 */ 653 654 if (!BN_mul(tmp, D, X, ctx)) 655 goto err; 656 if (!BN_add(tmp, tmp, Y)) 657 goto err; 658 659 M = Y; /* keep the BIGNUM object, the value does not 660 * matter */ 661 Y = X; 662 X = tmp; 663 sign = -sign; 664 } 665 666 /*- 667 * The while loop (Euclid's algorithm) ends when 668 * A == gcd(a,n); 669 * we have 670 * sign*Y*a == A (mod |n|), 671 * where Y is non-negative. 672 */ 673 674 if (sign < 0) { 675 if (!BN_sub(Y, n, Y)) 676 goto err; 677 } 678 /* Now Y*a == A (mod |n|). */ 679 680 if (BN_is_one(A)) { 681 /* Y*a == 1 (mod |n|) */ 682 if (!Y->neg && BN_ucmp(Y, n) < 0) { 683 if (!BN_copy(R, Y)) 684 goto err; 685 } else { 686 if (!BN_nnmod(R, Y, n, ctx)) 687 goto err; 688 } 689 } else { 690 BNerr(BN_F_BN_MOD_INVERSE_NO_BRANCH, BN_R_NO_INVERSE); 691 goto err; 692 } 693 ret = R; 694 err: 695 if ((ret == NULL) && (in == NULL)) 696 BN_free(R); 697 BN_CTX_end(ctx); 698 bn_check_top(ret); 699 return (ret); 700} 701