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 13296341Sdelphij * 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/* 71160814Ssimon * This file implements the wNAF-based interleaving multi-exponentation method 72160814Ssimon * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp>); 73160814Ssimon * for multiplication with precomputation, we use wNAF splitting 74160814Ssimon * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp>). 75160814Ssimon */ 76109998Smarkm 77160814Ssimon/* structure for precomputed multiples of the generator */ 78160814Ssimontypedef struct ec_pre_comp_st { 79296341Sdelphij const EC_GROUP *group; /* parent EC_GROUP object */ 80296341Sdelphij size_t blocksize; /* block size for wNAF splitting */ 81296341Sdelphij size_t numblocks; /* max. number of blocks for which we have 82296341Sdelphij * precomputation */ 83296341Sdelphij size_t w; /* window size */ 84296341Sdelphij EC_POINT **points; /* array with pre-calculated multiples of 85296341Sdelphij * generator: 'num' pointers to EC_POINT 86296341Sdelphij * objects followed by a NULL */ 87296341Sdelphij size_t num; /* numblocks * 2^(w-1) */ 88296341Sdelphij int references; 89160814Ssimon} EC_PRE_COMP; 90296341Sdelphij 91160814Ssimon/* functions to manage EC_PRE_COMP within the EC_GROUP extra_data framework */ 92160814Ssimonstatic void *ec_pre_comp_dup(void *); 93160814Ssimonstatic void ec_pre_comp_free(void *); 94160814Ssimonstatic void ec_pre_comp_clear_free(void *); 95109998Smarkm 96160814Ssimonstatic EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group) 97296341Sdelphij{ 98296341Sdelphij EC_PRE_COMP *ret = NULL; 99160814Ssimon 100296341Sdelphij if (!group) 101296341Sdelphij return NULL; 102160814Ssimon 103296341Sdelphij ret = (EC_PRE_COMP *)OPENSSL_malloc(sizeof(EC_PRE_COMP)); 104296341Sdelphij if (!ret) { 105296341Sdelphij ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE); 106296341Sdelphij return ret; 107296341Sdelphij } 108296341Sdelphij ret->group = group; 109296341Sdelphij ret->blocksize = 8; /* default */ 110296341Sdelphij ret->numblocks = 0; 111296341Sdelphij ret->w = 4; /* default */ 112296341Sdelphij ret->points = NULL; 113296341Sdelphij ret->num = 0; 114296341Sdelphij ret->references = 1; 115296341Sdelphij return ret; 116296341Sdelphij} 117160814Ssimon 118160814Ssimonstatic void *ec_pre_comp_dup(void *src_) 119296341Sdelphij{ 120296341Sdelphij EC_PRE_COMP *src = src_; 121160814Ssimon 122296341Sdelphij /* no need to actually copy, these objects never change! */ 123160814Ssimon 124296341Sdelphij CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP); 125160814Ssimon 126296341Sdelphij return src_; 127296341Sdelphij} 128160814Ssimon 129160814Ssimonstatic void ec_pre_comp_free(void *pre_) 130296341Sdelphij{ 131296341Sdelphij int i; 132296341Sdelphij EC_PRE_COMP *pre = pre_; 133160814Ssimon 134296341Sdelphij if (!pre) 135296341Sdelphij return; 136160814Ssimon 137296341Sdelphij i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); 138296341Sdelphij if (i > 0) 139296341Sdelphij return; 140160814Ssimon 141296341Sdelphij if (pre->points) { 142296341Sdelphij EC_POINT **p; 143160814Ssimon 144296341Sdelphij for (p = pre->points; *p != NULL; p++) 145296341Sdelphij EC_POINT_free(*p); 146296341Sdelphij OPENSSL_free(pre->points); 147296341Sdelphij } 148296341Sdelphij OPENSSL_free(pre); 149296341Sdelphij} 150160814Ssimon 151160814Ssimonstatic void ec_pre_comp_clear_free(void *pre_) 152296341Sdelphij{ 153296341Sdelphij int i; 154296341Sdelphij EC_PRE_COMP *pre = pre_; 155160814Ssimon 156296341Sdelphij if (!pre) 157296341Sdelphij return; 158160814Ssimon 159296341Sdelphij i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); 160296341Sdelphij if (i > 0) 161296341Sdelphij return; 162160814Ssimon 163296341Sdelphij if (pre->points) { 164296341Sdelphij EC_POINT **p; 165160814Ssimon 166296341Sdelphij for (p = pre->points; *p != NULL; p++) { 167296341Sdelphij EC_POINT_clear_free(*p); 168296341Sdelphij OPENSSL_cleanse(p, sizeof *p); 169296341Sdelphij } 170296341Sdelphij OPENSSL_free(pre->points); 171296341Sdelphij } 172296341Sdelphij OPENSSL_cleanse(pre, sizeof *pre); 173296341Sdelphij OPENSSL_free(pre); 174296341Sdelphij} 175160814Ssimon 176296341Sdelphij/*- 177296341Sdelphij * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'. 178109998Smarkm * This is an array r[] of values that are either zero or odd with an 179109998Smarkm * absolute value less than 2^w satisfying 180109998Smarkm * scalar = \sum_j r[j]*2^j 181160814Ssimon * where at most one of any w+1 consecutive digits is non-zero 182160814Ssimon * with the exception that the most significant digit may be only 183160814Ssimon * w-1 zeros away from that next non-zero digit. 184109998Smarkm */ 185160814Ssimonstatic signed char *compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len) 186296341Sdelphij{ 187296341Sdelphij int window_val; 188296341Sdelphij int ok = 0; 189296341Sdelphij signed char *r = NULL; 190296341Sdelphij int sign = 1; 191296341Sdelphij int bit, next_bit, mask; 192296341Sdelphij size_t len = 0, j; 193109998Smarkm 194296341Sdelphij if (BN_is_zero(scalar)) { 195296341Sdelphij r = OPENSSL_malloc(1); 196296341Sdelphij if (!r) { 197296341Sdelphij ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); 198296341Sdelphij goto err; 199296341Sdelphij } 200296341Sdelphij r[0] = 0; 201296341Sdelphij *ret_len = 1; 202296341Sdelphij return r; 203296341Sdelphij } 204109998Smarkm 205296341Sdelphij if (w <= 0 || w > 7) { /* 'signed char' can represent integers with 206296341Sdelphij * absolute values less than 2^7 */ 207296341Sdelphij ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 208296341Sdelphij goto err; 209296341Sdelphij } 210296341Sdelphij bit = 1 << w; /* at most 128 */ 211296341Sdelphij next_bit = bit << 1; /* at most 256 */ 212296341Sdelphij mask = next_bit - 1; /* at most 255 */ 213238405Sjkim 214296341Sdelphij if (BN_is_negative(scalar)) { 215296341Sdelphij sign = -1; 216296341Sdelphij } 217109998Smarkm 218296341Sdelphij if (scalar->d == NULL || scalar->top == 0) { 219296341Sdelphij ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 220296341Sdelphij goto err; 221296341Sdelphij } 222160814Ssimon 223296341Sdelphij len = BN_num_bits(scalar); 224296341Sdelphij r = OPENSSL_malloc(len + 1); /* modified wNAF may be one digit longer 225296341Sdelphij * than binary representation (*ret_len will 226296341Sdelphij * be set to the actual length, i.e. at most 227296341Sdelphij * BN_num_bits(scalar) + 1) */ 228296341Sdelphij if (r == NULL) { 229296341Sdelphij ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); 230296341Sdelphij goto err; 231296341Sdelphij } 232296341Sdelphij window_val = scalar->d[0] & mask; 233296341Sdelphij j = 0; 234296341Sdelphij while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len, 235296341Sdelphij * window_val will not 236296341Sdelphij * increase */ 237296341Sdelphij int digit = 0; 238160814Ssimon 239296341Sdelphij /* 0 <= window_val <= 2^(w+1) */ 240160814Ssimon 241296341Sdelphij if (window_val & 1) { 242296341Sdelphij /* 0 < window_val < 2^(w+1) */ 243296341Sdelphij 244296341Sdelphij if (window_val & bit) { 245296341Sdelphij digit = window_val - next_bit; /* -2^w < digit < 0 */ 246296341Sdelphij 247296341Sdelphij#if 1 /* modified wNAF */ 248296341Sdelphij if (j + w + 1 >= len) { 249296341Sdelphij /* 250296341Sdelphij * special case for generating modified wNAFs: no new 251296341Sdelphij * bits will be added into window_val, so using a 252296341Sdelphij * positive digit here will decrease the total length of 253296341Sdelphij * the representation 254296341Sdelphij */ 255296341Sdelphij 256296341Sdelphij digit = window_val & (mask >> 1); /* 0 < digit < 2^w */ 257296341Sdelphij } 258160814Ssimon#endif 259296341Sdelphij } else { 260296341Sdelphij digit = window_val; /* 0 < digit < 2^w */ 261296341Sdelphij } 262109998Smarkm 263296341Sdelphij if (digit <= -bit || digit >= bit || !(digit & 1)) { 264296341Sdelphij ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 265296341Sdelphij goto err; 266296341Sdelphij } 267160814Ssimon 268296341Sdelphij window_val -= digit; 269109998Smarkm 270296341Sdelphij /* 271296341Sdelphij * now window_val is 0 or 2^(w+1) in standard wNAF generation; 272296341Sdelphij * for modified window NAFs, it may also be 2^w 273296341Sdelphij */ 274296341Sdelphij if (window_val != 0 && window_val != next_bit 275296341Sdelphij && window_val != bit) { 276296341Sdelphij ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 277296341Sdelphij goto err; 278296341Sdelphij } 279296341Sdelphij } 280160814Ssimon 281296341Sdelphij r[j++] = sign * digit; 282160814Ssimon 283296341Sdelphij window_val >>= 1; 284296341Sdelphij window_val += bit * BN_is_bit_set(scalar, j + w); 285109998Smarkm 286296341Sdelphij if (window_val > next_bit) { 287296341Sdelphij ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 288296341Sdelphij goto err; 289296341Sdelphij } 290296341Sdelphij } 291109998Smarkm 292296341Sdelphij if (j > len + 1) { 293296341Sdelphij ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 294296341Sdelphij goto err; 295296341Sdelphij } 296296341Sdelphij len = j; 297296341Sdelphij ok = 1; 298296341Sdelphij 299109998Smarkm err: 300296341Sdelphij if (!ok) { 301296341Sdelphij OPENSSL_free(r); 302296341Sdelphij r = NULL; 303296341Sdelphij } 304296341Sdelphij if (ok) 305296341Sdelphij *ret_len = len; 306296341Sdelphij return r; 307296341Sdelphij} 308109998Smarkm 309296341Sdelphij/* 310296341Sdelphij * TODO: table should be optimised for the wNAF-based implementation, 311296341Sdelphij * sometimes smaller windows will give better performance (thus the 312296341Sdelphij * boundaries should be increased) 313109998Smarkm */ 314109998Smarkm#define EC_window_bits_for_scalar_size(b) \ 315296341Sdelphij ((size_t) \ 316296341Sdelphij ((b) >= 2000 ? 6 : \ 317296341Sdelphij (b) >= 800 ? 5 : \ 318296341Sdelphij (b) >= 300 ? 4 : \ 319296341Sdelphij (b) >= 70 ? 3 : \ 320296341Sdelphij (b) >= 20 ? 2 : \ 321296341Sdelphij 1)) 322109998Smarkm 323296341Sdelphij/*- 324296341Sdelphij * Compute 325109998Smarkm * \sum scalars[i]*points[i], 326109998Smarkm * also including 327109998Smarkm * scalar*generator 328109998Smarkm * in the addition if scalar != NULL 329109998Smarkm */ 330160814Ssimonint ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 331296341Sdelphij size_t num, const EC_POINT *points[], const BIGNUM *scalars[], 332296341Sdelphij BN_CTX *ctx) 333296341Sdelphij{ 334296341Sdelphij BN_CTX *new_ctx = NULL; 335296341Sdelphij const EC_POINT *generator = NULL; 336296341Sdelphij EC_POINT *tmp = NULL; 337296341Sdelphij size_t totalnum; 338296341Sdelphij size_t blocksize = 0, numblocks = 0; /* for wNAF splitting */ 339296341Sdelphij size_t pre_points_per_block = 0; 340296341Sdelphij size_t i, j; 341296341Sdelphij int k; 342296341Sdelphij int r_is_inverted = 0; 343296341Sdelphij int r_is_at_infinity = 1; 344296341Sdelphij size_t *wsize = NULL; /* individual window sizes */ 345296341Sdelphij signed char **wNAF = NULL; /* individual wNAFs */ 346296341Sdelphij size_t *wNAF_len = NULL; 347296341Sdelphij size_t max_len = 0; 348296341Sdelphij size_t num_val; 349296341Sdelphij EC_POINT **val = NULL; /* precomputation */ 350296341Sdelphij EC_POINT **v; 351296341Sdelphij EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' or 352296341Sdelphij * 'pre_comp->points' */ 353296341Sdelphij const EC_PRE_COMP *pre_comp = NULL; 354296341Sdelphij int num_scalar = 0; /* flag: will be set to 1 if 'scalar' must be 355296341Sdelphij * treated like other scalars, i.e. 356296341Sdelphij * precomputation is not available */ 357296341Sdelphij int ret = 0; 358111147Snectar 359296341Sdelphij if (group->meth != r->meth) { 360296341Sdelphij ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); 361296341Sdelphij return 0; 362296341Sdelphij } 363111147Snectar 364296341Sdelphij if ((scalar == NULL) && (num == 0)) { 365296341Sdelphij return EC_POINT_set_to_infinity(group, r); 366296341Sdelphij } 367160814Ssimon 368296341Sdelphij for (i = 0; i < num; i++) { 369296341Sdelphij if (group->meth != points[i]->meth) { 370296341Sdelphij ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); 371296341Sdelphij return 0; 372296341Sdelphij } 373296341Sdelphij } 374160814Ssimon 375296341Sdelphij if (ctx == NULL) { 376296341Sdelphij ctx = new_ctx = BN_CTX_new(); 377296341Sdelphij if (ctx == NULL) 378296341Sdelphij goto err; 379296341Sdelphij } 380109998Smarkm 381296341Sdelphij if (scalar != NULL) { 382296341Sdelphij generator = EC_GROUP_get0_generator(group); 383296341Sdelphij if (generator == NULL) { 384296341Sdelphij ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR); 385296341Sdelphij goto err; 386296341Sdelphij } 387109998Smarkm 388296341Sdelphij /* look if we can use precomputed multiples of generator */ 389160814Ssimon 390296341Sdelphij pre_comp = 391296341Sdelphij EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, 392296341Sdelphij ec_pre_comp_free, ec_pre_comp_clear_free); 393160814Ssimon 394296341Sdelphij if (pre_comp && pre_comp->numblocks 395296341Sdelphij && (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) == 396296341Sdelphij 0)) { 397296341Sdelphij blocksize = pre_comp->blocksize; 398160814Ssimon 399296341Sdelphij /* 400296341Sdelphij * determine maximum number of blocks that wNAF splitting may 401296341Sdelphij * yield (NB: maximum wNAF length is bit length plus one) 402296341Sdelphij */ 403296341Sdelphij numblocks = (BN_num_bits(scalar) / blocksize) + 1; 404160814Ssimon 405296341Sdelphij /* 406296341Sdelphij * we cannot use more blocks than we have precomputation for 407296341Sdelphij */ 408296341Sdelphij if (numblocks > pre_comp->numblocks) 409296341Sdelphij numblocks = pre_comp->numblocks; 410109998Smarkm 411296341Sdelphij pre_points_per_block = (size_t)1 << (pre_comp->w - 1); 412279264Sdelphij 413296341Sdelphij /* check that pre_comp looks sane */ 414296341Sdelphij if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block)) { 415296341Sdelphij ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 416296341Sdelphij goto err; 417296341Sdelphij } 418296341Sdelphij } else { 419296341Sdelphij /* can't use precomputation */ 420296341Sdelphij pre_comp = NULL; 421296341Sdelphij numblocks = 1; 422296341Sdelphij num_scalar = 1; /* treat 'scalar' like 'num'-th element of 423296341Sdelphij * 'scalars' */ 424296341Sdelphij } 425296341Sdelphij } 426279264Sdelphij 427296341Sdelphij totalnum = num + numblocks; 428160814Ssimon 429296341Sdelphij wsize = OPENSSL_malloc(totalnum * sizeof wsize[0]); 430296341Sdelphij wNAF_len = OPENSSL_malloc(totalnum * sizeof wNAF_len[0]); 431296341Sdelphij wNAF = OPENSSL_malloc((totalnum + 1) * sizeof wNAF[0]); /* includes space 432296341Sdelphij * for pivot */ 433296341Sdelphij val_sub = OPENSSL_malloc(totalnum * sizeof val_sub[0]); 434160814Ssimon 435296341Sdelphij /* Ensure wNAF is initialised in case we end up going to err */ 436296341Sdelphij if (wNAF) 437296341Sdelphij wNAF[0] = NULL; /* preliminary pivot */ 438109998Smarkm 439296341Sdelphij if (!wsize || !wNAF_len || !wNAF || !val_sub) { 440296341Sdelphij ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 441296341Sdelphij goto err; 442296341Sdelphij } 443109998Smarkm 444296341Sdelphij /* 445296341Sdelphij * num_val will be the total number of temporarily precomputed points 446296341Sdelphij */ 447296341Sdelphij num_val = 0; 448160814Ssimon 449296341Sdelphij for (i = 0; i < num + num_scalar; i++) { 450296341Sdelphij size_t bits; 451160814Ssimon 452296341Sdelphij bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar); 453296341Sdelphij wsize[i] = EC_window_bits_for_scalar_size(bits); 454296341Sdelphij num_val += (size_t)1 << (wsize[i] - 1); 455296341Sdelphij wNAF[i + 1] = NULL; /* make sure we always have a pivot */ 456296341Sdelphij wNAF[i] = 457296341Sdelphij compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], 458296341Sdelphij &wNAF_len[i]); 459296341Sdelphij if (wNAF[i] == NULL) 460296341Sdelphij goto err; 461296341Sdelphij if (wNAF_len[i] > max_len) 462296341Sdelphij max_len = wNAF_len[i]; 463296341Sdelphij } 464160814Ssimon 465296341Sdelphij if (numblocks) { 466296341Sdelphij /* we go here iff scalar != NULL */ 467160814Ssimon 468296341Sdelphij if (pre_comp == NULL) { 469296341Sdelphij if (num_scalar != 1) { 470296341Sdelphij ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 471296341Sdelphij goto err; 472296341Sdelphij } 473296341Sdelphij /* we have already generated a wNAF for 'scalar' */ 474296341Sdelphij } else { 475296341Sdelphij signed char *tmp_wNAF = NULL; 476296341Sdelphij size_t tmp_len = 0; 477160814Ssimon 478296341Sdelphij if (num_scalar != 0) { 479296341Sdelphij ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 480296341Sdelphij goto err; 481296341Sdelphij } 482160814Ssimon 483296341Sdelphij /* 484296341Sdelphij * use the window size for which we have precomputation 485296341Sdelphij */ 486296341Sdelphij wsize[num] = pre_comp->w; 487296341Sdelphij tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len); 488296341Sdelphij if (!tmp_wNAF) 489296341Sdelphij goto err; 490160814Ssimon 491296341Sdelphij if (tmp_len <= max_len) { 492296341Sdelphij /* 493296341Sdelphij * One of the other wNAFs is at least as long as the wNAF 494296341Sdelphij * belonging to the generator, so wNAF splitting will not buy 495296341Sdelphij * us anything. 496296341Sdelphij */ 497109998Smarkm 498296341Sdelphij numblocks = 1; 499296341Sdelphij totalnum = num + 1; /* don't use wNAF splitting */ 500296341Sdelphij wNAF[num] = tmp_wNAF; 501296341Sdelphij wNAF[num + 1] = NULL; 502296341Sdelphij wNAF_len[num] = tmp_len; 503296341Sdelphij if (tmp_len > max_len) 504296341Sdelphij max_len = tmp_len; 505296341Sdelphij /* 506296341Sdelphij * pre_comp->points starts with the points that we need here: 507296341Sdelphij */ 508296341Sdelphij val_sub[num] = pre_comp->points; 509296341Sdelphij } else { 510296341Sdelphij /* 511296341Sdelphij * don't include tmp_wNAF directly into wNAF array - use wNAF 512296341Sdelphij * splitting and include the blocks 513296341Sdelphij */ 514109998Smarkm 515296341Sdelphij signed char *pp; 516296341Sdelphij EC_POINT **tmp_points; 517109998Smarkm 518296341Sdelphij if (tmp_len < numblocks * blocksize) { 519296341Sdelphij /* 520296341Sdelphij * possibly we can do with fewer blocks than estimated 521296341Sdelphij */ 522296341Sdelphij numblocks = (tmp_len + blocksize - 1) / blocksize; 523296341Sdelphij if (numblocks > pre_comp->numblocks) { 524296341Sdelphij ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 525296341Sdelphij goto err; 526296341Sdelphij } 527296341Sdelphij totalnum = num + numblocks; 528296341Sdelphij } 529109998Smarkm 530296341Sdelphij /* split wNAF in 'numblocks' parts */ 531296341Sdelphij pp = tmp_wNAF; 532296341Sdelphij tmp_points = pre_comp->points; 533109998Smarkm 534296341Sdelphij for (i = num; i < totalnum; i++) { 535296341Sdelphij if (i < totalnum - 1) { 536296341Sdelphij wNAF_len[i] = blocksize; 537296341Sdelphij if (tmp_len < blocksize) { 538296341Sdelphij ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 539296341Sdelphij goto err; 540296341Sdelphij } 541296341Sdelphij tmp_len -= blocksize; 542296341Sdelphij } else 543296341Sdelphij /* 544296341Sdelphij * last block gets whatever is left (this could be 545296341Sdelphij * more or less than 'blocksize'!) 546296341Sdelphij */ 547296341Sdelphij wNAF_len[i] = tmp_len; 548296341Sdelphij 549296341Sdelphij wNAF[i + 1] = NULL; 550296341Sdelphij wNAF[i] = OPENSSL_malloc(wNAF_len[i]); 551296341Sdelphij if (wNAF[i] == NULL) { 552296341Sdelphij ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 553296341Sdelphij OPENSSL_free(tmp_wNAF); 554296341Sdelphij goto err; 555296341Sdelphij } 556296341Sdelphij memcpy(wNAF[i], pp, wNAF_len[i]); 557296341Sdelphij if (wNAF_len[i] > max_len) 558296341Sdelphij max_len = wNAF_len[i]; 559296341Sdelphij 560296341Sdelphij if (*tmp_points == NULL) { 561296341Sdelphij ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 562296341Sdelphij OPENSSL_free(tmp_wNAF); 563296341Sdelphij goto err; 564296341Sdelphij } 565296341Sdelphij val_sub[i] = tmp_points; 566296341Sdelphij tmp_points += pre_points_per_block; 567296341Sdelphij pp += blocksize; 568296341Sdelphij } 569296341Sdelphij OPENSSL_free(tmp_wNAF); 570296341Sdelphij } 571296341Sdelphij } 572296341Sdelphij } 573296341Sdelphij 574296341Sdelphij /* 575296341Sdelphij * All points we precompute now go into a single array 'val'. 576296341Sdelphij * 'val_sub[i]' is a pointer to the subarray for the i-th point, or to a 577296341Sdelphij * subarray of 'pre_comp->points' if we already have precomputation. 578296341Sdelphij */ 579296341Sdelphij val = OPENSSL_malloc((num_val + 1) * sizeof val[0]); 580296341Sdelphij if (val == NULL) { 581296341Sdelphij ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 582296341Sdelphij goto err; 583296341Sdelphij } 584296341Sdelphij val[num_val] = NULL; /* pivot element */ 585296341Sdelphij 586296341Sdelphij /* allocate points for precomputation */ 587296341Sdelphij v = val; 588296341Sdelphij for (i = 0; i < num + num_scalar; i++) { 589296341Sdelphij val_sub[i] = v; 590296341Sdelphij for (j = 0; j < ((size_t)1 << (wsize[i] - 1)); j++) { 591296341Sdelphij *v = EC_POINT_new(group); 592296341Sdelphij if (*v == NULL) 593296341Sdelphij goto err; 594296341Sdelphij v++; 595296341Sdelphij } 596296341Sdelphij } 597296341Sdelphij if (!(v == val + num_val)) { 598296341Sdelphij ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 599296341Sdelphij goto err; 600296341Sdelphij } 601296341Sdelphij 602296341Sdelphij if (!(tmp = EC_POINT_new(group))) 603296341Sdelphij goto err; 604296341Sdelphij 605296341Sdelphij /*- 606296341Sdelphij * prepare precomputed values: 607296341Sdelphij * val_sub[i][0] := points[i] 608296341Sdelphij * val_sub[i][1] := 3 * points[i] 609296341Sdelphij * val_sub[i][2] := 5 * points[i] 610296341Sdelphij * ... 611296341Sdelphij */ 612296341Sdelphij for (i = 0; i < num + num_scalar; i++) { 613296341Sdelphij if (i < num) { 614296341Sdelphij if (!EC_POINT_copy(val_sub[i][0], points[i])) 615296341Sdelphij goto err; 616296341Sdelphij } else { 617296341Sdelphij if (!EC_POINT_copy(val_sub[i][0], generator)) 618296341Sdelphij goto err; 619296341Sdelphij } 620296341Sdelphij 621296341Sdelphij if (wsize[i] > 1) { 622296341Sdelphij if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) 623296341Sdelphij goto err; 624296341Sdelphij for (j = 1; j < ((size_t)1 << (wsize[i] - 1)); j++) { 625296341Sdelphij if (!EC_POINT_add 626296341Sdelphij (group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) 627296341Sdelphij goto err; 628296341Sdelphij } 629296341Sdelphij } 630296341Sdelphij } 631296341Sdelphij 632296341Sdelphij#if 1 /* optional; EC_window_bits_for_scalar_size 633296341Sdelphij * assumes we do this step */ 634296341Sdelphij if (!EC_POINTs_make_affine(group, num_val, val, ctx)) 635296341Sdelphij goto err; 636109998Smarkm#endif 637109998Smarkm 638296341Sdelphij r_is_at_infinity = 1; 639109998Smarkm 640296341Sdelphij for (k = max_len - 1; k >= 0; k--) { 641296341Sdelphij if (!r_is_at_infinity) { 642296341Sdelphij if (!EC_POINT_dbl(group, r, r, ctx)) 643296341Sdelphij goto err; 644296341Sdelphij } 645109998Smarkm 646296341Sdelphij for (i = 0; i < totalnum; i++) { 647296341Sdelphij if (wNAF_len[i] > (size_t)k) { 648296341Sdelphij int digit = wNAF[i][k]; 649296341Sdelphij int is_neg; 650109998Smarkm 651296341Sdelphij if (digit) { 652296341Sdelphij is_neg = digit < 0; 653109998Smarkm 654296341Sdelphij if (is_neg) 655296341Sdelphij digit = -digit; 656109998Smarkm 657296341Sdelphij if (is_neg != r_is_inverted) { 658296341Sdelphij if (!r_is_at_infinity) { 659296341Sdelphij if (!EC_POINT_invert(group, r, ctx)) 660296341Sdelphij goto err; 661296341Sdelphij } 662296341Sdelphij r_is_inverted = !r_is_inverted; 663296341Sdelphij } 664109998Smarkm 665296341Sdelphij /* digit > 0 */ 666109998Smarkm 667296341Sdelphij if (r_is_at_infinity) { 668296341Sdelphij if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) 669296341Sdelphij goto err; 670296341Sdelphij r_is_at_infinity = 0; 671296341Sdelphij } else { 672296341Sdelphij if (!EC_POINT_add 673296341Sdelphij (group, r, r, val_sub[i][digit >> 1], ctx)) 674296341Sdelphij goto err; 675296341Sdelphij } 676296341Sdelphij } 677296341Sdelphij } 678296341Sdelphij } 679296341Sdelphij } 680109998Smarkm 681296341Sdelphij if (r_is_at_infinity) { 682296341Sdelphij if (!EC_POINT_set_to_infinity(group, r)) 683296341Sdelphij goto err; 684296341Sdelphij } else { 685296341Sdelphij if (r_is_inverted) 686296341Sdelphij if (!EC_POINT_invert(group, r, ctx)) 687296341Sdelphij goto err; 688296341Sdelphij } 689296341Sdelphij 690296341Sdelphij ret = 1; 691296341Sdelphij 692109998Smarkm err: 693296341Sdelphij if (new_ctx != NULL) 694296341Sdelphij BN_CTX_free(new_ctx); 695296341Sdelphij if (tmp != NULL) 696296341Sdelphij EC_POINT_free(tmp); 697296341Sdelphij if (wsize != NULL) 698296341Sdelphij OPENSSL_free(wsize); 699296341Sdelphij if (wNAF_len != NULL) 700296341Sdelphij OPENSSL_free(wNAF_len); 701296341Sdelphij if (wNAF != NULL) { 702296341Sdelphij signed char **w; 703109998Smarkm 704296341Sdelphij for (w = wNAF; *w != NULL; w++) 705296341Sdelphij OPENSSL_free(*w); 706109998Smarkm 707296341Sdelphij OPENSSL_free(wNAF); 708296341Sdelphij } 709296341Sdelphij if (val != NULL) { 710296341Sdelphij for (v = val; *v != NULL; v++) 711296341Sdelphij EC_POINT_clear_free(*v); 712109998Smarkm 713296341Sdelphij OPENSSL_free(val); 714296341Sdelphij } 715296341Sdelphij if (val_sub != NULL) { 716296341Sdelphij OPENSSL_free(val_sub); 717296341Sdelphij } 718296341Sdelphij return ret; 719296341Sdelphij} 720296341Sdelphij 721296341Sdelphij/*- 722296341Sdelphij * ec_wNAF_precompute_mult() 723160814Ssimon * creates an EC_PRE_COMP object with preprecomputed multiples of the generator 724160814Ssimon * for use with wNAF splitting as implemented in ec_wNAF_mul(). 725296341Sdelphij * 726160814Ssimon * 'pre_comp->points' is an array of multiples of the generator 727160814Ssimon * of the following form: 728160814Ssimon * points[0] = generator; 729160814Ssimon * points[1] = 3 * generator; 730160814Ssimon * ... 731160814Ssimon * points[2^(w-1)-1] = (2^(w-1)-1) * generator; 732160814Ssimon * points[2^(w-1)] = 2^blocksize * generator; 733160814Ssimon * points[2^(w-1)+1] = 3 * 2^blocksize * generator; 734160814Ssimon * ... 735160814Ssimon * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) * 2^(blocksize*(numblocks-2)) * generator 736160814Ssimon * points[2^(w-1)*(numblocks-1)] = 2^(blocksize*(numblocks-1)) * generator 737160814Ssimon * ... 738160814Ssimon * points[2^(w-1)*numblocks-1] = (2^(w-1)) * 2^(blocksize*(numblocks-1)) * generator 739160814Ssimon * points[2^(w-1)*numblocks] = NULL 740160814Ssimon */ 741160814Ssimonint ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) 742296341Sdelphij{ 743296341Sdelphij const EC_POINT *generator; 744296341Sdelphij EC_POINT *tmp_point = NULL, *base = NULL, **var; 745296341Sdelphij BN_CTX *new_ctx = NULL; 746296341Sdelphij BIGNUM *order; 747296341Sdelphij size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num; 748296341Sdelphij EC_POINT **points = NULL; 749296341Sdelphij EC_PRE_COMP *pre_comp; 750296341Sdelphij int ret = 0; 751109998Smarkm 752296341Sdelphij /* if there is an old EC_PRE_COMP object, throw it away */ 753296341Sdelphij EC_EX_DATA_free_data(&group->extra_data, ec_pre_comp_dup, 754296341Sdelphij ec_pre_comp_free, ec_pre_comp_clear_free); 755160814Ssimon 756296341Sdelphij if ((pre_comp = ec_pre_comp_new(group)) == NULL) 757296341Sdelphij return 0; 758160814Ssimon 759296341Sdelphij generator = EC_GROUP_get0_generator(group); 760296341Sdelphij if (generator == NULL) { 761296341Sdelphij ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR); 762296341Sdelphij goto err; 763296341Sdelphij } 764109998Smarkm 765296341Sdelphij if (ctx == NULL) { 766296341Sdelphij ctx = new_ctx = BN_CTX_new(); 767296341Sdelphij if (ctx == NULL) 768296341Sdelphij goto err; 769296341Sdelphij } 770109998Smarkm 771296341Sdelphij BN_CTX_start(ctx); 772296341Sdelphij order = BN_CTX_get(ctx); 773296341Sdelphij if (order == NULL) 774296341Sdelphij goto err; 775109998Smarkm 776296341Sdelphij if (!EC_GROUP_get_order(group, order, ctx)) 777296341Sdelphij goto err; 778296341Sdelphij if (BN_is_zero(order)) { 779296341Sdelphij ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER); 780296341Sdelphij goto err; 781296341Sdelphij } 782160814Ssimon 783296341Sdelphij bits = BN_num_bits(order); 784296341Sdelphij /* 785296341Sdelphij * The following parameters mean we precompute (approximately) one point 786296341Sdelphij * per bit. TBD: The combination 8, 4 is perfect for 160 bits; for other 787296341Sdelphij * bit lengths, other parameter combinations might provide better 788296341Sdelphij * efficiency. 789296341Sdelphij */ 790296341Sdelphij blocksize = 8; 791296341Sdelphij w = 4; 792296341Sdelphij if (EC_window_bits_for_scalar_size(bits) > w) { 793296341Sdelphij /* let's not make the window too small ... */ 794296341Sdelphij w = EC_window_bits_for_scalar_size(bits); 795296341Sdelphij } 796160814Ssimon 797296341Sdelphij numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks 798296341Sdelphij * to use for wNAF 799296341Sdelphij * splitting */ 800160814Ssimon 801296341Sdelphij pre_points_per_block = (size_t)1 << (w - 1); 802296341Sdelphij num = pre_points_per_block * numblocks; /* number of points to compute 803296341Sdelphij * and store */ 804160814Ssimon 805296341Sdelphij points = OPENSSL_malloc(sizeof(EC_POINT *) * (num + 1)); 806296341Sdelphij if (!points) { 807296341Sdelphij ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 808296341Sdelphij goto err; 809296341Sdelphij } 810160814Ssimon 811296341Sdelphij var = points; 812296341Sdelphij var[num] = NULL; /* pivot */ 813296341Sdelphij for (i = 0; i < num; i++) { 814296341Sdelphij if ((var[i] = EC_POINT_new(group)) == NULL) { 815296341Sdelphij ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 816296341Sdelphij goto err; 817296341Sdelphij } 818296341Sdelphij } 819160814Ssimon 820296341Sdelphij if (!(tmp_point = EC_POINT_new(group)) || !(base = EC_POINT_new(group))) { 821296341Sdelphij ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 822296341Sdelphij goto err; 823296341Sdelphij } 824160814Ssimon 825296341Sdelphij if (!EC_POINT_copy(base, generator)) 826296341Sdelphij goto err; 827160814Ssimon 828296341Sdelphij /* do the precomputation */ 829296341Sdelphij for (i = 0; i < numblocks; i++) { 830296341Sdelphij size_t j; 831160814Ssimon 832296341Sdelphij if (!EC_POINT_dbl(group, tmp_point, base, ctx)) 833296341Sdelphij goto err; 834160814Ssimon 835296341Sdelphij if (!EC_POINT_copy(*var++, base)) 836296341Sdelphij goto err; 837160814Ssimon 838296341Sdelphij for (j = 1; j < pre_points_per_block; j++, var++) { 839296341Sdelphij /* 840296341Sdelphij * calculate odd multiples of the current base point 841296341Sdelphij */ 842296341Sdelphij if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx)) 843296341Sdelphij goto err; 844296341Sdelphij } 845160814Ssimon 846296341Sdelphij if (i < numblocks - 1) { 847296341Sdelphij /* 848296341Sdelphij * get the next base (multiply current one by 2^blocksize) 849296341Sdelphij */ 850296341Sdelphij size_t k; 851296341Sdelphij 852296341Sdelphij if (blocksize <= 2) { 853296341Sdelphij ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_INTERNAL_ERROR); 854296341Sdelphij goto err; 855296341Sdelphij } 856296341Sdelphij 857296341Sdelphij if (!EC_POINT_dbl(group, base, tmp_point, ctx)) 858296341Sdelphij goto err; 859296341Sdelphij for (k = 2; k < blocksize; k++) { 860296341Sdelphij if (!EC_POINT_dbl(group, base, base, ctx)) 861296341Sdelphij goto err; 862296341Sdelphij } 863296341Sdelphij } 864296341Sdelphij } 865296341Sdelphij 866296341Sdelphij if (!EC_POINTs_make_affine(group, num, points, ctx)) 867296341Sdelphij goto err; 868296341Sdelphij 869296341Sdelphij pre_comp->group = group; 870296341Sdelphij pre_comp->blocksize = blocksize; 871296341Sdelphij pre_comp->numblocks = numblocks; 872296341Sdelphij pre_comp->w = w; 873296341Sdelphij pre_comp->points = points; 874296341Sdelphij points = NULL; 875296341Sdelphij pre_comp->num = num; 876296341Sdelphij 877296341Sdelphij if (!EC_EX_DATA_set_data(&group->extra_data, pre_comp, 878296341Sdelphij ec_pre_comp_dup, ec_pre_comp_free, 879296341Sdelphij ec_pre_comp_clear_free)) 880296341Sdelphij goto err; 881296341Sdelphij pre_comp = NULL; 882296341Sdelphij 883296341Sdelphij ret = 1; 884109998Smarkm err: 885296341Sdelphij if (ctx != NULL) 886296341Sdelphij BN_CTX_end(ctx); 887296341Sdelphij if (new_ctx != NULL) 888296341Sdelphij BN_CTX_free(new_ctx); 889296341Sdelphij if (pre_comp) 890296341Sdelphij ec_pre_comp_free(pre_comp); 891296341Sdelphij if (points) { 892296341Sdelphij EC_POINT **p; 893160814Ssimon 894296341Sdelphij for (p = points; *p != NULL; p++) 895296341Sdelphij EC_POINT_free(*p); 896296341Sdelphij OPENSSL_free(points); 897296341Sdelphij } 898296341Sdelphij if (tmp_point) 899296341Sdelphij EC_POINT_free(tmp_point); 900296341Sdelphij if (base) 901296341Sdelphij EC_POINT_free(base); 902296341Sdelphij return ret; 903296341Sdelphij} 904160814Ssimon 905160814Ssimonint ec_wNAF_have_precompute_mult(const EC_GROUP *group) 906296341Sdelphij{ 907296341Sdelphij if (EC_EX_DATA_get_data 908296341Sdelphij (group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, 909296341Sdelphij ec_pre_comp_clear_free) != NULL) 910296341Sdelphij return 1; 911296341Sdelphij else 912296341Sdelphij return 0; 913296341Sdelphij} 914