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-2007 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 (at) 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 (at) cryptsoft.com). This product includes software written by Tim 55 * Hudson (tjh (at) 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 { 108 ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE); 109 return ret; 110 } 111 ret->group = group; 112 ret->blocksize = 8; /* default */ 113 ret->numblocks = 0; 114 ret->w = 4; /* default */ 115 ret->points = NULL; 116 ret->num = 0; 117 ret->references = 1; 118 return ret; 119 } 120 121 static void *ec_pre_comp_dup(void *src_) 122 { 123 EC_PRE_COMP *src = src_; 124 125 /* no need to actually copy, these objects never change! */ 126 127 CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP); 128 129 return src_; 130 } 131 132 static void ec_pre_comp_free(void *pre_) 133 { 134 int i; 135 EC_PRE_COMP *pre = pre_; 136 137 if (!pre) 138 return; 139 140 i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); 141 if (i > 0) 142 return; 143 144 if (pre->points) 145 { 146 EC_POINT **p; 147 148 for (p = pre->points; *p != NULL; p++) 149 EC_POINT_free(*p); 150 OPENSSL_free(pre->points); 151 } 152 OPENSSL_free(pre); 153 } 154 155 static void ec_pre_comp_clear_free(void *pre_) 156 { 157 int i; 158 EC_PRE_COMP *pre = pre_; 159 160 if (!pre) 161 return; 162 163 i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); 164 if (i > 0) 165 return; 166 167 if (pre->points) 168 { 169 EC_POINT **p; 170 171 for (p = pre->points; *p != NULL; p++) 172 EC_POINT_clear_free(*p); 173 OPENSSL_cleanse(pre->points, sizeof pre->points); 174 OPENSSL_free(pre->points); 175 } 176 OPENSSL_cleanse(pre, sizeof pre); 177 OPENSSL_free(pre); 178 } 179 180 181 182 183 /* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'. 184 * This is an array r[] of values that are either zero or odd with an 185 * absolute value less than 2^w satisfying 186 * scalar = \sum_j r[j]*2^j 187 * where at most one of any w+1 consecutive digits is non-zero 188 * with the exception that the most significant digit may be only 189 * w-1 zeros away from that next non-zero digit. 190 */ 191 static signed char *compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len) 192 { 193 int window_val; 194 int ok = 0; 195 signed char *r = NULL; 196 int sign = 1; 197 int bit, next_bit, mask; 198 size_t len = 0, j; 199 200 if (BN_is_zero(scalar)) 201 { 202 r = OPENSSL_malloc(1); 203 if (!r) 204 { 205 ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); 206 goto err; 207 } 208 r[0] = 0; 209 *ret_len = 1; 210 return r; 211 } 212 213 if (w <= 0 || w > 7) /* 'signed char' can represent integers with absolute values less than 2^7 */ 214 { 215 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 216 goto err; 217 } 218 bit = 1 << w; /* at most 128 */ 219 next_bit = bit << 1; /* at most 256 */ 220 mask = next_bit - 1; /* at most 255 */ 221 222 if (BN_is_negative(scalar)) 223 { 224 sign = -1; 225 } 226 227 len = BN_num_bits(scalar); 228 r = OPENSSL_malloc(len + 1); /* modified wNAF may be one digit longer than binary representation 229 * (*ret_len will be set to the actual length, i.e. at most 230 * BN_num_bits(scalar) + 1) */ 231 if (r == NULL) 232 { 233 ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); 234 goto err; 235 } 236 237 if (scalar->d == NULL || scalar->top == 0) 238 { 239 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 240 goto err; 241 } 242 window_val = scalar->d[0] & mask; 243 j = 0; 244 while ((window_val != 0) || (j + w + 1 < len)) /* if j+w+1 >= len, window_val will not increase */ 245 { 246 int digit = 0; 247 248 /* 0 <= window_val <= 2^(w+1) */ 249 250 if (window_val & 1) 251 { 252 /* 0 < window_val < 2^(w+1) */ 253 254 if (window_val & bit) 255 { 256 digit = window_val - next_bit; /* -2^w < digit < 0 */ 257 258 #if 1 /* modified wNAF */ 259 if (j + w + 1 >= len) 260 { 261 /* special case for generating modified wNAFs: 262 * no new bits will be added into window_val, 263 * so using a positive digit here will decrease 264 * the total length of the representation */ 265 266 digit = window_val & (mask >> 1); /* 0 < digit < 2^w */ 267 } 268 #endif 269 } 270 else 271 { 272 digit = window_val; /* 0 < digit < 2^w */ 273 } 274 275 if (digit <= -bit || digit >= bit || !(digit & 1)) 276 { 277 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 278 goto err; 279 } 280 281 window_val -= digit; 282 283 /* now window_val is 0 or 2^(w+1) in standard wNAF generation; 284 * for modified window NAFs, it may also be 2^w 285 */ 286 if (window_val != 0 && window_val != next_bit && window_val != bit) 287 { 288 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 289 goto err; 290 } 291 } 292 293 r[j++] = sign * digit; 294 295 window_val >>= 1; 296 window_val += bit * BN_is_bit_set(scalar, j + w); 297 298 if (window_val > next_bit) 299 { 300 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 301 goto err; 302 } 303 } 304 305 if (j > len + 1) 306 { 307 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 308 goto err; 309 } 310 len = j; 311 ok = 1; 312 313 err: 314 if (!ok) 315 { 316 OPENSSL_free(r); 317 r = NULL; 318 } 319 if (ok) 320 *ret_len = len; 321 return r; 322 } 323 324 325 /* TODO: table should be optimised for the wNAF-based implementation, 326 * sometimes smaller windows will give better performance 327 * (thus the boundaries should be increased) 328 */ 329 #define EC_window_bits_for_scalar_size(b) \ 330 ((size_t) \ 331 ((b) >= 2000 ? 6 : \ 332 (b) >= 800 ? 5 : \ 333 (b) >= 300 ? 4 : \ 334 (b) >= 70 ? 3 : \ 335 (b) >= 20 ? 2 : \ 336 1)) 337 338 /* Compute 339 * \sum scalars[i]*points[i], 340 * also including 341 * scalar*generator 342 * in the addition if scalar != NULL 343 */ 344 int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 345 size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx) 346 { 347 BN_CTX *new_ctx = NULL; 348 const EC_POINT *generator = NULL; 349 EC_POINT *tmp = NULL; 350 size_t totalnum; 351 size_t blocksize = 0, numblocks = 0; /* for wNAF splitting */ 352 size_t pre_points_per_block = 0; 353 size_t i, j; 354 int k; 355 int r_is_inverted = 0; 356 int r_is_at_infinity = 1; 357 size_t *wsize = NULL; /* individual window sizes */ 358 signed char **wNAF = NULL; /* individual wNAFs */ 359 size_t *wNAF_len = NULL; 360 size_t max_len = 0; 361 size_t num_val; 362 EC_POINT **val = NULL; /* precomputation */ 363 EC_POINT **v; 364 EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' or 'pre_comp->points' */ 365 const EC_PRE_COMP *pre_comp = NULL; 366 int num_scalar = 0; /* flag: will be set to 1 if 'scalar' must be treated like other scalars, 367 * i.e. precomputation is not available */ 368 int ret = 0; 369 370 if (group->meth != r->meth) 371 { 372 ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); 373 return 0; 374 } 375 376 if ((scalar == NULL) && (num == 0)) 377 { 378 return EC_POINT_set_to_infinity(group, r); 379 } 380 381 for (i = 0; i < num; i++) 382 { 383 if (group->meth != points[i]->meth) 384 { 385 ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); 386 return 0; 387 } 388 } 389 390 if (ctx == NULL) 391 { 392 ctx = new_ctx = BN_CTX_new(); 393 if (ctx == NULL) 394 goto err; 395 } 396 397 if (scalar != NULL) 398 { 399 generator = EC_GROUP_get0_generator(group); 400 if (generator == NULL) 401 { 402 ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR); 403 goto err; 404 } 405 406 /* look if we can use precomputed multiples of generator */ 407 408 pre_comp = EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free); 409 410 if (pre_comp && pre_comp->numblocks && (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) == 0)) 411 { 412 blocksize = pre_comp->blocksize; 413 414 /* determine maximum number of blocks that wNAF splitting may yield 415 * (NB: maximum wNAF length is bit length plus one) */ 416 numblocks = (BN_num_bits(scalar) / blocksize) + 1; 417 418 /* we cannot use more blocks than we have precomputation for */ 419 if (numblocks > pre_comp->numblocks) 420 numblocks = pre_comp->numblocks; 421 422 pre_points_per_block = 1u << (pre_comp->w - 1); 423 424 /* check that pre_comp looks sane */ 425 if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block)) 426 { 427 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 428 goto err; 429 } 430 } 431 else 432 { 433 /* can't use precomputation */ 434 pre_comp = NULL; 435 numblocks = 1; 436 num_scalar = 1; /* treat 'scalar' like 'num'-th element of 'scalars' */ 437 } 438 } 439 440 totalnum = num + numblocks; 441 442 wsize = OPENSSL_malloc(totalnum * sizeof wsize[0]); 443 wNAF_len = OPENSSL_malloc(totalnum * sizeof wNAF_len[0]); 444 wNAF = OPENSSL_malloc((totalnum + 1) * sizeof wNAF[0]); /* includes space for pivot */ 445 val_sub = OPENSSL_malloc(totalnum * sizeof val_sub[0]); 446 447 if (!wsize || !wNAF_len || !wNAF || !val_sub) 448 { 449 ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 450 goto err; 451 } 452 453 wNAF[0] = NULL; /* preliminary pivot */ 454 455 /* num_val will be the total number of temporarily precomputed points */ 456 num_val = 0; 457 458 for (i = 0; i < num + num_scalar; i++) 459 { 460 size_t bits; 461 462 bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar); 463 wsize[i] = EC_window_bits_for_scalar_size(bits); 464 num_val += 1u << (wsize[i] - 1); 465 wNAF[i + 1] = NULL; /* make sure we always have a pivot */ 466 wNAF[i] = compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], &wNAF_len[i]); 467 if (wNAF[i] == NULL) 468 goto err; 469 if (wNAF_len[i] > max_len) 470 max_len = wNAF_len[i]; 471 } 472 473 if (numblocks) 474 { 475 /* we go here iff scalar != NULL */ 476 477 if (pre_comp == NULL) 478 { 479 if (num_scalar != 1) 480 { 481 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 482 goto err; 483 } 484 /* we have already generated a wNAF for 'scalar' */ 485 } 486 else 487 { 488 signed char *tmp_wNAF = NULL; 489 size_t tmp_len = 0; 490 491 if (num_scalar != 0) 492 { 493 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 494 goto err; 495 } 496 497 /* use the window size for which we have precomputation */ 498 wsize[num] = pre_comp->w; 499 tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len); 500 if (!tmp_wNAF) 501 goto err; 502 503 if (tmp_len <= max_len) 504 { 505 /* One of the other wNAFs is at least as long 506 * as the wNAF belonging to the generator, 507 * so wNAF splitting will not buy us anything. */ 508 509 numblocks = 1; 510 totalnum = num + 1; /* don't use wNAF splitting */ 511 wNAF[num] = tmp_wNAF; 512 wNAF[num + 1] = NULL; 513 wNAF_len[num] = tmp_len; 514 if (tmp_len > max_len) 515 max_len = tmp_len; 516 /* pre_comp->points starts with the points that we need here: */ 517 val_sub[num] = pre_comp->points; 518 } 519 else 520 { 521 /* don't include tmp_wNAF directly into wNAF array 522 * - use wNAF splitting and include the blocks */ 523 524 signed char *pp; 525 EC_POINT **tmp_points; 526 527 if (tmp_len < numblocks * blocksize) 528 { 529 /* possibly we can do with fewer blocks than estimated */ 530 numblocks = (tmp_len + blocksize - 1) / blocksize; 531 if (numblocks > pre_comp->numblocks) 532 { 533 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 534 goto err; 535 } 536 totalnum = num + numblocks; 537 } 538 539 /* split wNAF in 'numblocks' parts */ 540 pp = tmp_wNAF; 541 tmp_points = pre_comp->points; 542 543 for (i = num; i < totalnum; i++) 544 { 545 if (i < totalnum - 1) 546 { 547 wNAF_len[i] = blocksize; 548 if (tmp_len < blocksize) 549 { 550 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 551 goto err; 552 } 553 tmp_len -= blocksize; 554 } 555 else 556 /* last block gets whatever is left 557 * (this could be more or less than 'blocksize'!) */ 558 wNAF_len[i] = tmp_len; 559 560 wNAF[i + 1] = NULL; 561 wNAF[i] = OPENSSL_malloc(wNAF_len[i]); 562 if (wNAF[i] == NULL) 563 { 564 ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 565 OPENSSL_free(tmp_wNAF); 566 goto err; 567 } 568 memcpy(wNAF[i], pp, wNAF_len[i]); 569 if (wNAF_len[i] > max_len) 570 max_len = wNAF_len[i]; 571 572 if (*tmp_points == NULL) 573 { 574 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 575 OPENSSL_free(tmp_wNAF); 576 goto err; 577 } 578 val_sub[i] = tmp_points; 579 tmp_points += pre_points_per_block; 580 pp += blocksize; 581 } 582 OPENSSL_free(tmp_wNAF); 583 } 584 } 585 } 586 587 /* All points we precompute now go into a single array 'val'. 588 * 'val_sub[i]' is a pointer to the subarray for the i-th point, 589 * or to a subarray of 'pre_comp->points' if we already have precomputation. */ 590 val = OPENSSL_malloc((num_val + 1) * sizeof val[0]); 591 if (val == NULL) 592 { 593 ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 594 goto err; 595 } 596 val[num_val] = NULL; /* pivot element */ 597 598 /* allocate points for precomputation */ 599 v = val; 600 for (i = 0; i < num + num_scalar; i++) 601 { 602 val_sub[i] = v; 603 for (j = 0; j < (1u << (wsize[i] - 1)); j++) 604 { 605 *v = EC_POINT_new(group); 606 if (*v == NULL) goto err; 607 v++; 608 } 609 } 610 if (!(v == val + num_val)) 611 { 612 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 613 goto err; 614 } 615 616 if (!(tmp = EC_POINT_new(group))) 617 goto err; 618 619 /* prepare precomputed values: 620 * val_sub[i][0] := points[i] 621 * val_sub[i][1] := 3 * points[i] 622 * val_sub[i][2] := 5 * points[i] 623 * ... 624 */ 625 for (i = 0; i < num + num_scalar; i++) 626 { 627 if (i < num) 628 { 629 if (!EC_POINT_copy(val_sub[i][0], points[i])) goto err; 630 } 631 else 632 { 633 if (!EC_POINT_copy(val_sub[i][0], generator)) goto err; 634 } 635 636 if (wsize[i] > 1) 637 { 638 if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) goto err; 639 for (j = 1; j < (1u << (wsize[i] - 1)); j++) 640 { 641 if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) goto err; 642 } 643 } 644 } 645 646 #if 1 /* optional; EC_window_bits_for_scalar_size assumes we do this step */ 647 if (!EC_POINTs_make_affine(group, num_val, val, ctx)) 648 goto err; 649 #endif 650 651 r_is_at_infinity = 1; 652 653 for (k = max_len - 1; k >= 0; k--) 654 { 655 if (!r_is_at_infinity) 656 { 657 if (!EC_POINT_dbl(group, r, r, ctx)) goto err; 658 } 659 660 for (i = 0; i < totalnum; i++) 661 { 662 if (wNAF_len[i] > (size_t)k) 663 { 664 int digit = wNAF[i][k]; 665 int is_neg; 666 667 if (digit) 668 { 669 is_neg = digit < 0; 670 671 if (is_neg) 672 digit = -digit; 673 674 if (is_neg != r_is_inverted) 675 { 676 if (!r_is_at_infinity) 677 { 678 if (!EC_POINT_invert(group, r, ctx)) goto err; 679 } 680 r_is_inverted = !r_is_inverted; 681 } 682 683 /* digit > 0 */ 684 685 if (r_is_at_infinity) 686 { 687 if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) goto err; 688 r_is_at_infinity = 0; 689 } 690 else 691 { 692 if (!EC_POINT_add(group, r, r, val_sub[i][digit >> 1], ctx)) goto err; 693 } 694 } 695 } 696 } 697 } 698 699 if (r_is_at_infinity) 700 { 701 if (!EC_POINT_set_to_infinity(group, r)) goto err; 702 } 703 else 704 { 705 if (r_is_inverted) 706 if (!EC_POINT_invert(group, r, ctx)) goto err; 707 } 708 709 ret = 1; 710 711 err: 712 if (new_ctx != NULL) 713 BN_CTX_free(new_ctx); 714 if (tmp != NULL) 715 EC_POINT_free(tmp); 716 if (wsize != NULL) 717 OPENSSL_free(wsize); 718 if (wNAF_len != NULL) 719 OPENSSL_free(wNAF_len); 720 if (wNAF != NULL) 721 { 722 signed char **w; 723 724 for (w = wNAF; *w != NULL; w++) 725 OPENSSL_free(*w); 726 727 OPENSSL_free(wNAF); 728 } 729 if (val != NULL) 730 { 731 for (v = val; *v != NULL; v++) 732 EC_POINT_clear_free(*v); 733 734 OPENSSL_free(val); 735 } 736 if (val_sub != NULL) 737 { 738 OPENSSL_free(val_sub); 739 } 740 return ret; 741 } 742 743 744 /* ec_wNAF_precompute_mult() 745 * creates an EC_PRE_COMP object with preprecomputed multiples of the generator 746 * for use with wNAF splitting as implemented in ec_wNAF_mul(). 747 * 748 * 'pre_comp->points' is an array of multiples of the generator 749 * of the following form: 750 * points[0] = generator; 751 * points[1] = 3 * generator; 752 * ... 753 * points[2^(w-1)-1] = (2^(w-1)-1) * generator; 754 * points[2^(w-1)] = 2^blocksize * generator; 755 * points[2^(w-1)+1] = 3 * 2^blocksize * generator; 756 * ... 757 * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) * 2^(blocksize*(numblocks-2)) * generator 758 * points[2^(w-1)*(numblocks-1)] = 2^(blocksize*(numblocks-1)) * generator 759 * ... 760 * points[2^(w-1)*numblocks-1] = (2^(w-1)) * 2^(blocksize*(numblocks-1)) * generator 761 * points[2^(w-1)*numblocks] = NULL 762 */ 763 int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) 764 { 765 const EC_POINT *generator; 766 EC_POINT *tmp_point = NULL, *base = NULL, **var; 767 BN_CTX *new_ctx = NULL; 768 BIGNUM *order; 769 size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num; 770 EC_POINT **points = NULL; 771 EC_PRE_COMP *pre_comp; 772 int ret = 0; 773 774 /* if there is an old EC_PRE_COMP object, throw it away */ 775 EC_EX_DATA_free_data(&group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free); 776 777 if ((pre_comp = ec_pre_comp_new(group)) == NULL) 778 return 0; 779 780 generator = EC_GROUP_get0_generator(group); 781 if (generator == NULL) 782 { 783 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR); 784 goto err; 785 } 786 787 if (ctx == NULL) 788 { 789 ctx = new_ctx = BN_CTX_new(); 790 if (ctx == NULL) 791 goto err; 792 } 793 794 BN_CTX_start(ctx); 795 order = BN_CTX_get(ctx); 796 if (order == NULL) goto err; 797 798 if (!EC_GROUP_get_order(group, order, ctx)) goto err; 799 if (BN_is_zero(order)) 800 { 801 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER); 802 goto err; 803 } 804 805 bits = BN_num_bits(order); 806 /* The following parameters mean we precompute (approximately) 807 * one point per bit. 808 * 809 * TBD: The combination 8, 4 is perfect for 160 bits; for other 810 * bit lengths, other parameter combinations might provide better 811 * efficiency. 812 */ 813 blocksize = 8; 814 w = 4; 815 if (EC_window_bits_for_scalar_size(bits) > w) 816 { 817 /* let's not make the window too small ... */ 818 w = EC_window_bits_for_scalar_size(bits); 819 } 820 821 numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks to use for wNAF splitting */ 822 823 pre_points_per_block = 1u << (w - 1); 824 num = pre_points_per_block * numblocks; /* number of points to compute and store */ 825 826 points = OPENSSL_malloc(sizeof (EC_POINT*)*(num + 1)); 827 if (!points) 828 { 829 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 830 goto err; 831 } 832 833 var = points; 834 var[num] = NULL; /* pivot */ 835 for (i = 0; i < num; i++) 836 { 837 if ((var[i] = EC_POINT_new(group)) == NULL) 838 { 839 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 840 goto err; 841 } 842 } 843 844 if (!(tmp_point = EC_POINT_new(group)) || !(base = EC_POINT_new(group))) 845 { 846 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 847 goto err; 848 } 849 850 if (!EC_POINT_copy(base, generator)) 851 goto err; 852 853 /* do the precomputation */ 854 for (i = 0; i < numblocks; i++) 855 { 856 size_t j; 857 858 if (!EC_POINT_dbl(group, tmp_point, base, ctx)) 859 goto err; 860 861 if (!EC_POINT_copy(*var++, base)) 862 goto err; 863 864 for (j = 1; j < pre_points_per_block; j++, var++) 865 { 866 /* calculate odd multiples of the current base point */ 867 if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx)) 868 goto err; 869 } 870 871 if (i < numblocks - 1) 872 { 873 /* get the next base (multiply current one by 2^blocksize) */ 874 size_t k; 875 876 if (blocksize <= 2) 877 { 878 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_INTERNAL_ERROR); 879 goto err; 880 } 881 882 if (!EC_POINT_dbl(group, base, tmp_point, ctx)) 883 goto err; 884 for (k = 2; k < blocksize; k++) 885 { 886 if (!EC_POINT_dbl(group,base,base,ctx)) 887 goto err; 888 } 889 } 890 } 891 892 if (!EC_POINTs_make_affine(group, num, points, ctx)) 893 goto err; 894 895 pre_comp->group = group; 896 pre_comp->blocksize = blocksize; 897 pre_comp->numblocks = numblocks; 898 pre_comp->w = w; 899 pre_comp->points = points; 900 points = NULL; 901 pre_comp->num = num; 902 903 if (!EC_EX_DATA_set_data(&group->extra_data, pre_comp, 904 ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free)) 905 goto err; 906 pre_comp = NULL; 907 908 ret = 1; 909 err: 910 if (ctx != NULL) 911 BN_CTX_end(ctx); 912 if (new_ctx != NULL) 913 BN_CTX_free(new_ctx); 914 if (pre_comp) 915 ec_pre_comp_free(pre_comp); 916 if (points) 917 { 918 EC_POINT **p; 919 920 for (p = points; *p != NULL; p++) 921 EC_POINT_free(*p); 922 OPENSSL_free(points); 923 } 924 if (tmp_point) 925 EC_POINT_free(tmp_point); 926 if (base) 927 EC_POINT_free(base); 928 return ret; 929 } 930 931 932 int ec_wNAF_have_precompute_mult(const EC_GROUP *group) 933 { 934 if (EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free) != NULL) 935 return 1; 936 else 937 return 0; 938 } 939
