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 // Binary inversion algorithm; requires odd modulus. This is faster than the 274 // general algorithm if the modulus is sufficiently small (about 400 .. 500 275 // bits on 32-bit systems, but much more on 64-bit systems) 276 int shift; 277 278 while (!BN_is_zero(B)) { 279 // 0 < B < |n|, 280 // 0 < A <= |n|, 281 // (1) -sign*X*a == B (mod |n|), 282 // (2) sign*Y*a == A (mod |n|) 283 284 // Now divide B by the maximum possible power of two in the integers, 285 // and divide X by the same value mod |n|. 286 // When we're done, (1) still holds. 287 shift = 0; 288 while (!BN_is_bit_set(B, shift)) { 289 // note that 0 < B 290 shift++; 291 292 if (BN_is_odd(X)) { 293 if (!BN_uadd(X, X, n)) { 294 goto err; 295 } 296 } 297 // now X is even, so we can easily divide it by two 298 if (!BN_rshift1(X, X)) { 299 goto err; 300 } 301 } 302 if (shift > 0) { 303 if (!BN_rshift(B, B, shift)) { 304 goto err; 305 } 306 } 307 308 // Same for A and Y. Afterwards, (2) still holds. 309 shift = 0; 310 while (!BN_is_bit_set(A, shift)) { 311 // note that 0 < A 312 shift++; 313 314 if (BN_is_odd(Y)) { 315 if (!BN_uadd(Y, Y, n)) { 316 goto err; 317 } 318 } 319 // now Y is even 320 if (!BN_rshift1(Y, Y)) { 321 goto err; 322 } 323 } 324 if (shift > 0) { 325 if (!BN_rshift(A, A, shift)) { 326 goto err; 327 } 328 } 329 330 // We still have (1) and (2). 331 // Both A and B are odd. 332 // The following computations ensure that 333 // 334 // 0 <= B < |n|, 335 // 0 < A < |n|, 336 // (1) -sign*X*a == B (mod |n|), 337 // (2) sign*Y*a == A (mod |n|), 338 // 339 // and that either A or B is even in the next iteration. 340 if (BN_ucmp(B, A) >= 0) { 341 // -sign*(X + Y)*a == B - A (mod |n|) 342 if (!BN_uadd(X, X, Y)) { 343 goto err; 344 } 345 // NB: we could use BN_mod_add_quick(X, X, Y, n), but that 346 // actually makes the algorithm slower 347 if (!BN_usub(B, B, A)) { 348 goto err; 349 } 350 } else { 351 // sign*(X + Y)*a == A - B (mod |n|) 352 if (!BN_uadd(Y, Y, X)) { 353 goto err; 354 } 355 // as above, BN_mod_add_quick(Y, Y, X, n) would slow things down 356 if (!BN_usub(A, A, B)) { 357 goto err; 358 } 359 } 360 } 361 362 if (!BN_is_one(A)) { 363 *out_no_inverse = 1; 364 OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE); 365 goto err; 366 } 367 368 // The while loop (Euclid's algorithm) ends when 369 // A == gcd(a,n); 370 // we have 371 // sign*Y*a == A (mod |n|), 372 // where Y is non-negative. 373 374 if (sign < 0) { 375 if (!BN_sub(Y, n, Y)) { 376 goto err; 377 } 378 } 379 // Now Y*a == A (mod |n|). 380 381 // Y*a == 1 (mod |n|) 382 if (!Y->neg && BN_ucmp(Y, n) < 0) { 383 if (!BN_copy(R, Y)) { 384 goto err; 385 } 386 } else { 387 if (!BN_nnmod(R, Y, n, ctx)) { 388 goto err; 389 } 390 } 391 392 ret = 1; 393 394 err: 395 BN_CTX_end(ctx); 396 return ret; 397 } 398 399 BIGNUM *BN_mod_inverse(BIGNUM *out, const BIGNUM *a, const BIGNUM *n, 400 BN_CTX *ctx) { 401 BIGNUM *new_out = NULL; 402 if (out == NULL) { 403 new_out = BN_new(); 404 if (new_out == NULL) { 405 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE); 406 return NULL; 407 } 408 out = new_out; 409 } 410 411 int ok = 0; 412 BIGNUM *a_reduced = NULL; 413 if (a->neg || BN_ucmp(a, n) >= 0) { 414 a_reduced = BN_dup(a); 415 if (a_reduced == NULL) { 416 goto err; 417 } 418 if (!BN_nnmod(a_reduced, a_reduced, n, ctx)) { 419 goto err; 420 } 421 a = a_reduced; 422 } 423 424 int no_inverse; 425 if (!BN_is_odd(n)) { 426 if (!bn_mod_inverse_general(out, &no_inverse, a, n, ctx)) { 427 goto err; 428 } 429 } else if (!BN_mod_inverse_odd(out, &no_inverse, a, n, ctx)) { 430 goto err; 431 } 432 433 ok = 1; 434 435 err: 436 if (!ok) { 437 BN_free(new_out); 438 out = NULL; 439 } 440 BN_free(a_reduced); 441 return out; 442 } 443 444 int BN_mod_inverse_blinded(BIGNUM *out, int *out_no_inverse, const BIGNUM *a, 445 const BN_MONT_CTX *mont, BN_CTX *ctx) { 446 *out_no_inverse = 0; 447 448 if (BN_is_negative(a) || BN_cmp(a, &mont->N) >= 0) { 449 OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED); 450 return 0; 451 } 452 453 int ret = 0; 454 BIGNUM blinding_factor; 455 BN_init(&blinding_factor); 456 457 if (!BN_rand_range_ex(&blinding_factor, 1, &mont->N) || 458 !BN_mod_mul_montgomery(out, &blinding_factor, a, mont, ctx) || 459 !BN_mod_inverse_odd(out, out_no_inverse, out, &mont->N, ctx) || 460 !BN_mod_mul_montgomery(out, &blinding_factor, out, mont, ctx)) { 461 OPENSSL_PUT_ERROR(BN, ERR_R_BN_LIB); 462 goto err; 463 } 464 465 ret = 1; 466 467 err: 468 BN_free(&blinding_factor); 469 return ret; 470 } 471 472 // bn_mod_inverse_general is the general inversion algorithm that works for 473 // both even and odd |n|. It was specifically designed to contain fewer 474 // branches that may leak sensitive information; see "New Branch Prediction 475 // Vulnerabilities in OpenSSL and Necessary Software Countermeasures" by 476 // Onur Acmez, Shay Gueron, and Jean-Pierre Seifert. 477 static int bn_mod_inverse_general(BIGNUM *out, int *out_no_inverse, 478 const BIGNUM *a, const BIGNUM *n, 479 BN_CTX *ctx) { 480 BIGNUM *A, *B, *X, *Y, *M, *D, *T; 481 int ret = 0; 482 int sign; 483 484 *out_no_inverse = 0; 485 486 BN_CTX_start(ctx); 487 A = BN_CTX_get(ctx); 488 B = BN_CTX_get(ctx); 489 X = BN_CTX_get(ctx); 490 D = BN_CTX_get(ctx); 491 M = BN_CTX_get(ctx); 492 Y = BN_CTX_get(ctx); 493 T = BN_CTX_get(ctx); 494 if (T == NULL) { 495 goto err; 496 } 497 498 BIGNUM *R = out; 499 500 BN_zero(Y); 501 if (!BN_one(X) || BN_copy(B, a) == NULL || BN_copy(A, n) == NULL) { 502 goto err; 503 } 504 A->neg = 0; 505 506 sign = -1; 507 // From B = a mod |n|, A = |n| it follows that 508 // 509 // 0 <= B < A, 510 // -sign*X*a == B (mod |n|), 511 // sign*Y*a == A (mod |n|). 512 513 while (!BN_is_zero(B)) { 514 BIGNUM *tmp; 515 516 // 0 < B < A, 517 // (*) -sign*X*a == B (mod |n|), 518 // sign*Y*a == A (mod |n|) 519 520 // (D, M) := (A/B, A%B) ... 521 if (!BN_div(D, M, A, B, ctx)) { 522 goto err; 523 } 524 525 // Now 526 // A = D*B + M; 527 // thus we have 528 // (**) sign*Y*a == D*B + M (mod |n|). 529 530 tmp = A; // keep the BIGNUM object, the value does not matter 531 532 // (A, B) := (B, A mod B) ... 533 A = B; 534 B = M; 535 // ... so we have 0 <= B < A again 536 537 // Since the former M is now B and the former B is now A, 538 // (**) translates into 539 // sign*Y*a == D*A + B (mod |n|), 540 // i.e. 541 // sign*Y*a - D*A == B (mod |n|). 542 // Similarly, (*) translates into 543 // -sign*X*a == A (mod |n|). 544 // 545 // Thus, 546 // sign*Y*a + D*sign*X*a == B (mod |n|), 547 // i.e. 548 // sign*(Y + D*X)*a == B (mod |n|). 549 // 550 // So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at 551 // -sign*X*a == B (mod |n|), 552 // sign*Y*a == A (mod |n|). 553 // Note that X and Y stay non-negative all the time. 554 555 if (!BN_mul(tmp, D, X, ctx)) { 556 goto err; 557 } 558 if (!BN_add(tmp, tmp, Y)) { 559 goto err; 560 } 561 562 M = Y; // keep the BIGNUM object, the value does not matter 563 Y = X; 564 X = tmp; 565 sign = -sign; 566 } 567 568 if (!BN_is_one(A)) { 569 *out_no_inverse = 1; 570 OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE); 571 goto err; 572 } 573 574 // The while loop (Euclid's algorithm) ends when 575 // A == gcd(a,n); 576 // we have 577 // sign*Y*a == A (mod |n|), 578 // where Y is non-negative. 579 580 if (sign < 0) { 581 if (!BN_sub(Y, n, Y)) { 582 goto err; 583 } 584 } 585 // Now Y*a == A (mod |n|). 586 587 // Y*a == 1 (mod |n|) 588 if (!Y->neg && BN_ucmp(Y, n) < 0) { 589 if (!BN_copy(R, Y)) { 590 goto err; 591 } 592 } else { 593 if (!BN_nnmod(R, Y, n, ctx)) { 594 goto err; 595 } 596 } 597 598 ret = 1; 599 600 err: 601 BN_CTX_end(ctx); 602 return ret; 603 } 604 605 int bn_mod_inverse_prime(BIGNUM *out, const BIGNUM *a, const BIGNUM *p, 606 BN_CTX *ctx, const BN_MONT_CTX *mont_p) { 607 BN_CTX_start(ctx); 608 BIGNUM *p_minus_2 = BN_CTX_get(ctx); 609 int ok = p_minus_2 != NULL && 610 BN_copy(p_minus_2, p) && 611 BN_sub_word(p_minus_2, 2) && 612 BN_mod_exp_mont(out, a, p_minus_2, p, ctx, mont_p); 613 BN_CTX_end(ctx); 614 return ok; 615 } 616 617 int bn_mod_inverse_secret_prime(BIGNUM *out, const BIGNUM *a, const BIGNUM *p, 618 BN_CTX *ctx, const BN_MONT_CTX *mont_p) { 619 BN_CTX_start(ctx); 620 BIGNUM *p_minus_2 = BN_CTX_get(ctx); 621 int ok = p_minus_2 != NULL && 622 BN_copy(p_minus_2, p) && 623 BN_sub_word(p_minus_2, 2) && 624 BN_mod_exp_mont_consttime(out, a, p_minus_2, p, ctx, mont_p); 625 BN_CTX_end(ctx); 626 return ok; 627 } 628
