177957Sbenno/* crypto/ec/ec_mult.c */ 290643Sbenno/* 390643Sbenno * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project. 490643Sbenno */ 590643Sbenno/* ==================================================================== 690643Sbenno * Copyright (c) 1998-2007 The OpenSSL Project. All rights reserved. 790643Sbenno * 890643Sbenno * Redistribution and use in source and binary forms, with or without 990643Sbenno * modification, are permitted provided that the following conditions 1090643Sbenno * are met: 1190643Sbenno * 1290643Sbenno * 1. Redistributions of source code must retain the above copyright 1390643Sbenno * notice, this list of conditions and the following disclaimer. 1490643Sbenno * 1590643Sbenno * 2. Redistributions in binary form must reproduce the above copyright 1690643Sbenno * notice, this list of conditions and the following disclaimer in 1790643Sbenno * the documentation and/or other materials provided with the 1890643Sbenno * distribution. 1990643Sbenno * 2090643Sbenno * 3. All advertising materials mentioning features or use of this 2190643Sbenno * software must display the following acknowledgment: 2290643Sbenno * "This product includes software developed by the OpenSSL Project 2390643Sbenno * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 2490643Sbenno * 2590643Sbenno * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 2690643Sbenno * endorse or promote products derived from this software without 2790643Sbenno * prior written permission. For written permission, please contact 2890643Sbenno * openssl-core@openssl.org. 2990643Sbenno * 3090643Sbenno * 5. Products derived from this software may not be called "OpenSSL" 3190643Sbenno * nor may "OpenSSL" appear in their names without prior written 3290643Sbenno * permission of the OpenSSL Project. 3390643Sbenno * 3490643Sbenno * 6. Redistributions of any form whatsoever must retain the following 3590643Sbenno * acknowledgment: 3690643Sbenno * "This product includes software developed by the OpenSSL Project 3777957Sbenno * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 3877957Sbenno * 3977957Sbenno * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 4077957Sbenno * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4177957Sbenno * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 4277957Sbenno * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 4377957Sbenno * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 4477957Sbenno * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 4577957Sbenno * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 4677957Sbenno * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4777957Sbenno * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 4877957Sbenno * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 4977957Sbenno * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 5077957Sbenno * OF THE POSSIBILITY OF SUCH DAMAGE. 5177957Sbenno * ==================================================================== 5277957Sbenno * 5377957Sbenno * This product includes cryptographic software written by Eric Young 5477957Sbenno * (eay@cryptsoft.com). This product includes software written by Tim 5577957Sbenno * Hudson (tjh@cryptsoft.com). 5677957Sbenno * 5777957Sbenno */ 5877957Sbenno/* ==================================================================== 5977957Sbenno * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 6077957Sbenno * Portions of this software developed by SUN MICROSYSTEMS, INC., 6177957Sbenno * and contributed to the OpenSSL project. 6277957Sbenno */ 6377957Sbenno 6477957Sbenno#include <string.h> 6577957Sbenno 6678880Sbenno#include <openssl/err.h> 6777957Sbenno 6877957Sbenno#include "ec_lcl.h" 6977957Sbenno 7077957Sbenno 7177957Sbenno/* 7277957Sbenno * This file implements the wNAF-based interleaving multi-exponentation method 7377957Sbenno * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp>); 7477957Sbenno * for multiplication with precomputation, we use wNAF splitting 7577957Sbenno * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp>). 7677957Sbenno */ 7777957Sbenno 7877957Sbenno 7977957Sbenno 8077957Sbenno 8177957Sbenno/* structure for precomputed multiples of the generator */ 8277957Sbennotypedef struct ec_pre_comp_st { 8377957Sbenno const EC_GROUP *group; /* parent EC_GROUP object */ 8477957Sbenno size_t blocksize; /* block size for wNAF splitting */ 8577957Sbenno size_t numblocks; /* max. number of blocks for which we have precomputation */ 8677957Sbenno size_t w; /* window size */ 8777957Sbenno EC_POINT **points; /* array with pre-calculated multiples of generator: 8877957Sbenno * 'num' pointers to EC_POINT objects followed by a NULL */ 8977957Sbenno size_t num; /* numblocks * 2^(w-1) */ 9077957Sbenno int references; 9177957Sbenno} EC_PRE_COMP; 9277957Sbenno 93113038Sobrien/* functions to manage EC_PRE_COMP within the EC_GROUP extra_data framework */ 94113038Sobrienstatic void *ec_pre_comp_dup(void *); 9577957Sbennostatic void ec_pre_comp_free(void *); 9690643Sbennostatic void ec_pre_comp_clear_free(void *); 9790643Sbenno 9890643Sbennostatic EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group) 9990643Sbenno { 10090643Sbenno EC_PRE_COMP *ret = NULL; 10190643Sbenno 10290643Sbenno if (!group) 10390643Sbenno return NULL; 10490643Sbenno 10590643Sbenno ret = (EC_PRE_COMP *)OPENSSL_malloc(sizeof(EC_PRE_COMP)); 10690643Sbenno if (!ret) 10790643Sbenno { 10890643Sbenno ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE); 10990643Sbenno return ret; 11090643Sbenno } 11190643Sbenno ret->group = group; 11290643Sbenno ret->blocksize = 8; /* default */ 11390643Sbenno ret->numblocks = 0; 11490643Sbenno ret->w = 4; /* default */ 11590643Sbenno ret->points = NULL; 11690643Sbenno ret->num = 0; 117118239Speter ret->references = 1; 118118239Speter return ret; 11977957Sbenno } 12080431Speter 12190643Sbennostatic void *ec_pre_comp_dup(void *src_) 12290643Sbenno { 12390643Sbenno EC_PRE_COMP *src = src_; 12490643Sbenno 12577957Sbenno /* no need to actually copy, these objects never change! */ 12690643Sbenno 12790643Sbenno CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP); 12877957Sbenno 12977957Sbenno return src_; 13090643Sbenno } 13190643Sbenno 13290643Sbennostatic void ec_pre_comp_free(void *pre_) 13377957Sbenno { 13477957Sbenno int i; 13577957Sbenno EC_PRE_COMP *pre = pre_; 13677957Sbenno 13777957Sbenno if (!pre) 13877957Sbenno return; 13977957Sbenno 14077957Sbenno i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); 14192847Sjeff if (i > 0) 14277957Sbenno return; 14397346Sbenno 14483730Smp if (pre->points) 14590643Sbenno { 14690643Sbenno EC_POINT **p; 14790643Sbenno 14877957Sbenno for (p = pre->points; *p != NULL; p++) 14990643Sbenno EC_POINT_free(*p); 15077957Sbenno OPENSSL_free(pre->points); 15190643Sbenno } 15277957Sbenno OPENSSL_free(pre); 15390643Sbenno } 15477957Sbenno 15590643Sbennostatic void ec_pre_comp_clear_free(void *pre_) 15690643Sbenno { 15790643Sbenno int i; 15890643Sbenno EC_PRE_COMP *pre = pre_; 15990643Sbenno 16090643Sbenno if (!pre) 16190643Sbenno return; 16290643Sbenno 16390643Sbenno i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); 16490643Sbenno if (i > 0) 16590643Sbenno return; 16690643Sbenno 16790643Sbenno if (pre->points) 16890643Sbenno { 16990643Sbenno EC_POINT **p; 17090643Sbenno 17190643Sbenno for (p = pre->points; *p != NULL; p++) 17294835Sbenno { 17392521Sbenno EC_POINT_clear_free(*p); 17490643Sbenno OPENSSL_cleanse(p, sizeof *p); 17590643Sbenno } 17690643Sbenno OPENSSL_free(pre->points); 17790643Sbenno } 17890643Sbenno OPENSSL_cleanse(pre, sizeof *pre); 17990643Sbenno OPENSSL_free(pre); 18090643Sbenno } 18190643Sbenno 18290643Sbenno 18390643Sbenno 18490643Sbenno 18590643Sbenno/* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'. 18690643Sbenno * This is an array r[] of values that are either zero or odd with an 18790643Sbenno * absolute value less than 2^w satisfying 18890643Sbenno * scalar = \sum_j r[j]*2^j 18990643Sbenno * where at most one of any w+1 consecutive digits is non-zero 19090643Sbenno * with the exception that the most significant digit may be only 19177957Sbenno * w-1 zeros away from that next non-zero digit. 19290643Sbenno */ 19377957Sbennostatic signed char *compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len) 19490643Sbenno { 19590643Sbenno int window_val; 19690643Sbenno int ok = 0; 19790643Sbenno signed char *r = NULL; 19890643Sbenno int sign = 1; 19977957Sbenno int bit, next_bit, mask; 20090643Sbenno size_t len = 0, j; 20190643Sbenno 20290643Sbenno if (BN_is_zero(scalar)) 20390643Sbenno { 20490643Sbenno r = OPENSSL_malloc(1); 20577957Sbenno if (!r) 206110172Sgrehan { 207110172Sgrehan ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); 20890643Sbenno goto err; 20990643Sbenno } 21090643Sbenno r[0] = 0; 21190643Sbenno *ret_len = 1; 21290643Sbenno return r; 21397346Sbenno } 21497346Sbenno 21597346Sbenno if (w <= 0 || w > 7) /* 'signed char' can represent integers with absolute values less than 2^7 */ 216100319Sbenno { 21777957Sbenno ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 21890643Sbenno goto err; 21990643Sbenno } 22090643Sbenno bit = 1 << w; /* at most 128 */ 22190643Sbenno next_bit = bit << 1; /* at most 256 */ 22290643Sbenno mask = next_bit - 1; /* at most 255 */ 22390643Sbenno 22477957Sbenno if (BN_is_negative(scalar)) 22590643Sbenno { 22690643Sbenno sign = -1; 22790643Sbenno } 22890643Sbenno 22990643Sbenno if (scalar->d == NULL || scalar->top == 0) 23077957Sbenno { 23190643Sbenno ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 23290643Sbenno goto err; 23390643Sbenno } 23490643Sbenno 23590643Sbenno len = BN_num_bits(scalar); 23690643Sbenno r = OPENSSL_malloc(len + 1); /* modified wNAF may be one digit longer than binary representation 23777957Sbenno * (*ret_len will be set to the actual length, i.e. at most 23890643Sbenno * BN_num_bits(scalar) + 1) */ 23990643Sbenno if (r == NULL) 24090643Sbenno { 24190643Sbenno ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); 24290643Sbenno goto err; 24390643Sbenno } 24490643Sbenno window_val = scalar->d[0] & mask; 24590643Sbenno j = 0; 24677957Sbenno while ((window_val != 0) || (j + w + 1 < len)) /* if j+w+1 >= len, window_val will not increase */ 24792847Sjeff { 24892847Sjeff int digit = 0; 24990643Sbenno 25090643Sbenno /* 0 <= window_val <= 2^(w+1) */ 25177957Sbenno 25299037Sbenno if (window_val & 1) 25392521Sbenno { 25499037Sbenno /* 0 < window_val < 2^(w+1) */ 25577957Sbenno 25690643Sbenno if (window_val & bit) 25790643Sbenno { 25877957Sbenno digit = window_val - next_bit; /* -2^w < digit < 0 */ 25990643Sbenno 26077957Sbenno#if 1 /* modified wNAF */ 26190643Sbenno if (j + w + 1 >= len) 26290643Sbenno { 26390643Sbenno /* special case for generating modified wNAFs: 26490643Sbenno * no new bits will be added into window_val, 26590643Sbenno * so using a positive digit here will decrease 26690643Sbenno * the total length of the representation */ 26790643Sbenno 26890643Sbenno digit = window_val & (mask >> 1); /* 0 < digit < 2^w */ 26990643Sbenno } 27090643Sbenno#endif 27190643Sbenno } 27290643Sbenno else 27390643Sbenno { 27490643Sbenno digit = window_val; /* 0 < digit < 2^w */ 27590643Sbenno } 27690643Sbenno 27790643Sbenno if (digit <= -bit || digit >= bit || !(digit & 1)) 27890643Sbenno { 27990643Sbenno ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 28090643Sbenno goto err; 28190643Sbenno } 28290643Sbenno 28390643Sbenno window_val -= digit; 28490643Sbenno 28577957Sbenno /* now window_val is 0 or 2^(w+1) in standard wNAF generation; 28690643Sbenno * for modified window NAFs, it may also be 2^w 28777957Sbenno */ 28890643Sbenno if (window_val != 0 && window_val != next_bit && window_val != bit) 28990643Sbenno { 29077957Sbenno ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 29190643Sbenno goto err; 29290643Sbenno } 29390643Sbenno } 29490643Sbenno 29577957Sbenno r[j++] = sign * digit; 29690643Sbenno 29790643Sbenno window_val >>= 1; 29890643Sbenno window_val += bit * BN_is_bit_set(scalar, j + w); 29990643Sbenno 30077957Sbenno if (window_val > next_bit) 30177957Sbenno { 30290643Sbenno ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 30377957Sbenno goto err; 30492847Sjeff } 30590643Sbenno } 30690643Sbenno 30790643Sbenno if (j > len + 1) 30890643Sbenno { 30990643Sbenno ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 31090643Sbenno goto err; 31190643Sbenno } 31290643Sbenno len = j; 31392654Sjeff ok = 1; 31490643Sbenno 31590643Sbenno err: 31690643Sbenno if (!ok) 31790643Sbenno { 31890643Sbenno OPENSSL_free(r); 31990643Sbenno r = NULL; 320110172Sgrehan } 32190643Sbenno if (ok) 32290643Sbenno *ret_len = len; 32390643Sbenno return r; 32490643Sbenno } 32577957Sbenno 32690643Sbenno 32790643Sbenno/* TODO: table should be optimised for the wNAF-based implementation, 32877957Sbenno * sometimes smaller windows will give better performance 32990643Sbenno * (thus the boundaries should be increased) 33090643Sbenno */ 33190643Sbenno#define EC_window_bits_for_scalar_size(b) \ 33290643Sbenno ((size_t) \ 33390643Sbenno ((b) >= 2000 ? 6 : \ 33490643Sbenno (b) >= 800 ? 5 : \ 33590643Sbenno (b) >= 300 ? 4 : \ 33690643Sbenno (b) >= 70 ? 3 : \ 33777957Sbenno (b) >= 20 ? 2 : \ 33877957Sbenno 1)) 33990643Sbenno 34096250Sbenno/* Compute 34177957Sbenno * \sum scalars[i]*points[i], 34290643Sbenno * also including 34377957Sbenno * scalar*generator 34490643Sbenno * in the addition if scalar != NULL 34590643Sbenno */ 34696250Sbennoint ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 34796250Sbenno size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx) 34896250Sbenno { 34990643Sbenno BN_CTX *new_ctx = NULL; 35090643Sbenno const EC_POINT *generator = NULL; 35190643Sbenno EC_POINT *tmp = NULL; 35290643Sbenno size_t totalnum; 35377957Sbenno size_t blocksize = 0, numblocks = 0; /* for wNAF splitting */ 35477957Sbenno size_t pre_points_per_block = 0; 35590643Sbenno size_t i, j; 35690643Sbenno int k; 35790643Sbenno int r_is_inverted = 0; 35890643Sbenno int r_is_at_infinity = 1; 35990643Sbenno size_t *wsize = NULL; /* individual window sizes */ 36090643Sbenno signed char **wNAF = NULL; /* individual wNAFs */ 36190643Sbenno size_t *wNAF_len = NULL; 36277957Sbenno size_t max_len = 0; 36390643Sbenno size_t num_val; 36477957Sbenno EC_POINT **val = NULL; /* precomputation */ 36590643Sbenno EC_POINT **v; 36690643Sbenno EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' or 'pre_comp->points' */ 36777957Sbenno const EC_PRE_COMP *pre_comp = NULL; 36877957Sbenno int num_scalar = 0; /* flag: will be set to 1 if 'scalar' must be treated like other scalars, 36977957Sbenno * i.e. precomputation is not available */ 37090643Sbenno int ret = 0; 37177957Sbenno 37277957Sbenno if (group->meth != r->meth) 37390643Sbenno { 37477957Sbenno ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); 37577957Sbenno return 0; 37690643Sbenno } 37790643Sbenno 37890643Sbenno if ((scalar == NULL) && (num == 0)) 37990643Sbenno { 38090643Sbenno return EC_POINT_set_to_infinity(group, r); 38190643Sbenno } 38290643Sbenno 38377957Sbenno for (i = 0; i < num; i++) 38490643Sbenno { 38577957Sbenno if (group->meth != points[i]->meth) 38690643Sbenno { 38790643Sbenno ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); 38890643Sbenno return 0; 38990643Sbenno } 39077957Sbenno } 39177957Sbenno 39277957Sbenno if (ctx == NULL) 39390643Sbenno { 39477957Sbenno ctx = new_ctx = BN_CTX_new(); 39590643Sbenno if (ctx == NULL) 39690643Sbenno goto err; 39790643Sbenno } 39890643Sbenno 39977957Sbenno if (scalar != NULL) 40090643Sbenno { 40190643Sbenno generator = EC_GROUP_get0_generator(group); 40290643Sbenno if (generator == NULL) 40390643Sbenno { 40490643Sbenno ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR); 40590643Sbenno goto err; 40690643Sbenno } 40790643Sbenno 40890643Sbenno /* look if we can use precomputed multiples of generator */ 40990643Sbenno 41090643Sbenno pre_comp = EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free); 41190643Sbenno 41277957Sbenno if (pre_comp && pre_comp->numblocks && (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) == 0)) 41377957Sbenno { 41490643Sbenno blocksize = pre_comp->blocksize; 41590643Sbenno 41677957Sbenno /* determine maximum number of blocks that wNAF splitting may yield 41777957Sbenno * (NB: maximum wNAF length is bit length plus one) */ 41890643Sbenno numblocks = (BN_num_bits(scalar) / blocksize) + 1; 41977957Sbenno 42077957Sbenno /* we cannot use more blocks than we have precomputation for */ 42190643Sbenno if (numblocks > pre_comp->numblocks) 42290643Sbenno numblocks = pre_comp->numblocks; 42377957Sbenno 42477957Sbenno pre_points_per_block = (size_t)1 << (pre_comp->w - 1); 42590643Sbenno 42690643Sbenno /* check that pre_comp looks sane */ 42790643Sbenno if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block)) 42890643Sbenno { 42990643Sbenno ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 43090643Sbenno goto err; 43190643Sbenno } 43290643Sbenno } 43377957Sbenno else 43477957Sbenno { 43590643Sbenno /* can't use precomputation */ 43690643Sbenno pre_comp = NULL; 43777957Sbenno numblocks = 1; 43877957Sbenno num_scalar = 1; /* treat 'scalar' like 'num'-th element of 'scalars' */ 43990643Sbenno } 44090643Sbenno } 44177957Sbenno 44290643Sbenno totalnum = num + numblocks; 44390643Sbenno 44490643Sbenno wsize = OPENSSL_malloc(totalnum * sizeof wsize[0]); 44577957Sbenno wNAF_len = OPENSSL_malloc(totalnum * sizeof wNAF_len[0]); 44690643Sbenno wNAF = OPENSSL_malloc((totalnum + 1) * sizeof wNAF[0]); /* includes space for pivot */ 44790643Sbenno val_sub = OPENSSL_malloc(totalnum * sizeof val_sub[0]); 44890643Sbenno 44990643Sbenno if (!wsize || !wNAF_len || !wNAF || !val_sub) 45090643Sbenno { 45190643Sbenno ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 45277957Sbenno goto err; 45390643Sbenno } 45490643Sbenno 45590643Sbenno wNAF[0] = NULL; /* preliminary pivot */ 45690643Sbenno 45790643Sbenno /* num_val will be the total number of temporarily precomputed points */ 45890643Sbenno num_val = 0; 45977957Sbenno 46090643Sbenno for (i = 0; i < num + num_scalar; i++) 46177957Sbenno { 46290643Sbenno size_t bits; 46377957Sbenno 46490643Sbenno bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar); 46590643Sbenno wsize[i] = EC_window_bits_for_scalar_size(bits); 46690643Sbenno num_val += (size_t)1 << (wsize[i] - 1); 46790643Sbenno wNAF[i + 1] = NULL; /* make sure we always have a pivot */ 46877957Sbenno wNAF[i] = compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], &wNAF_len[i]); 46990643Sbenno if (wNAF[i] == NULL) 47090643Sbenno goto err; 47190643Sbenno if (wNAF_len[i] > max_len) 47290643Sbenno max_len = wNAF_len[i]; 47390643Sbenno } 47477957Sbenno 47590643Sbenno if (numblocks) 47690643Sbenno { 47790643Sbenno /* we go here iff scalar != NULL */ 47890643Sbenno 47990643Sbenno if (pre_comp == NULL) 48077957Sbenno { 48177957Sbenno if (num_scalar != 1) 48290643Sbenno { 48390643Sbenno ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 48490643Sbenno goto err; 48590643Sbenno } 48690643Sbenno /* we have already generated a wNAF for 'scalar' */ 48790643Sbenno } 48890643Sbenno else 48990643Sbenno { 49090643Sbenno signed char *tmp_wNAF = NULL; 49190643Sbenno size_t tmp_len = 0; 49290643Sbenno 49377957Sbenno if (num_scalar != 0) 49490643Sbenno { 49577957Sbenno ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 49690643Sbenno goto err; 49790643Sbenno } 49890643Sbenno 49990643Sbenno /* use the window size for which we have precomputation */ 50090643Sbenno wsize[num] = pre_comp->w; 50177957Sbenno tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len); 50290643Sbenno if (!tmp_wNAF) 50390643Sbenno goto err; 50477957Sbenno 50590643Sbenno if (tmp_len <= max_len) 50690643Sbenno { 50790643Sbenno /* One of the other wNAFs is at least as long 50890643Sbenno * as the wNAF belonging to the generator, 50990643Sbenno * so wNAF splitting will not buy us anything. */ 51090643Sbenno 51190643Sbenno numblocks = 1; 51290643Sbenno totalnum = num + 1; /* don't use wNAF splitting */ 51390643Sbenno wNAF[num] = tmp_wNAF; 51477957Sbenno wNAF[num + 1] = NULL; 51590643Sbenno wNAF_len[num] = tmp_len; 51690643Sbenno if (tmp_len > max_len) 51790643Sbenno max_len = tmp_len; 51890643Sbenno /* pre_comp->points starts with the points that we need here: */ 51990643Sbenno val_sub[num] = pre_comp->points; 52090643Sbenno } 52190643Sbenno else 52290643Sbenno { 52390643Sbenno /* don't include tmp_wNAF directly into wNAF array 52490643Sbenno * - use wNAF splitting and include the blocks */ 52590643Sbenno 52690643Sbenno signed char *pp; 52790643Sbenno EC_POINT **tmp_points; 52890643Sbenno 52977957Sbenno if (tmp_len < numblocks * blocksize) 53077957Sbenno { 53177957Sbenno /* possibly we can do with fewer blocks than estimated */ 53290643Sbenno numblocks = (tmp_len + blocksize - 1) / blocksize; 53377957Sbenno if (numblocks > pre_comp->numblocks) 53497346Sbenno { 53590643Sbenno ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 53690643Sbenno goto err; 53790643Sbenno } 538103604Sgrehan totalnum = num + numblocks; 53991793Sbenno } 54090643Sbenno 54190643Sbenno /* split wNAF in 'numblocks' parts */ 54277957Sbenno pp = tmp_wNAF; 54399037Sbenno tmp_points = pre_comp->points; 544103604Sgrehan 54599037Sbenno for (i = num; i < totalnum; i++) 54699037Sbenno { 54799037Sbenno if (i < totalnum - 1) 54899037Sbenno { 54999037Sbenno wNAF_len[i] = blocksize; 55099037Sbenno if (tmp_len < blocksize) 55199037Sbenno { 55299037Sbenno ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 55399037Sbenno goto err; 55499037Sbenno } 55599037Sbenno tmp_len -= blocksize; 55699037Sbenno } 55799037Sbenno else 55899037Sbenno /* last block gets whatever is left 55999037Sbenno * (this could be more or less than 'blocksize'!) */ 56099037Sbenno wNAF_len[i] = tmp_len; 56199037Sbenno 56299037Sbenno wNAF[i + 1] = NULL; 56399037Sbenno wNAF[i] = OPENSSL_malloc(wNAF_len[i]); 56499037Sbenno if (wNAF[i] == NULL) 56599037Sbenno { 56699037Sbenno ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 56799037Sbenno OPENSSL_free(tmp_wNAF); 56899037Sbenno goto err; 56999037Sbenno } 57077957Sbenno memcpy(wNAF[i], pp, wNAF_len[i]); 57190643Sbenno if (wNAF_len[i] > max_len) 57290643Sbenno max_len = wNAF_len[i]; 57377957Sbenno 57490643Sbenno if (*tmp_points == NULL) 57590643Sbenno { 57690643Sbenno ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 57790643Sbenno OPENSSL_free(tmp_wNAF); 57899037Sbenno goto err; 57990643Sbenno } 58099037Sbenno val_sub[i] = tmp_points; 58199037Sbenno tmp_points += pre_points_per_block; 58299037Sbenno pp += blocksize; 58399037Sbenno } 58499037Sbenno OPENSSL_free(tmp_wNAF); 58599037Sbenno } 58699037Sbenno } 58799037Sbenno } 58899037Sbenno 58990643Sbenno /* All points we precompute now go into a single array 'val'. 59099037Sbenno * 'val_sub[i]' is a pointer to the subarray for the i-th point, 59199037Sbenno * or to a subarray of 'pre_comp->points' if we already have precomputation. */ 59290643Sbenno val = OPENSSL_malloc((num_val + 1) * sizeof val[0]); 59390643Sbenno if (val == NULL) 59477957Sbenno { 59577957Sbenno ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 59690643Sbenno goto err; 59777957Sbenno } 59890643Sbenno val[num_val] = NULL; /* pivot element */ 59990643Sbenno 60090643Sbenno /* allocate points for precomputation */ 60197346Sbenno v = val; 60297346Sbenno for (i = 0; i < num + num_scalar; i++) 60397346Sbenno { 60497346Sbenno val_sub[i] = v; 60597346Sbenno for (j = 0; j < ((size_t)1 << (wsize[i] - 1)); j++) 606103604Sgrehan { 607103604Sgrehan *v = EC_POINT_new(group); 608103604Sgrehan if (*v == NULL) goto err; 60997346Sbenno v++; 61097346Sbenno } 61197346Sbenno } 61297346Sbenno if (!(v == val + num_val)) 613103604Sgrehan { 614103604Sgrehan ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 615103604Sgrehan goto err; 616103604Sgrehan } 617103604Sgrehan 618103604Sgrehan if (!(tmp = EC_POINT_new(group))) 619103604Sgrehan goto err; 620103604Sgrehan 621103604Sgrehan /* prepare precomputed values: 622103604Sgrehan * val_sub[i][0] := points[i] 623103604Sgrehan * val_sub[i][1] := 3 * points[i] 624103604Sgrehan * val_sub[i][2] := 5 * points[i] 625103604Sgrehan * ... 626103604Sgrehan */ 627103604Sgrehan for (i = 0; i < num + num_scalar; i++) 628103604Sgrehan { 62997346Sbenno if (i < num) 63097346Sbenno { 63197346Sbenno if (!EC_POINT_copy(val_sub[i][0], points[i])) goto err; 63290643Sbenno } 63397346Sbenno else 63490643Sbenno { 63591793Sbenno if (!EC_POINT_copy(val_sub[i][0], generator)) goto err; 63697346Sbenno } 63790643Sbenno 63890643Sbenno if (wsize[i] > 1) 63990643Sbenno { 64090643Sbenno if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) goto err; 64190643Sbenno for (j = 1; j < ((size_t)1 << (wsize[i] - 1)); j++) 64290643Sbenno { 64391793Sbenno if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) goto err; 64477957Sbenno } 64591793Sbenno } 64677957Sbenno } 64777957Sbenno 64890643Sbenno#if 1 /* optional; EC_window_bits_for_scalar_size assumes we do this step */ 64977957Sbenno if (!EC_POINTs_make_affine(group, num_val, val, ctx)) 65090643Sbenno goto err; 65190643Sbenno#endif 65290643Sbenno 65390643Sbenno r_is_at_infinity = 1; 65477957Sbenno 65590643Sbenno for (k = max_len - 1; k >= 0; k--) 65690643Sbenno { 65777957Sbenno if (!r_is_at_infinity) 65890643Sbenno { 65990643Sbenno if (!EC_POINT_dbl(group, r, r, ctx)) goto err; 66077957Sbenno } 66190643Sbenno 66290643Sbenno for (i = 0; i < totalnum; i++) 66390643Sbenno { 66490643Sbenno if (wNAF_len[i] > (size_t)k) 66590643Sbenno { 66690643Sbenno int digit = wNAF[i][k]; 66790643Sbenno int is_neg; 66877957Sbenno 66990643Sbenno if (digit) 67094839Sbenno { 67190643Sbenno is_neg = digit < 0; 67290643Sbenno 67390643Sbenno if (is_neg) 67490643Sbenno digit = -digit; 67590643Sbenno 67690643Sbenno if (is_neg != r_is_inverted) 67790643Sbenno { 67877957Sbenno if (!r_is_at_infinity) 67990643Sbenno { 68090643Sbenno if (!EC_POINT_invert(group, r, ctx)) goto err; 68190643Sbenno } 68290643Sbenno r_is_inverted = !r_is_inverted; 68377957Sbenno } 68490643Sbenno 68590643Sbenno /* digit > 0 */ 68690643Sbenno 68799037Sbenno if (r_is_at_infinity) 68899037Sbenno { 68992521Sbenno if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) goto err; 69077957Sbenno r_is_at_infinity = 0; 69177957Sbenno } 69290643Sbenno else 69377957Sbenno { 69490643Sbenno if (!EC_POINT_add(group, r, r, val_sub[i][digit >> 1], ctx)) goto err; 69590643Sbenno } 69690643Sbenno } 69777957Sbenno } 69890643Sbenno } 69990643Sbenno } 70090643Sbenno 70190643Sbenno if (r_is_at_infinity) 70290643Sbenno { 70390643Sbenno if (!EC_POINT_set_to_infinity(group, r)) goto err; 70490643Sbenno } 70590643Sbenno else 70690643Sbenno { 70790643Sbenno if (r_is_inverted) 70890643Sbenno if (!EC_POINT_invert(group, r, ctx)) goto err; 70990643Sbenno } 710100319Sbenno 711100319Sbenno ret = 1; 712100319Sbenno 713100319Sbenno err: 714100319Sbenno if (new_ctx != NULL) 715100319Sbenno BN_CTX_free(new_ctx); 716100319Sbenno if (tmp != NULL) 71790643Sbenno EC_POINT_free(tmp); 71890643Sbenno if (wsize != NULL) 71990643Sbenno OPENSSL_free(wsize); 72090643Sbenno if (wNAF_len != NULL) 72197346Sbenno OPENSSL_free(wNAF_len); 72290643Sbenno if (wNAF != NULL) 723103604Sgrehan { 72490643Sbenno signed char **w; 72590643Sbenno 72690643Sbenno for (w = wNAF; *w != NULL; w++) 72777957Sbenno OPENSSL_free(*w); 728103604Sgrehan 729103604Sgrehan OPENSSL_free(wNAF); 730103604Sgrehan } 731103604Sgrehan if (val != NULL) 732103604Sgrehan { 733103604Sgrehan for (v = val; *v != NULL; v++) 73477957Sbenno EC_POINT_clear_free(*v); 735103604Sgrehan 73690643Sbenno OPENSSL_free(val); 73790643Sbenno } 73877957Sbenno if (val_sub != NULL) 73990643Sbenno { 74090643Sbenno OPENSSL_free(val_sub); 741103604Sgrehan } 742103604Sgrehan return ret; 74377957Sbenno } 74477957Sbenno 74590643Sbenno 74690643Sbenno/* ec_wNAF_precompute_mult() 74790643Sbenno * creates an EC_PRE_COMP object with preprecomputed multiples of the generator 74877957Sbenno * for use with wNAF splitting as implemented in ec_wNAF_mul(). 74990643Sbenno * 75090643Sbenno * 'pre_comp->points' is an array of multiples of the generator 75190643Sbenno * of the following form: 75290643Sbenno * points[0] = generator; 75390643Sbenno * points[1] = 3 * generator; 75477957Sbenno * ... 75590643Sbenno * points[2^(w-1)-1] = (2^(w-1)-1) * generator; 75690643Sbenno * points[2^(w-1)] = 2^blocksize * generator; 75777957Sbenno * points[2^(w-1)+1] = 3 * 2^blocksize * generator; 75877957Sbenno * ... 75990643Sbenno * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) * 2^(blocksize*(numblocks-2)) * generator 76090643Sbenno * points[2^(w-1)*(numblocks-1)] = 2^(blocksize*(numblocks-1)) * generator 76177957Sbenno * ... 76290643Sbenno * points[2^(w-1)*numblocks-1] = (2^(w-1)) * 2^(blocksize*(numblocks-1)) * generator 76390643Sbenno * points[2^(w-1)*numblocks] = NULL 76490643Sbenno */ 76590643Sbennoint ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) 76690643Sbenno { 76790643Sbenno const EC_POINT *generator; 76890643Sbenno EC_POINT *tmp_point = NULL, *base = NULL, **var; 76990643Sbenno BN_CTX *new_ctx = NULL; 77090643Sbenno BIGNUM *order; 77190643Sbenno size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num; 77290643Sbenno EC_POINT **points = NULL; 77377957Sbenno EC_PRE_COMP *pre_comp; 77477957Sbenno int ret = 0; 77590643Sbenno 77690643Sbenno /* if there is an old EC_PRE_COMP object, throw it away */ 77790643Sbenno EC_EX_DATA_free_data(&group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free); 77890643Sbenno 77990643Sbenno if ((pre_comp = ec_pre_comp_new(group)) == NULL) 78090643Sbenno return 0; 78190643Sbenno 78290643Sbenno generator = EC_GROUP_get0_generator(group); 78377957Sbenno if (generator == NULL) 78477957Sbenno { 78590643Sbenno ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR); 78677957Sbenno goto err; 78790643Sbenno } 78890643Sbenno 78977957Sbenno if (ctx == NULL) 79077957Sbenno { 79190643Sbenno ctx = new_ctx = BN_CTX_new(); 79277957Sbenno if (ctx == NULL) 79377957Sbenno goto err; 79494836Sbenno } 79577957Sbenno 79677957Sbenno BN_CTX_start(ctx); 79790643Sbenno order = BN_CTX_get(ctx); 79877957Sbenno if (order == NULL) goto err; 79990643Sbenno 80077957Sbenno if (!EC_GROUP_get_order(group, order, ctx)) goto err; 80177957Sbenno if (BN_is_zero(order)) 80290643Sbenno { 80377957Sbenno ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER); 80477957Sbenno goto err; 80577957Sbenno } 80690643Sbenno 80790643Sbenno bits = BN_num_bits(order); 80877957Sbenno /* The following parameters mean we precompute (approximately) 80977957Sbenno * one point per bit. 81090643Sbenno * 81177957Sbenno * TBD: The combination 8, 4 is perfect for 160 bits; for other 81296250Sbenno * bit lengths, other parameter combinations might provide better 81377957Sbenno * efficiency. 81477957Sbenno */ 815103604Sgrehan blocksize = 8; 81690643Sbenno w = 4; 81777957Sbenno if (EC_window_bits_for_scalar_size(bits) > w) 81890643Sbenno { 81977957Sbenno /* let's not make the window too small ... */ 82096250Sbenno w = EC_window_bits_for_scalar_size(bits); 82196250Sbenno } 82296250Sbenno 82390643Sbenno numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks to use for wNAF splitting */ 82496250Sbenno 82577957Sbenno pre_points_per_block = (size_t)1 << (w - 1); 82677957Sbenno num = pre_points_per_block * numblocks; /* number of points to compute and store */ 82791483Sbenno 82891483Sbenno points = OPENSSL_malloc(sizeof (EC_POINT*)*(num + 1)); 82991483Sbenno if (!points) 83091483Sbenno { 83191483Sbenno ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 83291483Sbenno goto err; 83391483Sbenno } 83496250Sbenno 83591483Sbenno var = points; 83691483Sbenno var[num] = NULL; /* pivot */ 83790643Sbenno for (i = 0; i < num; i++) 83890643Sbenno { 83977957Sbenno if ((var[i] = EC_POINT_new(group)) == NULL) 84096353Sbenno { 84196353Sbenno ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 84277957Sbenno goto err; 84377957Sbenno } 84477957Sbenno } 84596353Sbenno 84677957Sbenno if (!(tmp_point = EC_POINT_new(group)) || !(base = EC_POINT_new(group))) 84796353Sbenno { 84896353Sbenno ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 84996353Sbenno goto err; 85096353Sbenno } 85196353Sbenno 85296353Sbenno if (!EC_POINT_copy(base, generator)) 85396353Sbenno goto err; 85496353Sbenno 85596353Sbenno /* do the precomputation */ 85696353Sbenno for (i = 0; i < numblocks; i++) 85796353Sbenno { 85896353Sbenno size_t j; 85996353Sbenno 86096353Sbenno if (!EC_POINT_dbl(group, tmp_point, base, ctx)) 86196353Sbenno goto err; 86277957Sbenno 86377957Sbenno if (!EC_POINT_copy(*var++, base)) 86477957Sbenno goto err; 86590643Sbenno 86690643Sbenno for (j = 1; j < pre_points_per_block; j++, var++) 86777957Sbenno { 86897385Sbenno /* calculate odd multiples of the current base point */ 86997385Sbenno if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx)) 87097385Sbenno goto err; 87197385Sbenno } 87297385Sbenno 87377957Sbenno if (i < numblocks - 1) 87477957Sbenno { 87577957Sbenno /* get the next base (multiply current one by 2^blocksize) */ 87697385Sbenno size_t k; 87777957Sbenno 87897385Sbenno if (blocksize <= 2) 87997385Sbenno { 88097385Sbenno ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_INTERNAL_ERROR); 88197385Sbenno goto err; 88297385Sbenno } 88397385Sbenno 88497385Sbenno if (!EC_POINT_dbl(group, base, tmp_point, ctx)) 88577957Sbenno goto err; 88677957Sbenno for (k = 2; k < blocksize; k++) 88777957Sbenno { 88890643Sbenno if (!EC_POINT_dbl(group,base,base,ctx)) 88977957Sbenno goto err; 89077957Sbenno } 89194777Speter } 89277957Sbenno } 89394777Speter 894110172Sgrehan if (!EC_POINTs_make_affine(group, num, points, ctx)) 89577957Sbenno goto err; 89690643Sbenno 89790643Sbenno pre_comp->group = group; 89890643Sbenno pre_comp->blocksize = blocksize; 89990643Sbenno pre_comp->numblocks = numblocks; 90090643Sbenno pre_comp->w = w; 90190643Sbenno pre_comp->points = points; 90290643Sbenno points = NULL; 90390643Sbenno pre_comp->num = num; 90490643Sbenno 90577957Sbenno if (!EC_EX_DATA_set_data(&group->extra_data, pre_comp, 90690643Sbenno ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free)) 90790643Sbenno goto err; 90890643Sbenno pre_comp = NULL; 90990643Sbenno 91090643Sbenno ret = 1; 91177957Sbenno err: 91277957Sbenno if (ctx != NULL) 91377957Sbenno BN_CTX_end(ctx); 91494777Speter if (new_ctx != NULL) 91577957Sbenno BN_CTX_free(new_ctx); 91699666Sbenno if (pre_comp) 917103604Sgrehan ec_pre_comp_free(pre_comp); 91899666Sbenno if (points) 91999666Sbenno { 92099666Sbenno EC_POINT **p; 92199666Sbenno 92299666Sbenno for (p = points; *p != NULL; p++) 92399666Sbenno EC_POINT_free(*p); 92499666Sbenno OPENSSL_free(points); 92599666Sbenno } 92699666Sbenno if (tmp_point) 92799666Sbenno EC_POINT_free(tmp_point); 92899666Sbenno if (base) 92999666Sbenno EC_POINT_free(base); 930103604Sgrehan return ret; 93199666Sbenno } 93299666Sbenno 93399666Sbenno 93477957Sbennoint ec_wNAF_have_precompute_mult(const EC_GROUP *group) 93577957Sbenno { 93699571Speter if (EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free) != NULL) 93799571Speter return 1; 93899571Speter else 93999571Speter return 0; 94099571Speter } 94199571Speter