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