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