"Fossies" - the Fresh Open Source Software Archive

Member "openssl-1.1.1g/crypto/ec/ec_mult.c" (21 Apr 2020, 31318 Bytes) of package /linux/misc/openssl-1.1.1g.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "ec_mult.c" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 1.1.1f_vs_1.1.1g.

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