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