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