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(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 } 284 q--; 285 rem += d0; 286 if (rem < d0) { 287 break; /* don't let rem overflow */ 288 } 289 t2 -= d1; 290 } 291#else /* !BN_LLONG */ 292 BN_ULONG t2l, t2h; 293 294#if defined(div_asm) 295 q = div_asm(n0, n1, d0); 296#else 297 q = bn_div_words(n0, n1, d0); 298#endif 299 300#ifndef REMAINDER_IS_ALREADY_CALCULATED 301 rem = (n1 - q * d0) & BN_MASK2; 302#endif 303 304#if defined(BN_UMULT_LOHI) 305 BN_UMULT_LOHI(t2l, t2h, d1, q); 306#elif defined(BN_UMULT_HIGH) 307 t2l = d1 * q; 308 t2h = BN_UMULT_HIGH(d1, q); 309#else 310 { 311 BN_ULONG ql, qh; 312 t2l = LBITS(d1); 313 t2h = HBITS(d1); 314 ql = LBITS(q); 315 qh = HBITS(q); 316 mul64(t2l, t2h, ql, qh); /* t2=(BN_ULLONG)d1*q; */ 317 } 318#endif 319 320 for (;;) { 321 if ((t2h < rem) || ((t2h == rem) && (t2l <= wnump[-2]))) { 322 break; 323 } 324 q--; 325 rem += d0; 326 if (rem < d0) { 327 break; /* don't let rem overflow */ 328 } 329 if (t2l < d1) { 330 t2h--; 331 } 332 t2l -= d1; 333 } 334#endif /* !BN_LLONG */ 335 } 336 337 l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q); 338 tmp->d[div_n] = l0; 339 wnum.d--; 340 /* ingore top values of the bignums just sub the two 341 * BN_ULONG arrays with bn_sub_words */ 342 if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) { 343 /* Note: As we have considered only the leading 344 * two BN_ULONGs in the calculation of q, sdiv * q 345 * might be greater than wnum (but then (q-1) * sdiv 346 * is less or equal than wnum) 347 */ 348 q--; 349 if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) { 350 /* we can't have an overflow here (assuming 351 * that q != 0, but if q == 0 then tmp is 352 * zero anyway) */ 353 (*wnump)++; 354 } 355 } 356 /* store part of the result */ 357 *resp = q; 358 } 359 bn_correct_top(snum); 360 if (rm != NULL) { 361 /* Keep a copy of the neg flag in num because if rm==num 362 * BN_rshift() will overwrite it. 363 */ 364 int neg = num->neg; 365 if (!BN_rshift(rm, snum, norm_shift)) { 366 goto err; 367 } 368 if (!BN_is_zero(rm)) { 369 rm->neg = neg; 370 } 371 } 372 if (no_branch) { 373 bn_correct_top(res); 374 } 375 BN_CTX_end(ctx); 376 return 1; 377 378err: 379 BN_CTX_end(ctx); 380 return 0; 381} 382 383int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) { 384 if (!(BN_mod(r, m, d, ctx))) { 385 return 0; 386 } 387 if (!r->neg) { 388 return 1; 389 } 390 391 /* now -|d| < r < 0, so we have to set r := r + |d|. */ 392 return (d->neg ? BN_sub : BN_add)(r, r, d); 393} 394 395int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 396 BN_CTX *ctx) { 397 if (!BN_add(r, a, b)) { 398 return 0; 399 } 400 return BN_nnmod(r, r, m, ctx); 401} 402 403int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 404 const BIGNUM *m) { 405 if (!BN_uadd(r, a, b)) { 406 return 0; 407 } 408 if (BN_ucmp(r, m) >= 0) { 409 return BN_usub(r, r, m); 410 } 411 return 1; 412} 413 414int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 415 BN_CTX *ctx) { 416 if (!BN_sub(r, a, b)) { 417 return 0; 418 } 419 return BN_nnmod(r, r, m, ctx); 420} 421 422/* BN_mod_sub variant that may be used if both a and b are non-negative 423 * and less than m */ 424int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 425 const BIGNUM *m) { 426 if (!BN_sub(r, a, b)) { 427 return 0; 428 } 429 if (r->neg) { 430 return BN_add(r, r, m); 431 } 432 return 1; 433} 434 435int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 436 BN_CTX *ctx) { 437 BIGNUM *t; 438 int ret = 0; 439 440 BN_CTX_start(ctx); 441 t = BN_CTX_get(ctx); 442 if (t == NULL) { 443 goto err; 444 } 445 446 if (a == b) { 447 if (!BN_sqr(t, a, ctx)) { 448 goto err; 449 } 450 } else { 451 if (!BN_mul(t, a, b, ctx)) { 452 goto err; 453 } 454 } 455 456 if (!BN_nnmod(r, t, m, ctx)) { 457 goto err; 458 } 459 460 ret = 1; 461 462err: 463 BN_CTX_end(ctx); 464 return ret; 465} 466 467int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) { 468 if (!BN_sqr(r, a, ctx)) { 469 return 0; 470 } 471 472 /* r->neg == 0, thus we don't need BN_nnmod */ 473 return BN_mod(r, r, m, ctx); 474} 475 476int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, 477 BN_CTX *ctx) { 478 BIGNUM *abs_m = NULL; 479 int ret; 480 481 if (!BN_nnmod(r, a, m, ctx)) { 482 return 0; 483 } 484 485 if (m->neg) { 486 abs_m = BN_dup(m); 487 if (abs_m == NULL) { 488 return 0; 489 } 490 abs_m->neg = 0; 491 } 492 493 ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); 494 495 BN_free(abs_m); 496 return ret; 497} 498 499int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) { 500 if (r != a) { 501 if (BN_copy(r, a) == NULL) { 502 return 0; 503 } 504 } 505 506 while (n > 0) { 507 int max_shift; 508 509 /* 0 < r < m */ 510 max_shift = BN_num_bits(m) - BN_num_bits(r); 511 /* max_shift >= 0 */ 512 513 if (max_shift < 0) { 514 OPENSSL_PUT_ERROR(BN, BN_mod_lshift_quick, BN_R_INPUT_NOT_REDUCED); 515 return 0; 516 } 517 518 if (max_shift > n) { 519 max_shift = n; 520 } 521 522 if (max_shift) { 523 if (!BN_lshift(r, r, max_shift)) { 524 return 0; 525 } 526 n -= max_shift; 527 } else { 528 if (!BN_lshift1(r, r)) { 529 return 0; 530 } 531 --n; 532 } 533 534 /* BN_num_bits(r) <= BN_num_bits(m) */ 535 if (BN_cmp(r, m) >= 0) { 536 if (!BN_sub(r, r, m)) { 537 return 0; 538 } 539 } 540 } 541 542 return 1; 543} 544 545int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) { 546 if (!BN_lshift1(r, a)) { 547 return 0; 548 } 549 550 return BN_nnmod(r, r, m, ctx); 551} 552 553int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) { 554 if (!BN_lshift1(r, a)) { 555 return 0; 556 } 557 if (BN_cmp(r, m) >= 0) { 558 return BN_sub(r, r, m); 559 } 560 561 return 1; 562} 563 564BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w) { 565 BN_ULONG ret = 0; 566 int i, j; 567 568 w &= BN_MASK2; 569 570 if (!w) { 571 /* actually this an error (division by zero) */ 572 return (BN_ULONG) - 1; 573 } 574 575 if (a->top == 0) { 576 return 0; 577 } 578 579 /* normalize input (so bn_div_words doesn't complain) */ 580 j = BN_BITS2 - BN_num_bits_word(w); 581 w <<= j; 582 if (!BN_lshift(a, a, j)) { 583 return (BN_ULONG) - 1; 584 } 585 586 for (i = a->top - 1; i >= 0; i--) { 587 BN_ULONG l, d; 588 589 l = a->d[i]; 590 d = bn_div_words(ret, l, w); 591 ret = (l - ((d * w) & BN_MASK2)) & BN_MASK2; 592 a->d[i] = d; 593 } 594 595 if ((a->top > 0) && (a->d[a->top - 1] == 0)) { 596 a->top--; 597 } 598 599 ret >>= j; 600 return ret; 601} 602 603BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w) { 604#ifndef BN_LLONG 605 BN_ULONG ret = 0; 606#else 607 BN_ULLONG ret = 0; 608#endif 609 int i; 610 611 if (w == 0) { 612 return (BN_ULONG) -1; 613 } 614 615 w &= BN_MASK2; 616 for (i = a->top - 1; i >= 0; i--) { 617#ifndef BN_LLONG 618 ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w; 619 ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w; 620#else 621 ret = (BN_ULLONG)(((ret << (BN_ULLONG)BN_BITS2) | a->d[i]) % (BN_ULLONG)w); 622#endif 623 } 624 return (BN_ULONG)ret; 625} 626