crypto/ec/ec_mult.c

   1 /*
   2  * Copyright 2001-2019 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 /* ====================================================================
  11  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  12  * Portions of this software developed by SUN MICROSYSTEMS, INC.,
  13  * and contributed to the OpenSSL project.
  14  */
  15
  16 #include <string.h>
  17 #include <openssl/err.h>
  18
  19 #include "internal/cryptlib.h"
  20 #include "internal/bn_int.h"
  21 #include "ec_lcl.h"
  22
  23 /*
  24  * This file implements the wNAF-based interleaving multi-exponentiation method
  25  * Formerly at:
  26  *   http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp
  27  * You might now find it here:
  28  *   http://link.springer.com/chapter/10.1007%2F3-540-45537-X_13
  29  *   http://www.bmoeller.de/pdf/TI-01-08.multiexp.pdf
  30  * For multiplication with precomputation, we use wNAF splitting, formerly at:
  31  *   http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp
  32  */
  33
  34 /* structure for precomputed multiples of the generator */
  35 struct ec_pre_comp_st {
  36     const EC_GROUP *group;      /* parent EC_GROUP object */
  37     size_t blocksize;           /* block size for wNAF splitting */
  38     size_t numblocks;           /* max. number of blocks for which we have
  39                                  * precomputation */
  40     size_t w;                   /* window size */
  41     EC_POINT **points;          /* array with pre-calculated multiples of
  42                                  * generator: 'num' pointers to EC_POINT
  43                                  * objects followed by a NULL */
  44     size_t num;                 /* numblocks * 2^(w-1) */
  45     int references;
  46     CRYPTO_RWLOCK *lock;
  47 };
  48
  49 static EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group)
  50 {
  51     EC_PRE_COMP *ret = NULL;
  52
  53     if (!group)
  54         return NULL;
  55
  56     ret = OPENSSL_zalloc(sizeof(*ret));
  57     if (ret == NULL) {
  58         ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE);
  59         return ret;
  60     }
  61
  62     ret->group = group;
  63     ret->blocksize = 8;         /* default */
  64     ret->w = 4;                 /* default */
  65     ret->references = 1;
  66
  67     ret->lock = CRYPTO_THREAD_lock_new();
  68     if (ret->lock == NULL) {
  69         ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE);
  70         OPENSSL_free(ret);
  71         return NULL;
  72     }
  73     return ret;
  74 }
  75
  76 EC_PRE_COMP *EC_ec_pre_comp_dup(EC_PRE_COMP *pre)
  77 {
  78     int i;
  79     if (pre != NULL)
  80         CRYPTO_atomic_add(&pre->references, 1, &i, pre->lock);
  81     return pre;
  82 }
  83
  84 void EC_ec_pre_comp_free(EC_PRE_COMP *pre)
  85 {
  86     int i;
  87
  88     if (pre == NULL)
  89         return;
  90
  91     CRYPTO_atomic_add(&pre->references, -1, &i, pre->lock);
  92     REF_PRINT_COUNT("EC_ec", pre);
  93     if (i > 0)
  94         return;
  95     REF_ASSERT_ISNT(i < 0);
  96
  97     if (pre->points != NULL) {
  98         EC_POINT **pts;
  99
 100         for (pts = pre->points; *pts != NULL; pts++)
 101             EC_POINT_free(*pts);
 102         OPENSSL_free(pre->points);
 103     }
 104     CRYPTO_THREAD_lock_free(pre->lock);
 105     OPENSSL_free(pre);
 106 }
 107
 108 #define EC_POINT_BN_set_flags(P, flags) do { \
 109     BN_set_flags((P)->X, (flags)); \
 110     BN_set_flags((P)->Y, (flags)); \
 111     BN_set_flags((P)->Z, (flags)); \
 112 } while(0)
 113
 114 /*-
 115  * This functions computes (in constant time) a point multiplication over the
 116  * EC group.
 117  *
 118  * At a high level, it is Montgomery ladder with conditional swaps.
 119  *
 120  * It performs either a fixed scalar point multiplication
 121  *          (scalar * generator)
 122  * when point is NULL, or a generic scalar point multiplication
 123  *          (scalar * point)
 124  * when point is not NULL.
 125  *
 126  * scalar should be in the range [0,n) otherwise all constant time bets are off.
 127  *
 128  * NB: This says nothing about EC_POINT_add and EC_POINT_dbl,
 129  * which of course are not constant time themselves.
 130  *
 131  * The product is stored in r.
 132  *
 133  * Returns 1 on success, 0 otherwise.
 134  */
 135 static int ec_mul_consttime(const EC_GROUP *group, EC_POINT *r,
 136                             const BIGNUM *scalar, const EC_POINT *point,
 137                             BN_CTX *ctx)
 138 {
 139     int i, cardinality_bits, group_top, kbit, pbit, Z_is_one;
 140     EC_POINT *s = NULL;
 141     BIGNUM *k = NULL;
 142     BIGNUM *lambda = NULL;
 143     BIGNUM *cardinality = NULL;
 144     BN_CTX *new_ctx = NULL;
 145     int ret = 0;
 146
 147     if (ctx == NULL && (ctx = new_ctx = BN_CTX_secure_new()) == NULL)
 148         return 0;
 149
 150     BN_CTX_start(ctx);
 151
 152     s = EC_POINT_new(group);
 153     if (s == NULL)
 154         goto err;
 155
 156     if (point == NULL) {
 157         if (!EC_POINT_copy(s, group->generator))
 158             goto err;
 159     } else {
 160         if (!EC_POINT_copy(s, point))
 161             goto err;
 162     }
 163
 164     EC_POINT_BN_set_flags(s, BN_FLG_CONSTTIME);
 165
 166     cardinality = BN_CTX_get(ctx);
 167     lambda = BN_CTX_get(ctx);
 168     k = BN_CTX_get(ctx);
 169     if (k == NULL || !BN_mul(cardinality, group->order, group->cofactor, ctx))
 170         goto err;
 171
 172     /*
 173      * Group cardinalities are often on a word boundary.
 174      * So when we pad the scalar, some timing diff might
 175      * pop if it needs to be expanded due to carries.
 176      * So expand ahead of time.
 177      */
 178     cardinality_bits = BN_num_bits(cardinality);
 179     group_top = bn_get_top(cardinality);
 180     if ((bn_wexpand(k, group_top + 2) == NULL)
 181         || (bn_wexpand(lambda, group_top + 2) == NULL))
 182         goto err;
 183
 184     if (!BN_copy(k, scalar))
 185         goto err;
 186
 187     BN_set_flags(k, BN_FLG_CONSTTIME);
 188
 189     if ((BN_num_bits(k) > cardinality_bits) || (BN_is_negative(k))) {
 190         /*-
 191          * this is an unusual input, and we don't guarantee
 192          * constant-timeness
 193          */
 194         if (!BN_nnmod(k, k, cardinality, ctx))
 195             goto err;
 196     }
 197
 198     if (!BN_add(lambda, k, cardinality))
 199         goto err;
 200     BN_set_flags(lambda, BN_FLG_CONSTTIME);
 201     if (!BN_add(k, lambda, cardinality))
 202         goto err;
 203     /*
 204      * lambda := scalar + cardinality
 205      * k := scalar + 2*cardinality
 206      */
 207     kbit = BN_is_bit_set(lambda, cardinality_bits);
 208     BN_consttime_swap(kbit, k, lambda, group_top + 2);
 209
 210     group_top = bn_get_top(group->field);
 211     if ((bn_wexpand(s->X, group_top) == NULL)
 212         || (bn_wexpand(s->Y, group_top) == NULL)
 213         || (bn_wexpand(s->Z, group_top) == NULL)
 214         || (bn_wexpand(r->X, group_top) == NULL)
 215         || (bn_wexpand(r->Y, group_top) == NULL)
 216         || (bn_wexpand(r->Z, group_top) == NULL))
 217         goto err;
 218
 219     /*-
 220      * Apply coordinate blinding for EC_POINT.
 221      *
 222      * The underlying EC_METHOD can optionally implement this function:
 223      * ec_point_blind_coordinates() returns 0 in case of errors or 1 on
 224      * success or if coordinate blinding is not implemented for this
 225      * group.
 226      */
 227     if (!ec_point_blind_coordinates(group, s, ctx))
 228         goto err;
 229
 230     /* top bit is a 1, in a fixed pos */
 231     if (!EC_POINT_copy(r, s))
 232         goto err;
 233
 234     EC_POINT_BN_set_flags(r, BN_FLG_CONSTTIME);
 235
 236     if (!EC_POINT_dbl(group, s, s, ctx))
 237         goto err;
 238
 239     pbit = 0;
 240
 241 #define EC_POINT_CSWAP(c, a, b, w, t) do {         \
 242         BN_consttime_swap(c, (a)->X, (b)->X, w);   \
 243         BN_consttime_swap(c, (a)->Y, (b)->Y, w);   \
 244         BN_consttime_swap(c, (a)->Z, (b)->Z, w);   \
 245         t = ((a)->Z_is_one ^ (b)->Z_is_one) & (c); \
 246         (a)->Z_is_one ^= (t);                      \
 247         (b)->Z_is_one ^= (t);                      \
 248 } while(0)
 249
 250     /*-
 251      * The ladder step, with branches, is
 252      *
 253      * k[i] == 0: S = add(R, S), R = dbl(R)
 254      * k[i] == 1: R = add(S, R), S = dbl(S)
 255      *
 256      * Swapping R, S conditionally on k[i] leaves you with state
 257      *
 258      * k[i] == 0: T, U = R, S
 259      * k[i] == 1: T, U = S, R
 260      *
 261      * Then perform the ECC ops.
 262      *
 263      * U = add(T, U)
 264      * T = dbl(T)
 265      *
 266      * Which leaves you with state
 267      *
 268      * k[i] == 0: U = add(R, S), T = dbl(R)
 269      * k[i] == 1: U = add(S, R), T = dbl(S)
 270      *
 271      * Swapping T, U conditionally on k[i] leaves you with state
 272      *
 273      * k[i] == 0: R, S = T, U
 274      * k[i] == 1: R, S = U, T
 275      *
 276      * Which leaves you with state
 277      *
 278      * k[i] == 0: S = add(R, S), R = dbl(R)
 279      * k[i] == 1: R = add(S, R), S = dbl(S)
 280      *
 281      * So we get the same logic, but instead of a branch it's a
 282      * conditional swap, followed by ECC ops, then another conditional swap.
 283      *
 284      * Optimization: The end of iteration i and start of i-1 looks like
 285      *
 286      * ...
 287      * CSWAP(k[i], R, S)
 288      * ECC
 289      * CSWAP(k[i], R, S)
 290      * (next iteration)
 291      * CSWAP(k[i-1], R, S)
 292      * ECC
 293      * CSWAP(k[i-1], R, S)
 294      * ...
 295      *
 296      * So instead of two contiguous swaps, you can merge the condition
 297      * bits and do a single swap.
 298      *
 299      * k[i]   k[i-1]    Outcome
 300      * 0      0         No Swap
 301      * 0      1         Swap
 302      * 1      0         Swap
 303      * 1      1         No Swap
 304      *
 305      * This is XOR. pbit tracks the previous bit of k.
 306      */
 307
 308     for (i = cardinality_bits - 1; i >= 0; i--) {
 309         kbit = BN_is_bit_set(k, i) ^ pbit;
 310         EC_POINT_CSWAP(kbit, r, s, group_top, Z_is_one);
 311         if (!EC_POINT_add(group, s, r, s, ctx))
 312             goto err;
 313         if (!EC_POINT_dbl(group, r, r, ctx))
 314             goto err;
 315         /*
 316          * pbit logic merges this cswap with that of the
 317          * next iteration
 318          */
 319         pbit ^= kbit;
 320     }
 321     /* one final cswap to move the right value into r */
 322     EC_POINT_CSWAP(pbit, r, s, group_top, Z_is_one);
 323 #undef EC_POINT_CSWAP
 324
 325     ret = 1;
 326
 327  err:
 328     EC_POINT_clear_free(s);
 329     BN_CTX_end(ctx);
 330     BN_CTX_free(new_ctx);
 331
 332     return ret;
 333 }
 334
 335 #undef EC_POINT_BN_set_flags
 336
 337 /*
 338  * TODO: table should be optimised for the wNAF-based implementation,
 339  * sometimes smaller windows will give better performance (thus the
 340  * boundaries should be increased)
 341  */
 342 #define EC_window_bits_for_scalar_size(b) \
 343                 ((size_t) \
 344                  ((b) >= 2000 ? 6 : \
 345                   (b) >=  800 ? 5 : \
 346                   (b) >=  300 ? 4 : \
 347                   (b) >=   70 ? 3 : \
 348                   (b) >=   20 ? 2 : \
 349                   1))
 350
 351 /*-
 352  * Compute
 353  *      \sum scalars[i]*points[i],
 354  * also including
 355  *      scalar*generator
 356  * in the addition if scalar != NULL
 357  */
 358 int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 359                 size_t num, const EC_POINT *points[], const BIGNUM *scalars[],
 360                 BN_CTX *ctx)
 361 {
 362     BN_CTX *new_ctx = NULL;
 363     const EC_POINT *generator = NULL;
 364     EC_POINT *tmp = NULL;
 365     size_t totalnum;
 366     size_t blocksize = 0, numblocks = 0; /* for wNAF splitting */
 367     size_t pre_points_per_block = 0;
 368     size_t i, j;
 369     int k;
 370     int r_is_inverted = 0;
 371     int r_is_at_infinity = 1;
 372     size_t *wsize = NULL;       /* individual window sizes */
 373     signed char **wNAF = NULL;  /* individual wNAFs */
 374     size_t *wNAF_len = NULL;
 375     size_t max_len = 0;
 376     size_t num_val;
 377     EC_POINT **val = NULL;      /* precomputation */
 378     EC_POINT **v;
 379     EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' or
 380                                  * 'pre_comp->points' */
 381     const EC_PRE_COMP *pre_comp = NULL;
 382     int num_scalar = 0;         /* flag: will be set to 1 if 'scalar' must be
 383                                  * treated like other scalars, i.e.
 384                                  * precomputation is not available */
 385     int ret = 0;
 386
 387     if (!ec_point_is_compat(r, group)) {
 388         ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
 389         return 0;
 390     }
 391
 392     if ((scalar == NULL) && (num == 0)) {
 393         return EC_POINT_set_to_infinity(group, r);
 394     }
 395
 396     if (!BN_is_zero(group->order) && !BN_is_zero(group->cofactor)) {
 397         /*-
 398          * Handle the common cases where the scalar is secret, enforcing a constant
 399          * time scalar multiplication algorithm.
 400          */
 401         if ((scalar != NULL) && (num == 0)) {
 402             /*-
 403              * In this case we want to compute scalar * GeneratorPoint: this
 404              * codepath is reached most prominently by (ephemeral) key generation
 405              * of EC cryptosystems (i.e. ECDSA keygen and sign setup, ECDH
 406              * keygen/first half), where the scalar is always secret. This is why
 407              * we ignore if BN_FLG_CONSTTIME is actually set and we always call the
 408              * constant time version.
 409              */
 410             return ec_mul_consttime(group, r, scalar, NULL, ctx);
 411         }
 412         if ((scalar == NULL) && (num == 1)) {
 413             /*-
 414              * In this case we want to compute scalar * GenericPoint: this codepath
 415              * is reached most prominently by the second half of ECDH, where the
 416              * secret scalar is multiplied by the peer's public point. To protect
 417              * the secret scalar, we ignore if BN_FLG_CONSTTIME is actually set and
 418              * we always call the constant time version.
 419              */
 420             return ec_mul_consttime(group, r, scalars[0], points[0], ctx);
 421         }
 422     }
 423
 424     for (i = 0; i < num; i++) {
 425         if (!ec_point_is_compat(points[i], group)) {
 426             ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
 427             return 0;
 428         }
 429     }
 430
 431     if (ctx == NULL) {
 432         ctx = new_ctx = BN_CTX_new();
 433         if (ctx == NULL)
 434             goto err;
 435     }
 436
 437     if (scalar != NULL) {
 438         generator = EC_GROUP_get0_generator(group);
 439         if (generator == NULL) {
 440             ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR);
 441             goto err;
 442         }
 443
 444         /* look if we can use precomputed multiples of generator */
 445
 446         pre_comp = group->pre_comp.ec;
 447         if (pre_comp && pre_comp->numblocks
 448             && (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) ==
 449                 0)) {
 450             blocksize = pre_comp->blocksize;
 451
 452             /*
 453              * determine maximum number of blocks that wNAF splitting may
 454              * yield (NB: maximum wNAF length is bit length plus one)
 455              */
 456             numblocks = (BN_num_bits(scalar) / blocksize) + 1;
 457
 458             /*
 459              * we cannot use more blocks than we have precomputation for
 460              */
 461             if (numblocks > pre_comp->numblocks)
 462                 numblocks = pre_comp->numblocks;
 463
 464             pre_points_per_block = (size_t)1 << (pre_comp->w - 1);
 465
 466             /* check that pre_comp looks sane */
 467             if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block)) {
 468                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 469                 goto err;
 470             }
 471         } else {
 472             /* can't use precomputation */
 473             pre_comp = NULL;
 474             numblocks = 1;
 475             num_scalar = 1;     /* treat 'scalar' like 'num'-th element of
 476                                  * 'scalars' */
 477         }
 478     }
 479
 480     totalnum = num + numblocks;
 481
 482     wsize = OPENSSL_malloc(totalnum * sizeof(wsize[0]));
 483     wNAF_len = OPENSSL_malloc(totalnum * sizeof(wNAF_len[0]));
 484     /* include space for pivot */
 485     wNAF = OPENSSL_malloc((totalnum + 1) * sizeof(wNAF[0]));
 486     val_sub = OPENSSL_malloc(totalnum * sizeof(val_sub[0]));
 487
 488     /* Ensure wNAF is initialised in case we end up going to err */
 489     if (wNAF != NULL)
 490         wNAF[0] = NULL;         /* preliminary pivot */
 491
 492     if (wsize == NULL || wNAF_len == NULL || wNAF == NULL || val_sub == NULL) {
 493         ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE);
 494         goto err;
 495     }
 496
 497     /*
 498      * num_val will be the total number of temporarily precomputed points
 499      */
 500     num_val = 0;
 501
 502     for (i = 0; i < num + num_scalar; i++) {
 503         size_t bits;
 504
 505         bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar);
 506         wsize[i] = EC_window_bits_for_scalar_size(bits);
 507         num_val += (size_t)1 << (wsize[i] - 1);
 508         wNAF[i + 1] = NULL;     /* make sure we always have a pivot */
 509         wNAF[i] =
 510             bn_compute_wNAF((i < num ? scalars[i] : scalar), wsize[i],
 511                             &wNAF_len[i]);
 512         if (wNAF[i] == NULL)
 513             goto err;
 514         if (wNAF_len[i] > max_len)
 515             max_len = wNAF_len[i];
 516     }
 517
 518     if (numblocks) {
 519         /* we go here iff scalar != NULL */
 520
 521         if (pre_comp == NULL) {
 522             if (num_scalar != 1) {
 523                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 524                 goto err;
 525             }
 526             /* we have already generated a wNAF for 'scalar' */
 527         } else {
 528             signed char *tmp_wNAF = NULL;
 529             size_t tmp_len = 0;
 530
 531             if (num_scalar != 0) {
 532                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 533                 goto err;
 534             }
 535
 536             /*
 537              * use the window size for which we have precomputation
 538              */
 539             wsize[num] = pre_comp->w;
 540             tmp_wNAF = bn_compute_wNAF(scalar, wsize[num], &tmp_len);
 541             if (!tmp_wNAF)
 542                 goto err;
 543
 544             if (tmp_len <= max_len) {
 545                 /*
 546                  * One of the other wNAFs is at least as long as the wNAF
 547                  * belonging to the generator, so wNAF splitting will not buy
 548                  * us anything.
 549                  */
 550
 551                 numblocks = 1;
 552                 totalnum = num + 1; /* don't use wNAF splitting */
 553                 wNAF[num] = tmp_wNAF;
 554                 wNAF[num + 1] = NULL;
 555                 wNAF_len[num] = tmp_len;
 556                 /*
 557                  * pre_comp->points starts with the points that we need here:
 558                  */
 559                 val_sub[num] = pre_comp->points;
 560             } else {
 561                 /*
 562                  * don't include tmp_wNAF directly into wNAF array - use wNAF
 563                  * splitting and include the blocks
 564                  */
 565
 566                 signed char *pp;
 567                 EC_POINT **tmp_points;
 568
 569                 if (tmp_len < numblocks * blocksize) {
 570                     /*
 571                      * possibly we can do with fewer blocks than estimated
 572                      */
 573                     numblocks = (tmp_len + blocksize - 1) / blocksize;
 574                     if (numblocks > pre_comp->numblocks) {
 575                         ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 576                         OPENSSL_free(tmp_wNAF);
 577                         goto err;
 578                     }
 579                     totalnum = num + numblocks;
 580                 }
 581
 582                 /* split wNAF in 'numblocks' parts */
 583                 pp = tmp_wNAF;
 584                 tmp_points = pre_comp->points;
 585
 586                 for (i = num; i < totalnum; i++) {
 587                     if (i < totalnum - 1) {
 588                         wNAF_len[i] = blocksize;
 589                         if (tmp_len < blocksize) {
 590                             ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 591                             OPENSSL_free(tmp_wNAF);
 592                             goto err;
 593                         }
 594                         tmp_len -= blocksize;
 595                     } else
 596                         /*
 597                          * last block gets whatever is left (this could be
 598                          * more or less than 'blocksize'!)
 599                          */
 600                         wNAF_len[i] = tmp_len;
 601
 602                     wNAF[i + 1] = NULL;
 603                     wNAF[i] = OPENSSL_malloc(wNAF_len[i]);
 604                     if (wNAF[i] == NULL) {
 605                         ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE);
 606                         OPENSSL_free(tmp_wNAF);
 607                         goto err;
 608                     }
 609                     memcpy(wNAF[i], pp, wNAF_len[i]);
 610                     if (wNAF_len[i] > max_len)
 611                         max_len = wNAF_len[i];
 612
 613                     if (*tmp_points == NULL) {
 614                         ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 615                         OPENSSL_free(tmp_wNAF);
 616                         goto err;
 617                     }
 618                     val_sub[i] = tmp_points;
 619                     tmp_points += pre_points_per_block;
 620                     pp += blocksize;
 621                 }
 622                 OPENSSL_free(tmp_wNAF);
 623             }
 624         }
 625     }
 626
 627     /*
 628      * All points we precompute now go into a single array 'val'.
 629      * 'val_sub[i]' is a pointer to the subarray for the i-th point, or to a
 630      * subarray of 'pre_comp->points' if we already have precomputation.
 631      */
 632     val = OPENSSL_malloc((num_val + 1) * sizeof(val[0]));
 633     if (val == NULL) {
 634         ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE);
 635         goto err;
 636     }
 637     val[num_val] = NULL;        /* pivot element */
 638
 639     /* allocate points for precomputation */
 640     v = val;
 641     for (i = 0; i < num + num_scalar; i++) {
 642         val_sub[i] = v;
 643         for (j = 0; j < ((size_t)1 << (wsize[i] - 1)); j++) {
 644             *v = EC_POINT_new(group);
 645             if (*v == NULL)
 646                 goto err;
 647             v++;
 648         }
 649     }
 650     if (!(v == val + num_val)) {
 651         ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 652         goto err;
 653     }
 654
 655     if ((tmp = EC_POINT_new(group)) == NULL)
 656         goto err;
 657
 658     /*-
 659      * prepare precomputed values:
 660      *    val_sub[i][0] :=     points[i]
 661      *    val_sub[i][1] := 3 * points[i]
 662      *    val_sub[i][2] := 5 * points[i]
 663      *    ...
 664      */
 665     for (i = 0; i < num + num_scalar; i++) {
 666         if (i < num) {
 667             if (!EC_POINT_copy(val_sub[i][0], points[i]))
 668                 goto err;
 669         } else {
 670             if (!EC_POINT_copy(val_sub[i][0], generator))
 671                 goto err;
 672         }
 673
 674         if (wsize[i] > 1) {
 675             if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx))
 676                 goto err;
 677             for (j = 1; j < ((size_t)1 << (wsize[i] - 1)); j++) {
 678                 if (!EC_POINT_add
 679                     (group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx))
 680                     goto err;
 681             }
 682         }
 683     }
 684
 685     if (!EC_POINTs_make_affine(group, num_val, val, ctx))
 686         goto err;
 687
 688     r_is_at_infinity = 1;
 689
 690     for (k = max_len - 1; k >= 0; k--) {
 691         if (!r_is_at_infinity) {
 692             if (!EC_POINT_dbl(group, r, r, ctx))
 693                 goto err;
 694         }
 695
 696         for (i = 0; i < totalnum; i++) {
 697             if (wNAF_len[i] > (size_t)k) {
 698                 int digit = wNAF[i][k];
 699                 int is_neg;
 700
 701                 if (digit) {
 702                     is_neg = digit < 0;
 703
 704                     if (is_neg)
 705                         digit = -digit;
 706
 707                     if (is_neg != r_is_inverted) {
 708                         if (!r_is_at_infinity) {
 709                             if (!EC_POINT_invert(group, r, ctx))
 710                                 goto err;
 711                         }
 712                         r_is_inverted = !r_is_inverted;
 713                     }
 714
 715                     /* digit > 0 */
 716
 717                     if (r_is_at_infinity) {
 718                         if (!EC_POINT_copy(r, val_sub[i][digit >> 1]))
 719                             goto err;
 720                         r_is_at_infinity = 0;
 721                     } else {
 722                         if (!EC_POINT_add
 723                             (group, r, r, val_sub[i][digit >> 1], ctx))
 724                             goto err;
 725                     }
 726                 }
 727             }
 728         }
 729     }
 730
 731     if (r_is_at_infinity) {
 732         if (!EC_POINT_set_to_infinity(group, r))
 733             goto err;
 734     } else {
 735         if (r_is_inverted)
 736             if (!EC_POINT_invert(group, r, ctx))
 737                 goto err;
 738     }
 739
 740     ret = 1;
 741
 742  err:
 743     BN_CTX_free(new_ctx);
 744     EC_POINT_free(tmp);
 745     OPENSSL_free(wsize);
 746     OPENSSL_free(wNAF_len);
 747     if (wNAF != NULL) {
 748         signed char **w;
 749
 750         for (w = wNAF; *w != NULL; w++)
 751             OPENSSL_free(*w);
 752
 753         OPENSSL_free(wNAF);
 754     }
 755     if (val != NULL) {
 756         for (v = val; *v != NULL; v++)
 757             EC_POINT_clear_free(*v);
 758
 759         OPENSSL_free(val);
 760     }
 761     OPENSSL_free(val_sub);
 762     return ret;
 763 }
 764
 765 /*-
 766  * ec_wNAF_precompute_mult()
 767  * creates an EC_PRE_COMP object with preprecomputed multiples of the generator
 768  * for use with wNAF splitting as implemented in ec_wNAF_mul().
 769  *
 770  * 'pre_comp->points' is an array of multiples of the generator
 771  * of the following form:
 772  * points[0] =     generator;
 773  * points[1] = 3 * generator;
 774  * ...
 775  * points[2^(w-1)-1] =     (2^(w-1)-1) * generator;
 776  * points[2^(w-1)]   =     2^blocksize * generator;
 777  * points[2^(w-1)+1] = 3 * 2^blocksize * generator;
 778  * ...
 779  * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) *  2^(blocksize*(numblocks-2)) * generator
 780  * points[2^(w-1)*(numblocks-1)]   =              2^(blocksize*(numblocks-1)) * generator
 781  * ...
 782  * points[2^(w-1)*numblocks-1]     = (2^(w-1)) *  2^(blocksize*(numblocks-1)) * generator
 783  * points[2^(w-1)*numblocks]       = NULL
 784  */
 785 int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
 786 {
 787     const EC_POINT *generator;
 788     EC_POINT *tmp_point = NULL, *base = NULL, **var;
 789     BN_CTX *new_ctx = NULL;
 790     const BIGNUM *order;
 791     size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num;
 792     EC_POINT **points = NULL;
 793     EC_PRE_COMP *pre_comp;
 794     int ret = 0;
 795
 796     /* if there is an old EC_PRE_COMP object, throw it away */
 797     EC_pre_comp_free(group);
 798     if ((pre_comp = ec_pre_comp_new(group)) == NULL)
 799         return 0;
 800
 801     generator = EC_GROUP_get0_generator(group);
 802     if (generator == NULL) {
 803         ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR);
 804         goto err;
 805     }
 806
 807     if (ctx == NULL) {
 808         ctx = new_ctx = BN_CTX_new();
 809         if (ctx == NULL)
 810             goto err;
 811     }
 812
 813     BN_CTX_start(ctx);
 814
 815     order = EC_GROUP_get0_order(group);
 816     if (order == NULL)
 817         goto err;
 818     if (BN_is_zero(order)) {
 819         ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER);
 820         goto err;
 821     }
 822
 823     bits = BN_num_bits(order);
 824     /*
 825      * The following parameters mean we precompute (approximately) one point
 826      * per bit. TBD: The combination 8, 4 is perfect for 160 bits; for other
 827      * bit lengths, other parameter combinations might provide better
 828      * efficiency.
 829      */
 830     blocksize = 8;
 831     w = 4;
 832     if (EC_window_bits_for_scalar_size(bits) > w) {
 833         /* let's not make the window too small ... */
 834         w = EC_window_bits_for_scalar_size(bits);
 835     }
 836
 837     numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks
 838                                                      * to use for wNAF
 839                                                      * splitting */
 840
 841     pre_points_per_block = (size_t)1 << (w - 1);
 842     num = pre_points_per_block * numblocks; /* number of points to compute
 843                                              * and store */
 844
 845     points = OPENSSL_malloc(sizeof(*points) * (num + 1));
 846     if (points == NULL) {
 847         ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
 848         goto err;
 849     }
 850
 851     var = points;
 852     var[num] = NULL;            /* pivot */
 853     for (i = 0; i < num; i++) {
 854         if ((var[i] = EC_POINT_new(group)) == NULL) {
 855             ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
 856             goto err;
 857         }
 858     }
 859
 860     if ((tmp_point = EC_POINT_new(group)) == NULL
 861         || (base = EC_POINT_new(group)) == NULL) {
 862         ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
 863         goto err;
 864     }
 865
 866     if (!EC_POINT_copy(base, generator))
 867         goto err;
 868
 869     /* do the precomputation */
 870     for (i = 0; i < numblocks; i++) {
 871         size_t j;
 872
 873         if (!EC_POINT_dbl(group, tmp_point, base, ctx))
 874             goto err;
 875
 876         if (!EC_POINT_copy(*var++, base))
 877             goto err;
 878
 879         for (j = 1; j < pre_points_per_block; j++, var++) {
 880             /*
 881              * calculate odd multiples of the current base point
 882              */
 883             if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx))
 884                 goto err;
 885         }
 886
 887         if (i < numblocks - 1) {
 888             /*
 889              * get the next base (multiply current one by 2^blocksize)
 890              */
 891             size_t k;
 892
 893             if (blocksize <= 2) {
 894                 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_INTERNAL_ERROR);
 895                 goto err;
 896             }
 897
 898             if (!EC_POINT_dbl(group, base, tmp_point, ctx))
 899                 goto err;
 900             for (k = 2; k < blocksize; k++) {
 901                 if (!EC_POINT_dbl(group, base, base, ctx))
 902                     goto err;
 903             }
 904         }
 905     }
 906
 907     if (!EC_POINTs_make_affine(group, num, points, ctx))
 908         goto err;
 909
 910     pre_comp->group = group;
 911     pre_comp->blocksize = blocksize;
 912     pre_comp->numblocks = numblocks;
 913     pre_comp->w = w;
 914     pre_comp->points = points;
 915     points = NULL;
 916     pre_comp->num = num;
 917     SETPRECOMP(group, ec, pre_comp);
 918     pre_comp = NULL;
 919     ret = 1;
 920
 921  err:
 922     if (ctx != NULL)
 923         BN_CTX_end(ctx);
 924     BN_CTX_free(new_ctx);
 925     EC_ec_pre_comp_free(pre_comp);
 926     if (points) {
 927         EC_POINT **p;
 928
 929         for (p = points; *p != NULL; p++)
 930             EC_POINT_free(*p);
 931         OPENSSL_free(points);
 932     }
 933     EC_POINT_free(tmp_point);
 934     EC_POINT_free(base);
 935     return ret;
 936 }
 937
 938 int ec_wNAF_have_precompute_mult(const EC_GROUP *group)
 939 {
 940     return HAVEPRECOMP(group, ec);
 941 }