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