1109998Smarkm/* crypto/ec/ec_mult.c */ 2160814Ssimon/* 3160814Ssimon * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project. 4160814Ssimon */ 5109998Smarkm/* ==================================================================== 6348343Sjkim * Copyright (c) 1998-2019 The OpenSSL Project. All rights reserved. 7109998Smarkm * 8109998Smarkm * Redistribution and use in source and binary forms, with or without 9109998Smarkm * modification, are permitted provided that the following conditions 10109998Smarkm * are met: 11109998Smarkm * 12109998Smarkm * 1. Redistributions of source code must retain the above copyright 13280297Sjkim * notice, this list of conditions and the following disclaimer. 14109998Smarkm * 15109998Smarkm * 2. Redistributions in binary form must reproduce the above copyright 16109998Smarkm * notice, this list of conditions and the following disclaimer in 17109998Smarkm * the documentation and/or other materials provided with the 18109998Smarkm * distribution. 19109998Smarkm * 20109998Smarkm * 3. All advertising materials mentioning features or use of this 21109998Smarkm * software must display the following acknowledgment: 22109998Smarkm * "This product includes software developed by the OpenSSL Project 23109998Smarkm * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 24109998Smarkm * 25109998Smarkm * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 26109998Smarkm * endorse or promote products derived from this software without 27109998Smarkm * prior written permission. For written permission, please contact 28109998Smarkm * openssl-core@openssl.org. 29109998Smarkm * 30109998Smarkm * 5. Products derived from this software may not be called "OpenSSL" 31109998Smarkm * nor may "OpenSSL" appear in their names without prior written 32109998Smarkm * permission of the OpenSSL Project. 33109998Smarkm * 34109998Smarkm * 6. Redistributions of any form whatsoever must retain the following 35109998Smarkm * acknowledgment: 36109998Smarkm * "This product includes software developed by the OpenSSL Project 37109998Smarkm * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 38109998Smarkm * 39109998Smarkm * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 40109998Smarkm * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 41109998Smarkm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 42109998Smarkm * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 43109998Smarkm * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44109998Smarkm * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 45109998Smarkm * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 46109998Smarkm * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47109998Smarkm * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 48109998Smarkm * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 49109998Smarkm * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 50109998Smarkm * OF THE POSSIBILITY OF SUCH DAMAGE. 51109998Smarkm * ==================================================================== 52109998Smarkm * 53109998Smarkm * This product includes cryptographic software written by Eric Young 54109998Smarkm * (eay@cryptsoft.com). This product includes software written by Tim 55109998Smarkm * Hudson (tjh@cryptsoft.com). 56109998Smarkm * 57109998Smarkm */ 58160814Ssimon/* ==================================================================== 59160814Ssimon * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 60160814Ssimon * Portions of this software developed by SUN MICROSYSTEMS, INC., 61160814Ssimon * and contributed to the OpenSSL project. 62160814Ssimon */ 63109998Smarkm 64160814Ssimon#include <string.h> 65160814Ssimon 66109998Smarkm#include <openssl/err.h> 67109998Smarkm 68109998Smarkm#include "ec_lcl.h" 69109998Smarkm 70160814Ssimon/* 71325335Sjkim * This file implements the wNAF-based interleaving multi-exponentiation method 72325335Sjkim * Formerly at: 73325335Sjkim * http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp 74325335Sjkim * You might now find it here: 75325335Sjkim * http://link.springer.com/chapter/10.1007%2F3-540-45537-X_13 76325335Sjkim * http://www.bmoeller.de/pdf/TI-01-08.multiexp.pdf 77325335Sjkim * For multiplication with precomputation, we use wNAF splitting, formerly at: 78325335Sjkim * http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp 79160814Ssimon */ 80109998Smarkm 81160814Ssimon/* structure for precomputed multiples of the generator */ 82160814Ssimontypedef struct ec_pre_comp_st { 83280297Sjkim const EC_GROUP *group; /* parent EC_GROUP object */ 84280297Sjkim size_t blocksize; /* block size for wNAF splitting */ 85280297Sjkim size_t numblocks; /* max. number of blocks for which we have 86280297Sjkim * precomputation */ 87280297Sjkim size_t w; /* window size */ 88280297Sjkim EC_POINT **points; /* array with pre-calculated multiples of 89280297Sjkim * generator: 'num' pointers to EC_POINT 90280297Sjkim * objects followed by a NULL */ 91280297Sjkim size_t num; /* numblocks * 2^(w-1) */ 92280297Sjkim int references; 93160814Ssimon} EC_PRE_COMP; 94280297Sjkim 95160814Ssimon/* functions to manage EC_PRE_COMP within the EC_GROUP extra_data framework */ 96160814Ssimonstatic void *ec_pre_comp_dup(void *); 97160814Ssimonstatic void ec_pre_comp_free(void *); 98160814Ssimonstatic void ec_pre_comp_clear_free(void *); 99109998Smarkm 100160814Ssimonstatic EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group) 101280297Sjkim{ 102280297Sjkim EC_PRE_COMP *ret = NULL; 103160814Ssimon 104280297Sjkim if (!group) 105280297Sjkim return NULL; 106160814Ssimon 107280297Sjkim ret = (EC_PRE_COMP *)OPENSSL_malloc(sizeof(EC_PRE_COMP)); 108280297Sjkim if (!ret) { 109280297Sjkim ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE); 110280297Sjkim return ret; 111280297Sjkim } 112280297Sjkim ret->group = group; 113280297Sjkim ret->blocksize = 8; /* default */ 114280297Sjkim ret->numblocks = 0; 115280297Sjkim ret->w = 4; /* default */ 116280297Sjkim ret->points = NULL; 117280297Sjkim ret->num = 0; 118280297Sjkim ret->references = 1; 119280297Sjkim return ret; 120280297Sjkim} 121160814Ssimon 122160814Ssimonstatic void *ec_pre_comp_dup(void *src_) 123280297Sjkim{ 124280297Sjkim EC_PRE_COMP *src = src_; 125160814Ssimon 126280297Sjkim /* no need to actually copy, these objects never change! */ 127160814Ssimon 128280297Sjkim CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP); 129160814Ssimon 130280297Sjkim return src_; 131280297Sjkim} 132160814Ssimon 133160814Ssimonstatic void ec_pre_comp_free(void *pre_) 134280297Sjkim{ 135280297Sjkim int i; 136280297Sjkim EC_PRE_COMP *pre = pre_; 137160814Ssimon 138280297Sjkim if (!pre) 139280297Sjkim return; 140160814Ssimon 141280297Sjkim i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); 142280297Sjkim if (i > 0) 143280297Sjkim return; 144160814Ssimon 145280297Sjkim if (pre->points) { 146280297Sjkim EC_POINT **p; 147160814Ssimon 148280297Sjkim for (p = pre->points; *p != NULL; p++) 149280297Sjkim EC_POINT_free(*p); 150280297Sjkim OPENSSL_free(pre->points); 151280297Sjkim } 152280297Sjkim OPENSSL_free(pre); 153280297Sjkim} 154160814Ssimon 155160814Ssimonstatic void ec_pre_comp_clear_free(void *pre_) 156280297Sjkim{ 157280297Sjkim int i; 158280297Sjkim EC_PRE_COMP *pre = pre_; 159160814Ssimon 160280297Sjkim if (!pre) 161280297Sjkim return; 162160814Ssimon 163280297Sjkim i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); 164280297Sjkim if (i > 0) 165280297Sjkim return; 166160814Ssimon 167280297Sjkim if (pre->points) { 168280297Sjkim EC_POINT **p; 169160814Ssimon 170280297Sjkim for (p = pre->points; *p != NULL; p++) { 171280297Sjkim EC_POINT_clear_free(*p); 172331638Sjkim OPENSSL_cleanse(p, sizeof(*p)); 173280297Sjkim } 174280297Sjkim OPENSSL_free(pre->points); 175280297Sjkim } 176331638Sjkim OPENSSL_cleanse(pre, sizeof(*pre)); 177280297Sjkim OPENSSL_free(pre); 178280297Sjkim} 179160814Ssimon 180280297Sjkim/*- 181280297Sjkim * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'. 182109998Smarkm * This is an array r[] of values that are either zero or odd with an 183109998Smarkm * absolute value less than 2^w satisfying 184109998Smarkm * scalar = \sum_j r[j]*2^j 185160814Ssimon * where at most one of any w+1 consecutive digits is non-zero 186160814Ssimon * with the exception that the most significant digit may be only 187160814Ssimon * w-1 zeros away from that next non-zero digit. 188109998Smarkm */ 189160814Ssimonstatic signed char *compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len) 190280297Sjkim{ 191280297Sjkim int window_val; 192280297Sjkim int ok = 0; 193280297Sjkim signed char *r = NULL; 194280297Sjkim int sign = 1; 195280297Sjkim int bit, next_bit, mask; 196280297Sjkim size_t len = 0, j; 197109998Smarkm 198280297Sjkim if (BN_is_zero(scalar)) { 199280297Sjkim r = OPENSSL_malloc(1); 200280297Sjkim if (!r) { 201280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); 202280297Sjkim goto err; 203280297Sjkim } 204280297Sjkim r[0] = 0; 205280297Sjkim *ret_len = 1; 206280297Sjkim return r; 207280297Sjkim } 208109998Smarkm 209280297Sjkim if (w <= 0 || w > 7) { /* 'signed char' can represent integers with 210280297Sjkim * absolute values less than 2^7 */ 211280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 212280297Sjkim goto err; 213280297Sjkim } 214280297Sjkim bit = 1 << w; /* at most 128 */ 215280297Sjkim next_bit = bit << 1; /* at most 256 */ 216280297Sjkim mask = next_bit - 1; /* at most 255 */ 217238405Sjkim 218280297Sjkim if (BN_is_negative(scalar)) { 219280297Sjkim sign = -1; 220280297Sjkim } 221109998Smarkm 222280297Sjkim if (scalar->d == NULL || scalar->top == 0) { 223280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 224280297Sjkim goto err; 225280297Sjkim } 226160814Ssimon 227280297Sjkim len = BN_num_bits(scalar); 228280297Sjkim r = OPENSSL_malloc(len + 1); /* modified wNAF may be one digit longer 229280297Sjkim * than binary representation (*ret_len will 230280297Sjkim * be set to the actual length, i.e. at most 231280297Sjkim * BN_num_bits(scalar) + 1) */ 232280297Sjkim if (r == NULL) { 233280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); 234280297Sjkim goto err; 235280297Sjkim } 236280297Sjkim window_val = scalar->d[0] & mask; 237280297Sjkim j = 0; 238280297Sjkim while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len, 239280297Sjkim * window_val will not 240280297Sjkim * increase */ 241280297Sjkim int digit = 0; 242160814Ssimon 243280297Sjkim /* 0 <= window_val <= 2^(w+1) */ 244160814Ssimon 245280297Sjkim if (window_val & 1) { 246280297Sjkim /* 0 < window_val < 2^(w+1) */ 247280297Sjkim 248280297Sjkim if (window_val & bit) { 249280297Sjkim digit = window_val - next_bit; /* -2^w < digit < 0 */ 250280297Sjkim 251280297Sjkim#if 1 /* modified wNAF */ 252280297Sjkim if (j + w + 1 >= len) { 253280297Sjkim /* 254280297Sjkim * special case for generating modified wNAFs: no new 255280297Sjkim * bits will be added into window_val, so using a 256280297Sjkim * positive digit here will decrease the total length of 257280297Sjkim * the representation 258280297Sjkim */ 259280297Sjkim 260280297Sjkim digit = window_val & (mask >> 1); /* 0 < digit < 2^w */ 261280297Sjkim } 262160814Ssimon#endif 263280297Sjkim } else { 264280297Sjkim digit = window_val; /* 0 < digit < 2^w */ 265280297Sjkim } 266109998Smarkm 267280297Sjkim if (digit <= -bit || digit >= bit || !(digit & 1)) { 268280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 269280297Sjkim goto err; 270280297Sjkim } 271160814Ssimon 272280297Sjkim window_val -= digit; 273109998Smarkm 274280297Sjkim /* 275280297Sjkim * now window_val is 0 or 2^(w+1) in standard wNAF generation; 276280297Sjkim * for modified window NAFs, it may also be 2^w 277280297Sjkim */ 278280297Sjkim if (window_val != 0 && window_val != next_bit 279280297Sjkim && window_val != bit) { 280280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 281280297Sjkim goto err; 282280297Sjkim } 283280297Sjkim } 284160814Ssimon 285280297Sjkim r[j++] = sign * digit; 286160814Ssimon 287280297Sjkim window_val >>= 1; 288280297Sjkim window_val += bit * BN_is_bit_set(scalar, j + w); 289109998Smarkm 290280297Sjkim if (window_val > next_bit) { 291280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 292280297Sjkim goto err; 293280297Sjkim } 294280297Sjkim } 295109998Smarkm 296280297Sjkim if (j > len + 1) { 297280297Sjkim ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); 298280297Sjkim goto err; 299280297Sjkim } 300280297Sjkim len = j; 301280297Sjkim ok = 1; 302280297Sjkim 303109998Smarkm err: 304280297Sjkim if (!ok) { 305280297Sjkim OPENSSL_free(r); 306280297Sjkim r = NULL; 307280297Sjkim } 308280297Sjkim if (ok) 309280297Sjkim *ret_len = len; 310280297Sjkim return r; 311280297Sjkim} 312109998Smarkm 313340704Sjkim#define EC_POINT_BN_set_flags(P, flags) do { \ 314340704Sjkim BN_set_flags(&(P)->X, (flags)); \ 315340704Sjkim BN_set_flags(&(P)->Y, (flags)); \ 316340704Sjkim BN_set_flags(&(P)->Z, (flags)); \ 317340704Sjkim} while(0) 318340704Sjkim 319340704Sjkim/*- 320340704Sjkim * This functions computes (in constant time) a point multiplication over the 321340704Sjkim * EC group. 322340704Sjkim * 323340704Sjkim * At a high level, it is Montgomery ladder with conditional swaps. 324340704Sjkim * 325340704Sjkim * It performs either a fixed scalar point multiplication 326340704Sjkim * (scalar * generator) 327340704Sjkim * when point is NULL, or a generic scalar point multiplication 328340704Sjkim * (scalar * point) 329340704Sjkim * when point is not NULL. 330340704Sjkim * 331340704Sjkim * scalar should be in the range [0,n) otherwise all constant time bets are off. 332340704Sjkim * 333340704Sjkim * NB: This says nothing about EC_POINT_add and EC_POINT_dbl, 334340704Sjkim * which of course are not constant time themselves. 335340704Sjkim * 336340704Sjkim * The product is stored in r. 337340704Sjkim * 338340704Sjkim * Returns 1 on success, 0 otherwise. 339340704Sjkim */ 340340704Sjkimstatic int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r, 341340704Sjkim const BIGNUM *scalar, const EC_POINT *point, 342340704Sjkim BN_CTX *ctx) 343340704Sjkim{ 344340704Sjkim int i, cardinality_bits, group_top, kbit, pbit, Z_is_one; 345340704Sjkim EC_POINT *s = NULL; 346340704Sjkim BIGNUM *k = NULL; 347340704Sjkim BIGNUM *lambda = NULL; 348340704Sjkim BIGNUM *cardinality = NULL; 349340704Sjkim BN_CTX *new_ctx = NULL; 350340704Sjkim int ret = 0; 351340704Sjkim 352340704Sjkim if (ctx == NULL && (ctx = new_ctx = BN_CTX_new()) == NULL) 353340704Sjkim return 0; 354340704Sjkim 355340704Sjkim BN_CTX_start(ctx); 356340704Sjkim 357340704Sjkim s = EC_POINT_new(group); 358340704Sjkim if (s == NULL) 359340704Sjkim goto err; 360340704Sjkim 361340704Sjkim if (point == NULL) { 362340704Sjkim if (!EC_POINT_copy(s, group->generator)) 363340704Sjkim goto err; 364340704Sjkim } else { 365340704Sjkim if (!EC_POINT_copy(s, point)) 366340704Sjkim goto err; 367340704Sjkim } 368340704Sjkim 369340704Sjkim EC_POINT_BN_set_flags(s, BN_FLG_CONSTTIME); 370340704Sjkim 371340704Sjkim cardinality = BN_CTX_get(ctx); 372340704Sjkim lambda = BN_CTX_get(ctx); 373340704Sjkim k = BN_CTX_get(ctx); 374340704Sjkim if (k == NULL || !BN_mul(cardinality, &group->order, &group->cofactor, ctx)) 375340704Sjkim goto err; 376340704Sjkim 377340704Sjkim /* 378340704Sjkim * Group cardinalities are often on a word boundary. 379340704Sjkim * So when we pad the scalar, some timing diff might 380340704Sjkim * pop if it needs to be expanded due to carries. 381340704Sjkim * So expand ahead of time. 382340704Sjkim */ 383340704Sjkim cardinality_bits = BN_num_bits(cardinality); 384340704Sjkim group_top = cardinality->top; 385340704Sjkim if ((bn_wexpand(k, group_top + 2) == NULL) 386340704Sjkim || (bn_wexpand(lambda, group_top + 2) == NULL)) 387340704Sjkim goto err; 388340704Sjkim 389340704Sjkim if (!BN_copy(k, scalar)) 390340704Sjkim goto err; 391340704Sjkim 392340704Sjkim BN_set_flags(k, BN_FLG_CONSTTIME); 393340704Sjkim 394340704Sjkim if ((BN_num_bits(k) > cardinality_bits) || (BN_is_negative(k))) { 395340704Sjkim /*- 396340704Sjkim * this is an unusual input, and we don't guarantee 397340704Sjkim * constant-timeness 398340704Sjkim */ 399340704Sjkim if (!BN_nnmod(k, k, cardinality, ctx)) 400340704Sjkim goto err; 401340704Sjkim } 402340704Sjkim 403340704Sjkim if (!BN_add(lambda, k, cardinality)) 404340704Sjkim goto err; 405340704Sjkim BN_set_flags(lambda, BN_FLG_CONSTTIME); 406340704Sjkim if (!BN_add(k, lambda, cardinality)) 407340704Sjkim goto err; 408340704Sjkim /* 409340704Sjkim * lambda := scalar + cardinality 410340704Sjkim * k := scalar + 2*cardinality 411340704Sjkim */ 412340704Sjkim kbit = BN_is_bit_set(lambda, cardinality_bits); 413340704Sjkim BN_consttime_swap(kbit, k, lambda, group_top + 2); 414340704Sjkim 415340704Sjkim group_top = group->field.top; 416340704Sjkim if ((bn_wexpand(&s->X, group_top) == NULL) 417340704Sjkim || (bn_wexpand(&s->Y, group_top) == NULL) 418340704Sjkim || (bn_wexpand(&s->Z, group_top) == NULL) 419340704Sjkim || (bn_wexpand(&r->X, group_top) == NULL) 420340704Sjkim || (bn_wexpand(&r->Y, group_top) == NULL) 421340704Sjkim || (bn_wexpand(&r->Z, group_top) == NULL)) 422340704Sjkim goto err; 423340704Sjkim 424340704Sjkim /* top bit is a 1, in a fixed pos */ 425340704Sjkim if (!EC_POINT_copy(r, s)) 426340704Sjkim goto err; 427340704Sjkim 428340704Sjkim EC_POINT_BN_set_flags(r, BN_FLG_CONSTTIME); 429340704Sjkim 430340704Sjkim if (!EC_POINT_dbl(group, s, s, ctx)) 431340704Sjkim goto err; 432340704Sjkim 433340704Sjkim pbit = 0; 434340704Sjkim 435340704Sjkim#define EC_POINT_CSWAP(c, a, b, w, t) do { \ 436340704Sjkim BN_consttime_swap(c, &(a)->X, &(b)->X, w); \ 437340704Sjkim BN_consttime_swap(c, &(a)->Y, &(b)->Y, w); \ 438340704Sjkim BN_consttime_swap(c, &(a)->Z, &(b)->Z, w); \ 439340704Sjkim t = ((a)->Z_is_one ^ (b)->Z_is_one) & (c); \ 440340704Sjkim (a)->Z_is_one ^= (t); \ 441340704Sjkim (b)->Z_is_one ^= (t); \ 442340704Sjkim} while(0) 443340704Sjkim 444340704Sjkim /*- 445340704Sjkim * The ladder step, with branches, is 446340704Sjkim * 447340704Sjkim * k[i] == 0: S = add(R, S), R = dbl(R) 448340704Sjkim * k[i] == 1: R = add(S, R), S = dbl(S) 449340704Sjkim * 450340704Sjkim * Swapping R, S conditionally on k[i] leaves you with state 451340704Sjkim * 452340704Sjkim * k[i] == 0: T, U = R, S 453340704Sjkim * k[i] == 1: T, U = S, R 454340704Sjkim * 455340704Sjkim * Then perform the ECC ops. 456340704Sjkim * 457340704Sjkim * U = add(T, U) 458340704Sjkim * T = dbl(T) 459340704Sjkim * 460340704Sjkim * Which leaves you with state 461340704Sjkim * 462340704Sjkim * k[i] == 0: U = add(R, S), T = dbl(R) 463340704Sjkim * k[i] == 1: U = add(S, R), T = dbl(S) 464340704Sjkim * 465340704Sjkim * Swapping T, U conditionally on k[i] leaves you with state 466340704Sjkim * 467340704Sjkim * k[i] == 0: R, S = T, U 468340704Sjkim * k[i] == 1: R, S = U, T 469340704Sjkim * 470340704Sjkim * Which leaves you with state 471340704Sjkim * 472340704Sjkim * k[i] == 0: S = add(R, S), R = dbl(R) 473340704Sjkim * k[i] == 1: R = add(S, R), S = dbl(S) 474340704Sjkim * 475340704Sjkim * So we get the same logic, but instead of a branch it's a 476340704Sjkim * conditional swap, followed by ECC ops, then another conditional swap. 477340704Sjkim * 478340704Sjkim * Optimization: The end of iteration i and start of i-1 looks like 479340704Sjkim * 480340704Sjkim * ... 481340704Sjkim * CSWAP(k[i], R, S) 482340704Sjkim * ECC 483340704Sjkim * CSWAP(k[i], R, S) 484340704Sjkim * (next iteration) 485340704Sjkim * CSWAP(k[i-1], R, S) 486340704Sjkim * ECC 487340704Sjkim * CSWAP(k[i-1], R, S) 488340704Sjkim * ... 489340704Sjkim * 490340704Sjkim * So instead of two contiguous swaps, you can merge the condition 491340704Sjkim * bits and do a single swap. 492340704Sjkim * 493340704Sjkim * k[i] k[i-1] Outcome 494340704Sjkim * 0 0 No Swap 495340704Sjkim * 0 1 Swap 496340704Sjkim * 1 0 Swap 497340704Sjkim * 1 1 No Swap 498340704Sjkim * 499340704Sjkim * This is XOR. pbit tracks the previous bit of k. 500340704Sjkim */ 501340704Sjkim 502340704Sjkim for (i = cardinality_bits - 1; i >= 0; i--) { 503340704Sjkim kbit = BN_is_bit_set(k, i) ^ pbit; 504340704Sjkim EC_POINT_CSWAP(kbit, r, s, group_top, Z_is_one); 505340704Sjkim if (!EC_POINT_add(group, s, r, s, ctx)) 506340704Sjkim goto err; 507340704Sjkim if (!EC_POINT_dbl(group, r, r, ctx)) 508340704Sjkim goto err; 509340704Sjkim /* 510340704Sjkim * pbit logic merges this cswap with that of the 511340704Sjkim * next iteration 512340704Sjkim */ 513340704Sjkim pbit ^= kbit; 514340704Sjkim } 515340704Sjkim /* one final cswap to move the right value into r */ 516340704Sjkim EC_POINT_CSWAP(pbit, r, s, group_top, Z_is_one); 517340704Sjkim#undef EC_POINT_CSWAP 518340704Sjkim 519340704Sjkim ret = 1; 520340704Sjkim 521340704Sjkim err: 522348343Sjkim EC_POINT_clear_free(s); 523340704Sjkim BN_CTX_end(ctx); 524340704Sjkim BN_CTX_free(new_ctx); 525340704Sjkim 526340704Sjkim return ret; 527340704Sjkim} 528340704Sjkim 529340704Sjkim#undef EC_POINT_BN_set_flags 530340704Sjkim 531280297Sjkim/* 532280297Sjkim * TODO: table should be optimised for the wNAF-based implementation, 533280297Sjkim * sometimes smaller windows will give better performance (thus the 534280297Sjkim * boundaries should be increased) 535109998Smarkm */ 536109998Smarkm#define EC_window_bits_for_scalar_size(b) \ 537280297Sjkim ((size_t) \ 538280297Sjkim ((b) >= 2000 ? 6 : \ 539280297Sjkim (b) >= 800 ? 5 : \ 540280297Sjkim (b) >= 300 ? 4 : \ 541280297Sjkim (b) >= 70 ? 3 : \ 542280297Sjkim (b) >= 20 ? 2 : \ 543280297Sjkim 1)) 544109998Smarkm 545280297Sjkim/*- 546280297Sjkim * Compute 547109998Smarkm * \sum scalars[i]*points[i], 548109998Smarkm * also including 549109998Smarkm * scalar*generator 550109998Smarkm * in the addition if scalar != NULL 551109998Smarkm */ 552160814Ssimonint ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 553280297Sjkim size_t num, const EC_POINT *points[], const BIGNUM *scalars[], 554280297Sjkim BN_CTX *ctx) 555280297Sjkim{ 556280297Sjkim BN_CTX *new_ctx = NULL; 557280297Sjkim const EC_POINT *generator = NULL; 558280297Sjkim EC_POINT *tmp = NULL; 559280297Sjkim size_t totalnum; 560280297Sjkim size_t blocksize = 0, numblocks = 0; /* for wNAF splitting */ 561280297Sjkim size_t pre_points_per_block = 0; 562280297Sjkim size_t i, j; 563280297Sjkim int k; 564280297Sjkim int r_is_inverted = 0; 565280297Sjkim int r_is_at_infinity = 1; 566280297Sjkim size_t *wsize = NULL; /* individual window sizes */ 567280297Sjkim signed char **wNAF = NULL; /* individual wNAFs */ 568280297Sjkim size_t *wNAF_len = NULL; 569280297Sjkim size_t max_len = 0; 570280297Sjkim size_t num_val; 571280297Sjkim EC_POINT **val = NULL; /* precomputation */ 572280297Sjkim EC_POINT **v; 573280297Sjkim EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' or 574280297Sjkim * 'pre_comp->points' */ 575280297Sjkim const EC_PRE_COMP *pre_comp = NULL; 576280297Sjkim int num_scalar = 0; /* flag: will be set to 1 if 'scalar' must be 577280297Sjkim * treated like other scalars, i.e. 578280297Sjkim * precomputation is not available */ 579280297Sjkim int ret = 0; 580111147Snectar 581280297Sjkim if (group->meth != r->meth) { 582280297Sjkim ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); 583280297Sjkim return 0; 584280297Sjkim } 585111147Snectar 586280297Sjkim if ((scalar == NULL) && (num == 0)) { 587280297Sjkim return EC_POINT_set_to_infinity(group, r); 588280297Sjkim } 589160814Ssimon 590340704Sjkim if (!BN_is_zero(&group->order) && !BN_is_zero(&group->cofactor)) { 591340704Sjkim /*- 592340704Sjkim * Handle the common cases where the scalar is secret, enforcing a constant 593340704Sjkim * time scalar multiplication algorithm. 594340704Sjkim */ 595340704Sjkim if ((scalar != NULL) && (num == 0)) { 596340704Sjkim /*- 597340704Sjkim * In this case we want to compute scalar * GeneratorPoint: this 598340704Sjkim * codepath is reached most prominently by (ephemeral) key generation 599340704Sjkim * of EC cryptosystems (i.e. ECDSA keygen and sign setup, ECDH 600340704Sjkim * keygen/first half), where the scalar is always secret. This is why 601340704Sjkim * we ignore if BN_FLG_CONSTTIME is actually set and we always call the 602340704Sjkim * constant time version. 603340704Sjkim */ 604340704Sjkim return ec_mul_consttime(group, r, scalar, NULL, ctx); 605340704Sjkim } 606340704Sjkim if ((scalar == NULL) && (num == 1)) { 607340704Sjkim /*- 608340704Sjkim * In this case we want to compute scalar * GenericPoint: this codepath 609340704Sjkim * is reached most prominently by the second half of ECDH, where the 610340704Sjkim * secret scalar is multiplied by the peer's public point. To protect 611340704Sjkim * the secret scalar, we ignore if BN_FLG_CONSTTIME is actually set and 612340704Sjkim * we always call the constant time version. 613340704Sjkim */ 614340704Sjkim return ec_mul_consttime(group, r, scalars[0], points[0], ctx); 615340704Sjkim } 616340704Sjkim } 617340704Sjkim 618280297Sjkim for (i = 0; i < num; i++) { 619280297Sjkim if (group->meth != points[i]->meth) { 620280297Sjkim ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS); 621280297Sjkim return 0; 622280297Sjkim } 623280297Sjkim } 624160814Ssimon 625280297Sjkim if (ctx == NULL) { 626280297Sjkim ctx = new_ctx = BN_CTX_new(); 627280297Sjkim if (ctx == NULL) 628280297Sjkim goto err; 629280297Sjkim } 630109998Smarkm 631280297Sjkim if (scalar != NULL) { 632280297Sjkim generator = EC_GROUP_get0_generator(group); 633280297Sjkim if (generator == NULL) { 634280297Sjkim ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR); 635280297Sjkim goto err; 636280297Sjkim } 637109998Smarkm 638280297Sjkim /* look if we can use precomputed multiples of generator */ 639160814Ssimon 640280297Sjkim pre_comp = 641280297Sjkim EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, 642280297Sjkim ec_pre_comp_free, ec_pre_comp_clear_free); 643160814Ssimon 644280297Sjkim if (pre_comp && pre_comp->numblocks 645280297Sjkim && (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) == 646280297Sjkim 0)) { 647280297Sjkim blocksize = pre_comp->blocksize; 648160814Ssimon 649280297Sjkim /* 650280297Sjkim * determine maximum number of blocks that wNAF splitting may 651280297Sjkim * yield (NB: maximum wNAF length is bit length plus one) 652280297Sjkim */ 653280297Sjkim numblocks = (BN_num_bits(scalar) / blocksize) + 1; 654160814Ssimon 655280297Sjkim /* 656280297Sjkim * we cannot use more blocks than we have precomputation for 657280297Sjkim */ 658280297Sjkim if (numblocks > pre_comp->numblocks) 659280297Sjkim numblocks = pre_comp->numblocks; 660109998Smarkm 661280297Sjkim pre_points_per_block = (size_t)1 << (pre_comp->w - 1); 662276861Sjkim 663280297Sjkim /* check that pre_comp looks sane */ 664280297Sjkim if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block)) { 665280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 666280297Sjkim goto err; 667280297Sjkim } 668280297Sjkim } else { 669280297Sjkim /* can't use precomputation */ 670280297Sjkim pre_comp = NULL; 671280297Sjkim numblocks = 1; 672280297Sjkim num_scalar = 1; /* treat 'scalar' like 'num'-th element of 673280297Sjkim * 'scalars' */ 674280297Sjkim } 675280297Sjkim } 676276861Sjkim 677280297Sjkim totalnum = num + numblocks; 678160814Ssimon 679331638Sjkim wsize = OPENSSL_malloc(totalnum * sizeof(wsize[0])); 680331638Sjkim wNAF_len = OPENSSL_malloc(totalnum * sizeof(wNAF_len[0])); 681331638Sjkim /* include space for pivot */ 682331638Sjkim wNAF = OPENSSL_malloc((totalnum + 1) * sizeof(wNAF[0])); 683331638Sjkim val_sub = OPENSSL_malloc(totalnum * sizeof(val_sub[0])); 684160814Ssimon 685280297Sjkim /* Ensure wNAF is initialised in case we end up going to err */ 686280297Sjkim if (wNAF) 687280297Sjkim wNAF[0] = NULL; /* preliminary pivot */ 688109998Smarkm 689280297Sjkim if (!wsize || !wNAF_len || !wNAF || !val_sub) { 690280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 691280297Sjkim goto err; 692280297Sjkim } 693109998Smarkm 694280297Sjkim /* 695280297Sjkim * num_val will be the total number of temporarily precomputed points 696280297Sjkim */ 697280297Sjkim num_val = 0; 698160814Ssimon 699280297Sjkim for (i = 0; i < num + num_scalar; i++) { 700280297Sjkim size_t bits; 701160814Ssimon 702280297Sjkim bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar); 703280297Sjkim wsize[i] = EC_window_bits_for_scalar_size(bits); 704280297Sjkim num_val += (size_t)1 << (wsize[i] - 1); 705280297Sjkim wNAF[i + 1] = NULL; /* make sure we always have a pivot */ 706280297Sjkim wNAF[i] = 707280297Sjkim compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], 708280297Sjkim &wNAF_len[i]); 709280297Sjkim if (wNAF[i] == NULL) 710280297Sjkim goto err; 711280297Sjkim if (wNAF_len[i] > max_len) 712280297Sjkim max_len = wNAF_len[i]; 713280297Sjkim } 714160814Ssimon 715280297Sjkim if (numblocks) { 716280297Sjkim /* we go here iff scalar != NULL */ 717160814Ssimon 718280297Sjkim if (pre_comp == NULL) { 719280297Sjkim if (num_scalar != 1) { 720280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 721280297Sjkim goto err; 722280297Sjkim } 723280297Sjkim /* we have already generated a wNAF for 'scalar' */ 724280297Sjkim } else { 725280297Sjkim signed char *tmp_wNAF = NULL; 726280297Sjkim size_t tmp_len = 0; 727160814Ssimon 728280297Sjkim if (num_scalar != 0) { 729280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 730280297Sjkim goto err; 731280297Sjkim } 732160814Ssimon 733280297Sjkim /* 734280297Sjkim * use the window size for which we have precomputation 735280297Sjkim */ 736280297Sjkim wsize[num] = pre_comp->w; 737280297Sjkim tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len); 738280297Sjkim if (!tmp_wNAF) 739280297Sjkim goto err; 740160814Ssimon 741280297Sjkim if (tmp_len <= max_len) { 742280297Sjkim /* 743280297Sjkim * One of the other wNAFs is at least as long as the wNAF 744280297Sjkim * belonging to the generator, so wNAF splitting will not buy 745280297Sjkim * us anything. 746280297Sjkim */ 747109998Smarkm 748280297Sjkim numblocks = 1; 749280297Sjkim totalnum = num + 1; /* don't use wNAF splitting */ 750280297Sjkim wNAF[num] = tmp_wNAF; 751280297Sjkim wNAF[num + 1] = NULL; 752280297Sjkim wNAF_len[num] = tmp_len; 753280297Sjkim if (tmp_len > max_len) 754280297Sjkim max_len = tmp_len; 755280297Sjkim /* 756280297Sjkim * pre_comp->points starts with the points that we need here: 757280297Sjkim */ 758280297Sjkim val_sub[num] = pre_comp->points; 759280297Sjkim } else { 760280297Sjkim /* 761280297Sjkim * don't include tmp_wNAF directly into wNAF array - use wNAF 762280297Sjkim * splitting and include the blocks 763280297Sjkim */ 764109998Smarkm 765280297Sjkim signed char *pp; 766280297Sjkim EC_POINT **tmp_points; 767109998Smarkm 768280297Sjkim if (tmp_len < numblocks * blocksize) { 769280297Sjkim /* 770280297Sjkim * possibly we can do with fewer blocks than estimated 771280297Sjkim */ 772280297Sjkim numblocks = (tmp_len + blocksize - 1) / blocksize; 773280297Sjkim if (numblocks > pre_comp->numblocks) { 774280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 775280297Sjkim goto err; 776280297Sjkim } 777280297Sjkim totalnum = num + numblocks; 778280297Sjkim } 779109998Smarkm 780280297Sjkim /* split wNAF in 'numblocks' parts */ 781280297Sjkim pp = tmp_wNAF; 782280297Sjkim tmp_points = pre_comp->points; 783109998Smarkm 784280297Sjkim for (i = num; i < totalnum; i++) { 785280297Sjkim if (i < totalnum - 1) { 786280297Sjkim wNAF_len[i] = blocksize; 787280297Sjkim if (tmp_len < blocksize) { 788280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 789280297Sjkim goto err; 790280297Sjkim } 791280297Sjkim tmp_len -= blocksize; 792280297Sjkim } else 793280297Sjkim /* 794280297Sjkim * last block gets whatever is left (this could be 795280297Sjkim * more or less than 'blocksize'!) 796280297Sjkim */ 797280297Sjkim wNAF_len[i] = tmp_len; 798280297Sjkim 799280297Sjkim wNAF[i + 1] = NULL; 800280297Sjkim wNAF[i] = OPENSSL_malloc(wNAF_len[i]); 801280297Sjkim if (wNAF[i] == NULL) { 802280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 803280297Sjkim OPENSSL_free(tmp_wNAF); 804280297Sjkim goto err; 805280297Sjkim } 806280297Sjkim memcpy(wNAF[i], pp, wNAF_len[i]); 807280297Sjkim if (wNAF_len[i] > max_len) 808280297Sjkim max_len = wNAF_len[i]; 809280297Sjkim 810280297Sjkim if (*tmp_points == NULL) { 811280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 812280297Sjkim OPENSSL_free(tmp_wNAF); 813280297Sjkim goto err; 814280297Sjkim } 815280297Sjkim val_sub[i] = tmp_points; 816280297Sjkim tmp_points += pre_points_per_block; 817280297Sjkim pp += blocksize; 818280297Sjkim } 819280297Sjkim OPENSSL_free(tmp_wNAF); 820280297Sjkim } 821280297Sjkim } 822280297Sjkim } 823280297Sjkim 824280297Sjkim /* 825280297Sjkim * All points we precompute now go into a single array 'val'. 826280297Sjkim * 'val_sub[i]' is a pointer to the subarray for the i-th point, or to a 827280297Sjkim * subarray of 'pre_comp->points' if we already have precomputation. 828280297Sjkim */ 829331638Sjkim val = OPENSSL_malloc((num_val + 1) * sizeof(val[0])); 830280297Sjkim if (val == NULL) { 831280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); 832280297Sjkim goto err; 833280297Sjkim } 834280297Sjkim val[num_val] = NULL; /* pivot element */ 835280297Sjkim 836280297Sjkim /* allocate points for precomputation */ 837280297Sjkim v = val; 838280297Sjkim for (i = 0; i < num + num_scalar; i++) { 839280297Sjkim val_sub[i] = v; 840280297Sjkim for (j = 0; j < ((size_t)1 << (wsize[i] - 1)); j++) { 841280297Sjkim *v = EC_POINT_new(group); 842280297Sjkim if (*v == NULL) 843280297Sjkim goto err; 844280297Sjkim v++; 845280297Sjkim } 846280297Sjkim } 847280297Sjkim if (!(v == val + num_val)) { 848280297Sjkim ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); 849280297Sjkim goto err; 850280297Sjkim } 851280297Sjkim 852280297Sjkim if (!(tmp = EC_POINT_new(group))) 853280297Sjkim goto err; 854280297Sjkim 855280297Sjkim /*- 856280297Sjkim * prepare precomputed values: 857280297Sjkim * val_sub[i][0] := points[i] 858280297Sjkim * val_sub[i][1] := 3 * points[i] 859280297Sjkim * val_sub[i][2] := 5 * points[i] 860280297Sjkim * ... 861280297Sjkim */ 862280297Sjkim for (i = 0; i < num + num_scalar; i++) { 863280297Sjkim if (i < num) { 864280297Sjkim if (!EC_POINT_copy(val_sub[i][0], points[i])) 865280297Sjkim goto err; 866280297Sjkim } else { 867280297Sjkim if (!EC_POINT_copy(val_sub[i][0], generator)) 868280297Sjkim goto err; 869280297Sjkim } 870280297Sjkim 871280297Sjkim if (wsize[i] > 1) { 872280297Sjkim if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) 873280297Sjkim goto err; 874280297Sjkim for (j = 1; j < ((size_t)1 << (wsize[i] - 1)); j++) { 875280297Sjkim if (!EC_POINT_add 876280297Sjkim (group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) 877280297Sjkim goto err; 878280297Sjkim } 879280297Sjkim } 880280297Sjkim } 881280297Sjkim 882280297Sjkim#if 1 /* optional; EC_window_bits_for_scalar_size 883280297Sjkim * assumes we do this step */ 884280297Sjkim if (!EC_POINTs_make_affine(group, num_val, val, ctx)) 885280297Sjkim goto err; 886109998Smarkm#endif 887109998Smarkm 888280297Sjkim r_is_at_infinity = 1; 889109998Smarkm 890280297Sjkim for (k = max_len - 1; k >= 0; k--) { 891280297Sjkim if (!r_is_at_infinity) { 892280297Sjkim if (!EC_POINT_dbl(group, r, r, ctx)) 893280297Sjkim goto err; 894280297Sjkim } 895109998Smarkm 896280297Sjkim for (i = 0; i < totalnum; i++) { 897280297Sjkim if (wNAF_len[i] > (size_t)k) { 898280297Sjkim int digit = wNAF[i][k]; 899280297Sjkim int is_neg; 900109998Smarkm 901280297Sjkim if (digit) { 902280297Sjkim is_neg = digit < 0; 903109998Smarkm 904280297Sjkim if (is_neg) 905280297Sjkim digit = -digit; 906109998Smarkm 907280297Sjkim if (is_neg != r_is_inverted) { 908280297Sjkim if (!r_is_at_infinity) { 909280297Sjkim if (!EC_POINT_invert(group, r, ctx)) 910280297Sjkim goto err; 911280297Sjkim } 912280297Sjkim r_is_inverted = !r_is_inverted; 913280297Sjkim } 914109998Smarkm 915280297Sjkim /* digit > 0 */ 916109998Smarkm 917280297Sjkim if (r_is_at_infinity) { 918280297Sjkim if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) 919280297Sjkim goto err; 920280297Sjkim r_is_at_infinity = 0; 921280297Sjkim } else { 922280297Sjkim if (!EC_POINT_add 923280297Sjkim (group, r, r, val_sub[i][digit >> 1], ctx)) 924280297Sjkim goto err; 925280297Sjkim } 926280297Sjkim } 927280297Sjkim } 928280297Sjkim } 929280297Sjkim } 930109998Smarkm 931280297Sjkim if (r_is_at_infinity) { 932280297Sjkim if (!EC_POINT_set_to_infinity(group, r)) 933280297Sjkim goto err; 934280297Sjkim } else { 935280297Sjkim if (r_is_inverted) 936280297Sjkim if (!EC_POINT_invert(group, r, ctx)) 937280297Sjkim goto err; 938280297Sjkim } 939280297Sjkim 940280297Sjkim ret = 1; 941280297Sjkim 942109998Smarkm err: 943280297Sjkim if (new_ctx != NULL) 944280297Sjkim BN_CTX_free(new_ctx); 945280297Sjkim if (tmp != NULL) 946280297Sjkim EC_POINT_free(tmp); 947280297Sjkim if (wsize != NULL) 948280297Sjkim OPENSSL_free(wsize); 949280297Sjkim if (wNAF_len != NULL) 950280297Sjkim OPENSSL_free(wNAF_len); 951280297Sjkim if (wNAF != NULL) { 952280297Sjkim signed char **w; 953109998Smarkm 954280297Sjkim for (w = wNAF; *w != NULL; w++) 955280297Sjkim OPENSSL_free(*w); 956109998Smarkm 957280297Sjkim OPENSSL_free(wNAF); 958280297Sjkim } 959280297Sjkim if (val != NULL) { 960280297Sjkim for (v = val; *v != NULL; v++) 961280297Sjkim EC_POINT_clear_free(*v); 962109998Smarkm 963280297Sjkim OPENSSL_free(val); 964280297Sjkim } 965280297Sjkim if (val_sub != NULL) { 966280297Sjkim OPENSSL_free(val_sub); 967280297Sjkim } 968280297Sjkim return ret; 969280297Sjkim} 970280297Sjkim 971280297Sjkim/*- 972280297Sjkim * ec_wNAF_precompute_mult() 973160814Ssimon * creates an EC_PRE_COMP object with preprecomputed multiples of the generator 974160814Ssimon * for use with wNAF splitting as implemented in ec_wNAF_mul(). 975280297Sjkim * 976160814Ssimon * 'pre_comp->points' is an array of multiples of the generator 977160814Ssimon * of the following form: 978160814Ssimon * points[0] = generator; 979160814Ssimon * points[1] = 3 * generator; 980160814Ssimon * ... 981160814Ssimon * points[2^(w-1)-1] = (2^(w-1)-1) * generator; 982160814Ssimon * points[2^(w-1)] = 2^blocksize * generator; 983160814Ssimon * points[2^(w-1)+1] = 3 * 2^blocksize * generator; 984160814Ssimon * ... 985160814Ssimon * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) * 2^(blocksize*(numblocks-2)) * generator 986160814Ssimon * points[2^(w-1)*(numblocks-1)] = 2^(blocksize*(numblocks-1)) * generator 987160814Ssimon * ... 988160814Ssimon * points[2^(w-1)*numblocks-1] = (2^(w-1)) * 2^(blocksize*(numblocks-1)) * generator 989160814Ssimon * points[2^(w-1)*numblocks] = NULL 990160814Ssimon */ 991160814Ssimonint ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) 992280297Sjkim{ 993280297Sjkim const EC_POINT *generator; 994280297Sjkim EC_POINT *tmp_point = NULL, *base = NULL, **var; 995280297Sjkim BN_CTX *new_ctx = NULL; 996280297Sjkim BIGNUM *order; 997280297Sjkim size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num; 998280297Sjkim EC_POINT **points = NULL; 999280297Sjkim EC_PRE_COMP *pre_comp; 1000280297Sjkim int ret = 0; 1001109998Smarkm 1002280297Sjkim /* if there is an old EC_PRE_COMP object, throw it away */ 1003280297Sjkim EC_EX_DATA_free_data(&group->extra_data, ec_pre_comp_dup, 1004280297Sjkim ec_pre_comp_free, ec_pre_comp_clear_free); 1005160814Ssimon 1006280297Sjkim if ((pre_comp = ec_pre_comp_new(group)) == NULL) 1007280297Sjkim return 0; 1008160814Ssimon 1009280297Sjkim generator = EC_GROUP_get0_generator(group); 1010280297Sjkim if (generator == NULL) { 1011280297Sjkim ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR); 1012280297Sjkim goto err; 1013280297Sjkim } 1014109998Smarkm 1015280297Sjkim if (ctx == NULL) { 1016280297Sjkim ctx = new_ctx = BN_CTX_new(); 1017280297Sjkim if (ctx == NULL) 1018280297Sjkim goto err; 1019280297Sjkim } 1020109998Smarkm 1021280297Sjkim BN_CTX_start(ctx); 1022280297Sjkim order = BN_CTX_get(ctx); 1023280297Sjkim if (order == NULL) 1024280297Sjkim goto err; 1025109998Smarkm 1026280297Sjkim if (!EC_GROUP_get_order(group, order, ctx)) 1027280297Sjkim goto err; 1028280297Sjkim if (BN_is_zero(order)) { 1029280297Sjkim ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER); 1030280297Sjkim goto err; 1031280297Sjkim } 1032160814Ssimon 1033280297Sjkim bits = BN_num_bits(order); 1034280297Sjkim /* 1035280297Sjkim * The following parameters mean we precompute (approximately) one point 1036280297Sjkim * per bit. TBD: The combination 8, 4 is perfect for 160 bits; for other 1037280297Sjkim * bit lengths, other parameter combinations might provide better 1038280297Sjkim * efficiency. 1039280297Sjkim */ 1040280297Sjkim blocksize = 8; 1041280297Sjkim w = 4; 1042280297Sjkim if (EC_window_bits_for_scalar_size(bits) > w) { 1043280297Sjkim /* let's not make the window too small ... */ 1044280297Sjkim w = EC_window_bits_for_scalar_size(bits); 1045280297Sjkim } 1046160814Ssimon 1047280297Sjkim numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks 1048280297Sjkim * to use for wNAF 1049280297Sjkim * splitting */ 1050160814Ssimon 1051280297Sjkim pre_points_per_block = (size_t)1 << (w - 1); 1052280297Sjkim num = pre_points_per_block * numblocks; /* number of points to compute 1053280297Sjkim * and store */ 1054160814Ssimon 1055280297Sjkim points = OPENSSL_malloc(sizeof(EC_POINT *) * (num + 1)); 1056280297Sjkim if (!points) { 1057280297Sjkim ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 1058280297Sjkim goto err; 1059280297Sjkim } 1060160814Ssimon 1061280297Sjkim var = points; 1062280297Sjkim var[num] = NULL; /* pivot */ 1063280297Sjkim for (i = 0; i < num; i++) { 1064280297Sjkim if ((var[i] = EC_POINT_new(group)) == NULL) { 1065280297Sjkim ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 1066280297Sjkim goto err; 1067280297Sjkim } 1068280297Sjkim } 1069160814Ssimon 1070280297Sjkim if (!(tmp_point = EC_POINT_new(group)) || !(base = EC_POINT_new(group))) { 1071280297Sjkim ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); 1072280297Sjkim goto err; 1073280297Sjkim } 1074160814Ssimon 1075280297Sjkim if (!EC_POINT_copy(base, generator)) 1076280297Sjkim goto err; 1077160814Ssimon 1078280297Sjkim /* do the precomputation */ 1079280297Sjkim for (i = 0; i < numblocks; i++) { 1080280297Sjkim size_t j; 1081160814Ssimon 1082280297Sjkim if (!EC_POINT_dbl(group, tmp_point, base, ctx)) 1083280297Sjkim goto err; 1084160814Ssimon 1085280297Sjkim if (!EC_POINT_copy(*var++, base)) 1086280297Sjkim goto err; 1087160814Ssimon 1088280297Sjkim for (j = 1; j < pre_points_per_block; j++, var++) { 1089280297Sjkim /* 1090280297Sjkim * calculate odd multiples of the current base point 1091280297Sjkim */ 1092280297Sjkim if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx)) 1093280297Sjkim goto err; 1094280297Sjkim } 1095160814Ssimon 1096280297Sjkim if (i < numblocks - 1) { 1097280297Sjkim /* 1098280297Sjkim * get the next base (multiply current one by 2^blocksize) 1099280297Sjkim */ 1100280297Sjkim size_t k; 1101280297Sjkim 1102280297Sjkim if (blocksize <= 2) { 1103280297Sjkim ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_INTERNAL_ERROR); 1104280297Sjkim goto err; 1105280297Sjkim } 1106280297Sjkim 1107280297Sjkim if (!EC_POINT_dbl(group, base, tmp_point, ctx)) 1108280297Sjkim goto err; 1109280297Sjkim for (k = 2; k < blocksize; k++) { 1110280297Sjkim if (!EC_POINT_dbl(group, base, base, ctx)) 1111280297Sjkim goto err; 1112280297Sjkim } 1113280297Sjkim } 1114280297Sjkim } 1115280297Sjkim 1116280297Sjkim if (!EC_POINTs_make_affine(group, num, points, ctx)) 1117280297Sjkim goto err; 1118280297Sjkim 1119280297Sjkim pre_comp->group = group; 1120280297Sjkim pre_comp->blocksize = blocksize; 1121280297Sjkim pre_comp->numblocks = numblocks; 1122280297Sjkim pre_comp->w = w; 1123280297Sjkim pre_comp->points = points; 1124280297Sjkim points = NULL; 1125280297Sjkim pre_comp->num = num; 1126280297Sjkim 1127280297Sjkim if (!EC_EX_DATA_set_data(&group->extra_data, pre_comp, 1128280297Sjkim ec_pre_comp_dup, ec_pre_comp_free, 1129280297Sjkim ec_pre_comp_clear_free)) 1130280297Sjkim goto err; 1131280297Sjkim pre_comp = NULL; 1132280297Sjkim 1133280297Sjkim ret = 1; 1134109998Smarkm err: 1135280297Sjkim if (ctx != NULL) 1136280297Sjkim BN_CTX_end(ctx); 1137280297Sjkim if (new_ctx != NULL) 1138280297Sjkim BN_CTX_free(new_ctx); 1139280297Sjkim if (pre_comp) 1140280297Sjkim ec_pre_comp_free(pre_comp); 1141280297Sjkim if (points) { 1142280297Sjkim EC_POINT **p; 1143160814Ssimon 1144280297Sjkim for (p = points; *p != NULL; p++) 1145280297Sjkim EC_POINT_free(*p); 1146280297Sjkim OPENSSL_free(points); 1147280297Sjkim } 1148280297Sjkim if (tmp_point) 1149280297Sjkim EC_POINT_free(tmp_point); 1150280297Sjkim if (base) 1151280297Sjkim EC_POINT_free(base); 1152280297Sjkim return ret; 1153280297Sjkim} 1154160814Ssimon 1155160814Ssimonint ec_wNAF_have_precompute_mult(const EC_GROUP *group) 1156280297Sjkim{ 1157280297Sjkim if (EC_EX_DATA_get_data 1158280297Sjkim (group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, 1159280297Sjkim ec_pre_comp_clear_free) != NULL) 1160280297Sjkim return 1; 1161280297Sjkim else 1162280297Sjkim return 0; 1163280297Sjkim} 1164