crypto/ec/ec_mult.c

   1 /*
   2  * Copyright 2001-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
   4  *
   5  * Licensed under the OpenSSL license (the "License").  You may not use
   6  * this file except in compliance with the License.  You can obtain a copy
   7  * in the file LICENSE in the source distribution or at
   8  * https://www.openssl.org/source/license.html
   9  */
  10
  11 #include <string.h>
  12 #include <openssl/err.h>
  13
  14 #include "internal/cryptlib.h"
  15 #include "internal/bn_int.h"
  16 #include "ec_lcl.h"
  17
  18 /*
  19  * This file implements the wNAF-based interleaving multi-exponentiation method
  20  * Formerly at:
  21  *   http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp
  22  * You might now find it here:
  23  *   http://link.springer.com/chapter/10.1007%2F3-540-45537-X_13
  24  *   http://www.bmoeller.de/pdf/TI-01-08.multiexp.pdf
  25  * For multiplication with precomputation, we use wNAF splitting, formerly at:
  26  *   http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp
  27  */
  28
  29 /* structure for precomputed multiples of the generator */
  30 struct ec_pre_comp_st {
  31     const EC_GROUP *group;      /* parent EC_GROUP object */
  32     size_t blocksize;           /* block size for wNAF splitting */
  33     size_t numblocks;           /* max. number of blocks for which we have
  34                                  * precomputation */
  35     size_t w;                   /* window size */
  36     EC_POINT **points;          /* array with pre-calculated multiples of
  37                                  * generator: 'num' pointers to EC_POINT
  38                                  * objects followed by a NULL */
  39     size_t num;                 /* numblocks * 2^(w-1) */
  40     CRYPTO_REF_COUNT references;
  41     CRYPTO_RWLOCK *lock;
  42 };
  43
  44 static EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group)
  45 {
  46     EC_PRE_COMP *ret = NULL;
  47
  48     if (!group)
  49         return NULL;
  50
  51     ret = OPENSSL_zalloc(sizeof(*ret));
  52     if (ret == NULL) {
  53         ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE);
  54         return ret;
  55     }
  56
  57     ret->group = group;
  58     ret->blocksize = 8;         /* default */
  59     ret->w = 4;                 /* default */
  60     ret->references = 1;
  61
  62     ret->lock = CRYPTO_THREAD_lock_new();
  63     if (ret->lock == NULL) {
  64         ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE);
  65         OPENSSL_free(ret);
  66         return NULL;
  67     }
  68     return ret;
  69 }
  70
  71 EC_PRE_COMP *EC_ec_pre_comp_dup(EC_PRE_COMP *pre)
  72 {
  73     int i;
  74     if (pre != NULL)
  75         CRYPTO_UP_REF(&pre->references, &i, pre->lock);
  76     return pre;
  77 }
  78
  79 void EC_ec_pre_comp_free(EC_PRE_COMP *pre)
  80 {
  81     int i;
  82
  83     if (pre == NULL)
  84         return;
  85
  86     CRYPTO_DOWN_REF(&pre->references, &i, pre->lock);
  87     REF_PRINT_COUNT("EC_ec", pre);
  88     if (i > 0)
  89         return;
  90     REF_ASSERT_ISNT(i < 0);
  91
  92     if (pre->points != NULL) {
  93         EC_POINT **pts;
  94
  95         for (pts = pre->points; *pts != NULL; pts++)
  96             EC_POINT_free(*pts);
  97         OPENSSL_free(pre->points);
  98     }
  99     CRYPTO_THREAD_lock_free(pre->lock);
 100     OPENSSL_free(pre);
 101 }
 102
 103 /*
 104  * TODO: table should be optimised for the wNAF-based implementation,
 105  * sometimes smaller windows will give better performance (thus the
 106  * boundaries should be increased)
 107  */
 108 #define EC_window_bits_for_scalar_size(b) \
 109                 ((size_t) \
 110                  ((b) >= 2000 ? 6 : \
 111                   (b) >=  800 ? 5 : \
 112                   (b) >=  300 ? 4 : \
 113                   (b) >=   70 ? 3 : \
 114                   (b) >=   20 ? 2 : \
 115                   1))
 116
 117 /*-
 118  * Compute
 119  *      \sum scalars[i]*points[i],
 120  * also including
 121  *      scalar*generator
 122  * in the addition if scalar != NULL
 123  */
 124 int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 125                 size_t num, const EC_POINT *points[], const BIGNUM *scalars[],
 126                 BN_CTX *ctx)
 127 {
 128     BN_CTX *new_ctx = NULL;
 129     const EC_POINT *generator = NULL;
 130     EC_POINT *tmp = NULL;
 131     size_t totalnum;
 132     size_t blocksize = 0, numblocks = 0; /* for wNAF splitting */
 133     size_t pre_points_per_block = 0;
 134     size_t i, j;
 135     int k;
 136     int r_is_inverted = 0;
 137     int r_is_at_infinity = 1;
 138     size_t *wsize = NULL;       /* individual window sizes */
 139     signed char **wNAF = NULL;  /* individual wNAFs */
 140     size_t *wNAF_len = NULL;
 141     size_t max_len = 0;
 142     size_t num_val;
 143     EC_POINT **val = NULL;      /* precomputation */
 144     EC_POINT **v;
 145     EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' or
 146                                  * 'pre_comp->points' */
 147     const EC_PRE_COMP *pre_comp = NULL;
 148     int num_scalar = 0;         /* flag: will be set to 1 if 'scalar' must be
 149                                  * treated like other scalars, i.e.
 150                                  * precomputation is not available */
 151     int ret = 0;
 152
 153     if (group->meth != r->meth) {
 154         ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
 155         return 0;
 156     }
 157
 158     if ((scalar == NULL) && (num == 0)) {
 159         return EC_POINT_set_to_infinity(group, r);
 160     }
 161
 162     for (i = 0; i < num; i++) {
 163         if (group->meth != points[i]->meth) {
 164             ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
 165             return 0;
 166         }
 167     }
 168
 169     if (ctx == NULL) {
 170         ctx = new_ctx = BN_CTX_new();
 171         if (ctx == NULL)
 172             goto err;
 173     }
 174
 175     if (scalar != NULL) {
 176         generator = EC_GROUP_get0_generator(group);
 177         if (generator == NULL) {
 178             ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR);
 179             goto err;
 180         }
 181
 182         /* look if we can use precomputed multiples of generator */
 183
 184         pre_comp = group->pre_comp.ec;
 185         if (pre_comp && pre_comp->numblocks
 186             && (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) ==
 187                 0)) {
 188             blocksize = pre_comp->blocksize;
 189
 190             /*
 191              * determine maximum number of blocks that wNAF splitting may
 192              * yield (NB: maximum wNAF length is bit length plus one)
 193              */
 194             numblocks = (BN_num_bits(scalar) / blocksize) + 1;
 195
 196             /*
 197              * we cannot use more blocks than we have precomputation for
 198              */
 199             if (numblocks > pre_comp->numblocks)
 200                 numblocks = pre_comp->numblocks;
 201
 202             pre_points_per_block = (size_t)1 << (pre_comp->w - 1);
 203
 204             /* check that pre_comp looks sane */
 205             if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block)) {
 206                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 207                 goto err;
 208             }
 209         } else {
 210             /* can't use precomputation */
 211             pre_comp = NULL;
 212             numblocks = 1;
 213             num_scalar = 1;     /* treat 'scalar' like 'num'-th element of
 214                                  * 'scalars' */
 215         }
 216     }
 217
 218     totalnum = num + numblocks;
 219
 220     wsize = OPENSSL_malloc(totalnum * sizeof wsize[0]);
 221     wNAF_len = OPENSSL_malloc(totalnum * sizeof wNAF_len[0]);
 222     wNAF = OPENSSL_malloc((totalnum + 1) * sizeof wNAF[0]); /* includes space
 223                                                              * for pivot */
 224     val_sub = OPENSSL_malloc(totalnum * sizeof val_sub[0]);
 225
 226     /* Ensure wNAF is initialised in case we end up going to err */
 227     if (wNAF != NULL)
 228         wNAF[0] = NULL;         /* preliminary pivot */
 229
 230     if (wsize == NULL || wNAF_len == NULL || wNAF == NULL || val_sub == NULL) {
 231         ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE);
 232         goto err;
 233     }
 234
 235     /*
 236      * num_val will be the total number of temporarily precomputed points
 237      */
 238     num_val = 0;
 239
 240     for (i = 0; i < num + num_scalar; i++) {
 241         size_t bits;
 242
 243         bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar);
 244         wsize[i] = EC_window_bits_for_scalar_size(bits);
 245         num_val += (size_t)1 << (wsize[i] - 1);
 246         wNAF[i + 1] = NULL;     /* make sure we always have a pivot */
 247         wNAF[i] =
 248             bn_compute_wNAF((i < num ? scalars[i] : scalar), wsize[i],
 249                             &wNAF_len[i]);
 250         if (wNAF[i] == NULL)
 251             goto err;
 252         if (wNAF_len[i] > max_len)
 253             max_len = wNAF_len[i];
 254     }
 255
 256     if (numblocks) {
 257         /* we go here iff scalar != NULL */
 258
 259         if (pre_comp == NULL) {
 260             if (num_scalar != 1) {
 261                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 262                 goto err;
 263             }
 264             /* we have already generated a wNAF for 'scalar' */
 265         } else {
 266             signed char *tmp_wNAF = NULL;
 267             size_t tmp_len = 0;
 268
 269             if (num_scalar != 0) {
 270                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 271                 goto err;
 272             }
 273
 274             /*
 275              * use the window size for which we have precomputation
 276              */
 277             wsize[num] = pre_comp->w;
 278             tmp_wNAF = bn_compute_wNAF(scalar, wsize[num], &tmp_len);
 279             if (!tmp_wNAF)
 280                 goto err;
 281
 282             if (tmp_len <= max_len) {
 283                 /*
 284                  * One of the other wNAFs is at least as long as the wNAF
 285                  * belonging to the generator, so wNAF splitting will not buy
 286                  * us anything.
 287                  */
 288
 289                 numblocks = 1;
 290                 totalnum = num + 1; /* don't use wNAF splitting */
 291                 wNAF[num] = tmp_wNAF;
 292                 wNAF[num + 1] = NULL;
 293                 wNAF_len[num] = tmp_len;
 294                 /*
 295                  * pre_comp->points starts with the points that we need here:
 296                  */
 297                 val_sub[num] = pre_comp->points;
 298             } else {
 299                 /*
 300                  * don't include tmp_wNAF directly into wNAF array - use wNAF
 301                  * splitting and include the blocks
 302                  */
 303
 304                 signed char *pp;
 305                 EC_POINT **tmp_points;
 306
 307                 if (tmp_len < numblocks * blocksize) {
 308                     /*
 309                      * possibly we can do with fewer blocks than estimated
 310                      */
 311                     numblocks = (tmp_len + blocksize - 1) / blocksize;
 312                     if (numblocks > pre_comp->numblocks) {
 313                         ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 314                         OPENSSL_free(tmp_wNAF);
 315                         goto err;
 316                     }
 317                     totalnum = num + numblocks;
 318                 }
 319
 320                 /* split wNAF in 'numblocks' parts */
 321                 pp = tmp_wNAF;
 322                 tmp_points = pre_comp->points;
 323
 324                 for (i = num; i < totalnum; i++) {
 325                     if (i < totalnum - 1) {
 326                         wNAF_len[i] = blocksize;
 327                         if (tmp_len < blocksize) {
 328                             ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 329                             OPENSSL_free(tmp_wNAF);
 330                             goto err;
 331                         }
 332                         tmp_len -= blocksize;
 333                     } else
 334                         /*
 335                          * last block gets whatever is left (this could be
 336                          * more or less than 'blocksize'!)
 337                          */
 338                         wNAF_len[i] = tmp_len;
 339
 340                     wNAF[i + 1] = NULL;
 341                     wNAF[i] = OPENSSL_malloc(wNAF_len[i]);
 342                     if (wNAF[i] == NULL) {
 343                         ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE);
 344                         OPENSSL_free(tmp_wNAF);
 345                         goto err;
 346                     }
 347                     memcpy(wNAF[i], pp, wNAF_len[i]);
 348                     if (wNAF_len[i] > max_len)
 349                         max_len = wNAF_len[i];
 350
 351                     if (*tmp_points == NULL) {
 352                         ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 353                         OPENSSL_free(tmp_wNAF);
 354                         goto err;
 355                     }
 356                     val_sub[i] = tmp_points;
 357                     tmp_points += pre_points_per_block;
 358                     pp += blocksize;
 359                 }
 360                 OPENSSL_free(tmp_wNAF);
 361             }
 362         }
 363     }
 364
 365     /*
 366      * All points we precompute now go into a single array 'val'.
 367      * 'val_sub[i]' is a pointer to the subarray for the i-th point, or to a
 368      * subarray of 'pre_comp->points' if we already have precomputation.
 369      */
 370     val = OPENSSL_malloc((num_val + 1) * sizeof val[0]);
 371     if (val == NULL) {
 372         ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE);
 373         goto err;
 374     }
 375     val[num_val] = NULL;        /* pivot element */
 376
 377     /* allocate points for precomputation */
 378     v = val;
 379     for (i = 0; i < num + num_scalar; i++) {
 380         val_sub[i] = v;
 381         for (j = 0; j < ((size_t)1 << (wsize[i] - 1)); j++) {
 382             *v = EC_POINT_new(group);
 383             if (*v == NULL)
 384                 goto err;
 385             v++;
 386         }
 387     }
 388     if (!(v == val + num_val)) {
 389         ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 390         goto err;
 391     }
 392
 393     if ((tmp = EC_POINT_new(group)) == NULL)
 394         goto err;
 395
 396     /*-
 397      * prepare precomputed values:
 398      *    val_sub[i][0] :=     points[i]
 399      *    val_sub[i][1] := 3 * points[i]
 400      *    val_sub[i][2] := 5 * points[i]
 401      *    ...
 402      */
 403     for (i = 0; i < num + num_scalar; i++) {
 404         if (i < num) {
 405             if (!EC_POINT_copy(val_sub[i][0], points[i]))
 406                 goto err;
 407         } else {
 408             if (!EC_POINT_copy(val_sub[i][0], generator))
 409                 goto err;
 410         }
 411
 412         if (wsize[i] > 1) {
 413             if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx))
 414                 goto err;
 415             for (j = 1; j < ((size_t)1 << (wsize[i] - 1)); j++) {
 416                 if (!EC_POINT_add
 417                     (group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx))
 418                     goto err;
 419             }
 420         }
 421     }
 422
 423     if (!EC_POINTs_make_affine(group, num_val, val, ctx))
 424         goto err;
 425
 426     r_is_at_infinity = 1;
 427
 428     for (k = max_len - 1; k >= 0; k--) {
 429         if (!r_is_at_infinity) {
 430             if (!EC_POINT_dbl(group, r, r, ctx))
 431                 goto err;
 432         }
 433
 434         for (i = 0; i < totalnum; i++) {
 435             if (wNAF_len[i] > (size_t)k) {
 436                 int digit = wNAF[i][k];
 437                 int is_neg;
 438
 439                 if (digit) {
 440                     is_neg = digit < 0;
 441
 442                     if (is_neg)
 443                         digit = -digit;
 444
 445                     if (is_neg != r_is_inverted) {
 446                         if (!r_is_at_infinity) {
 447                             if (!EC_POINT_invert(group, r, ctx))
 448                                 goto err;
 449                         }
 450                         r_is_inverted = !r_is_inverted;
 451                     }
 452
 453                     /* digit > 0 */
 454
 455                     if (r_is_at_infinity) {
 456                         if (!EC_POINT_copy(r, val_sub[i][digit >> 1]))
 457                             goto err;
 458                         r_is_at_infinity = 0;
 459                     } else {
 460                         if (!EC_POINT_add
 461                             (group, r, r, val_sub[i][digit >> 1], ctx))
 462                             goto err;
 463                     }
 464                 }
 465             }
 466         }
 467     }
 468
 469     if (r_is_at_infinity) {
 470         if (!EC_POINT_set_to_infinity(group, r))
 471             goto err;
 472     } else {
 473         if (r_is_inverted)
 474             if (!EC_POINT_invert(group, r, ctx))
 475                 goto err;
 476     }
 477
 478     ret = 1;
 479
 480  err:
 481     BN_CTX_free(new_ctx);
 482     EC_POINT_free(tmp);
 483     OPENSSL_free(wsize);
 484     OPENSSL_free(wNAF_len);
 485     if (wNAF != NULL) {
 486         signed char **w;
 487
 488         for (w = wNAF; *w != NULL; w++)
 489             OPENSSL_free(*w);
 490
 491         OPENSSL_free(wNAF);
 492     }
 493     if (val != NULL) {
 494         for (v = val; *v != NULL; v++)
 495             EC_POINT_clear_free(*v);
 496
 497         OPENSSL_free(val);
 498     }
 499     OPENSSL_free(val_sub);
 500     return ret;
 501 }
 502
 503 /*-
 504  * ec_wNAF_precompute_mult()
 505  * creates an EC_PRE_COMP object with preprecomputed multiples of the generator
 506  * for use with wNAF splitting as implemented in ec_wNAF_mul().
 507  *
 508  * 'pre_comp->points' is an array of multiples of the generator
 509  * of the following form:
 510  * points[0] =     generator;
 511  * points[1] = 3 * generator;
 512  * ...
 513  * points[2^(w-1)-1] =     (2^(w-1)-1) * generator;
 514  * points[2^(w-1)]   =     2^blocksize * generator;
 515  * points[2^(w-1)+1] = 3 * 2^blocksize * generator;
 516  * ...
 517  * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) *  2^(blocksize*(numblocks-2)) * generator
 518  * points[2^(w-1)*(numblocks-1)]   =              2^(blocksize*(numblocks-1)) * generator
 519  * ...
 520  * points[2^(w-1)*numblocks-1]     = (2^(w-1)) *  2^(blocksize*(numblocks-1)) * generator
 521  * points[2^(w-1)*numblocks]       = NULL
 522  */
 523 int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
 524 {
 525     const EC_POINT *generator;
 526     EC_POINT *tmp_point = NULL, *base = NULL, **var;
 527     BN_CTX *new_ctx = NULL;
 528     const BIGNUM *order;
 529     size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num;
 530     EC_POINT **points = NULL;
 531     EC_PRE_COMP *pre_comp;
 532     int ret = 0;
 533
 534     /* if there is an old EC_PRE_COMP object, throw it away */
 535     EC_pre_comp_free(group);
 536     if ((pre_comp = ec_pre_comp_new(group)) == NULL)
 537         return 0;
 538
 539     generator = EC_GROUP_get0_generator(group);
 540     if (generator == NULL) {
 541         ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR);
 542         goto err;
 543     }
 544
 545     if (ctx == NULL) {
 546         ctx = new_ctx = BN_CTX_new();
 547         if (ctx == NULL)
 548             goto err;
 549     }
 550
 551     BN_CTX_start(ctx);
 552
 553     order = EC_GROUP_get0_order(group);
 554     if (order == NULL)
 555         goto err;
 556     if (BN_is_zero(order)) {
 557         ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER);
 558         goto err;
 559     }
 560
 561     bits = BN_num_bits(order);
 562     /*
 563      * The following parameters mean we precompute (approximately) one point
 564      * per bit. TBD: The combination 8, 4 is perfect for 160 bits; for other
 565      * bit lengths, other parameter combinations might provide better
 566      * efficiency.
 567      */
 568     blocksize = 8;
 569     w = 4;
 570     if (EC_window_bits_for_scalar_size(bits) > w) {
 571         /* let's not make the window too small ... */
 572         w = EC_window_bits_for_scalar_size(bits);
 573     }
 574
 575     numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks
 576                                                      * to use for wNAF
 577                                                      * splitting */
 578
 579     pre_points_per_block = (size_t)1 << (w - 1);
 580     num = pre_points_per_block * numblocks; /* number of points to compute
 581                                              * and store */
 582
 583     points = OPENSSL_malloc(sizeof(*points) * (num + 1));
 584     if (points == NULL) {
 585         ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
 586         goto err;
 587     }
 588
 589     var = points;
 590     var[num] = NULL;            /* pivot */
 591     for (i = 0; i < num; i++) {
 592         if ((var[i] = EC_POINT_new(group)) == NULL) {
 593             ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
 594             goto err;
 595         }
 596     }
 597
 598     if ((tmp_point = EC_POINT_new(group)) == NULL
 599         || (base = EC_POINT_new(group)) == NULL) {
 600         ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
 601         goto err;
 602     }
 603
 604     if (!EC_POINT_copy(base, generator))
 605         goto err;
 606
 607     /* do the precomputation */
 608     for (i = 0; i < numblocks; i++) {
 609         size_t j;
 610
 611         if (!EC_POINT_dbl(group, tmp_point, base, ctx))
 612             goto err;
 613
 614         if (!EC_POINT_copy(*var++, base))
 615             goto err;
 616
 617         for (j = 1; j < pre_points_per_block; j++, var++) {
 618             /*
 619              * calculate odd multiples of the current base point
 620              */
 621             if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx))
 622                 goto err;
 623         }
 624
 625         if (i < numblocks - 1) {
 626             /*
 627              * get the next base (multiply current one by 2^blocksize)
 628              */
 629             size_t k;
 630
 631             if (blocksize <= 2) {
 632                 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_INTERNAL_ERROR);
 633                 goto err;
 634             }
 635
 636             if (!EC_POINT_dbl(group, base, tmp_point, ctx))
 637                 goto err;
 638             for (k = 2; k < blocksize; k++) {
 639                 if (!EC_POINT_dbl(group, base, base, ctx))
 640                     goto err;
 641             }
 642         }
 643     }
 644
 645     if (!EC_POINTs_make_affine(group, num, points, ctx))
 646         goto err;
 647
 648     pre_comp->group = group;
 649     pre_comp->blocksize = blocksize;
 650     pre_comp->numblocks = numblocks;
 651     pre_comp->w = w;
 652     pre_comp->points = points;
 653     points = NULL;
 654     pre_comp->num = num;
 655     SETPRECOMP(group, ec, pre_comp);
 656     pre_comp = NULL;
 657     ret = 1;
 658
 659  err:
 660     if (ctx != NULL)
 661         BN_CTX_end(ctx);
 662     BN_CTX_free(new_ctx);
 663     EC_ec_pre_comp_free(pre_comp);
 664     if (points) {
 665         EC_POINT **p;
 666
 667         for (p = points; *p != NULL; p++)
 668             EC_POINT_free(*p);
 669         OPENSSL_free(points);
 670     }
 671     EC_POINT_free(tmp_point);
 672     EC_POINT_free(base);
 673     return ret;
 674 }
 675
 676 int ec_wNAF_have_precompute_mult(const EC_GROUP *group)
 677 {
 678     return HAVEPRECOMP(group, ec);
 679 }