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_CAN_DIVIDE_ULLONG) && !defined(BN_CAN_USE_INLINE_ASM) 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_CAN_DIVIDE_ULLONG) && !defined(BN_CAN_USE_INLINE_ASM) 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(BN_CAN_USE_INLINE_ASM) && defined(OPENSSL_X86) 159 __asm__ volatile("divl %4" 160 : "=a"(*quotient_out), "=d"(*rem_out) 161 : "a"(n1), "d"(n0), "rm"(d0) 162 : "cc"); 163 #elif defined(BN_CAN_USE_INLINE_ASM) && defined(OPENSSL_X86_64) 164 __asm__ volatile("divq %4" 165 : "=a"(*quotient_out), "=d"(*rem_out) 166 : "a"(n1), "d"(n0), "rm"(d0) 167 : "cc"); 168 #else 169 #if defined(BN_CAN_DIVIDE_ULLONG) 170 BN_ULLONG n = (((BN_ULLONG)n0) << BN_BITS2) | n1; 171 *quotient_out = (BN_ULONG)(n / d0); 172 #else 173 *quotient_out = bn_div_words(n0, n1, d0); 174 #endif 175 *rem_out = n1 - (*quotient_out * d0); 176 #endif 177 } 178 179 // BN_div computes "quotient := numerator / divisor", rounding towards zero, 180 // and sets up |rem| such that "quotient * divisor + rem = numerator" holds. 181 // 182 // Thus: 183 // 184 // quotient->neg == numerator->neg ^ divisor->neg 185 // (unless the result is zero) 186 // rem->neg == numerator->neg 187 // (unless the remainder is zero) 188 // 189 // If |quotient| or |rem| is NULL, the respective value is not returned. 190 // 191 // This was specifically designed to contain fewer branches that may leak 192 // sensitive information; see "New Branch Prediction Vulnerabilities in OpenSSL 193 // and Necessary Software Countermeasures" by Onur Acmez, Shay Gueron, and 194 // Jean-Pierre Seifert. 195 int BN_div(BIGNUM *quotient, BIGNUM *rem, const BIGNUM *numerator, 196 const BIGNUM *divisor, BN_CTX *ctx) { 197 int norm_shift, loop; 198 BIGNUM wnum; 199 BN_ULONG *resp, *wnump; 200 BN_ULONG d0, d1; 201 int num_n, div_n; 202 203 // This function relies on the historical minimal-width |BIGNUM| invariant. 204 // It is already not constant-time (constant-time reductions should use 205 // Montgomery logic), so we shrink all inputs and intermediate values to 206 // retain the previous behavior. 207 208 // Invalid zero-padding would have particularly bad consequences. 209 int numerator_width = bn_minimal_width(numerator); 210 int divisor_width = bn_minimal_width(divisor); 211 if ((numerator_width > 0 && numerator->d[numerator_width - 1] == 0) || 212 (divisor_width > 0 && divisor->d[divisor_width - 1] == 0)) { 213 OPENSSL_PUT_ERROR(BN, BN_R_NOT_INITIALIZED); 214 return 0; 215 } 216 217 if (BN_is_zero(divisor)) { 218 OPENSSL_PUT_ERROR(BN, BN_R_DIV_BY_ZERO); 219 return 0; 220 } 221 222 BN_CTX_start(ctx); 223 BIGNUM *tmp = BN_CTX_get(ctx); 224 BIGNUM *snum = BN_CTX_get(ctx); 225 BIGNUM *sdiv = BN_CTX_get(ctx); 226 BIGNUM *res = NULL; 227 if (quotient == NULL) { 228 res = BN_CTX_get(ctx); 229 } else { 230 res = quotient; 231 } 232 if (sdiv == NULL || res == NULL) { 233 goto err; 234 } 235 236 // First we normalise the numbers 237 norm_shift = BN_BITS2 - (BN_num_bits(divisor) % BN_BITS2); 238 if (!BN_lshift(sdiv, divisor, norm_shift)) { 239 goto err; 240 } 241 bn_set_minimal_width(sdiv); 242 sdiv->neg = 0; 243 norm_shift += BN_BITS2; 244 if (!BN_lshift(snum, numerator, norm_shift)) { 245 goto err; 246 } 247 bn_set_minimal_width(snum); 248 snum->neg = 0; 249 250 // Since we don't want to have special-case logic for the case where snum is 251 // larger than sdiv, we pad snum with enough zeroes without changing its 252 // value. 253 if (snum->width <= sdiv->width + 1) { 254 if (!bn_wexpand(snum, sdiv->width + 2)) { 255 goto err; 256 } 257 for (int i = snum->width; i < sdiv->width + 2; i++) { 258 snum->d[i] = 0; 259 } 260 snum->width = sdiv->width + 2; 261 } else { 262 if (!bn_wexpand(snum, snum->width + 1)) { 263 goto err; 264 } 265 snum->d[snum->width] = 0; 266 snum->width++; 267 } 268 269 div_n = sdiv->width; 270 num_n = snum->width; 271 loop = num_n - div_n; 272 // Lets setup a 'window' into snum 273 // This is the part that corresponds to the current 274 // 'area' being divided 275 wnum.neg = 0; 276 wnum.d = &(snum->d[loop]); 277 wnum.width = div_n; 278 // only needed when BN_ucmp messes up the values between width and max 279 wnum.dmax = snum->dmax - loop; // so we don't step out of bounds 280 281 // Get the top 2 words of sdiv 282 // div_n=sdiv->width; 283 d0 = sdiv->d[div_n - 1]; 284 d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2]; 285 286 // pointer to the 'top' of snum 287 wnump = &(snum->d[num_n - 1]); 288 289 // Setup to 'res' 290 res->neg = (numerator->neg ^ divisor->neg); 291 if (!bn_wexpand(res, loop + 1)) { 292 goto err; 293 } 294 res->width = loop - 1; 295 resp = &(res->d[loop - 1]); 296 297 // space for temp 298 if (!bn_wexpand(tmp, div_n + 1)) { 299 goto err; 300 } 301 302 // if res->width == 0 then clear the neg value otherwise decrease 303 // the resp pointer 304 if (res->width == 0) { 305 res->neg = 0; 306 } else { 307 resp--; 308 } 309 310 for (int i = 0; i < loop - 1; i++, wnump--, resp--) { 311 BN_ULONG q, l0; 312 // the first part of the loop uses the top two words of snum and sdiv to 313 // calculate a BN_ULONG q such that | wnum - sdiv * q | < sdiv 314 BN_ULONG n0, n1, rm = 0; 315 316 n0 = wnump[0]; 317 n1 = wnump[-1]; 318 if (n0 == d0) { 319 q = BN_MASK2; 320 } else { 321 // n0 < d0 322 bn_div_rem_words(&q, &rm, n0, n1, d0); 323 324 #ifdef BN_ULLONG 325 BN_ULLONG t2 = (BN_ULLONG)d1 * q; 326 for (;;) { 327 if (t2 <= ((((BN_ULLONG)rm) << BN_BITS2) | wnump[-2])) { 328 break; 329 } 330 q--; 331 rm += d0; 332 if (rm < d0) { 333 break; // don't let rm overflow 334 } 335 t2 -= d1; 336 } 337 #else // !BN_ULLONG 338 BN_ULONG t2l, t2h; 339 BN_UMULT_LOHI(t2l, t2h, d1, q); 340 for (;;) { 341 if (t2h < rm || 342 (t2h == rm && t2l <= wnump[-2])) { 343 break; 344 } 345 q--; 346 rm += d0; 347 if (rm < d0) { 348 break; // don't let rm overflow 349 } 350 if (t2l < d1) { 351 t2h--; 352 } 353 t2l -= d1; 354 } 355 #endif // !BN_ULLONG 356 } 357 358 l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q); 359 tmp->d[div_n] = l0; 360 wnum.d--; 361 // ingore top values of the bignums just sub the two 362 // BN_ULONG arrays with bn_sub_words 363 if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) { 364 // Note: As we have considered only the leading 365 // two BN_ULONGs in the calculation of q, sdiv * q 366 // might be greater than wnum (but then (q-1) * sdiv 367 // is less or equal than wnum) 368 q--; 369 if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) { 370 // we can't have an overflow here (assuming 371 // that q != 0, but if q == 0 then tmp is 372 // zero anyway) 373 (*wnump)++; 374 } 375 } 376 // store part of the result 377 *resp = q; 378 } 379 380 bn_set_minimal_width(snum); 381 382 if (rem != NULL) { 383 // Keep a copy of the neg flag in numerator because if |rem| == |numerator| 384 // |BN_rshift| will overwrite it. 385 int neg = numerator->neg; 386 if (!BN_rshift(rem, snum, norm_shift)) { 387 goto err; 388 } 389 if (!BN_is_zero(rem)) { 390 rem->neg = neg; 391 } 392 } 393 394 bn_set_minimal_width(res); 395 BN_CTX_end(ctx); 396 return 1; 397 398 err: 399 BN_CTX_end(ctx); 400 return 0; 401 } 402 403 int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) { 404 if (!(BN_mod(r, m, d, ctx))) { 405 return 0; 406 } 407 if (!r->neg) { 408 return 1; 409 } 410 411 // now -|d| < r < 0, so we have to set r := r + |d|. 412 return (d->neg ? BN_sub : BN_add)(r, r, d); 413 } 414 415 BN_ULONG bn_reduce_once(BN_ULONG *r, const BN_ULONG *a, BN_ULONG carry, 416 const BN_ULONG *m, size_t num) { 417 assert(r != a); 418 // |r| = |a| - |m|. |bn_sub_words| performs the bulk of the subtraction, and 419 // then we apply the borrow to |carry|. 420 carry -= bn_sub_words(r, a, m, num); 421 // We know 0 <= |a| < 2*|m|, so -|m| <= |r| < |m|. 422 // 423 // If 0 <= |r| < |m|, |r| fits in |num| words and |carry| is zero. We then 424 // wish to select |r| as the answer. Otherwise -m <= r < 0 and we wish to 425 // return |r| + |m|, or |a|. |carry| must then be -1 or all ones. In both 426 // cases, |carry| is a suitable input to |bn_select_words|. 427 // 428 // Although |carry| may be one if it was one on input and |bn_sub_words| 429 // returns zero, this would give |r| > |m|, violating our input assumptions. 430 assert(carry == 0 || carry == (BN_ULONG)-1); 431 bn_select_words(r, carry, a /* r < 0 */, r /* r >= 0 */, num); 432 return carry; 433 } 434 435 BN_ULONG bn_reduce_once_in_place(BN_ULONG *r, BN_ULONG carry, const BN_ULONG *m, 436 BN_ULONG *tmp, size_t num) { 437 // See |bn_reduce_once| for why this logic works. 438 carry -= bn_sub_words(tmp, r, m, num); 439 assert(carry == 0 || carry == (BN_ULONG)-1); 440 bn_select_words(r, carry, r /* tmp < 0 */, tmp /* tmp >= 0 */, num); 441 return carry; 442 } 443 444 void bn_mod_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, 445 const BN_ULONG *m, BN_ULONG *tmp, size_t num) { 446 // r = a - b 447 BN_ULONG borrow = bn_sub_words(r, a, b, num); 448 // tmp = a - b + m 449 bn_add_words(tmp, r, m, num); 450 bn_select_words(r, 0 - borrow, tmp /* r < 0 */, r /* r >= 0 */, num); 451 } 452 453 void bn_mod_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, 454 const BN_ULONG *m, BN_ULONG *tmp, size_t num) { 455 BN_ULONG carry = bn_add_words(r, a, b, num); 456 bn_reduce_once_in_place(r, carry, m, tmp, num); 457 } 458 459 int bn_div_consttime(BIGNUM *quotient, BIGNUM *remainder, 460 const BIGNUM *numerator, const BIGNUM *divisor, 461 BN_CTX *ctx) { 462 if (BN_is_negative(numerator) || BN_is_negative(divisor)) { 463 OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); 464 return 0; 465 } 466 if (BN_is_zero(divisor)) { 467 OPENSSL_PUT_ERROR(BN, BN_R_DIV_BY_ZERO); 468 return 0; 469 } 470 471 // This function implements long division in binary. It is not very efficient, 472 // but it is simple, easy to make constant-time, and performant enough for RSA 473 // key generation. 474 475 int ret = 0; 476 BN_CTX_start(ctx); 477 BIGNUM *q = quotient, *r = remainder; 478 if (quotient == NULL || quotient == numerator || quotient == divisor) { 479 q = BN_CTX_get(ctx); 480 } 481 if (remainder == NULL || remainder == numerator || remainder == divisor) { 482 r = BN_CTX_get(ctx); 483 } 484 BIGNUM *tmp = BN_CTX_get(ctx); 485 if (q == NULL || r == NULL || tmp == NULL || 486 !bn_wexpand(q, numerator->width) || 487 !bn_wexpand(r, divisor->width) || 488 !bn_wexpand(tmp, divisor->width)) { 489 goto err; 490 } 491 492 OPENSSL_memset(q->d, 0, numerator->width * sizeof(BN_ULONG)); 493 q->width = numerator->width; 494 q->neg = 0; 495 496 OPENSSL_memset(r->d, 0, divisor->width * sizeof(BN_ULONG)); 497 r->width = divisor->width; 498 r->neg = 0; 499 500 // Incorporate |numerator| into |r|, one bit at a time, reducing after each 501 // step. At the start of each loop iteration, |r| < |divisor| 502 for (int i = numerator->width - 1; i >= 0; i--) { 503 for (int bit = BN_BITS2 - 1; bit >= 0; bit--) { 504 // Incorporate the next bit of the numerator, by computing 505 // r = 2*r or 2*r + 1. Note the result fits in one more word. We store the 506 // extra word in |carry|. 507 BN_ULONG carry = bn_add_words(r->d, r->d, r->d, divisor->width); 508 r->d[0] |= (numerator->d[i] >> bit) & 1; 509 // |r| was previously fully-reduced, so we know: 510 // 2*0 <= r <= 2*(divisor-1) + 1 511 // 0 <= r <= 2*divisor - 1 < 2*divisor. 512 // Thus |r| satisfies the preconditions for |bn_reduce_once_in_place|. 513 BN_ULONG subtracted = bn_reduce_once_in_place(r->d, carry, divisor->d, 514 tmp->d, divisor->width); 515 // The corresponding bit of the quotient is set iff we needed to subtract. 516 q->d[i] |= (~subtracted & 1) << bit; 517 } 518 } 519 520 if ((quotient != NULL && !BN_copy(quotient, q)) || 521 (remainder != NULL && !BN_copy(remainder, r))) { 522 goto err; 523 } 524 525 ret = 1; 526 527 err: 528 BN_CTX_end(ctx); 529 return ret; 530 } 531 532 static BIGNUM *bn_scratch_space_from_ctx(size_t width, BN_CTX *ctx) { 533 BIGNUM *ret = BN_CTX_get(ctx); 534 if (ret == NULL || 535 !bn_wexpand(ret, width)) { 536 return NULL; 537 } 538 ret->neg = 0; 539 ret->width = width; 540 return ret; 541 } 542 543 // bn_resized_from_ctx returns |bn| with width at least |width| or NULL on 544 // error. This is so it may be used with low-level "words" functions. If 545 // necessary, it allocates a new |BIGNUM| with a lifetime of the current scope 546 // in |ctx|, so the caller does not need to explicitly free it. |bn| must fit in 547 // |width| words. 548 static const BIGNUM *bn_resized_from_ctx(const BIGNUM *bn, size_t width, 549 BN_CTX *ctx) { 550 if ((size_t)bn->width >= width) { 551 // Any excess words must be zero. 552 assert(bn_fits_in_words(bn, width)); 553 return bn; 554 } 555 BIGNUM *ret = bn_scratch_space_from_ctx(width, ctx); 556 if (ret == NULL || 557 !BN_copy(ret, bn) || 558 !bn_resize_words(ret, width)) { 559 return NULL; 560 } 561 return ret; 562 } 563 564 int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 565 BN_CTX *ctx) { 566 if (!BN_add(r, a, b)) { 567 return 0; 568 } 569 return BN_nnmod(r, r, m, ctx); 570 } 571 572 int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 573 const BIGNUM *m) { 574 BN_CTX *ctx = BN_CTX_new(); 575 int ok = ctx != NULL && 576 bn_mod_add_consttime(r, a, b, m, ctx); 577 BN_CTX_free(ctx); 578 return ok; 579 } 580 581 int bn_mod_add_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 582 const BIGNUM *m, BN_CTX *ctx) { 583 BN_CTX_start(ctx); 584 a = bn_resized_from_ctx(a, m->width, ctx); 585 b = bn_resized_from_ctx(b, m->width, ctx); 586 BIGNUM *tmp = bn_scratch_space_from_ctx(m->width, ctx); 587 int ok = a != NULL && b != NULL && tmp != NULL && 588 bn_wexpand(r, m->width); 589 if (ok) { 590 bn_mod_add_words(r->d, a->d, b->d, m->d, tmp->d, m->width); 591 r->width = m->width; 592 r->neg = 0; 593 } 594 BN_CTX_end(ctx); 595 return ok; 596 } 597 598 int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 599 BN_CTX *ctx) { 600 if (!BN_sub(r, a, b)) { 601 return 0; 602 } 603 return BN_nnmod(r, r, m, ctx); 604 } 605 606 int bn_mod_sub_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 607 const BIGNUM *m, BN_CTX *ctx) { 608 BN_CTX_start(ctx); 609 a = bn_resized_from_ctx(a, m->width, ctx); 610 b = bn_resized_from_ctx(b, m->width, ctx); 611 BIGNUM *tmp = bn_scratch_space_from_ctx(m->width, ctx); 612 int ok = a != NULL && b != NULL && tmp != NULL && 613 bn_wexpand(r, m->width); 614 if (ok) { 615 bn_mod_sub_words(r->d, a->d, b->d, m->d, tmp->d, m->width); 616 r->width = m->width; 617 r->neg = 0; 618 } 619 BN_CTX_end(ctx); 620 return ok; 621 } 622 623 int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 624 const BIGNUM *m) { 625 BN_CTX *ctx = BN_CTX_new(); 626 int ok = ctx != NULL && 627 bn_mod_sub_consttime(r, a, b, m, ctx); 628 BN_CTX_free(ctx); 629 return ok; 630 } 631 632 int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 633 BN_CTX *ctx) { 634 BIGNUM *t; 635 int ret = 0; 636 637 BN_CTX_start(ctx); 638 t = BN_CTX_get(ctx); 639 if (t == NULL) { 640 goto err; 641 } 642 643 if (a == b) { 644 if (!BN_sqr(t, a, ctx)) { 645 goto err; 646 } 647 } else { 648 if (!BN_mul(t, a, b, ctx)) { 649 goto err; 650 } 651 } 652 653 if (!BN_nnmod(r, t, m, ctx)) { 654 goto err; 655 } 656 657 ret = 1; 658 659 err: 660 BN_CTX_end(ctx); 661 return ret; 662 } 663 664 int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) { 665 if (!BN_sqr(r, a, ctx)) { 666 return 0; 667 } 668 669 // r->neg == 0, thus we don't need BN_nnmod 670 return BN_mod(r, r, m, ctx); 671 } 672 673 int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, 674 BN_CTX *ctx) { 675 BIGNUM *abs_m = NULL; 676 int ret; 677 678 if (!BN_nnmod(r, a, m, ctx)) { 679 return 0; 680 } 681 682 if (m->neg) { 683 abs_m = BN_dup(m); 684 if (abs_m == NULL) { 685 return 0; 686 } 687 abs_m->neg = 0; 688 } 689 690 ret = bn_mod_lshift_consttime(r, r, n, (abs_m ? abs_m : m), ctx); 691 692 BN_free(abs_m); 693 return ret; 694 } 695 696 int bn_mod_lshift_consttime(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, 697 BN_CTX *ctx) { 698 if (!BN_copy(r, a)) { 699 return 0; 700 } 701 for (int i = 0; i < n; i++) { 702 if (!bn_mod_lshift1_consttime(r, r, m, ctx)) { 703 return 0; 704 } 705 } 706 return 1; 707 } 708 709 int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) { 710 BN_CTX *ctx = BN_CTX_new(); 711 int ok = ctx != NULL && 712 bn_mod_lshift_consttime(r, a, n, m, ctx); 713 BN_CTX_free(ctx); 714 return ok; 715 } 716 717 int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) { 718 if (!BN_lshift1(r, a)) { 719 return 0; 720 } 721 722 return BN_nnmod(r, r, m, ctx); 723 } 724 725 int bn_mod_lshift1_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, 726 BN_CTX *ctx) { 727 return bn_mod_add_consttime(r, a, a, m, ctx); 728 } 729 730 int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) { 731 BN_CTX *ctx = BN_CTX_new(); 732 int ok = ctx != NULL && 733 bn_mod_lshift1_consttime(r, a, m, ctx); 734 BN_CTX_free(ctx); 735 return ok; 736 } 737 738 BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w) { 739 BN_ULONG ret = 0; 740 int i, j; 741 742 if (!w) { 743 // actually this an error (division by zero) 744 return (BN_ULONG) - 1; 745 } 746 747 if (a->width == 0) { 748 return 0; 749 } 750 751 // normalize input for |bn_div_rem_words|. 752 j = BN_BITS2 - BN_num_bits_word(w); 753 w <<= j; 754 if (!BN_lshift(a, a, j)) { 755 return (BN_ULONG) - 1; 756 } 757 758 for (i = a->width - 1; i >= 0; i--) { 759 BN_ULONG l = a->d[i]; 760 BN_ULONG d; 761 BN_ULONG unused_rem; 762 bn_div_rem_words(&d, &unused_rem, ret, l, w); 763 ret = l - (d * w); 764 a->d[i] = d; 765 } 766 767 bn_set_minimal_width(a); 768 ret >>= j; 769 return ret; 770 } 771 772 BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w) { 773 #ifndef BN_CAN_DIVIDE_ULLONG 774 BN_ULONG ret = 0; 775 #else 776 BN_ULLONG ret = 0; 777 #endif 778 int i; 779 780 if (w == 0) { 781 return (BN_ULONG) -1; 782 } 783 784 #ifndef BN_CAN_DIVIDE_ULLONG 785 // If |w| is too long and we don't have |BN_ULLONG| division then we need to 786 // fall back to using |BN_div_word|. 787 if (w > ((BN_ULONG)1 << BN_BITS4)) { 788 BIGNUM *tmp = BN_dup(a); 789 if (tmp == NULL) { 790 return (BN_ULONG)-1; 791 } 792 ret = BN_div_word(tmp, w); 793 BN_free(tmp); 794 return ret; 795 } 796 #endif 797 798 for (i = a->width - 1; i >= 0; i--) { 799 #ifndef BN_CAN_DIVIDE_ULLONG 800 ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w; 801 ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w; 802 #else 803 ret = (BN_ULLONG)(((ret << (BN_ULLONG)BN_BITS2) | a->d[i]) % (BN_ULLONG)w); 804 #endif 805 } 806 return (BN_ULONG)ret; 807 } 808 809 int BN_mod_pow2(BIGNUM *r, const BIGNUM *a, size_t e) { 810 if (e == 0 || a->width == 0) { 811 BN_zero(r); 812 return 1; 813 } 814 815 size_t num_words = 1 + ((e - 1) / BN_BITS2); 816 817 // If |a| definitely has less than |e| bits, just BN_copy. 818 if ((size_t) a->width < num_words) { 819 return BN_copy(r, a) != NULL; 820 } 821 822 // Otherwise, first make sure we have enough space in |r|. 823 // Note that this will fail if num_words > INT_MAX. 824 if (!bn_wexpand(r, num_words)) { 825 return 0; 826 } 827 828 // Copy the content of |a| into |r|. 829 OPENSSL_memcpy(r->d, a->d, num_words * sizeof(BN_ULONG)); 830 831 // If |e| isn't word-aligned, we have to mask off some of our bits. 832 size_t top_word_exponent = e % (sizeof(BN_ULONG) * 8); 833 if (top_word_exponent != 0) { 834 r->d[num_words - 1] &= (((BN_ULONG) 1) << top_word_exponent) - 1; 835 } 836 837 // Fill in the remaining fields of |r|. 838 r->neg = a->neg; 839 r->width = (int) num_words; 840 bn_set_minimal_width(r); 841 return 1; 842 } 843 844 int BN_nnmod_pow2(BIGNUM *r, const BIGNUM *a, size_t e) { 845 if (!BN_mod_pow2(r, a, e)) { 846 return 0; 847 } 848 849 // If the returned value was non-negative, we're done. 850 if (BN_is_zero(r) || !r->neg) { 851 return 1; 852 } 853 854 size_t num_words = 1 + (e - 1) / BN_BITS2; 855 856 // Expand |r| to the size of our modulus. 857 if (!bn_wexpand(r, num_words)) { 858 return 0; 859 } 860 861 // Clear the upper words of |r|. 862 OPENSSL_memset(&r->d[r->width], 0, (num_words - r->width) * BN_BYTES); 863 864 // Set parameters of |r|. 865 r->neg = 0; 866 r->width = (int) num_words; 867 868 // Now, invert every word. The idea here is that we want to compute 2^e-|x|, 869 // which is actually equivalent to the twos-complement representation of |x| 870 // in |e| bits, which is -x = ~x + 1. 871 for (int i = 0; i < r->width; i++) { 872 r->d[i] = ~r->d[i]; 873 } 874 875 // If our exponent doesn't span the top word, we have to mask the rest. 876 size_t top_word_exponent = e % BN_BITS2; 877 if (top_word_exponent != 0) { 878 r->d[r->width - 1] &= (((BN_ULONG) 1) << top_word_exponent) - 1; 879 } 880 881 // Keep the minimal-width invariant for |BIGNUM|. 882 bn_set_minimal_width(r); 883 884 // Finally, add one, for the reason described above. 885 return BN_add(r, r, BN_value_one()); 886 } 887