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