1 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay (at) 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 (at) 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 (at) 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 (at) 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 (at) 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 (at) cryptsoft.com). This product includes software written by Tim 107 * Hudson (tjh (at) cryptsoft.com). */ 108 109 #include <openssl/bn.h> 110 111 #include <assert.h> 112 113 #include <openssl/err.h> 114 115 #include "internal.h" 116 117 static BIGNUM *euclid(BIGNUM *a, BIGNUM *b) { 118 BIGNUM *t; 119 int shifts = 0; 120 121 /* 0 <= b <= a */ 122 while (!BN_is_zero(b)) { 123 /* 0 < b <= a */ 124 125 if (BN_is_odd(a)) { 126 if (BN_is_odd(b)) { 127 if (!BN_sub(a, a, b)) { 128 goto err; 129 } 130 if (!BN_rshift1(a, a)) { 131 goto err; 132 } 133 if (BN_cmp(a, b) < 0) { 134 t = a; 135 a = b; 136 b = t; 137 } 138 } else { 139 /* a odd - b even */ 140 if (!BN_rshift1(b, b)) { 141 goto err; 142 } 143 if (BN_cmp(a, b) < 0) { 144 t = a; 145 a = b; 146 b = t; 147 } 148 } 149 } else { 150 /* a is even */ 151 if (BN_is_odd(b)) { 152 if (!BN_rshift1(a, a)) { 153 goto err; 154 } 155 if (BN_cmp(a, b) < 0) { 156 t = a; 157 a = b; 158 b = t; 159 } 160 } else { 161 /* a even - b even */ 162 if (!BN_rshift1(a, a)) { 163 goto err; 164 } 165 if (!BN_rshift1(b, b)) { 166 goto err; 167 } 168 shifts++; 169 } 170 } 171 /* 0 <= b <= a */ 172 } 173 174 if (shifts) { 175 if (!BN_lshift(a, a, shifts)) { 176 goto err; 177 } 178 } 179 180 return a; 181 182 err: 183 return NULL; 184 } 185 186 int BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) { 187 BIGNUM *a, *b, *t; 188 int ret = 0; 189 190 BN_CTX_start(ctx); 191 a = BN_CTX_get(ctx); 192 b = BN_CTX_get(ctx); 193 194 if (a == NULL || b == NULL) { 195 goto err; 196 } 197 if (BN_copy(a, in_a) == NULL) { 198 goto err; 199 } 200 if (BN_copy(b, in_b) == NULL) { 201 goto err; 202 } 203 204 a->neg = 0; 205 b->neg = 0; 206 207 if (BN_cmp(a, b) < 0) { 208 t = a; 209 a = b; 210 b = t; 211 } 212 t = euclid(a, b); 213 if (t == NULL) { 214 goto err; 215 } 216 217 if (BN_copy(r, t) == NULL) { 218 goto err; 219 } 220 ret = 1; 221 222 err: 223 BN_CTX_end(ctx); 224 return ret; 225 } 226 227 /* solves ax == 1 (mod n) */ 228 static int bn_mod_inverse_general(BIGNUM *out, int *out_no_inverse, 229 const BIGNUM *a, const BIGNUM *n, 230 BN_CTX *ctx); 231 232 int BN_mod_inverse_odd(BIGNUM *out, int *out_no_inverse, const BIGNUM *a, 233 const BIGNUM *n, BN_CTX *ctx) { 234 *out_no_inverse = 0; 235 236 if (!BN_is_odd(n)) { 237 OPENSSL_PUT_ERROR(BN, BN_R_CALLED_WITH_EVEN_MODULUS); 238 return 0; 239 } 240 241 if (BN_is_negative(a) || BN_cmp(a, n) >= 0) { 242 OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED); 243 return 0; 244 } 245 246 BIGNUM *A, *B, *X, *Y; 247 int ret = 0; 248 int sign; 249 250 BN_CTX_start(ctx); 251 A = BN_CTX_get(ctx); 252 B = BN_CTX_get(ctx); 253 X = BN_CTX_get(ctx); 254 Y = BN_CTX_get(ctx); 255 if (Y == NULL) { 256 goto err; 257 } 258 259 BIGNUM *R = out; 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 sign = -1; 267 /* From B = a mod |n|, A = |n| it follows that 268 * 269 * 0 <= B < A, 270 * -sign*X*a == B (mod |n|), 271 * sign*Y*a == A (mod |n|). 272 */ 273 274 /* Binary inversion algorithm; requires odd modulus. This is faster than the 275 * general algorithm if the modulus is sufficiently small (about 400 .. 500 276 * bits on 32-bit systems, but much more on 64-bit systems) */ 277 int shift; 278 279 while (!BN_is_zero(B)) { 280 /* 0 < B < |n|, 281 * 0 < A <= |n|, 282 * (1) -sign*X*a == B (mod |n|), 283 * (2) sign*Y*a == A (mod |n|) */ 284 285 /* Now divide B by the maximum possible power of two in the integers, 286 * and divide X by the same value mod |n|. 287 * When we're done, (1) still holds. */ 288 shift = 0; 289 while (!BN_is_bit_set(B, shift)) { 290 /* note that 0 < B */ 291 shift++; 292 293 if (BN_is_odd(X)) { 294 if (!BN_uadd(X, X, n)) { 295 goto err; 296 } 297 } 298 /* now X is even, so we can easily divide it by two */ 299 if (!BN_rshift1(X, X)) { 300 goto err; 301 } 302 } 303 if (shift > 0) { 304 if (!BN_rshift(B, B, shift)) { 305 goto err; 306 } 307 } 308 309 /* Same for A and Y. Afterwards, (2) still holds. */ 310 shift = 0; 311 while (!BN_is_bit_set(A, shift)) { 312 /* note that 0 < A */ 313 shift++; 314 315 if (BN_is_odd(Y)) { 316 if (!BN_uadd(Y, Y, n)) { 317 goto err; 318 } 319 } 320 /* now Y is even */ 321 if (!BN_rshift1(Y, Y)) { 322 goto err; 323 } 324 } 325 if (shift > 0) { 326 if (!BN_rshift(A, A, shift)) { 327 goto err; 328 } 329 } 330 331 /* We still have (1) and (2). 332 * Both A and B are odd. 333 * The following computations ensure that 334 * 335 * 0 <= B < |n|, 336 * 0 < A < |n|, 337 * (1) -sign*X*a == B (mod |n|), 338 * (2) sign*Y*a == A (mod |n|), 339 * 340 * and that either A or B is even in the next iteration. */ 341 if (BN_ucmp(B, A) >= 0) { 342 /* -sign*(X + Y)*a == B - A (mod |n|) */ 343 if (!BN_uadd(X, X, Y)) { 344 goto err; 345 } 346 /* NB: we could use BN_mod_add_quick(X, X, Y, n), but that 347 * actually makes the algorithm slower */ 348 if (!BN_usub(B, B, A)) { 349 goto err; 350 } 351 } else { 352 /* sign*(X + Y)*a == A - B (mod |n|) */ 353 if (!BN_uadd(Y, Y, X)) { 354 goto err; 355 } 356 /* as above, BN_mod_add_quick(Y, Y, X, n) would slow things down */ 357 if (!BN_usub(A, A, B)) { 358 goto err; 359 } 360 } 361 } 362 363 if (!BN_is_one(A)) { 364 *out_no_inverse = 1; 365 OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE); 366 goto err; 367 } 368 369 /* The while loop (Euclid's algorithm) ends when 370 * A == gcd(a,n); 371 * we have 372 * sign*Y*a == A (mod |n|), 373 * where Y is non-negative. */ 374 375 if (sign < 0) { 376 if (!BN_sub(Y, n, Y)) { 377 goto err; 378 } 379 } 380 /* Now Y*a == A (mod |n|). */ 381 382 /* Y*a == 1 (mod |n|) */ 383 if (!Y->neg && BN_ucmp(Y, n) < 0) { 384 if (!BN_copy(R, Y)) { 385 goto err; 386 } 387 } else { 388 if (!BN_nnmod(R, Y, n, ctx)) { 389 goto err; 390 } 391 } 392 393 ret = 1; 394 395 err: 396 BN_CTX_end(ctx); 397 return ret; 398 } 399 400 BIGNUM *BN_mod_inverse(BIGNUM *out, const BIGNUM *a, const BIGNUM *n, 401 BN_CTX *ctx) { 402 BIGNUM *new_out = NULL; 403 if (out == NULL) { 404 new_out = BN_new(); 405 if (new_out == NULL) { 406 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE); 407 return NULL; 408 } 409 out = new_out; 410 } 411 412 int ok = 0; 413 BIGNUM *a_reduced = NULL; 414 if (a->neg || BN_ucmp(a, n) >= 0) { 415 a_reduced = BN_dup(a); 416 if (a_reduced == NULL) { 417 goto err; 418 } 419 if (!BN_nnmod(a_reduced, a_reduced, n, ctx)) { 420 goto err; 421 } 422 a = a_reduced; 423 } 424 425 int no_inverse; 426 if (!BN_is_odd(n)) { 427 if (!bn_mod_inverse_general(out, &no_inverse, a, n, ctx)) { 428 goto err; 429 } 430 } else if (!BN_mod_inverse_odd(out, &no_inverse, a, n, ctx)) { 431 goto err; 432 } 433 434 ok = 1; 435 436 err: 437 if (!ok) { 438 BN_free(new_out); 439 out = NULL; 440 } 441 BN_free(a_reduced); 442 return out; 443 } 444 445 int BN_mod_inverse_blinded(BIGNUM *out, int *out_no_inverse, const BIGNUM *a, 446 const BN_MONT_CTX *mont, BN_CTX *ctx) { 447 *out_no_inverse = 0; 448 449 if (BN_is_negative(a) || BN_cmp(a, &mont->N) >= 0) { 450 OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED); 451 return 0; 452 } 453 454 int ret = 0; 455 BIGNUM blinding_factor; 456 BN_init(&blinding_factor); 457 458 if (!BN_rand_range_ex(&blinding_factor, 1, &mont->N) || 459 !BN_mod_mul_montgomery(out, &blinding_factor, a, mont, ctx) || 460 !BN_mod_inverse_odd(out, out_no_inverse, out, &mont->N, ctx) || 461 !BN_mod_mul_montgomery(out, &blinding_factor, out, mont, ctx)) { 462 OPENSSL_PUT_ERROR(BN, ERR_R_BN_LIB); 463 goto err; 464 } 465 466 ret = 1; 467 468 err: 469 BN_free(&blinding_factor); 470 return ret; 471 } 472 473 /* bn_mod_inverse_general is the general inversion algorithm that works for 474 * both even and odd |n|. It was specifically designed to contain fewer 475 * branches that may leak sensitive information; see "New Branch Prediction 476 * Vulnerabilities in OpenSSL and Necessary Software Countermeasures" by 477 * Onur Acmez, Shay Gueron, and Jean-Pierre Seifert. */ 478 static int bn_mod_inverse_general(BIGNUM *out, int *out_no_inverse, 479 const BIGNUM *a, const BIGNUM *n, 480 BN_CTX *ctx) { 481 BIGNUM *A, *B, *X, *Y, *M, *D, *T; 482 int ret = 0; 483 int sign; 484 485 *out_no_inverse = 0; 486 487 BN_CTX_start(ctx); 488 A = BN_CTX_get(ctx); 489 B = BN_CTX_get(ctx); 490 X = BN_CTX_get(ctx); 491 D = BN_CTX_get(ctx); 492 M = BN_CTX_get(ctx); 493 Y = BN_CTX_get(ctx); 494 T = BN_CTX_get(ctx); 495 if (T == NULL) { 496 goto err; 497 } 498 499 BIGNUM *R = out; 500 501 BN_zero(Y); 502 if (!BN_one(X) || BN_copy(B, a) == NULL || BN_copy(A, n) == NULL) { 503 goto err; 504 } 505 A->neg = 0; 506 507 sign = -1; 508 /* From B = a mod |n|, A = |n| it follows that 509 * 510 * 0 <= B < A, 511 * -sign*X*a == B (mod |n|), 512 * sign*Y*a == A (mod |n|). 513 */ 514 515 while (!BN_is_zero(B)) { 516 BIGNUM *tmp; 517 518 /* 519 * 0 < B < A, 520 * (*) -sign*X*a == B (mod |n|), 521 * sign*Y*a == A (mod |n|) 522 */ 523 524 /* (D, M) := (A/B, A%B) ... */ 525 if (!BN_div(D, M, A, B, ctx)) { 526 goto err; 527 } 528 529 /* Now 530 * A = D*B + M; 531 * thus we have 532 * (**) sign*Y*a == D*B + M (mod |n|). 533 */ 534 535 tmp = A; /* keep the BIGNUM object, the value does not matter */ 536 537 /* (A, B) := (B, A mod B) ... */ 538 A = B; 539 B = M; 540 /* ... so we have 0 <= B < A again */ 541 542 /* Since the former M is now B and the former B is now A, 543 * (**) translates into 544 * sign*Y*a == D*A + B (mod |n|), 545 * i.e. 546 * sign*Y*a - D*A == B (mod |n|). 547 * Similarly, (*) translates into 548 * -sign*X*a == A (mod |n|). 549 * 550 * Thus, 551 * sign*Y*a + D*sign*X*a == B (mod |n|), 552 * i.e. 553 * sign*(Y + D*X)*a == B (mod |n|). 554 * 555 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at 556 * -sign*X*a == B (mod |n|), 557 * sign*Y*a == A (mod |n|). 558 * Note that X and Y stay non-negative all the time. 559 */ 560 561 if (!BN_mul(tmp, D, X, ctx)) { 562 goto err; 563 } 564 if (!BN_add(tmp, tmp, Y)) { 565 goto err; 566 } 567 568 M = Y; /* keep the BIGNUM object, the value does not matter */ 569 Y = X; 570 X = tmp; 571 sign = -sign; 572 } 573 574 if (!BN_is_one(A)) { 575 *out_no_inverse = 1; 576 OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE); 577 goto err; 578 } 579 580 /* 581 * The while loop (Euclid's algorithm) ends when 582 * A == gcd(a,n); 583 * we have 584 * sign*Y*a == A (mod |n|), 585 * where Y is non-negative. 586 */ 587 588 if (sign < 0) { 589 if (!BN_sub(Y, n, Y)) { 590 goto err; 591 } 592 } 593 /* Now Y*a == A (mod |n|). */ 594 595 /* Y*a == 1 (mod |n|) */ 596 if (!Y->neg && BN_ucmp(Y, n) < 0) { 597 if (!BN_copy(R, Y)) { 598 goto err; 599 } 600 } else { 601 if (!BN_nnmod(R, Y, n, ctx)) { 602 goto err; 603 } 604 } 605 606 ret = 1; 607 608 err: 609 BN_CTX_end(ctx); 610 return ret; 611 } 612 613 int bn_mod_inverse_prime(BIGNUM *out, const BIGNUM *a, const BIGNUM *p, 614 BN_CTX *ctx, const BN_MONT_CTX *mont_p) { 615 BN_CTX_start(ctx); 616 BIGNUM *p_minus_2 = BN_CTX_get(ctx); 617 int ok = p_minus_2 != NULL && 618 BN_copy(p_minus_2, p) && 619 BN_sub_word(p_minus_2, 2) && 620 BN_mod_exp_mont(out, a, p_minus_2, p, ctx, mont_p); 621 BN_CTX_end(ctx); 622 return ok; 623 } 624 625 int bn_mod_inverse_secret_prime(BIGNUM *out, const BIGNUM *a, const BIGNUM *p, 626 BN_CTX *ctx, const BN_MONT_CTX *mont_p) { 627 BN_CTX_start(ctx); 628 BIGNUM *p_minus_2 = BN_CTX_get(ctx); 629 int ok = p_minus_2 != NULL && 630 BN_copy(p_minus_2, p) && 631 BN_sub_word(p_minus_2, 2) && 632 BN_mod_exp_mont_consttime(out, a, p_minus_2, p, ctx, mont_p); 633 BN_CTX_end(ctx); 634 return ok; 635 } 636
