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