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-2005 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 <assert.h> 112 113#include <openssl/cpu.h> 114#include <openssl/err.h> 115#include <openssl/mem.h> 116 117#include "internal.h" 118 119 120#if !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86_64) 121#define OPENSSL_BN_ASM_MONT5 122#define RSAZ_ENABLED 123 124#include "rsaz_exp.h" 125#endif 126 127int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) { 128 int i, bits, ret = 0; 129 BIGNUM *v, *rr; 130 131 if ((p->flags & BN_FLG_CONSTTIME) != 0) { 132 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ 133 OPENSSL_PUT_ERROR(BN, BN_exp, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 134 return 0; 135 } 136 137 BN_CTX_start(ctx); 138 if (r == a || r == p) { 139 rr = BN_CTX_get(ctx); 140 } else { 141 rr = r; 142 } 143 144 v = BN_CTX_get(ctx); 145 if (rr == NULL || v == NULL) { 146 goto err; 147 } 148 149 if (BN_copy(v, a) == NULL) { 150 goto err; 151 } 152 bits = BN_num_bits(p); 153 154 if (BN_is_odd(p)) { 155 if (BN_copy(rr, a) == NULL) { 156 goto err; 157 } 158 } else { 159 if (!BN_one(rr)) { 160 goto err; 161 } 162 } 163 164 for (i = 1; i < bits; i++) { 165 if (!BN_sqr(v, v, ctx)) { 166 goto err; 167 } 168 if (BN_is_bit_set(p, i)) { 169 if (!BN_mul(rr, rr, v, ctx)) { 170 goto err; 171 } 172 } 173 } 174 ret = 1; 175 176err: 177 if (r != rr) { 178 BN_copy(r, rr); 179 } 180 BN_CTX_end(ctx); 181 return ret; 182} 183 184/* maximum precomputation table size for *variable* sliding windows */ 185#define TABLE_SIZE 32 186 187typedef struct bn_recp_ctx_st { 188 BIGNUM N; /* the divisor */ 189 BIGNUM Nr; /* the reciprocal */ 190 int num_bits; 191 int shift; 192 int flags; 193} BN_RECP_CTX; 194 195static void BN_RECP_CTX_init(BN_RECP_CTX *recp) { 196 BN_init(&recp->N); 197 BN_init(&recp->Nr); 198 recp->num_bits = 0; 199 recp->flags = 0; 200} 201 202static void BN_RECP_CTX_free(BN_RECP_CTX *recp) { 203 if (recp == NULL) { 204 return; 205 } 206 207 BN_free(&recp->N); 208 BN_free(&recp->Nr); 209} 210 211static int BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx) { 212 if (!BN_copy(&(recp->N), d)) { 213 return 0; 214 } 215 BN_zero(&recp->Nr); 216 recp->num_bits = BN_num_bits(d); 217 recp->shift = 0; 218 219 return 1; 220} 221 222/* len is the expected size of the result We actually calculate with an extra 223 * word of precision, so we can do faster division if the remainder is not 224 * required. 225 * r := 2^len / m */ 226static int BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx) { 227 int ret = -1; 228 BIGNUM *t; 229 230 BN_CTX_start(ctx); 231 t = BN_CTX_get(ctx); 232 if (t == NULL) { 233 goto err; 234 } 235 236 if (!BN_set_bit(t, len)) { 237 goto err; 238 } 239 240 if (!BN_div(r, NULL, t, m, ctx)) { 241 goto err; 242 } 243 244 ret = len; 245 246err: 247 BN_CTX_end(ctx); 248 return ret; 249} 250 251static int BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, 252 BN_RECP_CTX *recp, BN_CTX *ctx) { 253 int i, j, ret = 0; 254 BIGNUM *a, *b, *d, *r; 255 256 BN_CTX_start(ctx); 257 a = BN_CTX_get(ctx); 258 b = BN_CTX_get(ctx); 259 if (dv != NULL) { 260 d = dv; 261 } else { 262 d = BN_CTX_get(ctx); 263 } 264 265 if (rem != NULL) { 266 r = rem; 267 } else { 268 r = BN_CTX_get(ctx); 269 } 270 271 if (a == NULL || b == NULL || d == NULL || r == NULL) { 272 goto err; 273 } 274 275 if (BN_ucmp(m, &(recp->N)) < 0) { 276 BN_zero(d); 277 if (!BN_copy(r, m)) { 278 return 0; 279 } 280 BN_CTX_end(ctx); 281 return 1; 282 } 283 284 /* We want the remainder 285 * Given input of ABCDEF / ab 286 * we need multiply ABCDEF by 3 digests of the reciprocal of ab */ 287 288 /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */ 289 i = BN_num_bits(m); 290 j = recp->num_bits << 1; 291 if (j > i) { 292 i = j; 293 } 294 295 /* Nr := round(2^i / N) */ 296 if (i != recp->shift) { 297 recp->shift = 298 BN_reciprocal(&(recp->Nr), &(recp->N), i, 299 ctx); /* BN_reciprocal returns i, or -1 for an error */ 300 } 301 302 if (recp->shift == -1) { 303 goto err; 304 } 305 306 /* d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - 307 * BN_num_bits(N)))| 308 * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - 309 * BN_num_bits(N)))| 310 * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)| 311 * = |m/N| */ 312 if (!BN_rshift(a, m, recp->num_bits)) { 313 goto err; 314 } 315 if (!BN_mul(b, a, &(recp->Nr), ctx)) { 316 goto err; 317 } 318 if (!BN_rshift(d, b, i - recp->num_bits)) { 319 goto err; 320 } 321 d->neg = 0; 322 323 if (!BN_mul(b, &(recp->N), d, ctx)) { 324 goto err; 325 } 326 if (!BN_usub(r, m, b)) { 327 goto err; 328 } 329 r->neg = 0; 330 331 j = 0; 332 while (BN_ucmp(r, &(recp->N)) >= 0) { 333 if (j++ > 2) { 334 OPENSSL_PUT_ERROR(BN, BN_div_recp, BN_R_BAD_RECIPROCAL); 335 goto err; 336 } 337 if (!BN_usub(r, r, &(recp->N))) { 338 goto err; 339 } 340 if (!BN_add_word(d, 1)) { 341 goto err; 342 } 343 } 344 345 r->neg = BN_is_zero(r) ? 0 : m->neg; 346 d->neg = m->neg ^ recp->N.neg; 347 ret = 1; 348 349err: 350 BN_CTX_end(ctx); 351 return ret; 352} 353 354static int BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, 355 BN_RECP_CTX *recp, BN_CTX *ctx) { 356 int ret = 0; 357 BIGNUM *a; 358 const BIGNUM *ca; 359 360 BN_CTX_start(ctx); 361 a = BN_CTX_get(ctx); 362 if (a == NULL) { 363 goto err; 364 } 365 366 if (y != NULL) { 367 if (x == y) { 368 if (!BN_sqr(a, x, ctx)) { 369 goto err; 370 } 371 } else { 372 if (!BN_mul(a, x, y, ctx)) { 373 goto err; 374 } 375 } 376 ca = a; 377 } else { 378 ca = x; /* Just do the mod */ 379 } 380 381 ret = BN_div_recp(NULL, r, ca, recp, ctx); 382 383err: 384 BN_CTX_end(ctx); 385 return ret; 386} 387 388/* BN_window_bits_for_exponent_size -- macro for sliding window mod_exp 389 * functions 390 * 391 * For window size 'w' (w >= 2) and a random 'b' bits exponent, the number of 392 * multiplications is a constant plus on average 393 * 394 * 2^(w-1) + (b-w)/(w+1); 395 * 396 * here 2^(w-1) is for precomputing the table (we actually need entries only 397 * for windows that have the lowest bit set), and (b-w)/(w+1) is an 398 * approximation for the expected number of w-bit windows, not counting the 399 * first one. 400 * 401 * Thus we should use 402 * 403 * w >= 6 if b > 671 404 * w = 5 if 671 > b > 239 405 * w = 4 if 239 > b > 79 406 * w = 3 if 79 > b > 23 407 * w <= 2 if 23 > b 408 * 409 * (with draws in between). Very small exponents are often selected 410 * with low Hamming weight, so we use w = 1 for b <= 23. */ 411#define BN_window_bits_for_exponent_size(b) \ 412 ((b) > 671 ? 6 : \ 413 (b) > 239 ? 5 : \ 414 (b) > 79 ? 4 : \ 415 (b) > 23 ? 3 : 1) 416 417static int mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, 418 const BIGNUM *m, BN_CTX *ctx) { 419 int i, j, bits, ret = 0, wstart, wend, window, wvalue; 420 int start = 1; 421 BIGNUM *aa; 422 /* Table of variables obtained from 'ctx' */ 423 BIGNUM *val[TABLE_SIZE]; 424 BN_RECP_CTX recp; 425 426 if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) { 427 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ 428 OPENSSL_PUT_ERROR(BN, mod_exp_recp, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 429 return 0; 430 } 431 432 bits = BN_num_bits(p); 433 434 if (bits == 0) { 435 ret = BN_one(r); 436 return ret; 437 } 438 439 BN_CTX_start(ctx); 440 aa = BN_CTX_get(ctx); 441 val[0] = BN_CTX_get(ctx); 442 if (!aa || !val[0]) { 443 goto err; 444 } 445 446 BN_RECP_CTX_init(&recp); 447 if (m->neg) { 448 /* ignore sign of 'm' */ 449 if (!BN_copy(aa, m)) { 450 goto err; 451 } 452 aa->neg = 0; 453 if (BN_RECP_CTX_set(&recp, aa, ctx) <= 0) { 454 goto err; 455 } 456 } else { 457 if (BN_RECP_CTX_set(&recp, m, ctx) <= 0) { 458 goto err; 459 } 460 } 461 462 if (!BN_nnmod(val[0], a, m, ctx)) { 463 goto err; /* 1 */ 464 } 465 if (BN_is_zero(val[0])) { 466 BN_zero(r); 467 ret = 1; 468 goto err; 469 } 470 471 window = BN_window_bits_for_exponent_size(bits); 472 if (window > 1) { 473 if (!BN_mod_mul_reciprocal(aa, val[0], val[0], &recp, ctx)) { 474 goto err; /* 2 */ 475 } 476 j = 1 << (window - 1); 477 for (i = 1; i < j; i++) { 478 if (((val[i] = BN_CTX_get(ctx)) == NULL) || 479 !BN_mod_mul_reciprocal(val[i], val[i - 1], aa, &recp, ctx)) { 480 goto err; 481 } 482 } 483 } 484 485 start = 1; /* This is used to avoid multiplication etc 486 * when there is only the value '1' in the 487 * buffer. */ 488 wvalue = 0; /* The 'value' of the window */ 489 wstart = bits - 1; /* The top bit of the window */ 490 wend = 0; /* The bottom bit of the window */ 491 492 if (!BN_one(r)) { 493 goto err; 494 } 495 496 for (;;) { 497 if (BN_is_bit_set(p, wstart) == 0) { 498 if (!start) { 499 if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx)) { 500 goto err; 501 } 502 } 503 if (wstart == 0) { 504 break; 505 } 506 wstart--; 507 continue; 508 } 509 510 /* We now have wstart on a 'set' bit, we now need to work out 511 * how bit a window to do. To do this we need to scan 512 * forward until the last set bit before the end of the 513 * window */ 514 wvalue = 1; 515 wend = 0; 516 for (i = 1; i < window; i++) { 517 if (wstart - i < 0) { 518 break; 519 } 520 if (BN_is_bit_set(p, wstart - i)) { 521 wvalue <<= (i - wend); 522 wvalue |= 1; 523 wend = i; 524 } 525 } 526 527 /* wend is the size of the current window */ 528 j = wend + 1; 529 /* add the 'bytes above' */ 530 if (!start) { 531 for (i = 0; i < j; i++) { 532 if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx)) { 533 goto err; 534 } 535 } 536 } 537 538 /* wvalue will be an odd number < 2^window */ 539 if (!BN_mod_mul_reciprocal(r, r, val[wvalue >> 1], &recp, ctx)) { 540 goto err; 541 } 542 543 /* move the 'window' down further */ 544 wstart -= wend + 1; 545 wvalue = 0; 546 start = 0; 547 if (wstart < 0) { 548 break; 549 } 550 } 551 ret = 1; 552 553err: 554 BN_CTX_end(ctx); 555 BN_RECP_CTX_free(&recp); 556 return ret; 557} 558 559int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, 560 BN_CTX *ctx) { 561 /* For even modulus m = 2^k*m_odd, it might make sense to compute 562 * a^p mod m_odd and a^p mod 2^k separately (with Montgomery 563 * exponentiation for the odd part), using appropriate exponent 564 * reductions, and combine the results using the CRT. 565 * 566 * For now, we use Montgomery only if the modulus is odd; otherwise, 567 * exponentiation using the reciprocal-based quick remaindering 568 * algorithm is used. 569 * 570 * (Timing obtained with expspeed.c [computations a^p mod m 571 * where a, p, m are of the same length: 256, 512, 1024, 2048, 572 * 4096, 8192 bits], compared to the running time of the 573 * standard algorithm: 574 * 575 * BN_mod_exp_mont 33 .. 40 % [AMD K6-2, Linux, debug configuration] 576 * 55 .. 77 % [UltraSparc processor, but 577 * debug-solaris-sparcv8-gcc conf.] 578 * 579 * BN_mod_exp_recp 50 .. 70 % [AMD K6-2, Linux, debug configuration] 580 * 62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc] 581 * 582 * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont 583 * at 2048 and more bits, but at 512 and 1024 bits, it was 584 * slower even than the standard algorithm! 585 * 586 * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations] 587 * should be obtained when the new Montgomery reduction code 588 * has been integrated into OpenSSL.) */ 589 590 if (BN_is_odd(m)) { 591 if (a->top == 1 && !a->neg && BN_get_flags(p, BN_FLG_CONSTTIME) == 0) { 592 BN_ULONG A = a->d[0]; 593 return BN_mod_exp_mont_word(r, A, p, m, ctx, NULL); 594 } 595 596 return BN_mod_exp_mont(r, a, p, m, ctx, NULL); 597 } 598 599 return mod_exp_recp(r, a, p, m, ctx); 600} 601 602int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, 603 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) { 604 int i, j, bits, ret = 0, wstart, wend, window, wvalue; 605 int start = 1; 606 BIGNUM *d, *r; 607 const BIGNUM *aa; 608 /* Table of variables obtained from 'ctx' */ 609 BIGNUM *val[TABLE_SIZE]; 610 BN_MONT_CTX *mont = NULL; 611 612 if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) { 613 return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont); 614 } 615 616 if (!BN_is_odd(m)) { 617 OPENSSL_PUT_ERROR(BN, BN_mod_exp_mont, BN_R_CALLED_WITH_EVEN_MODULUS); 618 return 0; 619 } 620 bits = BN_num_bits(p); 621 if (bits == 0) { 622 ret = BN_one(rr); 623 return ret; 624 } 625 626 BN_CTX_start(ctx); 627 d = BN_CTX_get(ctx); 628 r = BN_CTX_get(ctx); 629 val[0] = BN_CTX_get(ctx); 630 if (!d || !r || !val[0]) { 631 goto err; 632 } 633 634 /* If this is not done, things will break in the montgomery part */ 635 636 if (in_mont != NULL) { 637 mont = in_mont; 638 } else { 639 mont = BN_MONT_CTX_new(); 640 if (mont == NULL) { 641 goto err; 642 } 643 if (!BN_MONT_CTX_set(mont, m, ctx)) { 644 goto err; 645 } 646 } 647 648 if (a->neg || BN_ucmp(a, m) >= 0) { 649 if (!BN_nnmod(val[0], a, m, ctx)) { 650 goto err; 651 } 652 aa = val[0]; 653 } else { 654 aa = a; 655 } 656 657 if (BN_is_zero(aa)) { 658 BN_zero(rr); 659 ret = 1; 660 goto err; 661 } 662 if (!BN_to_montgomery(val[0], aa, mont, ctx)) { 663 goto err; /* 1 */ 664 } 665 666 window = BN_window_bits_for_exponent_size(bits); 667 if (window > 1) { 668 if (!BN_mod_mul_montgomery(d, val[0], val[0], mont, ctx)) { 669 goto err; /* 2 */ 670 } 671 j = 1 << (window - 1); 672 for (i = 1; i < j; i++) { 673 if (((val[i] = BN_CTX_get(ctx)) == NULL) || 674 !BN_mod_mul_montgomery(val[i], val[i - 1], d, mont, ctx)) { 675 goto err; 676 } 677 } 678 } 679 680 start = 1; /* This is used to avoid multiplication etc 681 * when there is only the value '1' in the 682 * buffer. */ 683 wvalue = 0; /* The 'value' of the window */ 684 wstart = bits - 1; /* The top bit of the window */ 685 wend = 0; /* The bottom bit of the window */ 686 687 j = m->top; /* borrow j */ 688 if (m->d[j - 1] & (((BN_ULONG)1) << (BN_BITS2 - 1))) { 689 if (bn_wexpand(r, j) == NULL) 690 goto err; 691 /* 2^(top*BN_BITS2) - m */ 692 r->d[0] = (0 - m->d[0]) & BN_MASK2; 693 for (i = 1; i < j; i++) 694 r->d[i] = (~m->d[i]) & BN_MASK2; 695 r->top = j; 696 /* Upper words will be zero if the corresponding words of 'm' 697 * were 0xfff[...], so decrement r->top accordingly. */ 698 bn_correct_top(r); 699 } else if (!BN_to_montgomery(r, BN_value_one(), mont, ctx)) { 700 goto err; 701 } 702 703 for (;;) { 704 if (BN_is_bit_set(p, wstart) == 0) { 705 if (!start) { 706 if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) 707 goto err; 708 } 709 if (wstart == 0) { 710 break; 711 } 712 wstart--; 713 continue; 714 } 715 716 /* We now have wstart on a 'set' bit, we now need to work out how bit a 717 * window to do. To do this we need to scan forward until the last set bit 718 * before the end of the window */ 719 j = wstart; 720 wvalue = 1; 721 wend = 0; 722 for (i = 1; i < window; i++) { 723 if (wstart - i < 0) { 724 break; 725 } 726 if (BN_is_bit_set(p, wstart - i)) { 727 wvalue <<= (i - wend); 728 wvalue |= 1; 729 wend = i; 730 } 731 } 732 733 /* wend is the size of the current window */ 734 j = wend + 1; 735 /* add the 'bytes above' */ 736 if (!start) { 737 for (i = 0; i < j; i++) { 738 if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) { 739 goto err; 740 } 741 } 742 } 743 744 /* wvalue will be an odd number < 2^window */ 745 if (!BN_mod_mul_montgomery(r, r, val[wvalue >> 1], mont, ctx)) { 746 goto err; 747 } 748 749 /* move the 'window' down further */ 750 wstart -= wend + 1; 751 wvalue = 0; 752 start = 0; 753 if (wstart < 0) { 754 break; 755 } 756 } 757 758 if (!BN_from_montgomery(rr, r, mont, ctx)) { 759 goto err; 760 } 761 ret = 1; 762 763err: 764 if (in_mont == NULL && mont != NULL) { 765 BN_MONT_CTX_free(mont); 766 } 767 BN_CTX_end(ctx); 768 return ret; 769} 770 771/* BN_mod_exp_mont_consttime() stores the precomputed powers in a specific 772 * layout so that accessing any of these table values shows the same access 773 * pattern as far as cache lines are concerned. The following functions are 774 * used to transfer a BIGNUM from/to that table. */ 775static int copy_to_prebuf(const BIGNUM *b, int top, unsigned char *buf, int idx, 776 int width) { 777 size_t i, j; 778 779 if (top > b->top) { 780 top = b->top; /* this works because 'buf' is explicitly zeroed */ 781 } 782 for (i = 0, j = idx; i < top * sizeof b->d[0]; i++, j += width) { 783 buf[j] = ((unsigned char *)b->d)[i]; 784 } 785 786 return 1; 787} 788 789static int copy_from_prebuf(BIGNUM *b, int top, unsigned char *buf, int idx, 790 int width) { 791 size_t i, j; 792 793 if (bn_wexpand(b, top) == NULL) { 794 return 0; 795 } 796 797 for (i = 0, j = idx; i < top * sizeof b->d[0]; i++, j += width) { 798 ((unsigned char *)b->d)[i] = buf[j]; 799 } 800 801 b->top = top; 802 bn_correct_top(b); 803 return 1; 804} 805 806/* BN_mod_exp_mont_conttime is based on the assumption that the L1 data cache 807 * line width of the target processor is at least the following value. */ 808#define MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH (64) 809#define MOD_EXP_CTIME_MIN_CACHE_LINE_MASK \ 810 (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - 1) 811 812/* Window sizes optimized for fixed window size modular exponentiation 813 * algorithm (BN_mod_exp_mont_consttime). 814 * 815 * To achieve the security goals of BN_mode_exp_mont_consttime, the maximum 816 * size of the window must not exceed 817 * log_2(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH). 818 * 819 * Window size thresholds are defined for cache line sizes of 32 and 64, cache 820 * line sizes where log_2(32)=5 and log_2(64)=6 respectively. A window size of 821 * 7 should only be used on processors that have a 128 byte or greater cache 822 * line size. */ 823#if MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 64 824 825#define BN_window_bits_for_ctime_exponent_size(b) \ 826 ((b) > 937 ? 6 : (b) > 306 ? 5 : (b) > 89 ? 4 : (b) > 22 ? 3 : 1) 827#define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (6) 828 829#elif MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 32 830 831#define BN_window_bits_for_ctime_exponent_size(b) \ 832 ((b) > 306 ? 5 : (b) > 89 ? 4 : (b) > 22 ? 3 : 1) 833#define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (5) 834 835#endif 836 837/* Given a pointer value, compute the next address that is a cache line 838 * multiple. */ 839#define MOD_EXP_CTIME_ALIGN(x_) \ 840 ((unsigned char *)(x_) + \ 841 (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - \ 842 (((size_t)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK)))) 843 844/* This variant of BN_mod_exp_mont() uses fixed windows and the special 845 * precomputation memory layout to limit data-dependency to a minimum 846 * to protect secret exponents (cf. the hyper-threading timing attacks 847 * pointed out by Colin Percival, 848 * http://www.daemonology.net/hyperthreading-considered-harmful/) 849 */ 850int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, 851 const BIGNUM *m, BN_CTX *ctx, 852 BN_MONT_CTX *in_mont) { 853 int i, bits, ret = 0, window, wvalue; 854 int top; 855 BN_MONT_CTX *mont = NULL; 856 857 int numPowers; 858 unsigned char *powerbufFree = NULL; 859 int powerbufLen = 0; 860 unsigned char *powerbuf = NULL; 861 BIGNUM tmp, am; 862 863 top = m->top; 864 865 if (!(m->d[0] & 1)) { 866 OPENSSL_PUT_ERROR(BN, BN_mod_exp_mont_consttime, 867 BN_R_CALLED_WITH_EVEN_MODULUS); 868 return 0; 869 } 870 bits = BN_num_bits(p); 871 if (bits == 0) { 872 ret = BN_one(rr); 873 return ret; 874 } 875 876 BN_CTX_start(ctx); 877 878 /* Allocate a montgomery context if it was not supplied by the caller. 879 * If this is not done, things will break in the montgomery part. 880 */ 881 if (in_mont != NULL) 882 mont = in_mont; 883 else { 884 if ((mont = BN_MONT_CTX_new()) == NULL) 885 goto err; 886 if (!BN_MONT_CTX_set(mont, m, ctx)) 887 goto err; 888 } 889 890#ifdef RSAZ_ENABLED 891 /* If the size of the operands allow it, perform the optimized 892 * RSAZ exponentiation. For further information see 893 * crypto/bn/rsaz_exp.c and accompanying assembly modules. */ 894 if ((16 == a->top) && (16 == p->top) && (BN_num_bits(m) == 1024) && 895 rsaz_avx2_eligible()) { 896 if (NULL == bn_wexpand(rr, 16)) 897 goto err; 898 RSAZ_1024_mod_exp_avx2(rr->d, a->d, p->d, m->d, mont->RR.d, mont->n0[0]); 899 rr->top = 16; 900 rr->neg = 0; 901 bn_correct_top(rr); 902 ret = 1; 903 goto err; 904 } else if ((8 == a->top) && (8 == p->top) && (BN_num_bits(m) == 512)) { 905 if (NULL == bn_wexpand(rr, 8)) 906 goto err; 907 RSAZ_512_mod_exp(rr->d, a->d, p->d, m->d, mont->n0[0], mont->RR.d); 908 rr->top = 8; 909 rr->neg = 0; 910 bn_correct_top(rr); 911 ret = 1; 912 goto err; 913 } 914#endif 915 916 /* Get the window size to use with size of p. */ 917 window = BN_window_bits_for_ctime_exponent_size(bits); 918#if defined(OPENSSL_BN_ASM_MONT5) 919 if (window >= 5) { 920 window = 5; /* ~5% improvement for RSA2048 sign, and even for RSA4096 */ 921 if ((top & 7) == 0) 922 powerbufLen += 2 * top * sizeof(m->d[0]); 923 } 924#endif 925 (void)0; 926 927 /* Allocate a buffer large enough to hold all of the pre-computed 928 * powers of am, am itself and tmp. 929 */ 930 numPowers = 1 << window; 931 powerbufLen += 932 sizeof(m->d[0]) * 933 (top * numPowers + ((2 * top) > numPowers ? (2 * top) : numPowers)); 934#ifdef alloca 935 if (powerbufLen < 3072) 936 powerbufFree = alloca(powerbufLen + MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH); 937 else 938#endif 939 if ((powerbufFree = (unsigned char *)OPENSSL_malloc( 940 powerbufLen + MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH)) == NULL) 941 goto err; 942 943 powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree); 944 memset(powerbuf, 0, powerbufLen); 945 946#ifdef alloca 947 if (powerbufLen < 3072) 948 powerbufFree = NULL; 949#endif 950 951 /* lay down tmp and am right after powers table */ 952 tmp.d = (BN_ULONG *)(powerbuf + sizeof(m->d[0]) * top * numPowers); 953 am.d = tmp.d + top; 954 tmp.top = am.top = 0; 955 tmp.dmax = am.dmax = top; 956 tmp.neg = am.neg = 0; 957 tmp.flags = am.flags = BN_FLG_STATIC_DATA; 958 959/* prepare a^0 in Montgomery domain */ 960/* by Shay Gueron's suggestion */ 961 if (m->d[top - 1] & (((BN_ULONG)1) << (BN_BITS2 - 1))) { 962 /* 2^(top*BN_BITS2) - m */ 963 tmp.d[0] = (0 - m->d[0]) & BN_MASK2; 964 for (i = 1; i < top; i++) 965 tmp.d[i] = (~m->d[i]) & BN_MASK2; 966 tmp.top = top; 967 } else if (!BN_to_montgomery(&tmp, BN_value_one(), mont, ctx)) 968 goto err; 969 970 /* prepare a^1 in Montgomery domain */ 971 if (a->neg || BN_ucmp(a, m) >= 0) { 972 if (!BN_mod(&am, a, m, ctx)) 973 goto err; 974 if (!BN_to_montgomery(&am, &am, mont, ctx)) 975 goto err; 976 } else if (!BN_to_montgomery(&am, a, mont, ctx)) 977 goto err; 978 979#if defined(OPENSSL_BN_ASM_MONT5) 980 /* This optimization uses ideas from http://eprint.iacr.org/2011/239, 981 * specifically optimization of cache-timing attack countermeasures 982 * and pre-computation optimization. */ 983 984 /* Dedicated window==4 case improves 512-bit RSA sign by ~15%, but as 985 * 512-bit RSA is hardly relevant, we omit it to spare size... */ 986 if (window == 5 && top > 1) { 987 void bn_mul_mont_gather5(BN_ULONG * rp, const BN_ULONG * ap, 988 const void * table, const BN_ULONG * np, 989 const BN_ULONG * n0, int num, int power); 990 void bn_scatter5(const BN_ULONG * inp, size_t num, void * table, 991 size_t power); 992 void bn_gather5(BN_ULONG * out, size_t num, void * table, size_t power); 993 void bn_power5(BN_ULONG * rp, const BN_ULONG * ap, const void * table, 994 const BN_ULONG * np, const BN_ULONG * n0, int num, 995 int power); 996 int bn_from_montgomery(BN_ULONG * rp, const BN_ULONG * ap, 997 const BN_ULONG * not_used, const BN_ULONG * np, 998 const BN_ULONG * n0, int num); 999 1000 BN_ULONG *np = mont->N.d, *n0 = mont->n0, *np2; 1001 1002 /* BN_to_montgomery can contaminate words above .top 1003 * [in BN_DEBUG[_DEBUG] build]... */ 1004 for (i = am.top; i < top; i++) 1005 am.d[i] = 0; 1006 for (i = tmp.top; i < top; i++) 1007 tmp.d[i] = 0; 1008 1009 if (top & 7) 1010 np2 = np; 1011 else 1012 for (np2 = am.d + top, i = 0; i < top; i++) 1013 np2[2 * i] = np[i]; 1014 1015 bn_scatter5(tmp.d, top, powerbuf, 0); 1016 bn_scatter5(am.d, am.top, powerbuf, 1); 1017 bn_mul_mont(tmp.d, am.d, am.d, np, n0, top); 1018 bn_scatter5(tmp.d, top, powerbuf, 2); 1019 1020 /* same as above, but uses squaring for 1/2 of operations */ 1021 for (i = 4; i < 32; i *= 2) { 1022 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); 1023 bn_scatter5(tmp.d, top, powerbuf, i); 1024 } 1025 for (i = 3; i < 8; i += 2) { 1026 int j; 1027 bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np2, n0, top, i - 1); 1028 bn_scatter5(tmp.d, top, powerbuf, i); 1029 for (j = 2 * i; j < 32; j *= 2) { 1030 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); 1031 bn_scatter5(tmp.d, top, powerbuf, j); 1032 } 1033 } 1034 for (; i < 16; i += 2) { 1035 bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np2, n0, top, i - 1); 1036 bn_scatter5(tmp.d, top, powerbuf, i); 1037 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); 1038 bn_scatter5(tmp.d, top, powerbuf, 2 * i); 1039 } 1040 for (; i < 32; i += 2) { 1041 bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np2, n0, top, i - 1); 1042 bn_scatter5(tmp.d, top, powerbuf, i); 1043 } 1044 1045 bits--; 1046 for (wvalue = 0, i = bits % 5; i >= 0; i--, bits--) 1047 wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); 1048 bn_gather5(tmp.d, top, powerbuf, wvalue); 1049 1050 /* At this point |bits| is 4 mod 5 and at least -1. (|bits| is the first bit 1051 * that has not been read yet.) */ 1052 assert(bits >= -1 && (bits == -1 || bits % 5 == 4)); 1053 1054 /* Scan the exponent one window at a time starting from the most 1055 * significant bits. 1056 */ 1057 if (top & 7) { 1058 while (bits >= 0) { 1059 for (wvalue = 0, i = 0; i < 5; i++, bits--) 1060 wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); 1061 1062 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); 1063 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); 1064 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); 1065 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); 1066 bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); 1067 bn_mul_mont_gather5(tmp.d, tmp.d, powerbuf, np, n0, top, wvalue); 1068 } 1069 } else { 1070 const uint8_t *p_bytes = (const uint8_t *)p->d; 1071 int max_bits = p->top * BN_BITS2; 1072 assert(bits < max_bits); 1073 /* |p = 0| has been handled as a special case, so |max_bits| is at least 1074 * one word. */ 1075 assert(max_bits >= 64); 1076 1077 /* If the first bit to be read lands in the last byte, unroll the first 1078 * iteration to avoid reading past the bounds of |p->d|. (After the first 1079 * iteration, we are guaranteed to be past the last byte.) Note |bits| 1080 * here is the top bit, inclusive. */ 1081 if (bits - 4 >= max_bits - 8) { 1082 /* Read five bits from |bits-4| through |bits|, inclusive. */ 1083 wvalue = p_bytes[p->top * BN_BYTES - 1]; 1084 wvalue >>= (bits - 4) & 7; 1085 wvalue &= 0x1f; 1086 bits -= 5; 1087 bn_power5(tmp.d, tmp.d, powerbuf, np2, n0, top, wvalue); 1088 } 1089 while (bits >= 0) { 1090 /* Read five bits from |bits-4| through |bits|, inclusive. */ 1091 int first_bit = bits - 4; 1092 wvalue = *(const uint16_t *) (p_bytes + (first_bit >> 3)); 1093 wvalue >>= first_bit & 7; 1094 wvalue &= 0x1f; 1095 bits -= 5; 1096 bn_power5(tmp.d, tmp.d, powerbuf, np2, n0, top, wvalue); 1097 } 1098 } 1099 1100 ret = bn_from_montgomery(tmp.d, tmp.d, NULL, np2, n0, top); 1101 tmp.top = top; 1102 bn_correct_top(&tmp); 1103 if (ret) { 1104 if (!BN_copy(rr, &tmp)) 1105 ret = 0; 1106 goto err; /* non-zero ret means it's not error */ 1107 } 1108 } else 1109#endif 1110 { 1111 if (!copy_to_prebuf(&tmp, top, powerbuf, 0, numPowers)) 1112 goto err; 1113 if (!copy_to_prebuf(&am, top, powerbuf, 1, numPowers)) 1114 goto err; 1115 1116 /* If the window size is greater than 1, then calculate 1117 * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1) 1118 * (even powers could instead be computed as (a^(i/2))^2 1119 * to use the slight performance advantage of sqr over mul). 1120 */ 1121 if (window > 1) { 1122 if (!BN_mod_mul_montgomery(&tmp, &am, &am, mont, ctx)) 1123 goto err; 1124 if (!copy_to_prebuf(&tmp, top, powerbuf, 2, numPowers)) 1125 goto err; 1126 for (i = 3; i < numPowers; i++) { 1127 /* Calculate a^i = a^(i-1) * a */ 1128 if (!BN_mod_mul_montgomery(&tmp, &am, &tmp, mont, ctx)) 1129 goto err; 1130 if (!copy_to_prebuf(&tmp, top, powerbuf, i, numPowers)) 1131 goto err; 1132 } 1133 } 1134 1135 bits--; 1136 for (wvalue = 0, i = bits % window; i >= 0; i--, bits--) 1137 wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); 1138 if (!copy_from_prebuf(&tmp, top, powerbuf, wvalue, numPowers)) 1139 goto err; 1140 1141 /* Scan the exponent one window at a time starting from the most 1142 * significant bits. 1143 */ 1144 while (bits >= 0) { 1145 wvalue = 0; /* The 'value' of the window */ 1146 1147 /* Scan the window, squaring the result as we go */ 1148 for (i = 0; i < window; i++, bits--) { 1149 if (!BN_mod_mul_montgomery(&tmp, &tmp, &tmp, mont, ctx)) 1150 goto err; 1151 wvalue = (wvalue << 1) + BN_is_bit_set(p, bits); 1152 } 1153 1154 /* Fetch the appropriate pre-computed value from the pre-buf */ 1155 if (!copy_from_prebuf(&am, top, powerbuf, wvalue, numPowers)) 1156 goto err; 1157 1158 /* Multiply the result into the intermediate result */ 1159 if (!BN_mod_mul_montgomery(&tmp, &tmp, &am, mont, ctx)) 1160 goto err; 1161 } 1162 } 1163 1164 /* Convert the final result from montgomery to standard format */ 1165 if (!BN_from_montgomery(rr, &tmp, mont, ctx)) 1166 goto err; 1167 ret = 1; 1168err: 1169 if ((in_mont == NULL) && (mont != NULL)) 1170 BN_MONT_CTX_free(mont); 1171 if (powerbuf != NULL) { 1172 OPENSSL_cleanse(powerbuf, powerbufLen); 1173 if (powerbufFree) 1174 OPENSSL_free(powerbufFree); 1175 } 1176 BN_CTX_end(ctx); 1177 return (ret); 1178} 1179 1180int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, 1181 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) { 1182 BN_MONT_CTX *mont = NULL; 1183 int b, bits, ret = 0; 1184 int r_is_one; 1185 BN_ULONG w, next_w; 1186 BIGNUM *d, *r, *t; 1187 BIGNUM *swap_tmp; 1188#define BN_MOD_MUL_WORD(r, w, m) \ 1189 (BN_mul_word(r, (w)) && \ 1190 (/* BN_ucmp(r, (m)) < 0 ? 1 :*/ \ 1191 (BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1)))) 1192 /* BN_MOD_MUL_WORD is only used with 'w' large, so the BN_ucmp test is 1193 * probably more overhead than always using BN_mod (which uses BN_copy if a 1194 * similar test returns true). We can use BN_mod and do not need BN_nnmod 1195 * because our accumulator is never negative (the result of BN_mod does not 1196 * depend on the sign of the modulus). */ 1197#define BN_TO_MONTGOMERY_WORD(r, w, mont) \ 1198 (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx)) 1199 1200 if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) { 1201 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ 1202 OPENSSL_PUT_ERROR(BN, BN_mod_exp_mont_word, 1203 ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1204 return 0; 1205 } 1206 1207 if (!BN_is_odd(m)) { 1208 OPENSSL_PUT_ERROR(BN, BN_mod_exp_mont_word, BN_R_CALLED_WITH_EVEN_MODULUS); 1209 return 0; 1210 } 1211 1212 if (m->top == 1) { 1213 a %= m->d[0]; /* make sure that 'a' is reduced */ 1214 } 1215 1216 bits = BN_num_bits(p); 1217 if (bits == 0) { 1218 /* x**0 mod 1 is still zero. */ 1219 if (BN_is_one(m)) { 1220 ret = 1; 1221 BN_zero(rr); 1222 } else { 1223 ret = BN_one(rr); 1224 } 1225 return ret; 1226 } 1227 if (a == 0) { 1228 BN_zero(rr); 1229 ret = 1; 1230 return ret; 1231 } 1232 1233 BN_CTX_start(ctx); 1234 d = BN_CTX_get(ctx); 1235 r = BN_CTX_get(ctx); 1236 t = BN_CTX_get(ctx); 1237 if (d == NULL || r == NULL || t == NULL) { 1238 goto err; 1239 } 1240 1241 if (in_mont != NULL) 1242 mont = in_mont; 1243 else { 1244 if ((mont = BN_MONT_CTX_new()) == NULL) { 1245 goto err; 1246 } 1247 if (!BN_MONT_CTX_set(mont, m, ctx)) { 1248 goto err; 1249 } 1250 } 1251 1252 r_is_one = 1; /* except for Montgomery factor */ 1253 1254 /* bits-1 >= 0 */ 1255 1256 /* The result is accumulated in the product r*w. */ 1257 w = a; /* bit 'bits-1' of 'p' is always set */ 1258 for (b = bits - 2; b >= 0; b--) { 1259 /* First, square r*w. */ 1260 next_w = w * w; 1261 if ((next_w / w) != w) { 1262 /* overflow */ 1263 if (r_is_one) { 1264 if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) { 1265 goto err; 1266 } 1267 r_is_one = 0; 1268 } else { 1269 if (!BN_MOD_MUL_WORD(r, w, m)) { 1270 goto err; 1271 } 1272 } 1273 next_w = 1; 1274 } 1275 1276 w = next_w; 1277 if (!r_is_one) { 1278 if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) { 1279 goto err; 1280 } 1281 } 1282 1283 /* Second, multiply r*w by 'a' if exponent bit is set. */ 1284 if (BN_is_bit_set(p, b)) { 1285 next_w = w * a; 1286 if ((next_w / a) != w) { 1287 /* overflow */ 1288 if (r_is_one) { 1289 if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) { 1290 goto err; 1291 } 1292 r_is_one = 0; 1293 } else { 1294 if (!BN_MOD_MUL_WORD(r, w, m)) { 1295 goto err; 1296 } 1297 } 1298 next_w = a; 1299 } 1300 w = next_w; 1301 } 1302 } 1303 1304 /* Finally, set r:=r*w. */ 1305 if (w != 1) { 1306 if (r_is_one) { 1307 if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) { 1308 goto err; 1309 } 1310 r_is_one = 0; 1311 } else { 1312 if (!BN_MOD_MUL_WORD(r, w, m)) { 1313 goto err; 1314 } 1315 } 1316 } 1317 1318 if (r_is_one) { 1319 /* can happen only if a == 1*/ 1320 if (!BN_one(rr)) { 1321 goto err; 1322 } 1323 } else { 1324 if (!BN_from_montgomery(rr, r, mont, ctx)) { 1325 goto err; 1326 } 1327 } 1328 ret = 1; 1329 1330err: 1331 if (in_mont == NULL && mont != NULL) { 1332 BN_MONT_CTX_free(mont); 1333 } 1334 BN_CTX_end(ctx); 1335 return ret; 1336} 1337 1338#define TABLE_SIZE 32 1339 1340int BN_mod_exp2_mont(BIGNUM *rr, const BIGNUM *a1, const BIGNUM *p1, 1341 const BIGNUM *a2, const BIGNUM *p2, const BIGNUM *m, 1342 BN_CTX *ctx, BN_MONT_CTX *in_mont) { 1343 int i, j, bits, b, bits1, bits2, ret = 0, wpos1, wpos2, window1, window2, 1344 wvalue1, wvalue2; 1345 int r_is_one = 1; 1346 BIGNUM *d, *r; 1347 const BIGNUM *a_mod_m; 1348 /* Tables of variables obtained from 'ctx' */ 1349 BIGNUM *val1[TABLE_SIZE], *val2[TABLE_SIZE]; 1350 BN_MONT_CTX *mont = NULL; 1351 1352 if (!(m->d[0] & 1)) { 1353 OPENSSL_PUT_ERROR(BN, BN_mod_exp2_mont, BN_R_CALLED_WITH_EVEN_MODULUS); 1354 return 0; 1355 } 1356 bits1 = BN_num_bits(p1); 1357 bits2 = BN_num_bits(p2); 1358 if (bits1 == 0 && bits2 == 0) { 1359 ret = BN_one(rr); 1360 return ret; 1361 } 1362 1363 bits = (bits1 > bits2) ? bits1 : bits2; 1364 1365 BN_CTX_start(ctx); 1366 d = BN_CTX_get(ctx); 1367 r = BN_CTX_get(ctx); 1368 val1[0] = BN_CTX_get(ctx); 1369 val2[0] = BN_CTX_get(ctx); 1370 if (!d || !r || !val1[0] || !val2[0]) { 1371 goto err; 1372 } 1373 1374 if (in_mont != NULL) { 1375 mont = in_mont; 1376 } else { 1377 mont = BN_MONT_CTX_new(); 1378 if (mont == NULL) { 1379 goto err; 1380 } 1381 if (!BN_MONT_CTX_set(mont, m, ctx)) { 1382 goto err; 1383 } 1384 } 1385 1386 window1 = BN_window_bits_for_exponent_size(bits1); 1387 window2 = BN_window_bits_for_exponent_size(bits2); 1388 1389 /* Build table for a1: val1[i] := a1^(2*i + 1) mod m for i = 0 .. 1390 * 2^(window1-1) */ 1391 if (a1->neg || BN_ucmp(a1, m) >= 0) { 1392 if (!BN_mod(val1[0], a1, m, ctx)) { 1393 goto err; 1394 } 1395 a_mod_m = val1[0]; 1396 } else { 1397 a_mod_m = a1; 1398 } 1399 1400 if (BN_is_zero(a_mod_m)) { 1401 BN_zero(rr); 1402 ret = 1; 1403 goto err; 1404 } 1405 1406 if (!BN_to_montgomery(val1[0], a_mod_m, mont, ctx)) { 1407 goto err; 1408 } 1409 1410 if (window1 > 1) { 1411 if (!BN_mod_mul_montgomery(d, val1[0], val1[0], mont, ctx)) { 1412 goto err; 1413 } 1414 1415 j = 1 << (window1 - 1); 1416 for (i = 1; i < j; i++) { 1417 if (((val1[i] = BN_CTX_get(ctx)) == NULL) || 1418 !BN_mod_mul_montgomery(val1[i], val1[i - 1], d, mont, ctx)) { 1419 goto err; 1420 } 1421 } 1422 } 1423 1424 /* Build table for a2: val2[i] := a2^(2*i + 1) mod m for i = 0 .. 1425 * 2^(window2-1) */ 1426 if (a2->neg || BN_ucmp(a2, m) >= 0) { 1427 if (!BN_mod(val2[0], a2, m, ctx)) { 1428 goto err; 1429 } 1430 a_mod_m = val2[0]; 1431 } else { 1432 a_mod_m = a2; 1433 } 1434 1435 if (BN_is_zero(a_mod_m)) { 1436 BN_zero(rr); 1437 ret = 1; 1438 goto err; 1439 } 1440 1441 if (!BN_to_montgomery(val2[0], a_mod_m, mont, ctx)) { 1442 goto err; 1443 } 1444 1445 if (window2 > 1) { 1446 if (!BN_mod_mul_montgomery(d, val2[0], val2[0], mont, ctx)) { 1447 goto err; 1448 } 1449 1450 j = 1 << (window2 - 1); 1451 for (i = 1; i < j; i++) { 1452 if (((val2[i] = BN_CTX_get(ctx)) == NULL) || 1453 !BN_mod_mul_montgomery(val2[i], val2[i - 1], d, mont, ctx)) { 1454 goto err; 1455 } 1456 } 1457 } 1458 1459 /* Now compute the power product, using independent windows. */ 1460 r_is_one = 1; 1461 wvalue1 = 0; /* The 'value' of the first window */ 1462 wvalue2 = 0; /* The 'value' of the second window */ 1463 wpos1 = 0; /* If wvalue1 > 0, the bottom bit of the first window */ 1464 wpos2 = 0; /* If wvalue2 > 0, the bottom bit of the second window */ 1465 1466 if (!BN_to_montgomery(r, BN_value_one(), mont, ctx)) { 1467 goto err; 1468 } 1469 1470 for (b = bits - 1; b >= 0; b--) { 1471 if (!r_is_one) { 1472 if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) { 1473 goto err; 1474 } 1475 } 1476 1477 if (!wvalue1 && BN_is_bit_set(p1, b)) { 1478 /* consider bits b-window1+1 .. b for this window */ 1479 i = b - window1 + 1; 1480 while (!BN_is_bit_set(p1, i)) /* works for i<0 */ 1481 i++; 1482 wpos1 = i; 1483 wvalue1 = 1; 1484 for (i = b - 1; i >= wpos1; i--) { 1485 wvalue1 <<= 1; 1486 if (BN_is_bit_set(p1, i)) 1487 wvalue1++; 1488 } 1489 } 1490 1491 if (!wvalue2 && BN_is_bit_set(p2, b)) { 1492 /* consider bits b-window2+1 .. b for this window */ 1493 i = b - window2 + 1; 1494 while (!BN_is_bit_set(p2, i)) 1495 i++; 1496 wpos2 = i; 1497 wvalue2 = 1; 1498 for (i = b - 1; i >= wpos2; i--) { 1499 wvalue2 <<= 1; 1500 if (BN_is_bit_set(p2, i)) 1501 wvalue2++; 1502 } 1503 } 1504 1505 if (wvalue1 && b == wpos1) { 1506 /* wvalue1 is odd and < 2^window1 */ 1507 if (!BN_mod_mul_montgomery(r, r, val1[wvalue1 >> 1], mont, ctx)) { 1508 goto err; 1509 } 1510 wvalue1 = 0; 1511 r_is_one = 0; 1512 } 1513 1514 if (wvalue2 && b == wpos2) { 1515 /* wvalue2 is odd and < 2^window2 */ 1516 if (!BN_mod_mul_montgomery(r, r, val2[wvalue2 >> 1], mont, ctx)) { 1517 goto err; 1518 } 1519 wvalue2 = 0; 1520 r_is_one = 0; 1521 } 1522 } 1523 1524 if (!BN_from_montgomery(rr, r, mont, ctx)) { 1525 goto err; 1526 } 1527 ret = 1; 1528 1529err: 1530 if (in_mont == NULL && mont != NULL) { 1531 BN_MONT_CTX_free(mont); 1532 } 1533 BN_CTX_end(ctx); 1534 return ret; 1535} 1536