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 #include <openssl/bn.h> 58 59 #include <assert.h> 60 #include <limits.h> 61 62 #include <openssl/err.h> 63 64 #include "internal.h" 65 66 67 #if !defined(BN_ULLONG) 68 // bn_div_words divides a double-width |h|,|l| by |d| and returns the result, 69 // which must fit in a |BN_ULONG|. 70 static BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d) { 71 BN_ULONG dh, dl, q, ret = 0, th, tl, t; 72 int i, count = 2; 73 74 if (d == 0) { 75 return BN_MASK2; 76 } 77 78 i = BN_num_bits_word(d); 79 assert((i == BN_BITS2) || (h <= (BN_ULONG)1 << i)); 80 81 i = BN_BITS2 - i; 82 if (h >= d) { 83 h -= d; 84 } 85 86 if (i) { 87 d <<= i; 88 h = (h << i) | (l >> (BN_BITS2 - i)); 89 l <<= i; 90 } 91 dh = (d & BN_MASK2h) >> BN_BITS4; 92 dl = (d & BN_MASK2l); 93 for (;;) { 94 if ((h >> BN_BITS4) == dh) { 95 q = BN_MASK2l; 96 } else { 97 q = h / dh; 98 } 99 100 th = q * dh; 101 tl = dl * q; 102 for (;;) { 103 t = h - th; 104 if ((t & BN_MASK2h) || 105 ((tl) <= ((t << BN_BITS4) | ((l & BN_MASK2h) >> BN_BITS4)))) { 106 break; 107 } 108 q--; 109 th -= dh; 110 tl -= dl; 111 } 112 t = (tl >> BN_BITS4); 113 tl = (tl << BN_BITS4) & BN_MASK2h; 114 th += t; 115 116 if (l < tl) { 117 th++; 118 } 119 l -= tl; 120 if (h < th) { 121 h += d; 122 q--; 123 } 124 h -= th; 125 126 if (--count == 0) { 127 break; 128 } 129 130 ret = q << BN_BITS4; 131 h = (h << BN_BITS4) | (l >> BN_BITS4); 132 l = (l & BN_MASK2l) << BN_BITS4; 133 } 134 135 ret |= q; 136 return ret; 137 } 138 #endif // !defined(BN_ULLONG) 139 140 static inline void bn_div_rem_words(BN_ULONG *quotient_out, BN_ULONG *rem_out, 141 BN_ULONG n0, BN_ULONG n1, BN_ULONG d0) { 142 // GCC and Clang generate function calls to |__udivdi3| and |__umoddi3| when 143 // the |BN_ULLONG|-based C code is used. 144 // 145 // GCC bugs: 146 // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14224 147 // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=43721 148 // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54183 149 // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=58897 150 // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65668 151 // 152 // Clang bugs: 153 // * https://llvm.org/bugs/show_bug.cgi?id=6397 154 // * https://llvm.org/bugs/show_bug.cgi?id=12418 155 // 156 // These issues aren't specific to x86 and x86_64, so it might be worthwhile 157 // to add more assembly language implementations. 158 #if !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86) && \ 159 (defined(__GNUC__) || defined(__clang__)) 160 __asm__ volatile("divl %4" 161 : "=a"(*quotient_out), "=d"(*rem_out) 162 : "a"(n1), "d"(n0), "rm"(d0) 163 : "cc"); 164 #elif !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86_64) && \ 165 (defined(__GNUC__) || defined(__clang__)) 166 __asm__ volatile("divq %4" 167 : "=a"(*quotient_out), "=d"(*rem_out) 168 : "a"(n1), "d"(n0), "rm"(d0) 169 : "cc"); 170 #else 171 #if defined(BN_ULLONG) 172 BN_ULLONG n = (((BN_ULLONG)n0) << BN_BITS2) | n1; 173 *quotient_out = (BN_ULONG)(n / d0); 174 #else 175 *quotient_out = bn_div_words(n0, n1, d0); 176 #endif 177 *rem_out = n1 - (*quotient_out * d0); 178 #endif 179 } 180 181 // BN_div computes "quotient := numerator / divisor", rounding towards zero, 182 // and sets up |rem| such that "quotient * divisor + rem = numerator" holds. 183 // 184 // Thus: 185 // 186 // quotient->neg == numerator->neg ^ divisor->neg 187 // (unless the result is zero) 188 // rem->neg == numerator->neg 189 // (unless the remainder is zero) 190 // 191 // If |quotient| or |rem| is NULL, the respective value is not returned. 192 // 193 // This was specifically designed to contain fewer branches that may leak 194 // sensitive information; see "New Branch Prediction Vulnerabilities in OpenSSL 195 // and Necessary Software Countermeasures" by Onur Acmez, Shay Gueron, and 196 // Jean-Pierre Seifert. 197 int BN_div(BIGNUM *quotient, BIGNUM *rem, const BIGNUM *numerator, 198 const BIGNUM *divisor, BN_CTX *ctx) { 199 int norm_shift, loop; 200 BIGNUM wnum; 201 BN_ULONG *resp, *wnump; 202 BN_ULONG d0, d1; 203 int num_n, div_n; 204 205 // Invalid zero-padding would have particularly bad consequences 206 // so don't just rely on bn_check_top() here 207 if ((numerator->top > 0 && numerator->d[numerator->top - 1] == 0) || 208 (divisor->top > 0 && divisor->d[divisor->top - 1] == 0)) { 209 OPENSSL_PUT_ERROR(BN, BN_R_NOT_INITIALIZED); 210 return 0; 211 } 212 213 if (BN_is_zero(divisor)) { 214 OPENSSL_PUT_ERROR(BN, BN_R_DIV_BY_ZERO); 215 return 0; 216 } 217 218 BN_CTX_start(ctx); 219 BIGNUM *tmp = BN_CTX_get(ctx); 220 BIGNUM *snum = BN_CTX_get(ctx); 221 BIGNUM *sdiv = BN_CTX_get(ctx); 222 BIGNUM *res = NULL; 223 if (quotient == NULL) { 224 res = BN_CTX_get(ctx); 225 } else { 226 res = quotient; 227 } 228 if (sdiv == NULL || res == NULL) { 229 goto err; 230 } 231 232 // First we normalise the numbers 233 norm_shift = BN_BITS2 - (BN_num_bits(divisor) % BN_BITS2); 234 if (!BN_lshift(sdiv, divisor, norm_shift)) { 235 goto err; 236 } 237 sdiv->neg = 0; 238 norm_shift += BN_BITS2; 239 if (!BN_lshift(snum, numerator, norm_shift)) { 240 goto err; 241 } 242 snum->neg = 0; 243 244 // Since we don't want to have special-case logic for the case where snum is 245 // larger than sdiv, we pad snum with enough zeroes without changing its 246 // value. 247 if (snum->top <= sdiv->top + 1) { 248 if (!bn_wexpand(snum, sdiv->top + 2)) { 249 goto err; 250 } 251 for (int i = snum->top; i < sdiv->top + 2; i++) { 252 snum->d[i] = 0; 253 } 254 snum->top = sdiv->top + 2; 255 } else { 256 if (!bn_wexpand(snum, snum->top + 1)) { 257 goto err; 258 } 259 snum->d[snum->top] = 0; 260 snum->top++; 261 } 262 263 div_n = sdiv->top; 264 num_n = snum->top; 265 loop = num_n - div_n; 266 // Lets setup a 'window' into snum 267 // This is the part that corresponds to the current 268 // 'area' being divided 269 wnum.neg = 0; 270 wnum.d = &(snum->d[loop]); 271 wnum.top = div_n; 272 // only needed when BN_ucmp messes up the values between top and max 273 wnum.dmax = snum->dmax - loop; // so we don't step out of bounds 274 275 // Get the top 2 words of sdiv 276 // div_n=sdiv->top; 277 d0 = sdiv->d[div_n - 1]; 278 d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2]; 279 280 // pointer to the 'top' of snum 281 wnump = &(snum->d[num_n - 1]); 282 283 // Setup to 'res' 284 res->neg = (numerator->neg ^ divisor->neg); 285 if (!bn_wexpand(res, loop + 1)) { 286 goto err; 287 } 288 res->top = loop - 1; 289 resp = &(res->d[loop - 1]); 290 291 // space for temp 292 if (!bn_wexpand(tmp, div_n + 1)) { 293 goto err; 294 } 295 296 // if res->top == 0 then clear the neg value otherwise decrease 297 // the resp pointer 298 if (res->top == 0) { 299 res->neg = 0; 300 } else { 301 resp--; 302 } 303 304 for (int i = 0; i < loop - 1; i++, wnump--, resp--) { 305 BN_ULONG q, l0; 306 // the first part of the loop uses the top two words of snum and sdiv to 307 // calculate a BN_ULONG q such that | wnum - sdiv * q | < sdiv 308 BN_ULONG n0, n1, rm = 0; 309 310 n0 = wnump[0]; 311 n1 = wnump[-1]; 312 if (n0 == d0) { 313 q = BN_MASK2; 314 } else { 315 // n0 < d0 316 bn_div_rem_words(&q, &rm, n0, n1, d0); 317 318 #ifdef BN_ULLONG 319 BN_ULLONG t2 = (BN_ULLONG)d1 * q; 320 for (;;) { 321 if (t2 <= ((((BN_ULLONG)rm) << BN_BITS2) | wnump[-2])) { 322 break; 323 } 324 q--; 325 rm += d0; 326 if (rm < d0) { 327 break; // don't let rm overflow 328 } 329 t2 -= d1; 330 } 331 #else // !BN_ULLONG 332 BN_ULONG t2l, t2h; 333 BN_UMULT_LOHI(t2l, t2h, d1, q); 334 for (;;) { 335 if (t2h < rm || 336 (t2h == rm && t2l <= wnump[-2])) { 337 break; 338 } 339 q--; 340 rm += d0; 341 if (rm < d0) { 342 break; // don't let rm overflow 343 } 344 if (t2l < d1) { 345 t2h--; 346 } 347 t2l -= d1; 348 } 349 #endif // !BN_ULLONG 350 } 351 352 l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q); 353 tmp->d[div_n] = l0; 354 wnum.d--; 355 // ingore top values of the bignums just sub the two 356 // BN_ULONG arrays with bn_sub_words 357 if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) { 358 // Note: As we have considered only the leading 359 // two BN_ULONGs in the calculation of q, sdiv * q 360 // might be greater than wnum (but then (q-1) * sdiv 361 // is less or equal than wnum) 362 q--; 363 if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) { 364 // we can't have an overflow here (assuming 365 // that q != 0, but if q == 0 then tmp is 366 // zero anyway) 367 (*wnump)++; 368 } 369 } 370 // store part of the result 371 *resp = q; 372 } 373 374 bn_correct_top(snum); 375 376 if (rem != NULL) { 377 // Keep a copy of the neg flag in numerator because if |rem| == |numerator| 378 // |BN_rshift| will overwrite it. 379 int neg = numerator->neg; 380 if (!BN_rshift(rem, snum, norm_shift)) { 381 goto err; 382 } 383 if (!BN_is_zero(rem)) { 384 rem->neg = neg; 385 } 386 } 387 388 bn_correct_top(res); 389 BN_CTX_end(ctx); 390 return 1; 391 392 err: 393 BN_CTX_end(ctx); 394 return 0; 395 } 396 397 int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) { 398 if (!(BN_mod(r, m, d, ctx))) { 399 return 0; 400 } 401 if (!r->neg) { 402 return 1; 403 } 404 405 // now -|d| < r < 0, so we have to set r := r + |d|. 406 return (d->neg ? BN_sub : BN_add)(r, r, d); 407 } 408 409 int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 410 BN_CTX *ctx) { 411 if (!BN_add(r, a, b)) { 412 return 0; 413 } 414 return BN_nnmod(r, r, m, ctx); 415 } 416 417 int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 418 const BIGNUM *m) { 419 if (!BN_uadd(r, a, b)) { 420 return 0; 421 } 422 if (BN_ucmp(r, m) >= 0) { 423 return BN_usub(r, r, m); 424 } 425 return 1; 426 } 427 428 int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 429 BN_CTX *ctx) { 430 if (!BN_sub(r, a, b)) { 431 return 0; 432 } 433 return BN_nnmod(r, r, m, ctx); 434 } 435 436 // BN_mod_sub variant that may be used if both a and b are non-negative 437 // and less than m 438 int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 439 const BIGNUM *m) { 440 if (!BN_sub(r, a, b)) { 441 return 0; 442 } 443 if (r->neg) { 444 return BN_add(r, r, m); 445 } 446 return 1; 447 } 448 449 int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 450 BN_CTX *ctx) { 451 BIGNUM *t; 452 int ret = 0; 453 454 BN_CTX_start(ctx); 455 t = BN_CTX_get(ctx); 456 if (t == NULL) { 457 goto err; 458 } 459 460 if (a == b) { 461 if (!BN_sqr(t, a, ctx)) { 462 goto err; 463 } 464 } else { 465 if (!BN_mul(t, a, b, ctx)) { 466 goto err; 467 } 468 } 469 470 if (!BN_nnmod(r, t, m, ctx)) { 471 goto err; 472 } 473 474 ret = 1; 475 476 err: 477 BN_CTX_end(ctx); 478 return ret; 479 } 480 481 int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) { 482 if (!BN_sqr(r, a, ctx)) { 483 return 0; 484 } 485 486 // r->neg == 0, thus we don't need BN_nnmod 487 return BN_mod(r, r, m, ctx); 488 } 489 490 int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, 491 BN_CTX *ctx) { 492 BIGNUM *abs_m = NULL; 493 int ret; 494 495 if (!BN_nnmod(r, a, m, ctx)) { 496 return 0; 497 } 498 499 if (m->neg) { 500 abs_m = BN_dup(m); 501 if (abs_m == NULL) { 502 return 0; 503 } 504 abs_m->neg = 0; 505 } 506 507 ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); 508 509 BN_free(abs_m); 510 return ret; 511 } 512 513 int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) { 514 if (r != a) { 515 if (BN_copy(r, a) == NULL) { 516 return 0; 517 } 518 } 519 520 while (n > 0) { 521 int max_shift; 522 523 // 0 < r < m 524 max_shift = BN_num_bits(m) - BN_num_bits(r); 525 // max_shift >= 0 526 527 if (max_shift < 0) { 528 OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED); 529 return 0; 530 } 531 532 if (max_shift > n) { 533 max_shift = n; 534 } 535 536 if (max_shift) { 537 if (!BN_lshift(r, r, max_shift)) { 538 return 0; 539 } 540 n -= max_shift; 541 } else { 542 if (!BN_lshift1(r, r)) { 543 return 0; 544 } 545 --n; 546 } 547 548 // BN_num_bits(r) <= BN_num_bits(m) 549 if (BN_cmp(r, m) >= 0) { 550 if (!BN_sub(r, r, m)) { 551 return 0; 552 } 553 } 554 } 555 556 return 1; 557 } 558 559 int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) { 560 if (!BN_lshift1(r, a)) { 561 return 0; 562 } 563 564 return BN_nnmod(r, r, m, ctx); 565 } 566 567 int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) { 568 if (!BN_lshift1(r, a)) { 569 return 0; 570 } 571 if (BN_cmp(r, m) >= 0) { 572 return BN_sub(r, r, m); 573 } 574 575 return 1; 576 } 577 578 BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w) { 579 BN_ULONG ret = 0; 580 int i, j; 581 582 if (!w) { 583 // actually this an error (division by zero) 584 return (BN_ULONG) - 1; 585 } 586 587 if (a->top == 0) { 588 return 0; 589 } 590 591 // normalize input for |bn_div_rem_words|. 592 j = BN_BITS2 - BN_num_bits_word(w); 593 w <<= j; 594 if (!BN_lshift(a, a, j)) { 595 return (BN_ULONG) - 1; 596 } 597 598 for (i = a->top - 1; i >= 0; i--) { 599 BN_ULONG l = a->d[i]; 600 BN_ULONG d; 601 BN_ULONG unused_rem; 602 bn_div_rem_words(&d, &unused_rem, ret, l, w); 603 ret = l - (d * w); 604 a->d[i] = d; 605 } 606 607 if ((a->top > 0) && (a->d[a->top - 1] == 0)) { 608 a->top--; 609 } 610 611 if (a->top == 0) { 612 a->neg = 0; 613 } 614 615 ret >>= j; 616 return ret; 617 } 618 619 BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w) { 620 #ifndef BN_CAN_DIVIDE_ULLONG 621 BN_ULONG ret = 0; 622 #else 623 BN_ULLONG ret = 0; 624 #endif 625 int i; 626 627 if (w == 0) { 628 return (BN_ULONG) -1; 629 } 630 631 #ifndef BN_CAN_DIVIDE_ULLONG 632 // If |w| is too long and we don't have |BN_ULLONG| division then we need to 633 // fall back to using |BN_div_word|. 634 if (w > ((BN_ULONG)1 << BN_BITS4)) { 635 BIGNUM *tmp = BN_dup(a); 636 if (tmp == NULL) { 637 return (BN_ULONG)-1; 638 } 639 ret = BN_div_word(tmp, w); 640 BN_free(tmp); 641 return ret; 642 } 643 #endif 644 645 for (i = a->top - 1; i >= 0; i--) { 646 #ifndef BN_CAN_DIVIDE_ULLONG 647 ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w; 648 ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w; 649 #else 650 ret = (BN_ULLONG)(((ret << (BN_ULLONG)BN_BITS2) | a->d[i]) % (BN_ULLONG)w); 651 #endif 652 } 653 return (BN_ULONG)ret; 654 } 655 656 int BN_mod_pow2(BIGNUM *r, const BIGNUM *a, size_t e) { 657 if (e == 0 || a->top == 0) { 658 BN_zero(r); 659 return 1; 660 } 661 662 size_t num_words = 1 + ((e - 1) / BN_BITS2); 663 664 // If |a| definitely has less than |e| bits, just BN_copy. 665 if ((size_t) a->top < num_words) { 666 return BN_copy(r, a) != NULL; 667 } 668 669 // Otherwise, first make sure we have enough space in |r|. 670 // Note that this will fail if num_words > INT_MAX. 671 if (!bn_wexpand(r, num_words)) { 672 return 0; 673 } 674 675 // Copy the content of |a| into |r|. 676 OPENSSL_memcpy(r->d, a->d, num_words * sizeof(BN_ULONG)); 677 678 // If |e| isn't word-aligned, we have to mask off some of our bits. 679 size_t top_word_exponent = e % (sizeof(BN_ULONG) * 8); 680 if (top_word_exponent != 0) { 681 r->d[num_words - 1] &= (((BN_ULONG) 1) << top_word_exponent) - 1; 682 } 683 684 // Fill in the remaining fields of |r|. 685 r->neg = a->neg; 686 r->top = (int) num_words; 687 bn_correct_top(r); 688 return 1; 689 } 690 691 int BN_nnmod_pow2(BIGNUM *r, const BIGNUM *a, size_t e) { 692 if (!BN_mod_pow2(r, a, e)) { 693 return 0; 694 } 695 696 // If the returned value was non-negative, we're done. 697 if (BN_is_zero(r) || !r->neg) { 698 return 1; 699 } 700 701 size_t num_words = 1 + (e - 1) / BN_BITS2; 702 703 // Expand |r| to the size of our modulus. 704 if (!bn_wexpand(r, num_words)) { 705 return 0; 706 } 707 708 // Clear the upper words of |r|. 709 OPENSSL_memset(&r->d[r->top], 0, (num_words - r->top) * BN_BYTES); 710 711 // Set parameters of |r|. 712 r->neg = 0; 713 r->top = (int) num_words; 714 715 // Now, invert every word. The idea here is that we want to compute 2^e-|x|, 716 // which is actually equivalent to the twos-complement representation of |x| 717 // in |e| bits, which is -x = ~x + 1. 718 for (int i = 0; i < r->top; i++) { 719 r->d[i] = ~r->d[i]; 720 } 721 722 // If our exponent doesn't span the top word, we have to mask the rest. 723 size_t top_word_exponent = e % BN_BITS2; 724 if (top_word_exponent != 0) { 725 r->d[r->top - 1] &= (((BN_ULONG) 1) << top_word_exponent) - 1; 726 } 727 728 // Keep the correct_top invariant for BN_add. 729 bn_correct_top(r); 730 731 // Finally, add one, for the reason described above. 732 return BN_add(r, r, BN_value_one()); 733 } 734