1 /* crypto/ec/ec_mult.c */ 2 /* 3 * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project. 4 */ 5 /* ==================================================================== 6 * Copyright (c) 1998-2003 The OpenSSL Project. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in 17 * the documentation and/or other materials provided with the 18 * distribution. 19 * 20 * 3. All advertising materials mentioning features or use of this 21 * software must display the following acknowledgment: 22 * "This product includes software developed by the OpenSSL Project 23 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 24 * 25 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 26 * endorse or promote products derived from this software without 27 * prior written permission. For written permission, please contact 28 * openssl-core@openssl.org. 29 * 30 * 5. Products derived from this software may not be called "OpenSSL" 31 * nor may "OpenSSL" appear in their names without prior written 32 * permission of the OpenSSL Project. 33 * 34 * 6. Redistributions of any form whatsoever must retain the following 35 * acknowledgment: 36 * "This product includes software developed by the OpenSSL Project 37 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 38 * 39 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 40 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 41 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 42 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 43 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 45 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 46 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 48 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 49 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 50 * OF THE POSSIBILITY OF SUCH DAMAGE. 51 * ==================================================================== 52 * 53 * This product includes cryptographic software written by Eric Young 54 * (eay@cryptsoft.com). This product includes software written by Tim 55 * Hudson (tjh@cryptsoft.com). 56 * 57 */ 58 /* ==================================================================== 59 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 60 * Portions of this software developed by SUN MICROSYSTEMS, INC., 61 * and contributed to the OpenSSL project. 62 */ 63 64 #include <string.h> 65 66 #include <openssl/err.h> 67 68 #include "ec_lcl.h" 69 70 71 /* 72 * This file implements the wNAF-based interleaving multi-exponentation method 73 * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp>); 74 * for multiplication with precomputation, we use wNAF splitting 75 * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp>). 76 */ 77 78 79 80 81 /* structure for precomputed multiples of the generator */ 82 typedef struct ec_pre_comp_st { 83 const EC_GROUP *group; /* parent EC_GROUP object */ 84 size_t blocksize; /* block size for wNAF splitting */ 85 size_t numblocks; /* max. number of blocks for which we have precomputation */ 86 size_t w; /* window size */ 87 EC_POINT **points; /* array with pre-calculated multiples of generator: 88 * 'num' pointers to EC_POINT objects followed by a NULL */ 89 size_t num; /* numblocks * 2^(w-1) */ 90 int references; 91 } EC_PRE_COMP; 92 93 /* functions to manage EC_PRE_COMP within the EC_GROUP extra_data framework */ 94 static void *ec_pre_comp_dup(void *); 95 static void ec_pre_comp_free(void *); 96 static void ec_pre_comp_clear_free(void *); 97 98 static EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group) 99 { 100 EC_PRE_COMP *ret = NULL; 101 102 if (!group) 103 return NULL; 104 105 ret = (EC_PRE_COMP *)OPENSSL_malloc(sizeof(EC_PRE_COMP)); 106 if (!ret) 107 return ret; 108 ret->group = group; 109 ret->blocksize = 8; /* default */ 110 ret->numblocks = 0; 111 ret->w = 4; /* default */ 112 ret->points = NULL; 113 ret->num = 0; 114 ret->references = 1; 115 return ret; 116 } 117 118 static void *ec_pre_comp_dup(void *src_) 119 { 120 EC_PRE_COMP *src = src_; 121 122 /* no need to actually copy, these objects never change! */ 123 124 CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP); 125 126 return src_; 127 } 128 129 static void ec_pre_comp_free(void *pre_) 130 { 131 int i; 132 EC_PRE_COMP *pre = pre_; 133 134 if (!pre) 135 return; 136 137 i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); 138 if (i > 0) 139 return; 140 141 if (pre->points) 142 { 143 EC_POINT **p; 144 145 for (p = pre->points; *p != NULL; p++) 146 EC_POINT_free(*p); 147 OPENSSL_free(pre->points); 148 } 149 OPENSSL_free(pre); 150 } 151 152 static void ec_pre_comp_clear_free(void *pre_) 153 { 154 int i; 155 EC_PRE_COMP *pre = pre_; 156 157 if (!pre) 158 return; 159 160 i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); 161 if (i > 0) 162 return; 163 164 if (pre->points) 165 { 166 EC_POINT **p; 167 168 for (p = pre->points; *p != NULL; p++) 169 EC_POINT_clear_free(*p); 170 OPENSSL_cleanse(pre->points, sizeof pre->points); 171 OPENSSL_free(pre->points); 172 } 173 OPENSSL_cleanse(pre, sizeof pre); 174 OPENSSL_free(pre); 175 } 176 177 178 179 180 /* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'. 181 * This is an array r[] of values that are either zero or odd with an 182 * absolute value less than 2^w satisfying 183 * scalar = \sum_j r[j]*2^j 184 * where at most one of any w+1 consecutive digits is non-zero 185 * with the exception that the most significant digit may be only 186 * w-1 zeros away from that next non-zero digit. 187 */ 188 static signed char *compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len) 189 { 190 int window_val; 191 int ok = 0; 192 signed char *r = NULL; 193 int sign = 1; 194 int bit, next_bit, mask; 195 size_t len = 0, j; 196 197 if (w <= 0 || w > 7) /* 'signed char' can represent integers with absolute values less than 2^7 */ 198 { 199 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 200 goto err; 201 } 202 bit = 1 << w; /* at most 128 */ 203 next_bit = bit << 1; /* at most 256 */ 204 mask = next_bit - 1; /* at most 255 */ 205 206 if (BN_is_negative(scalar)) 207 { 208 sign = -1; 209 } 210 211 len = BN_num_bits(scalar); 212 r = OPENSSL_malloc(len + 1); /* modified wNAF may be one digit longer than binary representation 213 * (*ret_len will be set to the actual length, i.e. at most 214 * BN_num_bits(scalar) + 1) */ 215 if (r == NULL) goto err; 216 217 if (scalar->d == NULL || scalar->top == 0) 218 { 219 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 220 goto err; 221 } 222 window_val = scalar->d[0] & mask; 223 j = 0; 224 while ((window_val != 0) || (j + w + 1 < len)) /* if j+w+1 >= len, window_val will not increase */ 225 { 226 int digit = 0; 227 228 /* 0 <= window_val <= 2^(w+1) */ 229 230 if (window_val & 1) 231 { 232 /* 0 < window_val < 2^(w+1) */ 233 234 if (window_val & bit) 235 { 236 digit = window_val - next_bit; /* -2^w < digit < 0 */ 237 238 #if 1 /* modified wNAF */ 239 if (j + w + 1 >= len) 240 { 241 /* special case for generating modified wNAFs: 242 * no new bits will be added into window_val, 243 * so using a positive digit here will decrease 244 * the total length of the representation */ 245 246 digit = window_val & (mask >> 1); /* 0 < digit < 2^w */ 247 } 248 #endif 249 } 250 else 251 { 252 digit = window_val; /* 0 < digit < 2^w */ 253 } 254 255 if (digit <= -bit || digit >= bit || !(digit & 1)) 256 { 257 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 258 goto err; 259 } 260 261 window_val -= digit; 262 263 /* now window_val is 0 or 2^(w+1) in standard wNAF generation; 264 * for modified window NAFs, it may also be 2^w 265 */ 266 if (window_val != 0 && window_val != next_bit && window_val != bit) 267 { 268 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 269 goto err; 270 } 271 } 272 273 r[j++] = sign * digit; 274 275 window_val >>= 1; 276 window_val += bit * BN_is_bit_set(scalar, j + w); 277 278 if (window_val > next_bit) 279 { 280 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 281 goto err; 282 } 283 } 284 285 if (j > len + 1) 286 { 287 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 288 goto err; 289 } 290 len = j; 291 ok = 1; 292 293 err: 294 if (!ok) 295 { 296 OPENSSL_free(r); 297 r = NULL; 298 } 299 if (ok) 300 *ret_len = len; 301 return r; 302 } 303 304 305 /* TODO: table should be optimised for the wNAF-based implementation, 306 * sometimes smaller windows will give better performance 307 * (thus the boundaries should be increased) 308 */ 309 #define EC_window_bits_for_scalar_size(b) \ 310 ((size_t) \ 311 ((b) >= 2000 ? 6 : \ 312 (b) >= 800 ? 5 : \ 313 (b) >= 300 ? 4 : \ 314 (b) >= 70 ? 3 : \ 315 (b) >= 20 ? 2 : \ 316 1)) 317 318 /* Compute 319 * \sum scalars[i]*points[i], 320 * also including 321 * scalar*generator 322 * in the addition if scalar != NULL 323 */ 324 int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 325 size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx) 326 { 327 BN_CTX *new_ctx = NULL; 328 const EC_POINT *generator = NULL; 329 EC_POINT *tmp = NULL; 330 size_t totalnum; 331 size_t blocksize = 0, numblocks = 0; /* for wNAF splitting */ 332 size_t pre_points_per_block = 0; 333 size_t i, j; 334 int k; 335 int r_is_inverted = 0; 336 int r_is_at_infinity = 1; 337 size_t *wsize = NULL; /* individual window sizes */ 338 signed char **wNAF = NULL; /* individual wNAFs */ 339 size_t *wNAF_len = NULL; 340 size_t max_len = 0; 341 size_t num_val; 342 EC_POINT **val = NULL; /* precomputation */ 343 EC_POINT **v; 344 EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' or 'pre_comp->points' */ 345 const EC_PRE_COMP *pre_comp = NULL; 346 int num_scalar = 0; /* flag: will be set to 1 if 'scalar' must be treated like other scalars, 347 * i.e. precomputation is not available */ 348 int ret = 0; 349 350 if (group->meth != r->meth) 351 { 352 ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); 353 return 0; 354 } 355 356 if ((scalar == NULL) && (num == 0)) 357 { 358 return EC_POINT_set_to_infinity(group, r); 359 } 360 361 for (i = 0; i < num; i++) 362 { 363 if (group->meth != points[i]->meth) 364 { 365 ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); 366 return 0; 367 } 368 } 369 370 if (ctx == NULL) 371 { 372 ctx = new_ctx = BN_CTX_new(); 373 if (ctx == NULL) 374 goto err; 375 } 376 377 if (scalar != NULL) 378 { 379 generator = EC_GROUP_get0_generator(group); 380 if (generator == NULL) 381 { 382 ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR); 383 goto err; 384 } 385 386 /* look if we can use precomputed multiples of generator */ 387 388 pre_comp = EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free); 389 390 if (pre_comp && pre_comp->numblocks && (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) == 0)) 391 { 392 blocksize = pre_comp->blocksize; 393 394 /* determine maximum number of blocks that wNAF splitting may yield 395 * (NB: maximum wNAF length is bit length plus one) */ 396 numblocks = (BN_num_bits(scalar) / blocksize) + 1; 397 398 /* we cannot use more blocks than we have precomputation for */ 399 if (numblocks > pre_comp->numblocks) 400 numblocks = pre_comp->numblocks; 401 402 pre_points_per_block = 1u << (pre_comp->w - 1); 403 404 /* check that pre_comp looks sane */ 405 if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block)) 406 { 407 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 408 goto err; 409 } 410 } 411 else 412 { 413 /* can't use precomputation */ 414 pre_comp = NULL; 415 numblocks = 1; 416 num_scalar = 1; /* treat 'scalar' like 'num'-th element of 'scalars' */ 417 } 418 } 419 420 totalnum = num + numblocks; 421 422 wsize = OPENSSL_malloc(totalnum * sizeof wsize[0]); 423 wNAF_len = OPENSSL_malloc(totalnum * sizeof wNAF_len[0]); 424 wNAF = OPENSSL_malloc((totalnum + 1) * sizeof wNAF[0]); /* includes space for pivot */ 425 val_sub = OPENSSL_malloc(totalnum * sizeof val_sub[0]); 426 427 if (!wsize || !wNAF_len || !wNAF || !val_sub) 428 goto err; 429 430 wNAF[0] = NULL; /* preliminary pivot */ 431 432 /* num_val will be the total number of temporarily precomputed points */ 433 num_val = 0; 434 435 for (i = 0; i < num + num_scalar; i++) 436 { 437 size_t bits; 438 439 bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar); 440 wsize[i] = EC_window_bits_for_scalar_size(bits); 441 num_val += 1u << (wsize[i] - 1); 442 wNAF[i + 1] = NULL; /* make sure we always have a pivot */ 443 wNAF[i] = compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], &wNAF_len[i]); 444 if (wNAF[i] == NULL) 445 goto err; 446 if (wNAF_len[i] > max_len) 447 max_len = wNAF_len[i]; 448 } 449 450 if (numblocks) 451 { 452 /* we go here iff scalar != NULL */ 453 454 if (pre_comp == NULL) 455 { 456 if (num_scalar != 1) 457 { 458 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 459 goto err; 460 } 461 /* we have already generated a wNAF for 'scalar' */ 462 } 463 else 464 { 465 signed char *tmp_wNAF = NULL; 466 size_t tmp_len = 0; 467 468 if (num_scalar != 0) 469 { 470 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 471 goto err; 472 } 473 474 /* use the window size for which we have precomputation */ 475 wsize[num] = pre_comp->w; 476 tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len); 477 if (!tmp_wNAF) 478 goto err; 479 480 if (tmp_len <= max_len) 481 { 482 /* One of the other wNAFs is at least as long 483 * as the wNAF belonging to the generator, 484 * so wNAF splitting will not buy us anything. */ 485 486 numblocks = 1; 487 totalnum = num + 1; /* don't use wNAF splitting */ 488 wNAF[num] = tmp_wNAF; 489 wNAF[num + 1] = NULL; 490 wNAF_len[num] = tmp_len; 491 if (tmp_len > max_len) 492 max_len = tmp_len; 493 /* pre_comp->points starts with the points that we need here: */ 494 val_sub[num] = pre_comp->points; 495 } 496 else 497 { 498 /* don't include tmp_wNAF directly into wNAF array 499 * - use wNAF splitting and include the blocks */ 500 501 signed char *pp; 502 EC_POINT **tmp_points; 503 504 if (tmp_len < numblocks * blocksize) 505 { 506 /* possibly we can do with fewer blocks than estimated */ 507 numblocks = (tmp_len + blocksize - 1) / blocksize; 508 if (numblocks > pre_comp->numblocks) 509 { 510 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 511 goto err; 512 } 513 totalnum = num + numblocks; 514 } 515 516 /* split wNAF in 'numblocks' parts */ 517 pp = tmp_wNAF; 518 tmp_points = pre_comp->points; 519 520 for (i = num; i < totalnum; i++) 521 { 522 if (i < totalnum - 1) 523 { 524 wNAF_len[i] = blocksize; 525 if (tmp_len < blocksize) 526 { 527 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 528 goto err; 529 } 530 tmp_len -= blocksize; 531 } 532 else 533 /* last block gets whatever is left 534 * (this could be more or less than 'blocksize'!) */ 535 wNAF_len[i] = tmp_len; 536 537 wNAF[i + 1] = NULL; 538 wNAF[i] = OPENSSL_malloc(wNAF_len[i]); 539 if (wNAF[i] == NULL) 540 { 541 OPENSSL_free(tmp_wNAF); 542 goto err; 543 } 544 memcpy(wNAF[i], pp, wNAF_len[i]); 545 if (wNAF_len[i] > max_len) 546 max_len = wNAF_len[i]; 547 548 if (*tmp_points == NULL) 549 { 550 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 551 OPENSSL_free(tmp_wNAF); 552 goto err; 553 } 554 val_sub[i] = tmp_points; 555 tmp_points += pre_points_per_block; 556 pp += blocksize; 557 } 558 OPENSSL_free(tmp_wNAF); 559 } 560 } 561 } 562 563 /* All points we precompute now go into a single array 'val'. 564 * 'val_sub[i]' is a pointer to the subarray for the i-th point, 565 * or to a subarray of 'pre_comp->points' if we already have precomputation. */ 566 val = OPENSSL_malloc((num_val + 1) * sizeof val[0]); 567 if (val == NULL) goto err; 568 val[num_val] = NULL; /* pivot element */ 569 570 /* allocate points for precomputation */ 571 v = val; 572 for (i = 0; i < num + num_scalar; i++) 573 { 574 val_sub[i] = v; 575 for (j = 0; j < (1u << (wsize[i] - 1)); j++) 576 { 577 *v = EC_POINT_new(group); 578 if (*v == NULL) goto err; 579 v++; 580 } 581 } 582 if (!(v == val + num_val)) 583 { 584 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 585 goto err; 586 } 587 588 if (!(tmp = EC_POINT_new(group))) 589 goto err; 590 591 /* prepare precomputed values: 592 * val_sub[i][0] := points[i] 593 * val_sub[i][1] := 3 * points[i] 594 * val_sub[i][2] := 5 * points[i] 595 * ... 596 */ 597 for (i = 0; i < num + num_scalar; i++) 598 { 599 if (i < num) 600 { 601 if (!EC_POINT_copy(val_sub[i][0], points[i])) goto err; 602 } 603 else 604 { 605 if (!EC_POINT_copy(val_sub[i][0], generator)) goto err; 606 } 607 608 if (wsize[i] > 1) 609 { 610 if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) goto err; 611 for (j = 1; j < (1u << (wsize[i] - 1)); j++) 612 { 613 if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) goto err; 614 } 615 } 616 } 617 618 #if 1 /* optional; EC_window_bits_for_scalar_size assumes we do this step */ 619 if (!EC_POINTs_make_affine(group, num_val, val, ctx)) 620 goto err; 621 #endif 622 623 r_is_at_infinity = 1; 624 625 for (k = max_len - 1; k >= 0; k--) 626 { 627 if (!r_is_at_infinity) 628 { 629 if (!EC_POINT_dbl(group, r, r, ctx)) goto err; 630 } 631 632 for (i = 0; i < totalnum; i++) 633 { 634 if (wNAF_len[i] > (size_t)k) 635 { 636 int digit = wNAF[i][k]; 637 int is_neg; 638 639 if (digit) 640 { 641 is_neg = digit < 0; 642 643 if (is_neg) 644 digit = -digit; 645 646 if (is_neg != r_is_inverted) 647 { 648 if (!r_is_at_infinity) 649 { 650 if (!EC_POINT_invert(group, r, ctx)) goto err; 651 } 652 r_is_inverted = !r_is_inverted; 653 } 654 655 /* digit > 0 */ 656 657 if (r_is_at_infinity) 658 { 659 if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) goto err; 660 r_is_at_infinity = 0; 661 } 662 else 663 { 664 if (!EC_POINT_add(group, r, r, val_sub[i][digit >> 1], ctx)) goto err; 665 } 666 } 667 } 668 } 669 } 670 671 if (r_is_at_infinity) 672 { 673 if (!EC_POINT_set_to_infinity(group, r)) goto err; 674 } 675 else 676 { 677 if (r_is_inverted) 678 if (!EC_POINT_invert(group, r, ctx)) goto err; 679 } 680 681 ret = 1; 682 683 err: 684 if (new_ctx != NULL) 685 BN_CTX_free(new_ctx); 686 if (tmp != NULL) 687 EC_POINT_free(tmp); 688 if (wsize != NULL) 689 OPENSSL_free(wsize); 690 if (wNAF_len != NULL) 691 OPENSSL_free(wNAF_len); 692 if (wNAF != NULL) 693 { 694 signed char **w; 695 696 for (w = wNAF; *w != NULL; w++) 697 OPENSSL_free(*w); 698 699 OPENSSL_free(wNAF); 700 } 701 if (val != NULL) 702 { 703 for (v = val; *v != NULL; v++) 704 EC_POINT_clear_free(*v); 705 706 OPENSSL_free(val); 707 } 708 if (val_sub != NULL) 709 { 710 OPENSSL_free(val_sub); 711 } 712 return ret; 713 } 714 715 716 /* ec_wNAF_precompute_mult() 717 * creates an EC_PRE_COMP object with preprecomputed multiples of the generator 718 * for use with wNAF splitting as implemented in ec_wNAF_mul(). 719 * 720 * 'pre_comp->points' is an array of multiples of the generator 721 * of the following form: 722 * points[0] = generator; 723 * points[1] = 3 * generator; 724 * ... 725 * points[2^(w-1)-1] = (2^(w-1)-1) * generator; 726 * points[2^(w-1)] = 2^blocksize * generator; 727 * points[2^(w-1)+1] = 3 * 2^blocksize * generator; 728 * ... 729 * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) * 2^(blocksize*(numblocks-2)) * generator 730 * points[2^(w-1)*(numblocks-1)] = 2^(blocksize*(numblocks-1)) * generator 731 * ... 732 * points[2^(w-1)*numblocks-1] = (2^(w-1)) * 2^(blocksize*(numblocks-1)) * generator 733 * points[2^(w-1)*numblocks] = NULL 734 */ 735 int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) 736 { 737 const EC_POINT *generator; 738 EC_POINT *tmp_point = NULL, *base = NULL, **var; 739 BN_CTX *new_ctx = NULL; 740 BIGNUM *order; 741 size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num; 742 EC_POINT **points = NULL; 743 EC_PRE_COMP *pre_comp; 744 int ret = 0; 745 746 /* if there is an old EC_PRE_COMP object, throw it away */ 747 EC_EX_DATA_free_data(&group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free); 748 749 if ((pre_comp = ec_pre_comp_new(group)) == NULL) 750 return 0; 751 752 generator = EC_GROUP_get0_generator(group); 753 if (generator == NULL) 754 { 755 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR); 756 goto err; 757 } 758 759 if (ctx == NULL) 760 { 761 ctx = new_ctx = BN_CTX_new(); 762 if (ctx == NULL) 763 goto err; 764 } 765 766 BN_CTX_start(ctx); 767 order = BN_CTX_get(ctx); 768 if (order == NULL) goto err; 769 770 if (!EC_GROUP_get_order(group, order, ctx)) goto err; 771 if (BN_is_zero(order)) 772 { 773 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER); 774 goto err; 775 } 776 777 bits = BN_num_bits(order); 778 /* The following parameters mean we precompute (approximately) 779 * one point per bit. 780 * 781 * TBD: The combination 8, 4 is perfect for 160 bits; for other 782 * bit lengths, other parameter combinations might provide better 783 * efficiency. 784 */ 785 blocksize = 8; 786 w = 4; 787 if (EC_window_bits_for_scalar_size(bits) > w) 788 { 789 /* let's not make the window too small ... */ 790 w = EC_window_bits_for_scalar_size(bits); 791 } 792 793 numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks to use for wNAF splitting */ 794 795 pre_points_per_block = 1u << (w - 1); 796 num = pre_points_per_block * numblocks; /* number of points to compute and store */ 797 798 points = OPENSSL_malloc(sizeof (EC_POINT*)*(num + 1)); 799 if (!points) 800 { 801 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 802 goto err; 803 } 804 805 var = points; 806 var[num] = NULL; /* pivot */ 807 for (i = 0; i < num; i++) 808 { 809 if ((var[i] = EC_POINT_new(group)) == NULL) 810 { 811 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 812 goto err; 813 } 814 } 815 816 if (!(tmp_point = EC_POINT_new(group)) || !(base = EC_POINT_new(group))) 817 { 818 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 819 goto err; 820 } 821 822 if (!EC_POINT_copy(base, generator)) 823 goto err; 824 825 /* do the precomputation */ 826 for (i = 0; i < numblocks; i++) 827 { 828 size_t j; 829 830 if (!EC_POINT_dbl(group, tmp_point, base, ctx)) 831 goto err; 832 833 if (!EC_POINT_copy(*var++, base)) 834 goto err; 835 836 for (j = 1; j < pre_points_per_block; j++, var++) 837 { 838 /* calculate odd multiples of the current base point */ 839 if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx)) 840 goto err; 841 } 842 843 if (i < numblocks - 1) 844 { 845 /* get the next base (multiply current one by 2^blocksize) */ 846 size_t k; 847 848 if (blocksize <= 2) 849 { 850 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_INTERNAL_ERROR); 851 goto err; 852 } 853 854 if (!EC_POINT_dbl(group, base, tmp_point, ctx)) 855 goto err; 856 for (k = 2; k < blocksize; k++) 857 { 858 if (!EC_POINT_dbl(group,base,base,ctx)) 859 goto err; 860 } 861 } 862 } 863 864 if (!EC_POINTs_make_affine(group, num, points, ctx)) 865 goto err; 866 867 pre_comp->group = group; 868 pre_comp->blocksize = blocksize; 869 pre_comp->numblocks = numblocks; 870 pre_comp->w = w; 871 pre_comp->points = points; 872 points = NULL; 873 pre_comp->num = num; 874 875 if (!EC_EX_DATA_set_data(&group->extra_data, pre_comp, 876 ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free)) 877 goto err; 878 pre_comp = NULL; 879 880 ret = 1; 881 err: 882 if (ctx != NULL) 883 BN_CTX_end(ctx); 884 if (new_ctx != NULL) 885 BN_CTX_free(new_ctx); 886 if (pre_comp) 887 ec_pre_comp_free(pre_comp); 888 if (points) 889 { 890 EC_POINT **p; 891 892 for (p = points; *p != NULL; p++) 893 EC_POINT_free(*p); 894 OPENSSL_free(points); 895 } 896 if (tmp_point) 897 EC_POINT_free(tmp_point); 898 if (base) 899 EC_POINT_free(base); 900 return ret; 901 } 902 903 904 int ec_wNAF_have_precompute_mult(const EC_GROUP *group) 905 { 906 if (EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free) != NULL) 907 return 1; 908 else 909 return 0; 910 } 911