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