ec_mult.c revision 325335
1109998Smarkm/* crypto/ec/ec_mult.c */ 2160814Ssimon/* 3160814Ssimon * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project. 4160814Ssimon */ 5109998Smarkm/* ==================================================================== 6194206Ssimon * Copyright (c) 1998-2007 The OpenSSL Project. All rights reserved. 7109998Smarkm * 8109998Smarkm * Redistribution and use in source and binary forms, with or without 9109998Smarkm * modification, are permitted provided that the following conditions 10109998Smarkm * are met: 11109998Smarkm * 12109998Smarkm * 1. Redistributions of source code must retain the above copyright 13280297Sjkim * notice, this list of conditions and the following disclaimer. 14109998Smarkm * 15109998Smarkm * 2. Redistributions in binary form must reproduce the above copyright 16109998Smarkm * notice, this list of conditions and the following disclaimer in 17109998Smarkm * the documentation and/or other materials provided with the 18109998Smarkm * distribution. 19109998Smarkm * 20109998Smarkm * 3. All advertising materials mentioning features or use of this 21109998Smarkm * software must display the following acknowledgment: 22109998Smarkm * "This product includes software developed by the OpenSSL Project 23109998Smarkm * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 24109998Smarkm * 25109998Smarkm * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 26109998Smarkm * endorse or promote products derived from this software without 27109998Smarkm * prior written permission. For written permission, please contact 28109998Smarkm * openssl-core@openssl.org. 29109998Smarkm * 30109998Smarkm * 5. Products derived from this software may not be called "OpenSSL" 31109998Smarkm * nor may "OpenSSL" appear in their names without prior written 32109998Smarkm * permission of the OpenSSL Project. 33109998Smarkm * 34109998Smarkm * 6. Redistributions of any form whatsoever must retain the following 35109998Smarkm * acknowledgment: 36109998Smarkm * "This product includes software developed by the OpenSSL Project 37109998Smarkm * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 38109998Smarkm * 39109998Smarkm * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 40109998Smarkm * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 41109998Smarkm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 42109998Smarkm * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 43109998Smarkm * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44109998Smarkm * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 45109998Smarkm * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 46109998Smarkm * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47109998Smarkm * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 48109998Smarkm * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 49109998Smarkm * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 50109998Smarkm * OF THE POSSIBILITY OF SUCH DAMAGE. 51109998Smarkm * ==================================================================== 52109998Smarkm * 53109998Smarkm * This product includes cryptographic software written by Eric Young 54109998Smarkm * (eay@cryptsoft.com). This product includes software written by Tim 55109998Smarkm * Hudson (tjh@cryptsoft.com). 56109998Smarkm * 57109998Smarkm */ 58160814Ssimon/* ==================================================================== 59160814Ssimon * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 60160814Ssimon * Portions of this software developed by SUN MICROSYSTEMS, INC., 61160814Ssimon * and contributed to the OpenSSL project. 62160814Ssimon */ 63109998Smarkm 64160814Ssimon#include <string.h> 65160814Ssimon 66109998Smarkm#include <openssl/err.h> 67109998Smarkm 68109998Smarkm#include "ec_lcl.h" 69109998Smarkm 70160814Ssimon/* 71325335Sjkim * This file implements the wNAF-based interleaving multi-exponentiation method 72325335Sjkim * Formerly at: 73325335Sjkim * http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp 74325335Sjkim * You might now find it here: 75325335Sjkim * http://link.springer.com/chapter/10.1007%2F3-540-45537-X_13 76325335Sjkim * http://www.bmoeller.de/pdf/TI-01-08.multiexp.pdf 77325335Sjkim * For multiplication with precomputation, we use wNAF splitting, formerly at: 78325335Sjkim * http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp 79160814Ssimon */ 80109998Smarkm 81160814Ssimon/* structure for precomputed multiples of the generator */ 82160814Ssimontypedef struct ec_pre_comp_st { 83280297Sjkim const EC_GROUP *group; /* parent EC_GROUP object */ 84280297Sjkim size_t blocksize; /* block size for wNAF splitting */ 85280297Sjkim size_t numblocks; /* max. number of blocks for which we have 86280297Sjkim * precomputation */ 87280297Sjkim size_t w; /* window size */ 88280297Sjkim EC_POINT **points; /* array with pre-calculated multiples of 89280297Sjkim * generator: 'num' pointers to EC_POINT 90280297Sjkim * objects followed by a NULL */ 91280297Sjkim size_t num; /* numblocks * 2^(w-1) */ 92280297Sjkim int references; 93160814Ssimon} EC_PRE_COMP; 94280297Sjkim 95160814Ssimon/* functions to manage EC_PRE_COMP within the EC_GROUP extra_data framework */ 96160814Ssimonstatic void *ec_pre_comp_dup(void *); 97160814Ssimonstatic void ec_pre_comp_free(void *); 98160814Ssimonstatic void ec_pre_comp_clear_free(void *); 99109998Smarkm 100160814Ssimonstatic EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group) 101280297Sjkim{ 102280297Sjkim EC_PRE_COMP *ret = NULL; 103160814Ssimon 104280297Sjkim if (!group) 105280297Sjkim return NULL; 106160814Ssimon 107280297Sjkim ret = (EC_PRE_COMP *)OPENSSL_malloc(sizeof(EC_PRE_COMP)); 108280297Sjkim if (!ret) { 109280297Sjkim ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE); 110280297Sjkim return ret; 111280297Sjkim } 112280297Sjkim ret->group = group; 113280297Sjkim ret->blocksize = 8; /* default */ 114280297Sjkim ret->numblocks = 0; 115280297Sjkim ret->w = 4; /* default */ 116280297Sjkim ret->points = NULL; 117280297Sjkim ret->num = 0; 118280297Sjkim ret->references = 1; 119280297Sjkim return ret; 120280297Sjkim} 121160814Ssimon 122160814Ssimonstatic void *ec_pre_comp_dup(void *src_) 123280297Sjkim{ 124280297Sjkim EC_PRE_COMP *src = src_; 125160814Ssimon 126280297Sjkim /* no need to actually copy, these objects never change! */ 127160814Ssimon 128280297Sjkim CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP); 129160814Ssimon 130280297Sjkim return src_; 131280297Sjkim} 132160814Ssimon 133160814Ssimonstatic void ec_pre_comp_free(void *pre_) 134280297Sjkim{ 135280297Sjkim int i; 136280297Sjkim EC_PRE_COMP *pre = pre_; 137160814Ssimon 138280297Sjkim if (!pre) 139280297Sjkim return; 140160814Ssimon 141280297Sjkim i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); 142280297Sjkim if (i > 0) 143280297Sjkim return; 144160814Ssimon 145280297Sjkim if (pre->points) { 146280297Sjkim EC_POINT **p; 147160814Ssimon 148280297Sjkim for (p = pre->points; *p != NULL; p++) 149280297Sjkim EC_POINT_free(*p); 150280297Sjkim OPENSSL_free(pre->points); 151280297Sjkim } 152280297Sjkim OPENSSL_free(pre); 153280297Sjkim} 154160814Ssimon 155160814Ssimonstatic void ec_pre_comp_clear_free(void *pre_) 156280297Sjkim{ 157280297Sjkim int i; 158280297Sjkim EC_PRE_COMP *pre = pre_; 159160814Ssimon 160280297Sjkim if (!pre) 161280297Sjkim return; 162160814Ssimon 163280297Sjkim i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); 164280297Sjkim if (i > 0) 165280297Sjkim return; 166160814Ssimon 167280297Sjkim if (pre->points) { 168280297Sjkim EC_POINT **p; 169160814Ssimon 170280297Sjkim for (p = pre->points; *p != NULL; p++) { 171280297Sjkim EC_POINT_clear_free(*p); 172280297Sjkim OPENSSL_cleanse(p, sizeof *p); 173280297Sjkim } 174280297Sjkim OPENSSL_free(pre->points); 175280297Sjkim } 176280297Sjkim OPENSSL_cleanse(pre, sizeof *pre); 177280297Sjkim OPENSSL_free(pre); 178280297Sjkim} 179160814Ssimon 180280297Sjkim/*- 181280297Sjkim * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'. 182109998Smarkm * This is an array r[] of values that are either zero or odd with an 183109998Smarkm * absolute value less than 2^w satisfying 184109998Smarkm * scalar = \sum_j r[j]*2^j 185160814Ssimon * where at most one of any w+1 consecutive digits is non-zero 186160814Ssimon * with the exception that the most significant digit may be only 187160814Ssimon * w-1 zeros away from that next non-zero digit. 188109998Smarkm */ 189160814Ssimonstatic signed char *compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len) 190280297Sjkim{ 191280297Sjkim int window_val; 192280297Sjkim int ok = 0; 193280297Sjkim signed char *r = NULL; 194280297Sjkim int sign = 1; 195280297Sjkim int bit, next_bit, mask; 196280297Sjkim size_t len = 0, j; 197109998Smarkm 198280297Sjkim if (BN_is_zero(scalar)) { 199280297Sjkim r = OPENSSL_malloc(1); 200280297Sjkim if (!r) { 201280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); 202280297Sjkim goto err; 203280297Sjkim } 204280297Sjkim r[0] = 0; 205280297Sjkim *ret_len = 1; 206280297Sjkim return r; 207280297Sjkim } 208109998Smarkm 209280297Sjkim if (w <= 0 || w > 7) { /* 'signed char' can represent integers with 210280297Sjkim * absolute values less than 2^7 */ 211280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 212280297Sjkim goto err; 213280297Sjkim } 214280297Sjkim bit = 1 << w; /* at most 128 */ 215280297Sjkim next_bit = bit << 1; /* at most 256 */ 216280297Sjkim mask = next_bit - 1; /* at most 255 */ 217238405Sjkim 218280297Sjkim if (BN_is_negative(scalar)) { 219280297Sjkim sign = -1; 220280297Sjkim } 221109998Smarkm 222280297Sjkim if (scalar->d == NULL || scalar->top == 0) { 223280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 224280297Sjkim goto err; 225280297Sjkim } 226160814Ssimon 227280297Sjkim len = BN_num_bits(scalar); 228280297Sjkim r = OPENSSL_malloc(len + 1); /* modified wNAF may be one digit longer 229280297Sjkim * than binary representation (*ret_len will 230280297Sjkim * be set to the actual length, i.e. at most 231280297Sjkim * BN_num_bits(scalar) + 1) */ 232280297Sjkim if (r == NULL) { 233280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); 234280297Sjkim goto err; 235280297Sjkim } 236280297Sjkim window_val = scalar->d[0] & mask; 237280297Sjkim j = 0; 238280297Sjkim while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len, 239280297Sjkim * window_val will not 240280297Sjkim * increase */ 241280297Sjkim int digit = 0; 242160814Ssimon 243280297Sjkim /* 0 <= window_val <= 2^(w+1) */ 244160814Ssimon 245280297Sjkim if (window_val & 1) { 246280297Sjkim /* 0 < window_val < 2^(w+1) */ 247280297Sjkim 248280297Sjkim if (window_val & bit) { 249280297Sjkim digit = window_val - next_bit; /* -2^w < digit < 0 */ 250280297Sjkim 251280297Sjkim#if 1 /* modified wNAF */ 252280297Sjkim if (j + w + 1 >= len) { 253280297Sjkim /* 254280297Sjkim * special case for generating modified wNAFs: no new 255280297Sjkim * bits will be added into window_val, so using a 256280297Sjkim * positive digit here will decrease the total length of 257280297Sjkim * the representation 258280297Sjkim */ 259280297Sjkim 260280297Sjkim digit = window_val & (mask >> 1); /* 0 < digit < 2^w */ 261280297Sjkim } 262160814Ssimon#endif 263280297Sjkim } else { 264280297Sjkim digit = window_val; /* 0 < digit < 2^w */ 265280297Sjkim } 266109998Smarkm 267280297Sjkim if (digit <= -bit || digit >= bit || !(digit & 1)) { 268280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 269280297Sjkim goto err; 270280297Sjkim } 271160814Ssimon 272280297Sjkim window_val -= digit; 273109998Smarkm 274280297Sjkim /* 275280297Sjkim * now window_val is 0 or 2^(w+1) in standard wNAF generation; 276280297Sjkim * for modified window NAFs, it may also be 2^w 277280297Sjkim */ 278280297Sjkim if (window_val != 0 && window_val != next_bit 279280297Sjkim && window_val != bit) { 280280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 281280297Sjkim goto err; 282280297Sjkim } 283280297Sjkim } 284160814Ssimon 285280297Sjkim r[j++] = sign * digit; 286160814Ssimon 287280297Sjkim window_val >>= 1; 288280297Sjkim window_val += bit * BN_is_bit_set(scalar, j + w); 289109998Smarkm 290280297Sjkim if (window_val > next_bit) { 291280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 292280297Sjkim goto err; 293280297Sjkim } 294280297Sjkim } 295109998Smarkm 296280297Sjkim if (j > len + 1) { 297280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 298280297Sjkim goto err; 299280297Sjkim } 300280297Sjkim len = j; 301280297Sjkim ok = 1; 302280297Sjkim 303109998Smarkm err: 304280297Sjkim if (!ok) { 305280297Sjkim OPENSSL_free(r); 306280297Sjkim r = NULL; 307280297Sjkim } 308280297Sjkim if (ok) 309280297Sjkim *ret_len = len; 310280297Sjkim return r; 311280297Sjkim} 312109998Smarkm 313280297Sjkim/* 314280297Sjkim * TODO: table should be optimised for the wNAF-based implementation, 315280297Sjkim * sometimes smaller windows will give better performance (thus the 316280297Sjkim * boundaries should be increased) 317109998Smarkm */ 318109998Smarkm#define EC_window_bits_for_scalar_size(b) \ 319280297Sjkim ((size_t) \ 320280297Sjkim ((b) >= 2000 ? 6 : \ 321280297Sjkim (b) >= 800 ? 5 : \ 322280297Sjkim (b) >= 300 ? 4 : \ 323280297Sjkim (b) >= 70 ? 3 : \ 324280297Sjkim (b) >= 20 ? 2 : \ 325280297Sjkim 1)) 326109998Smarkm 327280297Sjkim/*- 328280297Sjkim * Compute 329109998Smarkm * \sum scalars[i]*points[i], 330109998Smarkm * also including 331109998Smarkm * scalar*generator 332109998Smarkm * in the addition if scalar != NULL 333109998Smarkm */ 334160814Ssimonint ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 335280297Sjkim size_t num, const EC_POINT *points[], const BIGNUM *scalars[], 336280297Sjkim BN_CTX *ctx) 337280297Sjkim{ 338280297Sjkim BN_CTX *new_ctx = NULL; 339280297Sjkim const EC_POINT *generator = NULL; 340280297Sjkim EC_POINT *tmp = NULL; 341280297Sjkim size_t totalnum; 342280297Sjkim size_t blocksize = 0, numblocks = 0; /* for wNAF splitting */ 343280297Sjkim size_t pre_points_per_block = 0; 344280297Sjkim size_t i, j; 345280297Sjkim int k; 346280297Sjkim int r_is_inverted = 0; 347280297Sjkim int r_is_at_infinity = 1; 348280297Sjkim size_t *wsize = NULL; /* individual window sizes */ 349280297Sjkim signed char **wNAF = NULL; /* individual wNAFs */ 350280297Sjkim size_t *wNAF_len = NULL; 351280297Sjkim size_t max_len = 0; 352280297Sjkim size_t num_val; 353280297Sjkim EC_POINT **val = NULL; /* precomputation */ 354280297Sjkim EC_POINT **v; 355280297Sjkim EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' or 356280297Sjkim * 'pre_comp->points' */ 357280297Sjkim const EC_PRE_COMP *pre_comp = NULL; 358280297Sjkim int num_scalar = 0; /* flag: will be set to 1 if 'scalar' must be 359280297Sjkim * treated like other scalars, i.e. 360280297Sjkim * precomputation is not available */ 361280297Sjkim int ret = 0; 362111147Snectar 363280297Sjkim if (group->meth != r->meth) { 364280297Sjkim ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); 365280297Sjkim return 0; 366280297Sjkim } 367111147Snectar 368280297Sjkim if ((scalar == NULL) && (num == 0)) { 369280297Sjkim return EC_POINT_set_to_infinity(group, r); 370280297Sjkim } 371160814Ssimon 372280297Sjkim for (i = 0; i < num; i++) { 373280297Sjkim if (group->meth != points[i]->meth) { 374280297Sjkim ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); 375280297Sjkim return 0; 376280297Sjkim } 377280297Sjkim } 378160814Ssimon 379280297Sjkim if (ctx == NULL) { 380280297Sjkim ctx = new_ctx = BN_CTX_new(); 381280297Sjkim if (ctx == NULL) 382280297Sjkim goto err; 383280297Sjkim } 384109998Smarkm 385280297Sjkim if (scalar != NULL) { 386280297Sjkim generator = EC_GROUP_get0_generator(group); 387280297Sjkim if (generator == NULL) { 388280297Sjkim ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR); 389280297Sjkim goto err; 390280297Sjkim } 391109998Smarkm 392280297Sjkim /* look if we can use precomputed multiples of generator */ 393160814Ssimon 394280297Sjkim pre_comp = 395280297Sjkim EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, 396280297Sjkim ec_pre_comp_free, ec_pre_comp_clear_free); 397160814Ssimon 398280297Sjkim if (pre_comp && pre_comp->numblocks 399280297Sjkim && (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) == 400280297Sjkim 0)) { 401280297Sjkim blocksize = pre_comp->blocksize; 402160814Ssimon 403280297Sjkim /* 404280297Sjkim * determine maximum number of blocks that wNAF splitting may 405280297Sjkim * yield (NB: maximum wNAF length is bit length plus one) 406280297Sjkim */ 407280297Sjkim numblocks = (BN_num_bits(scalar) / blocksize) + 1; 408160814Ssimon 409280297Sjkim /* 410280297Sjkim * we cannot use more blocks than we have precomputation for 411280297Sjkim */ 412280297Sjkim if (numblocks > pre_comp->numblocks) 413280297Sjkim numblocks = pre_comp->numblocks; 414109998Smarkm 415280297Sjkim pre_points_per_block = (size_t)1 << (pre_comp->w - 1); 416276861Sjkim 417280297Sjkim /* check that pre_comp looks sane */ 418280297Sjkim if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block)) { 419280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 420280297Sjkim goto err; 421280297Sjkim } 422280297Sjkim } else { 423280297Sjkim /* can't use precomputation */ 424280297Sjkim pre_comp = NULL; 425280297Sjkim numblocks = 1; 426280297Sjkim num_scalar = 1; /* treat 'scalar' like 'num'-th element of 427280297Sjkim * 'scalars' */ 428280297Sjkim } 429280297Sjkim } 430276861Sjkim 431280297Sjkim totalnum = num + numblocks; 432160814Ssimon 433280297Sjkim wsize = OPENSSL_malloc(totalnum * sizeof wsize[0]); 434280297Sjkim wNAF_len = OPENSSL_malloc(totalnum * sizeof wNAF_len[0]); 435280297Sjkim wNAF = OPENSSL_malloc((totalnum + 1) * sizeof wNAF[0]); /* includes space 436280297Sjkim * for pivot */ 437280297Sjkim val_sub = OPENSSL_malloc(totalnum * sizeof val_sub[0]); 438160814Ssimon 439280297Sjkim /* Ensure wNAF is initialised in case we end up going to err */ 440280297Sjkim if (wNAF) 441280297Sjkim wNAF[0] = NULL; /* preliminary pivot */ 442109998Smarkm 443280297Sjkim if (!wsize || !wNAF_len || !wNAF || !val_sub) { 444280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 445280297Sjkim goto err; 446280297Sjkim } 447109998Smarkm 448280297Sjkim /* 449280297Sjkim * num_val will be the total number of temporarily precomputed points 450280297Sjkim */ 451280297Sjkim num_val = 0; 452160814Ssimon 453280297Sjkim for (i = 0; i < num + num_scalar; i++) { 454280297Sjkim size_t bits; 455160814Ssimon 456280297Sjkim bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar); 457280297Sjkim wsize[i] = EC_window_bits_for_scalar_size(bits); 458280297Sjkim num_val += (size_t)1 << (wsize[i] - 1); 459280297Sjkim wNAF[i + 1] = NULL; /* make sure we always have a pivot */ 460280297Sjkim wNAF[i] = 461280297Sjkim compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], 462280297Sjkim &wNAF_len[i]); 463280297Sjkim if (wNAF[i] == NULL) 464280297Sjkim goto err; 465280297Sjkim if (wNAF_len[i] > max_len) 466280297Sjkim max_len = wNAF_len[i]; 467280297Sjkim } 468160814Ssimon 469280297Sjkim if (numblocks) { 470280297Sjkim /* we go here iff scalar != NULL */ 471160814Ssimon 472280297Sjkim if (pre_comp == NULL) { 473280297Sjkim if (num_scalar != 1) { 474280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 475280297Sjkim goto err; 476280297Sjkim } 477280297Sjkim /* we have already generated a wNAF for 'scalar' */ 478280297Sjkim } else { 479280297Sjkim signed char *tmp_wNAF = NULL; 480280297Sjkim size_t tmp_len = 0; 481160814Ssimon 482280297Sjkim if (num_scalar != 0) { 483280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 484280297Sjkim goto err; 485280297Sjkim } 486160814Ssimon 487280297Sjkim /* 488280297Sjkim * use the window size for which we have precomputation 489280297Sjkim */ 490280297Sjkim wsize[num] = pre_comp->w; 491280297Sjkim tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len); 492280297Sjkim if (!tmp_wNAF) 493280297Sjkim goto err; 494160814Ssimon 495280297Sjkim if (tmp_len <= max_len) { 496280297Sjkim /* 497280297Sjkim * One of the other wNAFs is at least as long as the wNAF 498280297Sjkim * belonging to the generator, so wNAF splitting will not buy 499280297Sjkim * us anything. 500280297Sjkim */ 501109998Smarkm 502280297Sjkim numblocks = 1; 503280297Sjkim totalnum = num + 1; /* don't use wNAF splitting */ 504280297Sjkim wNAF[num] = tmp_wNAF; 505280297Sjkim wNAF[num + 1] = NULL; 506280297Sjkim wNAF_len[num] = tmp_len; 507280297Sjkim if (tmp_len > max_len) 508280297Sjkim max_len = tmp_len; 509280297Sjkim /* 510280297Sjkim * pre_comp->points starts with the points that we need here: 511280297Sjkim */ 512280297Sjkim val_sub[num] = pre_comp->points; 513280297Sjkim } else { 514280297Sjkim /* 515280297Sjkim * don't include tmp_wNAF directly into wNAF array - use wNAF 516280297Sjkim * splitting and include the blocks 517280297Sjkim */ 518109998Smarkm 519280297Sjkim signed char *pp; 520280297Sjkim EC_POINT **tmp_points; 521109998Smarkm 522280297Sjkim if (tmp_len < numblocks * blocksize) { 523280297Sjkim /* 524280297Sjkim * possibly we can do with fewer blocks than estimated 525280297Sjkim */ 526280297Sjkim numblocks = (tmp_len + blocksize - 1) / blocksize; 527280297Sjkim if (numblocks > pre_comp->numblocks) { 528280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 529280297Sjkim goto err; 530280297Sjkim } 531280297Sjkim totalnum = num + numblocks; 532280297Sjkim } 533109998Smarkm 534280297Sjkim /* split wNAF in 'numblocks' parts */ 535280297Sjkim pp = tmp_wNAF; 536280297Sjkim tmp_points = pre_comp->points; 537109998Smarkm 538280297Sjkim for (i = num; i < totalnum; i++) { 539280297Sjkim if (i < totalnum - 1) { 540280297Sjkim wNAF_len[i] = blocksize; 541280297Sjkim if (tmp_len < blocksize) { 542280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 543280297Sjkim goto err; 544280297Sjkim } 545280297Sjkim tmp_len -= blocksize; 546280297Sjkim } else 547280297Sjkim /* 548280297Sjkim * last block gets whatever is left (this could be 549280297Sjkim * more or less than 'blocksize'!) 550280297Sjkim */ 551280297Sjkim wNAF_len[i] = tmp_len; 552280297Sjkim 553280297Sjkim wNAF[i + 1] = NULL; 554280297Sjkim wNAF[i] = OPENSSL_malloc(wNAF_len[i]); 555280297Sjkim if (wNAF[i] == NULL) { 556280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 557280297Sjkim OPENSSL_free(tmp_wNAF); 558280297Sjkim goto err; 559280297Sjkim } 560280297Sjkim memcpy(wNAF[i], pp, wNAF_len[i]); 561280297Sjkim if (wNAF_len[i] > max_len) 562280297Sjkim max_len = wNAF_len[i]; 563280297Sjkim 564280297Sjkim if (*tmp_points == NULL) { 565280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 566280297Sjkim OPENSSL_free(tmp_wNAF); 567280297Sjkim goto err; 568280297Sjkim } 569280297Sjkim val_sub[i] = tmp_points; 570280297Sjkim tmp_points += pre_points_per_block; 571280297Sjkim pp += blocksize; 572280297Sjkim } 573280297Sjkim OPENSSL_free(tmp_wNAF); 574280297Sjkim } 575280297Sjkim } 576280297Sjkim } 577280297Sjkim 578280297Sjkim /* 579280297Sjkim * All points we precompute now go into a single array 'val'. 580280297Sjkim * 'val_sub[i]' is a pointer to the subarray for the i-th point, or to a 581280297Sjkim * subarray of 'pre_comp->points' if we already have precomputation. 582280297Sjkim */ 583280297Sjkim val = OPENSSL_malloc((num_val + 1) * sizeof val[0]); 584280297Sjkim if (val == NULL) { 585280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 586280297Sjkim goto err; 587280297Sjkim } 588280297Sjkim val[num_val] = NULL; /* pivot element */ 589280297Sjkim 590280297Sjkim /* allocate points for precomputation */ 591280297Sjkim v = val; 592280297Sjkim for (i = 0; i < num + num_scalar; i++) { 593280297Sjkim val_sub[i] = v; 594280297Sjkim for (j = 0; j < ((size_t)1 << (wsize[i] - 1)); j++) { 595280297Sjkim *v = EC_POINT_new(group); 596280297Sjkim if (*v == NULL) 597280297Sjkim goto err; 598280297Sjkim v++; 599280297Sjkim } 600280297Sjkim } 601280297Sjkim if (!(v == val + num_val)) { 602280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 603280297Sjkim goto err; 604280297Sjkim } 605280297Sjkim 606280297Sjkim if (!(tmp = EC_POINT_new(group))) 607280297Sjkim goto err; 608280297Sjkim 609280297Sjkim /*- 610280297Sjkim * prepare precomputed values: 611280297Sjkim * val_sub[i][0] := points[i] 612280297Sjkim * val_sub[i][1] := 3 * points[i] 613280297Sjkim * val_sub[i][2] := 5 * points[i] 614280297Sjkim * ... 615280297Sjkim */ 616280297Sjkim for (i = 0; i < num + num_scalar; i++) { 617280297Sjkim if (i < num) { 618280297Sjkim if (!EC_POINT_copy(val_sub[i][0], points[i])) 619280297Sjkim goto err; 620280297Sjkim } else { 621280297Sjkim if (!EC_POINT_copy(val_sub[i][0], generator)) 622280297Sjkim goto err; 623280297Sjkim } 624280297Sjkim 625280297Sjkim if (wsize[i] > 1) { 626280297Sjkim if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) 627280297Sjkim goto err; 628280297Sjkim for (j = 1; j < ((size_t)1 << (wsize[i] - 1)); j++) { 629280297Sjkim if (!EC_POINT_add 630280297Sjkim (group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) 631280297Sjkim goto err; 632280297Sjkim } 633280297Sjkim } 634280297Sjkim } 635280297Sjkim 636280297Sjkim#if 1 /* optional; EC_window_bits_for_scalar_size 637280297Sjkim * assumes we do this step */ 638280297Sjkim if (!EC_POINTs_make_affine(group, num_val, val, ctx)) 639280297Sjkim goto err; 640109998Smarkm#endif 641109998Smarkm 642280297Sjkim r_is_at_infinity = 1; 643109998Smarkm 644280297Sjkim for (k = max_len - 1; k >= 0; k--) { 645280297Sjkim if (!r_is_at_infinity) { 646280297Sjkim if (!EC_POINT_dbl(group, r, r, ctx)) 647280297Sjkim goto err; 648280297Sjkim } 649109998Smarkm 650280297Sjkim for (i = 0; i < totalnum; i++) { 651280297Sjkim if (wNAF_len[i] > (size_t)k) { 652280297Sjkim int digit = wNAF[i][k]; 653280297Sjkim int is_neg; 654109998Smarkm 655280297Sjkim if (digit) { 656280297Sjkim is_neg = digit < 0; 657109998Smarkm 658280297Sjkim if (is_neg) 659280297Sjkim digit = -digit; 660109998Smarkm 661280297Sjkim if (is_neg != r_is_inverted) { 662280297Sjkim if (!r_is_at_infinity) { 663280297Sjkim if (!EC_POINT_invert(group, r, ctx)) 664280297Sjkim goto err; 665280297Sjkim } 666280297Sjkim r_is_inverted = !r_is_inverted; 667280297Sjkim } 668109998Smarkm 669280297Sjkim /* digit > 0 */ 670109998Smarkm 671280297Sjkim if (r_is_at_infinity) { 672280297Sjkim if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) 673280297Sjkim goto err; 674280297Sjkim r_is_at_infinity = 0; 675280297Sjkim } else { 676280297Sjkim if (!EC_POINT_add 677280297Sjkim (group, r, r, val_sub[i][digit >> 1], ctx)) 678280297Sjkim goto err; 679280297Sjkim } 680280297Sjkim } 681280297Sjkim } 682280297Sjkim } 683280297Sjkim } 684109998Smarkm 685280297Sjkim if (r_is_at_infinity) { 686280297Sjkim if (!EC_POINT_set_to_infinity(group, r)) 687280297Sjkim goto err; 688280297Sjkim } else { 689280297Sjkim if (r_is_inverted) 690280297Sjkim if (!EC_POINT_invert(group, r, ctx)) 691280297Sjkim goto err; 692280297Sjkim } 693280297Sjkim 694280297Sjkim ret = 1; 695280297Sjkim 696109998Smarkm err: 697280297Sjkim if (new_ctx != NULL) 698280297Sjkim BN_CTX_free(new_ctx); 699280297Sjkim if (tmp != NULL) 700280297Sjkim EC_POINT_free(tmp); 701280297Sjkim if (wsize != NULL) 702280297Sjkim OPENSSL_free(wsize); 703280297Sjkim if (wNAF_len != NULL) 704280297Sjkim OPENSSL_free(wNAF_len); 705280297Sjkim if (wNAF != NULL) { 706280297Sjkim signed char **w; 707109998Smarkm 708280297Sjkim for (w = wNAF; *w != NULL; w++) 709280297Sjkim OPENSSL_free(*w); 710109998Smarkm 711280297Sjkim OPENSSL_free(wNAF); 712280297Sjkim } 713280297Sjkim if (val != NULL) { 714280297Sjkim for (v = val; *v != NULL; v++) 715280297Sjkim EC_POINT_clear_free(*v); 716109998Smarkm 717280297Sjkim OPENSSL_free(val); 718280297Sjkim } 719280297Sjkim if (val_sub != NULL) { 720280297Sjkim OPENSSL_free(val_sub); 721280297Sjkim } 722280297Sjkim return ret; 723280297Sjkim} 724280297Sjkim 725280297Sjkim/*- 726280297Sjkim * ec_wNAF_precompute_mult() 727160814Ssimon * creates an EC_PRE_COMP object with preprecomputed multiples of the generator 728160814Ssimon * for use with wNAF splitting as implemented in ec_wNAF_mul(). 729280297Sjkim * 730160814Ssimon * 'pre_comp->points' is an array of multiples of the generator 731160814Ssimon * of the following form: 732160814Ssimon * points[0] = generator; 733160814Ssimon * points[1] = 3 * generator; 734160814Ssimon * ... 735160814Ssimon * points[2^(w-1)-1] = (2^(w-1)-1) * generator; 736160814Ssimon * points[2^(w-1)] = 2^blocksize * generator; 737160814Ssimon * points[2^(w-1)+1] = 3 * 2^blocksize * generator; 738160814Ssimon * ... 739160814Ssimon * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) * 2^(blocksize*(numblocks-2)) * generator 740160814Ssimon * points[2^(w-1)*(numblocks-1)] = 2^(blocksize*(numblocks-1)) * generator 741160814Ssimon * ... 742160814Ssimon * points[2^(w-1)*numblocks-1] = (2^(w-1)) * 2^(blocksize*(numblocks-1)) * generator 743160814Ssimon * points[2^(w-1)*numblocks] = NULL 744160814Ssimon */ 745160814Ssimonint ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) 746280297Sjkim{ 747280297Sjkim const EC_POINT *generator; 748280297Sjkim EC_POINT *tmp_point = NULL, *base = NULL, **var; 749280297Sjkim BN_CTX *new_ctx = NULL; 750280297Sjkim BIGNUM *order; 751280297Sjkim size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num; 752280297Sjkim EC_POINT **points = NULL; 753280297Sjkim EC_PRE_COMP *pre_comp; 754280297Sjkim int ret = 0; 755109998Smarkm 756280297Sjkim /* if there is an old EC_PRE_COMP object, throw it away */ 757280297Sjkim EC_EX_DATA_free_data(&group->extra_data, ec_pre_comp_dup, 758280297Sjkim ec_pre_comp_free, ec_pre_comp_clear_free); 759160814Ssimon 760280297Sjkim if ((pre_comp = ec_pre_comp_new(group)) == NULL) 761280297Sjkim return 0; 762160814Ssimon 763280297Sjkim generator = EC_GROUP_get0_generator(group); 764280297Sjkim if (generator == NULL) { 765280297Sjkim ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR); 766280297Sjkim goto err; 767280297Sjkim } 768109998Smarkm 769280297Sjkim if (ctx == NULL) { 770280297Sjkim ctx = new_ctx = BN_CTX_new(); 771280297Sjkim if (ctx == NULL) 772280297Sjkim goto err; 773280297Sjkim } 774109998Smarkm 775280297Sjkim BN_CTX_start(ctx); 776280297Sjkim order = BN_CTX_get(ctx); 777280297Sjkim if (order == NULL) 778280297Sjkim goto err; 779109998Smarkm 780280297Sjkim if (!EC_GROUP_get_order(group, order, ctx)) 781280297Sjkim goto err; 782280297Sjkim if (BN_is_zero(order)) { 783280297Sjkim ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER); 784280297Sjkim goto err; 785280297Sjkim } 786160814Ssimon 787280297Sjkim bits = BN_num_bits(order); 788280297Sjkim /* 789280297Sjkim * The following parameters mean we precompute (approximately) one point 790280297Sjkim * per bit. TBD: The combination 8, 4 is perfect for 160 bits; for other 791280297Sjkim * bit lengths, other parameter combinations might provide better 792280297Sjkim * efficiency. 793280297Sjkim */ 794280297Sjkim blocksize = 8; 795280297Sjkim w = 4; 796280297Sjkim if (EC_window_bits_for_scalar_size(bits) > w) { 797280297Sjkim /* let's not make the window too small ... */ 798280297Sjkim w = EC_window_bits_for_scalar_size(bits); 799280297Sjkim } 800160814Ssimon 801280297Sjkim numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks 802280297Sjkim * to use for wNAF 803280297Sjkim * splitting */ 804160814Ssimon 805280297Sjkim pre_points_per_block = (size_t)1 << (w - 1); 806280297Sjkim num = pre_points_per_block * numblocks; /* number of points to compute 807280297Sjkim * and store */ 808160814Ssimon 809280297Sjkim points = OPENSSL_malloc(sizeof(EC_POINT *) * (num + 1)); 810280297Sjkim if (!points) { 811280297Sjkim ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 812280297Sjkim goto err; 813280297Sjkim } 814160814Ssimon 815280297Sjkim var = points; 816280297Sjkim var[num] = NULL; /* pivot */ 817280297Sjkim for (i = 0; i < num; i++) { 818280297Sjkim if ((var[i] = EC_POINT_new(group)) == NULL) { 819280297Sjkim ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 820280297Sjkim goto err; 821280297Sjkim } 822280297Sjkim } 823160814Ssimon 824280297Sjkim if (!(tmp_point = EC_POINT_new(group)) || !(base = EC_POINT_new(group))) { 825280297Sjkim ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 826280297Sjkim goto err; 827280297Sjkim } 828160814Ssimon 829280297Sjkim if (!EC_POINT_copy(base, generator)) 830280297Sjkim goto err; 831160814Ssimon 832280297Sjkim /* do the precomputation */ 833280297Sjkim for (i = 0; i < numblocks; i++) { 834280297Sjkim size_t j; 835160814Ssimon 836280297Sjkim if (!EC_POINT_dbl(group, tmp_point, base, ctx)) 837280297Sjkim goto err; 838160814Ssimon 839280297Sjkim if (!EC_POINT_copy(*var++, base)) 840280297Sjkim goto err; 841160814Ssimon 842280297Sjkim for (j = 1; j < pre_points_per_block; j++, var++) { 843280297Sjkim /* 844280297Sjkim * calculate odd multiples of the current base point 845280297Sjkim */ 846280297Sjkim if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx)) 847280297Sjkim goto err; 848280297Sjkim } 849160814Ssimon 850280297Sjkim if (i < numblocks - 1) { 851280297Sjkim /* 852280297Sjkim * get the next base (multiply current one by 2^blocksize) 853280297Sjkim */ 854280297Sjkim size_t k; 855280297Sjkim 856280297Sjkim if (blocksize <= 2) { 857280297Sjkim ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_INTERNAL_ERROR); 858280297Sjkim goto err; 859280297Sjkim } 860280297Sjkim 861280297Sjkim if (!EC_POINT_dbl(group, base, tmp_point, ctx)) 862280297Sjkim goto err; 863280297Sjkim for (k = 2; k < blocksize; k++) { 864280297Sjkim if (!EC_POINT_dbl(group, base, base, ctx)) 865280297Sjkim goto err; 866280297Sjkim } 867280297Sjkim } 868280297Sjkim } 869280297Sjkim 870280297Sjkim if (!EC_POINTs_make_affine(group, num, points, ctx)) 871280297Sjkim goto err; 872280297Sjkim 873280297Sjkim pre_comp->group = group; 874280297Sjkim pre_comp->blocksize = blocksize; 875280297Sjkim pre_comp->numblocks = numblocks; 876280297Sjkim pre_comp->w = w; 877280297Sjkim pre_comp->points = points; 878280297Sjkim points = NULL; 879280297Sjkim pre_comp->num = num; 880280297Sjkim 881280297Sjkim if (!EC_EX_DATA_set_data(&group->extra_data, pre_comp, 882280297Sjkim ec_pre_comp_dup, ec_pre_comp_free, 883280297Sjkim ec_pre_comp_clear_free)) 884280297Sjkim goto err; 885280297Sjkim pre_comp = NULL; 886280297Sjkim 887280297Sjkim ret = 1; 888109998Smarkm err: 889280297Sjkim if (ctx != NULL) 890280297Sjkim BN_CTX_end(ctx); 891280297Sjkim if (new_ctx != NULL) 892280297Sjkim BN_CTX_free(new_ctx); 893280297Sjkim if (pre_comp) 894280297Sjkim ec_pre_comp_free(pre_comp); 895280297Sjkim if (points) { 896280297Sjkim EC_POINT **p; 897160814Ssimon 898280297Sjkim for (p = points; *p != NULL; p++) 899280297Sjkim EC_POINT_free(*p); 900280297Sjkim OPENSSL_free(points); 901280297Sjkim } 902280297Sjkim if (tmp_point) 903280297Sjkim EC_POINT_free(tmp_point); 904280297Sjkim if (base) 905280297Sjkim EC_POINT_free(base); 906280297Sjkim return ret; 907280297Sjkim} 908160814Ssimon 909160814Ssimonint ec_wNAF_have_precompute_mult(const EC_GROUP *group) 910280297Sjkim{ 911280297Sjkim if (EC_EX_DATA_get_data 912280297Sjkim (group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, 913280297Sjkim ec_pre_comp_clear_free) != NULL) 914280297Sjkim return 1; 915280297Sjkim else 916280297Sjkim return 0; 917280297Sjkim} 918