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#include <openssl/bn.h> 58 59#include <limits.h> 60#include <openssl/err.h> 61 62#include "internal.h" 63 64 65#define asm __asm__ 66 67#if !defined(OPENSSL_NO_ASM) 68# if defined(__GNUC__) && __GNUC__>=2 69# if defined(OPENSSL_X86) 70 /* 71 * There were two reasons for implementing this template: 72 * - GNU C generates a call to a function (__udivdi3 to be exact) 73 * in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to 74 * understand why...); 75 * - divl doesn't only calculate quotient, but also leaves 76 * remainder in %edx which we can definitely use here:-) 77 * 78 * <appro@fy.chalmers.se> 79 */ 80#undef div_asm 81# define div_asm(n0,n1,d0) \ 82 ({ asm volatile ( \ 83 "divl %4" \ 84 : "=a"(q), "=d"(rem) \ 85 : "a"(n1), "d"(n0), "g"(d0) \ 86 : "cc"); \ 87 q; \ 88 }) 89# define REMAINDER_IS_ALREADY_CALCULATED 90# elif defined(OPENSSL_X86_64) 91 /* 92 * Same story here, but it's 128-bit by 64-bit division. Wow! 93 * <appro@fy.chalmers.se> 94 */ 95# undef div_asm 96# define div_asm(n0,n1,d0) \ 97 ({ asm volatile ( \ 98 "divq %4" \ 99 : "=a"(q), "=d"(rem) \ 100 : "a"(n1), "d"(n0), "g"(d0) \ 101 : "cc"); \ 102 q; \ 103 }) 104# define REMAINDER_IS_ALREADY_CALCULATED 105# endif /* __<cpu> */ 106# endif /* __GNUC__ */ 107#endif /* OPENSSL_NO_ASM */ 108 109/* BN_div computes dv := num / divisor, rounding towards 110 * zero, and sets up rm such that dv*divisor + rm = num holds. 111 * Thus: 112 * dv->neg == num->neg ^ divisor->neg (unless the result is zero) 113 * rm->neg == num->neg (unless the remainder is zero) 114 * If 'dv' or 'rm' is NULL, the respective value is not returned. */ 115int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, 116 BN_CTX *ctx) { 117 int norm_shift, i, loop; 118 BIGNUM *tmp, wnum, *snum, *sdiv, *res; 119 BN_ULONG *resp, *wnump; 120 BN_ULONG d0, d1; 121 int num_n, div_n; 122 int no_branch = 0; 123 124 /* Invalid zero-padding would have particularly bad consequences 125 * so don't just rely on bn_check_top() here */ 126 if ((num->top > 0 && num->d[num->top - 1] == 0) || 127 (divisor->top > 0 && divisor->d[divisor->top - 1] == 0)) { 128 OPENSSL_PUT_ERROR(BN, BN_div, BN_R_NOT_INITIALIZED); 129 return 0; 130 } 131 132 if ((num->flags & BN_FLG_CONSTTIME) != 0 || 133 (divisor->flags & BN_FLG_CONSTTIME) != 0) { 134 no_branch = 1; 135 } 136 137 if (BN_is_zero(divisor)) { 138 OPENSSL_PUT_ERROR(BN, BN_div, BN_R_DIV_BY_ZERO); 139 return 0; 140 } 141 142 if (!no_branch && BN_ucmp(num, divisor) < 0) { 143 if (rm != NULL) { 144 if (BN_copy(rm, num) == NULL) { 145 return 0; 146 } 147 } 148 if (dv != NULL) { 149 BN_zero(dv); 150 } 151 return 1; 152 } 153 154 BN_CTX_start(ctx); 155 tmp = BN_CTX_get(ctx); 156 snum = BN_CTX_get(ctx); 157 sdiv = BN_CTX_get(ctx); 158 if (dv == NULL) { 159 res = BN_CTX_get(ctx); 160 } else { 161 res = dv; 162 } 163 if (sdiv == NULL || res == NULL || tmp == NULL || snum == NULL) { 164 goto err; 165 } 166 167 /* First we normalise the numbers */ 168 norm_shift = BN_BITS2 - ((BN_num_bits(divisor)) % BN_BITS2); 169 if (!(BN_lshift(sdiv, divisor, norm_shift))) { 170 goto err; 171 } 172 sdiv->neg = 0; 173 norm_shift += BN_BITS2; 174 if (!(BN_lshift(snum, num, norm_shift))) { 175 goto err; 176 } 177 snum->neg = 0; 178 179 if (no_branch) { 180 /* Since we don't know whether snum is larger than sdiv, 181 * we pad snum with enough zeroes without changing its 182 * value. 183 */ 184 if (snum->top <= sdiv->top + 1) { 185 if (bn_wexpand(snum, sdiv->top + 2) == NULL) { 186 goto err; 187 } 188 for (i = snum->top; i < sdiv->top + 2; i++) { 189 snum->d[i] = 0; 190 } 191 snum->top = sdiv->top + 2; 192 } else { 193 if (bn_wexpand(snum, snum->top + 1) == NULL) { 194 goto err; 195 } 196 snum->d[snum->top] = 0; 197 snum->top++; 198 } 199 } 200 201 div_n = sdiv->top; 202 num_n = snum->top; 203 loop = num_n - div_n; 204 /* Lets setup a 'window' into snum 205 * This is the part that corresponds to the current 206 * 'area' being divided */ 207 wnum.neg = 0; 208 wnum.d = &(snum->d[loop]); 209 wnum.top = div_n; 210 /* only needed when BN_ucmp messes up the values between top and max */ 211 wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */ 212 213 /* Get the top 2 words of sdiv */ 214 /* div_n=sdiv->top; */ 215 d0 = sdiv->d[div_n - 1]; 216 d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2]; 217 218 /* pointer to the 'top' of snum */ 219 wnump = &(snum->d[num_n - 1]); 220 221 /* Setup to 'res' */ 222 res->neg = (num->neg ^ divisor->neg); 223 if (!bn_wexpand(res, (loop + 1))) { 224 goto err; 225 } 226 res->top = loop - no_branch; 227 resp = &(res->d[loop - 1]); 228 229 /* space for temp */ 230 if (!bn_wexpand(tmp, (div_n + 1))) { 231 goto err; 232 } 233 234 if (!no_branch) { 235 if (BN_ucmp(&wnum, sdiv) >= 0) { 236 bn_sub_words(wnum.d, wnum.d, sdiv->d, div_n); 237 *resp = 1; 238 } else { 239 res->top--; 240 } 241 } 242 243 /* if res->top == 0 then clear the neg value otherwise decrease 244 * the resp pointer */ 245 if (res->top == 0) { 246 res->neg = 0; 247 } else { 248 resp--; 249 } 250 251 for (i = 0; i < loop - 1; i++, wnump--, resp--) { 252 BN_ULONG q, l0; 253 /* the first part of the loop uses the top two words of snum and sdiv to 254 * calculate a BN_ULONG q such that | wnum - sdiv * q | < sdiv */ 255 BN_ULONG n0, n1, rem = 0; 256 257 n0 = wnump[0]; 258 n1 = wnump[-1]; 259 if (n0 == d0) { 260 q = BN_MASK2; 261 } else { 262 /* n0 < d0 */ 263#ifdef BN_LLONG 264 BN_ULLONG t2; 265 266#if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(div_asm) 267 q = (BN_ULONG)(((((BN_ULLONG)n0) << BN_BITS2) | n1) / d0); 268#else 269 q = div_asm(n0, n1, d0); 270#endif 271 272#ifndef REMAINDER_IS_ALREADY_CALCULATED 273 /* rem doesn't have to be BN_ULLONG. The least we know it's less that d0, 274 * isn't it? */ 275 rem = (n1 - q * d0) & BN_MASK2; 276#endif 277 278 t2 = (BN_ULLONG)d1 * q; 279 280 for (;;) { 281 if (t2 <= ((((BN_ULLONG)rem) << BN_BITS2) | wnump[-2])) 282 break; 283 q--; 284 rem += d0; 285 if (rem < d0) 286 break; /* don't let rem overflow */ 287 t2 -= d1; 288 } 289#else /* !BN_LLONG */ 290 BN_ULONG t2l, t2h; 291 292#if defined(div_asm) 293 q = div_asm(n0, n1, d0); 294#else 295 q = bn_div_words(n0, n1, d0); 296#endif 297 298#ifndef REMAINDER_IS_ALREADY_CALCULATED 299 rem = (n1 - q * d0) & BN_MASK2; 300#endif 301 302#if defined(BN_UMULT_LOHI) 303 BN_UMULT_LOHI(t2l, t2h, d1, q); 304#elif defined(BN_UMULT_HIGH) 305 t2l = d1 * q; 306 t2h = BN_UMULT_HIGH(d1, q); 307#else 308 { 309 BN_ULONG ql, qh; 310 t2l = LBITS(d1); 311 t2h = HBITS(d1); 312 ql = LBITS(q); 313 qh = HBITS(q); 314 mul64(t2l, t2h, ql, qh); /* t2=(BN_ULLONG)d1*q; */ 315 } 316#endif 317 318 for (;;) { 319 if ((t2h < rem) || ((t2h == rem) && (t2l <= wnump[-2]))) 320 break; 321 q--; 322 rem += d0; 323 if (rem < d0) 324 break; /* don't let rem overflow */ 325 if (t2l < d1) 326 t2h--; 327 t2l -= d1; 328 } 329#endif /* !BN_LLONG */ 330 } 331 332 l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q); 333 tmp->d[div_n] = l0; 334 wnum.d--; 335 /* ingore top values of the bignums just sub the two 336 * BN_ULONG arrays with bn_sub_words */ 337 if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) { 338 /* Note: As we have considered only the leading 339 * two BN_ULONGs in the calculation of q, sdiv * q 340 * might be greater than wnum (but then (q-1) * sdiv 341 * is less or equal than wnum) 342 */ 343 q--; 344 if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) { 345 /* we can't have an overflow here (assuming 346 * that q != 0, but if q == 0 then tmp is 347 * zero anyway) */ 348 (*wnump)++; 349 } 350 } 351 /* store part of the result */ 352 *resp = q; 353 } 354 bn_correct_top(snum); 355 if (rm != NULL) { 356 /* Keep a copy of the neg flag in num because if rm==num 357 * BN_rshift() will overwrite it. 358 */ 359 int neg = num->neg; 360 BN_rshift(rm, snum, norm_shift); 361 if (!BN_is_zero(rm)) { 362 rm->neg = neg; 363 } 364 } 365 if (no_branch) { 366 bn_correct_top(res); 367 } 368 BN_CTX_end(ctx); 369 return 1; 370 371err: 372 BN_CTX_end(ctx); 373 return 0; 374} 375 376int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) { 377 if (!(BN_mod(r, m, d, ctx))) { 378 return 0; 379 } 380 if (!r->neg) { 381 return 1; 382 } 383 384 /* now -|d| < r < 0, so we have to set r := r + |d|. */ 385 return (d->neg ? BN_sub : BN_add)(r, r, d); 386} 387 388int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 389 BN_CTX *ctx) { 390 if (!BN_add(r, a, b)) { 391 return 0; 392 } 393 return BN_nnmod(r, r, m, ctx); 394} 395 396int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 397 const BIGNUM *m) { 398 if (!BN_uadd(r, a, b)) { 399 return 0; 400 } 401 if (BN_ucmp(r, m) >= 0) { 402 return BN_usub(r, r, m); 403 } 404 return 1; 405} 406 407int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 408 BN_CTX *ctx) { 409 if (!BN_sub(r, a, b)) { 410 return 0; 411 } 412 return BN_nnmod(r, r, m, ctx); 413} 414 415/* BN_mod_sub variant that may be used if both a and b are non-negative 416 * and less than m */ 417int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 418 const BIGNUM *m) { 419 if (!BN_sub(r, a, b)) { 420 return 0; 421 } 422 if (r->neg) { 423 return BN_add(r, r, m); 424 } 425 return 1; 426} 427 428int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 429 BN_CTX *ctx) { 430 BIGNUM *t; 431 int ret = 0; 432 433 BN_CTX_start(ctx); 434 t = BN_CTX_get(ctx); 435 if (t == NULL) { 436 goto err; 437 } 438 439 if (a == b) { 440 if (!BN_sqr(t, a, ctx)) { 441 goto err; 442 } 443 } else { 444 if (!BN_mul(t, a, b, ctx)) { 445 goto err; 446 } 447 } 448 449 if (!BN_nnmod(r, t, m, ctx)) { 450 goto err; 451 } 452 453 ret = 1; 454 455err: 456 BN_CTX_end(ctx); 457 return ret; 458} 459 460int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) { 461 if (!BN_sqr(r, a, ctx)) { 462 return 0; 463 } 464 465 /* r->neg == 0, thus we don't need BN_nnmod */ 466 return BN_mod(r, r, m, ctx); 467} 468 469int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, 470 BN_CTX *ctx) { 471 BIGNUM *abs_m = NULL; 472 int ret; 473 474 if (!BN_nnmod(r, a, m, ctx)) { 475 return 0; 476 } 477 478 if (m->neg) { 479 abs_m = BN_dup(m); 480 if (abs_m == NULL) { 481 return 0; 482 } 483 abs_m->neg = 0; 484 } 485 486 ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); 487 488 if (abs_m) { 489 BN_free(abs_m); 490 } 491 return ret; 492} 493 494int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) { 495 if (r != a) { 496 if (BN_copy(r, a) == NULL) { 497 return 0; 498 } 499 } 500 501 while (n > 0) { 502 int max_shift; 503 504 /* 0 < r < m */ 505 max_shift = BN_num_bits(m) - BN_num_bits(r); 506 /* max_shift >= 0 */ 507 508 if (max_shift < 0) { 509 OPENSSL_PUT_ERROR(BN, BN_mod_lshift_quick, BN_R_INPUT_NOT_REDUCED); 510 return 0; 511 } 512 513 if (max_shift > n) { 514 max_shift = n; 515 } 516 517 if (max_shift) { 518 if (!BN_lshift(r, r, max_shift)) { 519 return 0; 520 } 521 n -= max_shift; 522 } else { 523 if (!BN_lshift1(r, r)) { 524 return 0; 525 } 526 --n; 527 } 528 529 /* BN_num_bits(r) <= BN_num_bits(m) */ 530 if (BN_cmp(r, m) >= 0) { 531 if (!BN_sub(r, r, m)) { 532 return 0; 533 } 534 } 535 } 536 537 return 1; 538} 539 540int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) { 541 if (!BN_lshift1(r, a)) { 542 return 0; 543 } 544 545 return BN_nnmod(r, r, m, ctx); 546} 547 548int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) { 549 if (!BN_lshift1(r, a)) { 550 return 0; 551 } 552 if (BN_cmp(r, m) >= 0) { 553 return BN_sub(r, r, m); 554 } 555 556 return 1; 557} 558 559BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w) { 560 BN_ULONG ret = 0; 561 int i, j; 562 563 w &= BN_MASK2; 564 565 if (!w) { 566 /* actually this an error (division by zero) */ 567 return (BN_ULONG) - 1; 568 } 569 570 if (a->top == 0) { 571 return 0; 572 } 573 574 /* normalize input (so bn_div_words doesn't complain) */ 575 j = BN_BITS2 - BN_num_bits_word(w); 576 w <<= j; 577 if (!BN_lshift(a, a, j)) { 578 return (BN_ULONG) - 1; 579 } 580 581 for (i = a->top - 1; i >= 0; i--) { 582 BN_ULONG l, d; 583 584 l = a->d[i]; 585 d = bn_div_words(ret, l, w); 586 ret = (l - ((d * w) & BN_MASK2)) & BN_MASK2; 587 a->d[i] = d; 588 } 589 590 if ((a->top > 0) && (a->d[a->top - 1] == 0)) { 591 a->top--; 592 } 593 594 ret >>= j; 595 return ret; 596} 597 598BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w) { 599#ifndef BN_LLONG 600 BN_ULONG ret = 0; 601#else 602 BN_ULLONG ret = 0; 603#endif 604 int i; 605 606 if (w == 0) { 607 return (BN_ULONG) -1; 608 } 609 610 w &= BN_MASK2; 611 for (i = a->top - 1; i >= 0; i--) { 612#ifndef BN_LLONG 613 ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w; 614 ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w; 615#else 616 ret = (BN_ULLONG)(((ret << (BN_ULLONG)BN_BITS2) | a->d[i]) % (BN_ULLONG)w); 617#endif 618 } 619 return (BN_ULONG)ret; 620} 621