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 <string.h> 61 62 #include "internal.h" 63 64 65 #define BN_MUL_RECURSIVE_SIZE_NORMAL 16 66 #define BN_SQR_RECURSIVE_SIZE_NORMAL BN_MUL_RECURSIVE_SIZE_NORMAL 67 68 69 static void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, 70 int nb) { 71 BN_ULONG *rr; 72 73 if (na < nb) { 74 int itmp; 75 BN_ULONG *ltmp; 76 77 itmp = na; 78 na = nb; 79 nb = itmp; 80 ltmp = a; 81 a = b; 82 b = ltmp; 83 } 84 rr = &(r[na]); 85 if (nb <= 0) { 86 (void)bn_mul_words(r, a, na, 0); 87 return; 88 } else { 89 rr[0] = bn_mul_words(r, a, na, b[0]); 90 } 91 92 for (;;) { 93 if (--nb <= 0) { 94 return; 95 } 96 rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]); 97 if (--nb <= 0) { 98 return; 99 } 100 rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]); 101 if (--nb <= 0) { 102 return; 103 } 104 rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]); 105 if (--nb <= 0) { 106 return; 107 } 108 rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]); 109 rr += 4; 110 r += 4; 111 b += 4; 112 } 113 } 114 115 #if !defined(OPENSSL_X86) || defined(OPENSSL_NO_ASM) 116 /* Here follows specialised variants of bn_add_words() and bn_sub_words(). They 117 * have the property performing operations on arrays of different sizes. The 118 * sizes of those arrays is expressed through cl, which is the common length ( 119 * basicall, min(len(a),len(b)) ), and dl, which is the delta between the two 120 * lengths, calculated as len(a)-len(b). All lengths are the number of 121 * BN_ULONGs... For the operations that require a result array as parameter, 122 * it must have the length cl+abs(dl). These functions should probably end up 123 * in bn_asm.c as soon as there are assembler counterparts for the systems that 124 * use assembler files. */ 125 126 static BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, 127 const BN_ULONG *b, int cl, int dl) { 128 BN_ULONG c, t; 129 130 assert(cl >= 0); 131 c = bn_sub_words(r, a, b, cl); 132 133 if (dl == 0) { 134 return c; 135 } 136 137 r += cl; 138 a += cl; 139 b += cl; 140 141 if (dl < 0) { 142 for (;;) { 143 t = b[0]; 144 r[0] = (0 - t - c) & BN_MASK2; 145 if (t != 0) { 146 c = 1; 147 } 148 if (++dl >= 0) { 149 break; 150 } 151 152 t = b[1]; 153 r[1] = (0 - t - c) & BN_MASK2; 154 if (t != 0) { 155 c = 1; 156 } 157 if (++dl >= 0) { 158 break; 159 } 160 161 t = b[2]; 162 r[2] = (0 - t - c) & BN_MASK2; 163 if (t != 0) { 164 c = 1; 165 } 166 if (++dl >= 0) { 167 break; 168 } 169 170 t = b[3]; 171 r[3] = (0 - t - c) & BN_MASK2; 172 if (t != 0) { 173 c = 1; 174 } 175 if (++dl >= 0) { 176 break; 177 } 178 179 b += 4; 180 r += 4; 181 } 182 } else { 183 int save_dl = dl; 184 while (c) { 185 t = a[0]; 186 r[0] = (t - c) & BN_MASK2; 187 if (t != 0) { 188 c = 0; 189 } 190 if (--dl <= 0) { 191 break; 192 } 193 194 t = a[1]; 195 r[1] = (t - c) & BN_MASK2; 196 if (t != 0) { 197 c = 0; 198 } 199 if (--dl <= 0) { 200 break; 201 } 202 203 t = a[2]; 204 r[2] = (t - c) & BN_MASK2; 205 if (t != 0) { 206 c = 0; 207 } 208 if (--dl <= 0) { 209 break; 210 } 211 212 t = a[3]; 213 r[3] = (t - c) & BN_MASK2; 214 if (t != 0) { 215 c = 0; 216 } 217 if (--dl <= 0) { 218 break; 219 } 220 221 save_dl = dl; 222 a += 4; 223 r += 4; 224 } 225 if (dl > 0) { 226 if (save_dl > dl) { 227 switch (save_dl - dl) { 228 case 1: 229 r[1] = a[1]; 230 if (--dl <= 0) { 231 break; 232 } 233 case 2: 234 r[2] = a[2]; 235 if (--dl <= 0) { 236 break; 237 } 238 case 3: 239 r[3] = a[3]; 240 if (--dl <= 0) { 241 break; 242 } 243 } 244 a += 4; 245 r += 4; 246 } 247 } 248 249 if (dl > 0) { 250 for (;;) { 251 r[0] = a[0]; 252 if (--dl <= 0) { 253 break; 254 } 255 r[1] = a[1]; 256 if (--dl <= 0) { 257 break; 258 } 259 r[2] = a[2]; 260 if (--dl <= 0) { 261 break; 262 } 263 r[3] = a[3]; 264 if (--dl <= 0) { 265 break; 266 } 267 268 a += 4; 269 r += 4; 270 } 271 } 272 } 273 274 return c; 275 } 276 #else 277 /* On other platforms the function is defined in asm. */ 278 BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, 279 int cl, int dl); 280 #endif 281 282 /* Karatsuba recursive multiplication algorithm 283 * (cf. Knuth, The Art of Computer Programming, Vol. 2) */ 284 285 /* r is 2*n2 words in size, 286 * a and b are both n2 words in size. 287 * n2 must be a power of 2. 288 * We multiply and return the result. 289 * t must be 2*n2 words in size 290 * We calculate 291 * a[0]*b[0] 292 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) 293 * a[1]*b[1] 294 */ 295 /* dnX may not be positive, but n2/2+dnX has to be */ 296 static void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, 297 int dna, int dnb, BN_ULONG *t) { 298 int n = n2 / 2, c1, c2; 299 int tna = n + dna, tnb = n + dnb; 300 unsigned int neg, zero; 301 BN_ULONG ln, lo, *p; 302 303 /* Only call bn_mul_comba 8 if n2 == 8 and the 304 * two arrays are complete [steve] 305 */ 306 if (n2 == 8 && dna == 0 && dnb == 0) { 307 bn_mul_comba8(r, a, b); 308 return; 309 } 310 311 /* Else do normal multiply */ 312 if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) { 313 bn_mul_normal(r, a, n2 + dna, b, n2 + dnb); 314 if ((dna + dnb) < 0) { 315 OPENSSL_memset(&r[2 * n2 + dna + dnb], 0, 316 sizeof(BN_ULONG) * -(dna + dnb)); 317 } 318 return; 319 } 320 321 /* r=(a[0]-a[1])*(b[1]-b[0]) */ 322 c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); 323 c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n); 324 zero = neg = 0; 325 switch (c1 * 3 + c2) { 326 case -4: 327 bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 328 bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 329 break; 330 case -3: 331 zero = 1; 332 break; 333 case -2: 334 bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 335 bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ 336 neg = 1; 337 break; 338 case -1: 339 case 0: 340 case 1: 341 zero = 1; 342 break; 343 case 2: 344 bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ 345 bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 346 neg = 1; 347 break; 348 case 3: 349 zero = 1; 350 break; 351 case 4: 352 bn_sub_part_words(t, a, &(a[n]), tna, n - tna); 353 bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); 354 break; 355 } 356 357 if (n == 4 && dna == 0 && dnb == 0) { 358 /* XXX: bn_mul_comba4 could take extra args to do this well */ 359 if (!zero) { 360 bn_mul_comba4(&(t[n2]), t, &(t[n])); 361 } else { 362 OPENSSL_memset(&(t[n2]), 0, 8 * sizeof(BN_ULONG)); 363 } 364 365 bn_mul_comba4(r, a, b); 366 bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n])); 367 } else if (n == 8 && dna == 0 && dnb == 0) { 368 /* XXX: bn_mul_comba8 could take extra args to do this well */ 369 if (!zero) { 370 bn_mul_comba8(&(t[n2]), t, &(t[n])); 371 } else { 372 OPENSSL_memset(&(t[n2]), 0, 16 * sizeof(BN_ULONG)); 373 } 374 375 bn_mul_comba8(r, a, b); 376 bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n])); 377 } else { 378 p = &(t[n2 * 2]); 379 if (!zero) { 380 bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p); 381 } else { 382 OPENSSL_memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG)); 383 } 384 bn_mul_recursive(r, a, b, n, 0, 0, p); 385 bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, dna, dnb, p); 386 } 387 388 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 389 * r[10] holds (a[0]*b[0]) 390 * r[32] holds (b[1]*b[1]) */ 391 392 c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); 393 394 if (neg) { 395 /* if t[32] is negative */ 396 c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); 397 } else { 398 /* Might have a carry */ 399 c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); 400 } 401 402 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 403 * r[10] holds (a[0]*b[0]) 404 * r[32] holds (b[1]*b[1]) 405 * c1 holds the carry bits */ 406 c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); 407 if (c1) { 408 p = &(r[n + n2]); 409 lo = *p; 410 ln = (lo + c1) & BN_MASK2; 411 *p = ln; 412 413 /* The overflow will stop before we over write 414 * words we should not overwrite */ 415 if (ln < (BN_ULONG)c1) { 416 do { 417 p++; 418 lo = *p; 419 ln = (lo + 1) & BN_MASK2; 420 *p = ln; 421 } while (ln == 0); 422 } 423 } 424 } 425 426 /* n+tn is the word length 427 * t needs to be n*4 is size, as does r */ 428 /* tnX may not be negative but less than n */ 429 static void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, 430 int tna, int tnb, BN_ULONG *t) { 431 int i, j, n2 = n * 2; 432 int c1, c2, neg; 433 BN_ULONG ln, lo, *p; 434 435 if (n < 8) { 436 bn_mul_normal(r, a, n + tna, b, n + tnb); 437 return; 438 } 439 440 /* r=(a[0]-a[1])*(b[1]-b[0]) */ 441 c1 = bn_cmp_part_words(a, &(a[n]), tna, n - tna); 442 c2 = bn_cmp_part_words(&(b[n]), b, tnb, tnb - n); 443 neg = 0; 444 switch (c1 * 3 + c2) { 445 case -4: 446 bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 447 bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 448 break; 449 case -3: 450 /* break; */ 451 case -2: 452 bn_sub_part_words(t, &(a[n]), a, tna, tna - n); /* - */ 453 bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); /* + */ 454 neg = 1; 455 break; 456 case -1: 457 case 0: 458 case 1: 459 /* break; */ 460 case 2: 461 bn_sub_part_words(t, a, &(a[n]), tna, n - tna); /* + */ 462 bn_sub_part_words(&(t[n]), b, &(b[n]), tnb, n - tnb); /* - */ 463 neg = 1; 464 break; 465 case 3: 466 /* break; */ 467 case 4: 468 bn_sub_part_words(t, a, &(a[n]), tna, n - tna); 469 bn_sub_part_words(&(t[n]), &(b[n]), b, tnb, tnb - n); 470 break; 471 } 472 473 if (n == 8) { 474 bn_mul_comba8(&(t[n2]), t, &(t[n])); 475 bn_mul_comba8(r, a, b); 476 bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb); 477 OPENSSL_memset(&(r[n2 + tna + tnb]), 0, sizeof(BN_ULONG) * (n2 - tna - tnb)); 478 } else { 479 p = &(t[n2 * 2]); 480 bn_mul_recursive(&(t[n2]), t, &(t[n]), n, 0, 0, p); 481 bn_mul_recursive(r, a, b, n, 0, 0, p); 482 i = n / 2; 483 /* If there is only a bottom half to the number, 484 * just do it */ 485 if (tna > tnb) { 486 j = tna - i; 487 } else { 488 j = tnb - i; 489 } 490 491 if (j == 0) { 492 bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), i, tna - i, tnb - i, p); 493 OPENSSL_memset(&(r[n2 + i * 2]), 0, sizeof(BN_ULONG) * (n2 - i * 2)); 494 } else if (j > 0) { 495 /* eg, n == 16, i == 8 and tn == 11 */ 496 bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]), i, tna - i, tnb - i, p); 497 OPENSSL_memset(&(r[n2 + tna + tnb]), 0, 498 sizeof(BN_ULONG) * (n2 - tna - tnb)); 499 } else { 500 /* (j < 0) eg, n == 16, i == 8 and tn == 5 */ 501 OPENSSL_memset(&(r[n2]), 0, sizeof(BN_ULONG) * n2); 502 if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL && 503 tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) { 504 bn_mul_normal(&(r[n2]), &(a[n]), tna, &(b[n]), tnb); 505 } else { 506 for (;;) { 507 i /= 2; 508 /* these simplified conditions work 509 * exclusively because difference 510 * between tna and tnb is 1 or 0 */ 511 if (i < tna || i < tnb) { 512 bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]), i, tna - i, 513 tnb - i, p); 514 break; 515 } else if (i == tna || i == tnb) { 516 bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), i, tna - i, tnb - i, 517 p); 518 break; 519 } 520 } 521 } 522 } 523 } 524 525 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 526 * r[10] holds (a[0]*b[0]) 527 * r[32] holds (b[1]*b[1]) 528 */ 529 530 c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); 531 532 if (neg) { 533 /* if t[32] is negative */ 534 c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); 535 } else { 536 /* Might have a carry */ 537 c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2)); 538 } 539 540 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 541 * r[10] holds (a[0]*b[0]) 542 * r[32] holds (b[1]*b[1]) 543 * c1 holds the carry bits */ 544 c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); 545 if (c1) { 546 p = &(r[n + n2]); 547 lo = *p; 548 ln = (lo + c1) & BN_MASK2; 549 *p = ln; 550 551 /* The overflow will stop before we over write 552 * words we should not overwrite */ 553 if (ln < (BN_ULONG)c1) { 554 do { 555 p++; 556 lo = *p; 557 ln = (lo + 1) & BN_MASK2; 558 *p = ln; 559 } while (ln == 0); 560 } 561 } 562 } 563 564 int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { 565 int ret = 0; 566 int top, al, bl; 567 BIGNUM *rr; 568 int i; 569 BIGNUM *t = NULL; 570 int j = 0, k; 571 572 al = a->top; 573 bl = b->top; 574 575 if ((al == 0) || (bl == 0)) { 576 BN_zero(r); 577 return 1; 578 } 579 top = al + bl; 580 581 BN_CTX_start(ctx); 582 if ((r == a) || (r == b)) { 583 if ((rr = BN_CTX_get(ctx)) == NULL) { 584 goto err; 585 } 586 } else { 587 rr = r; 588 } 589 rr->neg = a->neg ^ b->neg; 590 591 i = al - bl; 592 if (i == 0) { 593 if (al == 8) { 594 if (bn_wexpand(rr, 16) == NULL) { 595 goto err; 596 } 597 rr->top = 16; 598 bn_mul_comba8(rr->d, a->d, b->d); 599 goto end; 600 } 601 } 602 603 static const int kMulNormalSize = 16; 604 if (al >= kMulNormalSize && bl >= kMulNormalSize) { 605 if (i >= -1 && i <= 1) { 606 /* Find out the power of two lower or equal 607 to the longest of the two numbers */ 608 if (i >= 0) { 609 j = BN_num_bits_word((BN_ULONG)al); 610 } 611 if (i == -1) { 612 j = BN_num_bits_word((BN_ULONG)bl); 613 } 614 j = 1 << (j - 1); 615 assert(j <= al || j <= bl); 616 k = j + j; 617 t = BN_CTX_get(ctx); 618 if (t == NULL) { 619 goto err; 620 } 621 if (al > j || bl > j) { 622 if (bn_wexpand(t, k * 4) == NULL) { 623 goto err; 624 } 625 if (bn_wexpand(rr, k * 4) == NULL) { 626 goto err; 627 } 628 bn_mul_part_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d); 629 } else { 630 /* al <= j || bl <= j */ 631 if (bn_wexpand(t, k * 2) == NULL) { 632 goto err; 633 } 634 if (bn_wexpand(rr, k * 2) == NULL) { 635 goto err; 636 } 637 bn_mul_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d); 638 } 639 rr->top = top; 640 goto end; 641 } 642 } 643 644 if (bn_wexpand(rr, top) == NULL) { 645 goto err; 646 } 647 rr->top = top; 648 bn_mul_normal(rr->d, a->d, al, b->d, bl); 649 650 end: 651 bn_correct_top(rr); 652 if (r != rr && !BN_copy(r, rr)) { 653 goto err; 654 } 655 ret = 1; 656 657 err: 658 BN_CTX_end(ctx); 659 return ret; 660 } 661 662 /* tmp must have 2*n words */ 663 static void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp) { 664 int i, j, max; 665 const BN_ULONG *ap; 666 BN_ULONG *rp; 667 668 max = n * 2; 669 ap = a; 670 rp = r; 671 rp[0] = rp[max - 1] = 0; 672 rp++; 673 j = n; 674 675 if (--j > 0) { 676 ap++; 677 rp[j] = bn_mul_words(rp, ap, j, ap[-1]); 678 rp += 2; 679 } 680 681 for (i = n - 2; i > 0; i--) { 682 j--; 683 ap++; 684 rp[j] = bn_mul_add_words(rp, ap, j, ap[-1]); 685 rp += 2; 686 } 687 688 bn_add_words(r, r, r, max); 689 690 /* There will not be a carry */ 691 692 bn_sqr_words(tmp, a, n); 693 694 bn_add_words(r, r, tmp, max); 695 } 696 697 /* r is 2*n words in size, 698 * a and b are both n words in size. (There's not actually a 'b' here ...) 699 * n must be a power of 2. 700 * We multiply and return the result. 701 * t must be 2*n words in size 702 * We calculate 703 * a[0]*b[0] 704 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) 705 * a[1]*b[1] 706 */ 707 static void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t) { 708 int n = n2 / 2; 709 int zero, c1; 710 BN_ULONG ln, lo, *p; 711 712 if (n2 == 4) { 713 bn_sqr_comba4(r, a); 714 return; 715 } else if (n2 == 8) { 716 bn_sqr_comba8(r, a); 717 return; 718 } 719 if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL) { 720 bn_sqr_normal(r, a, n2, t); 721 return; 722 } 723 /* r=(a[0]-a[1])*(a[1]-a[0]) */ 724 c1 = bn_cmp_words(a, &(a[n]), n); 725 zero = 0; 726 if (c1 > 0) { 727 bn_sub_words(t, a, &(a[n]), n); 728 } else if (c1 < 0) { 729 bn_sub_words(t, &(a[n]), a, n); 730 } else { 731 zero = 1; 732 } 733 734 /* The result will always be negative unless it is zero */ 735 p = &(t[n2 * 2]); 736 737 if (!zero) { 738 bn_sqr_recursive(&(t[n2]), t, n, p); 739 } else { 740 OPENSSL_memset(&(t[n2]), 0, n2 * sizeof(BN_ULONG)); 741 } 742 bn_sqr_recursive(r, a, n, p); 743 bn_sqr_recursive(&(r[n2]), &(a[n]), n, p); 744 745 /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero 746 * r[10] holds (a[0]*b[0]) 747 * r[32] holds (b[1]*b[1]) */ 748 749 c1 = (int)(bn_add_words(t, r, &(r[n2]), n2)); 750 751 /* t[32] is negative */ 752 c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2)); 753 754 /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1]) 755 * r[10] holds (a[0]*a[0]) 756 * r[32] holds (a[1]*a[1]) 757 * c1 holds the carry bits */ 758 c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2)); 759 if (c1) { 760 p = &(r[n + n2]); 761 lo = *p; 762 ln = (lo + c1) & BN_MASK2; 763 *p = ln; 764 765 /* The overflow will stop before we over write 766 * words we should not overwrite */ 767 if (ln < (BN_ULONG)c1) { 768 do { 769 p++; 770 lo = *p; 771 ln = (lo + 1) & BN_MASK2; 772 *p = ln; 773 } while (ln == 0); 774 } 775 } 776 } 777 778 int BN_mul_word(BIGNUM *bn, BN_ULONG w) { 779 BN_ULONG ll; 780 781 w &= BN_MASK2; 782 if (!bn->top) { 783 return 1; 784 } 785 786 if (w == 0) { 787 BN_zero(bn); 788 return 1; 789 } 790 791 ll = bn_mul_words(bn->d, bn->d, bn->top, w); 792 if (ll) { 793 if (bn_wexpand(bn, bn->top + 1) == NULL) { 794 return 0; 795 } 796 bn->d[bn->top++] = ll; 797 } 798 799 return 1; 800 } 801 802 int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) { 803 int max, al; 804 int ret = 0; 805 BIGNUM *tmp, *rr; 806 807 al = a->top; 808 if (al <= 0) { 809 r->top = 0; 810 r->neg = 0; 811 return 1; 812 } 813 814 BN_CTX_start(ctx); 815 rr = (a != r) ? r : BN_CTX_get(ctx); 816 tmp = BN_CTX_get(ctx); 817 if (!rr || !tmp) { 818 goto err; 819 } 820 821 max = 2 * al; /* Non-zero (from above) */ 822 if (bn_wexpand(rr, max) == NULL) { 823 goto err; 824 } 825 826 if (al == 4) { 827 bn_sqr_comba4(rr->d, a->d); 828 } else if (al == 8) { 829 bn_sqr_comba8(rr->d, a->d); 830 } else { 831 if (al < BN_SQR_RECURSIVE_SIZE_NORMAL) { 832 BN_ULONG t[BN_SQR_RECURSIVE_SIZE_NORMAL * 2]; 833 bn_sqr_normal(rr->d, a->d, al, t); 834 } else { 835 int j, k; 836 837 j = BN_num_bits_word((BN_ULONG)al); 838 j = 1 << (j - 1); 839 k = j + j; 840 if (al == j) { 841 if (bn_wexpand(tmp, k * 2) == NULL) { 842 goto err; 843 } 844 bn_sqr_recursive(rr->d, a->d, al, tmp->d); 845 } else { 846 if (bn_wexpand(tmp, max) == NULL) { 847 goto err; 848 } 849 bn_sqr_normal(rr->d, a->d, al, tmp->d); 850 } 851 } 852 } 853 854 rr->neg = 0; 855 /* If the most-significant half of the top word of 'a' is zero, then 856 * the square of 'a' will max-1 words. */ 857 if (a->d[al - 1] == (a->d[al - 1] & BN_MASK2l)) { 858 rr->top = max - 1; 859 } else { 860 rr->top = max; 861 } 862 863 if (rr != r && !BN_copy(r, rr)) { 864 goto err; 865 } 866 ret = 1; 867 868 err: 869 BN_CTX_end(ctx); 870 return ret; 871 } 872
