Line data Source code
1 : /* crypto/ec/ec_mult.c */
2 : /*
3 : * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project.
4 : */
5 : /* ====================================================================
6 : * Copyright (c) 1998-2007 The OpenSSL Project. All rights reserved.
7 : *
8 : * Redistribution and use in source and binary forms, with or without
9 : * modification, are permitted provided that the following conditions
10 : * are met:
11 : *
12 : * 1. Redistributions of source code must retain the above copyright
13 : * notice, this list of conditions and the following disclaimer.
14 : *
15 : * 2. Redistributions in binary form must reproduce the above copyright
16 : * notice, this list of conditions and the following disclaimer in
17 : * the documentation and/or other materials provided with the
18 : * distribution.
19 : *
20 : * 3. All advertising materials mentioning features or use of this
21 : * software must display the following acknowledgment:
22 : * "This product includes software developed by the OpenSSL Project
23 : * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
24 : *
25 : * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
26 : * endorse or promote products derived from this software without
27 : * prior written permission. For written permission, please contact
28 : * openssl-core@openssl.org.
29 : *
30 : * 5. Products derived from this software may not be called "OpenSSL"
31 : * nor may "OpenSSL" appear in their names without prior written
32 : * permission of the OpenSSL Project.
33 : *
34 : * 6. Redistributions of any form whatsoever must retain the following
35 : * acknowledgment:
36 : * "This product includes software developed by the OpenSSL Project
37 : * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
38 : *
39 : * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
40 : * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
41 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
42 : * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
43 : * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44 : * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
45 : * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
46 : * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 : * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
48 : * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
49 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
50 : * OF THE POSSIBILITY OF SUCH DAMAGE.
51 : * ====================================================================
52 : *
53 : * This product includes cryptographic software written by Eric Young
54 : * (eay@cryptsoft.com). This product includes software written by Tim
55 : * Hudson (tjh@cryptsoft.com).
56 : *
57 : */
58 : /* ====================================================================
59 : * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
60 : * Portions of this software developed by SUN MICROSYSTEMS, INC.,
61 : * and contributed to the OpenSSL project.
62 : */
63 :
64 : #include <string.h>
65 :
66 : #include <openssl/err.h>
67 :
68 : #include "ec_lcl.h"
69 :
70 : /*
71 : * This file implements the wNAF-based interleaving multi-exponentation method
72 : * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp>);
73 : * for multiplication with precomputation, we use wNAF splitting
74 : * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp>).
75 : */
76 :
77 : /* structure for precomputed multiples of the generator */
78 : typedef struct ec_pre_comp_st {
79 : const EC_GROUP *group; /* parent EC_GROUP object */
80 : size_t blocksize; /* block size for wNAF splitting */
81 : size_t numblocks; /* max. number of blocks for which we have
82 : * precomputation */
83 : size_t w; /* window size */
84 : EC_POINT **points; /* array with pre-calculated multiples of
85 : * generator: 'num' pointers to EC_POINT
86 : * objects followed by a NULL */
87 : size_t num; /* numblocks * 2^(w-1) */
88 : int references;
89 : } EC_PRE_COMP;
90 :
91 : /* functions to manage EC_PRE_COMP within the EC_GROUP extra_data framework */
92 : static void *ec_pre_comp_dup(void *);
93 : static void ec_pre_comp_free(void *);
94 : static void ec_pre_comp_clear_free(void *);
95 :
96 0 : static EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group)
97 : {
98 : EC_PRE_COMP *ret = NULL;
99 :
100 0 : if (!group)
101 : return NULL;
102 :
103 0 : ret = (EC_PRE_COMP *)OPENSSL_malloc(sizeof(EC_PRE_COMP));
104 0 : if (!ret) {
105 0 : ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE);
106 0 : return ret;
107 : }
108 0 : ret->group = group;
109 0 : ret->blocksize = 8; /* default */
110 0 : ret->numblocks = 0;
111 0 : ret->w = 4; /* default */
112 0 : ret->points = NULL;
113 0 : ret->num = 0;
114 0 : ret->references = 1;
115 0 : return ret;
116 : }
117 :
118 0 : static void *ec_pre_comp_dup(void *src_)
119 : {
120 : EC_PRE_COMP *src = src_;
121 :
122 : /* no need to actually copy, these objects never change! */
123 :
124 0 : CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP);
125 :
126 0 : return src_;
127 : }
128 :
129 0 : static void ec_pre_comp_free(void *pre_)
130 : {
131 : int i;
132 : EC_PRE_COMP *pre = pre_;
133 :
134 0 : if (!pre)
135 : return;
136 :
137 0 : i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP);
138 0 : if (i > 0)
139 : return;
140 :
141 0 : if (pre->points) {
142 : EC_POINT **p;
143 :
144 0 : for (p = pre->points; *p != NULL; p++)
145 0 : EC_POINT_free(*p);
146 0 : OPENSSL_free(pre->points);
147 : }
148 0 : OPENSSL_free(pre);
149 : }
150 :
151 0 : static void ec_pre_comp_clear_free(void *pre_)
152 : {
153 : int i;
154 : EC_PRE_COMP *pre = pre_;
155 :
156 0 : if (!pre)
157 : return;
158 :
159 0 : i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP);
160 0 : if (i > 0)
161 : return;
162 :
163 0 : if (pre->points) {
164 : EC_POINT **p;
165 :
166 0 : for (p = pre->points; *p != NULL; p++) {
167 0 : EC_POINT_clear_free(*p);
168 0 : OPENSSL_cleanse(p, sizeof *p);
169 : }
170 0 : OPENSSL_free(pre->points);
171 : }
172 0 : OPENSSL_cleanse(pre, sizeof *pre);
173 0 : OPENSSL_free(pre);
174 : }
175 :
176 : /*-
177 : * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
178 : * This is an array r[] of values that are either zero or odd with an
179 : * absolute value less than 2^w satisfying
180 : * scalar = \sum_j r[j]*2^j
181 : * where at most one of any w+1 consecutive digits is non-zero
182 : * with the exception that the most significant digit may be only
183 : * w-1 zeros away from that next non-zero digit.
184 : */
185 2352 : static signed char *compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
186 : {
187 : int window_val;
188 : int ok = 0;
189 : signed char *r = NULL;
190 : int sign = 1;
191 : int bit, next_bit, mask;
192 : size_t len = 0, j;
193 :
194 2352 : if (BN_is_zero(scalar)) {
195 0 : r = OPENSSL_malloc(1);
196 0 : if (!r) {
197 0 : ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
198 0 : goto err;
199 : }
200 0 : r[0] = 0;
201 0 : *ret_len = 1;
202 0 : return r;
203 : }
204 :
205 2352 : if (w <= 0 || w > 7) { /* 'signed char' can represent integers with
206 : * absolute values less than 2^7 */
207 0 : ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
208 0 : goto err;
209 : }
210 2352 : bit = 1 << w; /* at most 128 */
211 2352 : next_bit = bit << 1; /* at most 256 */
212 2352 : mask = next_bit - 1; /* at most 255 */
213 :
214 2352 : if (BN_is_negative(scalar)) {
215 : sign = -1;
216 : }
217 :
218 2352 : if (scalar->d == NULL || scalar->top == 0) {
219 0 : ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
220 0 : goto err;
221 : }
222 :
223 2352 : len = BN_num_bits(scalar);
224 2352 : r = OPENSSL_malloc(len + 1); /* modified wNAF may be one digit longer
225 : * than binary representation (*ret_len will
226 : * be set to the actual length, i.e. at most
227 : * BN_num_bits(scalar) + 1) */
228 2352 : if (r == NULL) {
229 0 : ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
230 0 : goto err;
231 : }
232 2352 : window_val = scalar->d[0] & mask;
233 : j = 0;
234 603495 : while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len,
235 : * window_val will not
236 : * increase */
237 : int digit = 0;
238 :
239 : /* 0 <= window_val <= 2^(w+1) */
240 :
241 598791 : if (window_val & 1) {
242 : /* 0 < window_val < 2^(w+1) */
243 :
244 121443 : if (window_val & bit) {
245 59366 : digit = window_val - next_bit; /* -2^w < digit < 0 */
246 :
247 : #if 1 /* modified wNAF */
248 59366 : if (j + w + 1 >= len) {
249 : /*
250 : * special case for generating modified wNAFs: no new
251 : * bits will be added into window_val, so using a
252 : * positive digit here will decrease the total length of
253 : * the representation
254 : */
255 :
256 446 : digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
257 : }
258 : #endif
259 : } else {
260 : digit = window_val; /* 0 < digit < 2^w */
261 : }
262 :
263 121443 : if (digit <= -bit || digit >= bit || !(digit & 1)) {
264 0 : ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
265 0 : goto err;
266 : }
267 :
268 121443 : window_val -= digit;
269 :
270 : /*
271 : * now window_val is 0 or 2^(w+1) in standard wNAF generation;
272 : * for modified window NAFs, it may also be 2^w
273 : */
274 121443 : if (window_val != 0 && window_val != next_bit
275 446 : && window_val != bit) {
276 0 : ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
277 0 : goto err;
278 : }
279 : }
280 :
281 598791 : r[j++] = sign * digit;
282 :
283 598791 : window_val >>= 1;
284 598791 : window_val += bit * BN_is_bit_set(scalar, j + w);
285 :
286 598791 : if (window_val > next_bit) {
287 0 : ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
288 0 : goto err;
289 : }
290 : }
291 :
292 2352 : if (j > len + 1) {
293 0 : ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
294 0 : goto err;
295 : }
296 : len = j;
297 : ok = 1;
298 :
299 : err:
300 2352 : if (!ok) {
301 0 : OPENSSL_free(r);
302 : r = NULL;
303 : }
304 2352 : if (ok)
305 2352 : *ret_len = len;
306 2352 : return r;
307 : }
308 :
309 : /*
310 : * TODO: table should be optimised for the wNAF-based implementation,
311 : * sometimes smaller windows will give better performance (thus the
312 : * boundaries should be increased)
313 : */
314 : #define EC_window_bits_for_scalar_size(b) \
315 : ((size_t) \
316 : ((b) >= 2000 ? 6 : \
317 : (b) >= 800 ? 5 : \
318 : (b) >= 300 ? 4 : \
319 : (b) >= 70 ? 3 : \
320 : (b) >= 20 ? 2 : \
321 : 1))
322 :
323 : /*-
324 : * Compute
325 : * \sum scalars[i]*points[i],
326 : * also including
327 : * scalar*generator
328 : * in the addition if scalar != NULL
329 : */
330 2352 : int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
331 : size_t num, const EC_POINT *points[], const BIGNUM *scalars[],
332 : BN_CTX *ctx)
333 : {
334 : BN_CTX *new_ctx = NULL;
335 : const EC_POINT *generator = NULL;
336 : EC_POINT *tmp = NULL;
337 : size_t totalnum;
338 : size_t blocksize = 0, numblocks = 0; /* for wNAF splitting */
339 : size_t pre_points_per_block = 0;
340 : size_t i, j;
341 : int k;
342 : int r_is_inverted = 0;
343 : int r_is_at_infinity = 1;
344 : size_t *wsize = NULL; /* individual window sizes */
345 : signed char **wNAF = NULL; /* individual wNAFs */
346 : size_t *wNAF_len = NULL;
347 : size_t max_len = 0;
348 : size_t num_val;
349 : EC_POINT **val = NULL; /* precomputation */
350 : EC_POINT **v;
351 : EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' or
352 : * 'pre_comp->points' */
353 : const EC_PRE_COMP *pre_comp = NULL;
354 : int num_scalar = 0; /* flag: will be set to 1 if 'scalar' must be
355 : * treated like other scalars, i.e.
356 : * precomputation is not available */
357 : int ret = 0;
358 :
359 2352 : if (group->meth != r->meth) {
360 0 : ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
361 0 : return 0;
362 : }
363 :
364 2352 : if ((scalar == NULL) && (num == 0)) {
365 0 : return EC_POINT_set_to_infinity(group, r);
366 : }
367 :
368 737 : for (i = 0; i < num; i++) {
369 737 : if (group->meth != points[i]->meth) {
370 0 : ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
371 0 : return 0;
372 : }
373 : }
374 :
375 2352 : if (ctx == NULL) {
376 0 : ctx = new_ctx = BN_CTX_new();
377 0 : if (ctx == NULL)
378 : goto err;
379 : }
380 :
381 2352 : if (scalar != NULL) {
382 1615 : generator = EC_GROUP_get0_generator(group);
383 1615 : if (generator == NULL) {
384 0 : ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR);
385 0 : goto err;
386 : }
387 :
388 : /* look if we can use precomputed multiples of generator */
389 :
390 1615 : pre_comp =
391 1615 : EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup,
392 : ec_pre_comp_free, ec_pre_comp_clear_free);
393 :
394 1615 : if (pre_comp && pre_comp->numblocks
395 0 : && (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) ==
396 : 0)) {
397 0 : blocksize = pre_comp->blocksize;
398 :
399 : /*
400 : * determine maximum number of blocks that wNAF splitting may
401 : * yield (NB: maximum wNAF length is bit length plus one)
402 : */
403 0 : numblocks = (BN_num_bits(scalar) / blocksize) + 1;
404 :
405 : /*
406 : * we cannot use more blocks than we have precomputation for
407 : */
408 0 : if (numblocks > pre_comp->numblocks)
409 : numblocks = pre_comp->numblocks;
410 :
411 0 : pre_points_per_block = (size_t)1 << (pre_comp->w - 1);
412 :
413 : /* check that pre_comp looks sane */
414 0 : if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block)) {
415 0 : ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
416 0 : goto err;
417 : }
418 : } else {
419 : /* can't use precomputation */
420 : pre_comp = NULL;
421 : numblocks = 1;
422 : num_scalar = 1; /* treat 'scalar' like 'num'-th element of
423 : * 'scalars' */
424 : }
425 : }
426 :
427 2352 : totalnum = num + numblocks;
428 :
429 2352 : wsize = OPENSSL_malloc(totalnum * sizeof wsize[0]);
430 2352 : wNAF_len = OPENSSL_malloc(totalnum * sizeof wNAF_len[0]);
431 2352 : wNAF = OPENSSL_malloc((totalnum + 1) * sizeof wNAF[0]); /* includes space
432 : * for pivot */
433 2352 : val_sub = OPENSSL_malloc(totalnum * sizeof val_sub[0]);
434 :
435 : /* Ensure wNAF is initialised in case we end up going to err */
436 2352 : if (wNAF)
437 2352 : wNAF[0] = NULL; /* preliminary pivot */
438 :
439 2352 : if (!wsize || !wNAF_len || !wNAF || !val_sub) {
440 0 : ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE);
441 0 : goto err;
442 : }
443 :
444 : /*
445 : * num_val will be the total number of temporarily precomputed points
446 : */
447 : num_val = 0;
448 :
449 4704 : for (i = 0; i < num + num_scalar; i++) {
450 : size_t bits;
451 :
452 2352 : bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar);
453 2352 : wsize[i] = EC_window_bits_for_scalar_size(bits);
454 2352 : num_val += (size_t)1 << (wsize[i] - 1);
455 2352 : wNAF[i + 1] = NULL; /* make sure we always have a pivot */
456 4704 : wNAF[i] =
457 2352 : compute_wNAF((i < num ? scalars[i] : scalar), wsize[i],
458 : &wNAF_len[i]);
459 2352 : if (wNAF[i] == NULL)
460 : goto err;
461 2352 : if (wNAF_len[i] > max_len)
462 : max_len = wNAF_len[i];
463 : }
464 :
465 2352 : if (numblocks) {
466 : /* we go here iff scalar != NULL */
467 :
468 1615 : if (pre_comp == NULL) {
469 1615 : if (num_scalar != 1) {
470 0 : ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
471 0 : goto err;
472 : }
473 : /* we have already generated a wNAF for 'scalar' */
474 : } else {
475 : signed char *tmp_wNAF = NULL;
476 0 : size_t tmp_len = 0;
477 :
478 0 : if (num_scalar != 0) {
479 0 : ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
480 0 : goto err;
481 : }
482 :
483 : /*
484 : * use the window size for which we have precomputation
485 : */
486 0 : wsize[num] = pre_comp->w;
487 0 : tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len);
488 0 : if (!tmp_wNAF)
489 : goto err;
490 :
491 0 : if (tmp_len <= max_len) {
492 : /*
493 : * One of the other wNAFs is at least as long as the wNAF
494 : * belonging to the generator, so wNAF splitting will not buy
495 : * us anything.
496 : */
497 :
498 : numblocks = 1;
499 0 : totalnum = num + 1; /* don't use wNAF splitting */
500 0 : wNAF[num] = tmp_wNAF;
501 0 : wNAF[num + 1] = NULL;
502 0 : wNAF_len[num] = tmp_len;
503 0 : if (tmp_len > max_len)
504 : max_len = tmp_len;
505 : /*
506 : * pre_comp->points starts with the points that we need here:
507 : */
508 0 : val_sub[num] = pre_comp->points;
509 : } else {
510 : /*
511 : * don't include tmp_wNAF directly into wNAF array - use wNAF
512 : * splitting and include the blocks
513 : */
514 :
515 : signed char *pp;
516 : EC_POINT **tmp_points;
517 :
518 0 : if (tmp_len < numblocks * blocksize) {
519 : /*
520 : * possibly we can do with fewer blocks than estimated
521 : */
522 0 : numblocks = (tmp_len + blocksize - 1) / blocksize;
523 0 : if (numblocks > pre_comp->numblocks) {
524 0 : ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
525 0 : goto err;
526 : }
527 0 : totalnum = num + numblocks;
528 : }
529 :
530 : /* split wNAF in 'numblocks' parts */
531 : pp = tmp_wNAF;
532 0 : tmp_points = pre_comp->points;
533 :
534 0 : for (i = num; i < totalnum; i++) {
535 0 : if (i < totalnum - 1) {
536 0 : wNAF_len[i] = blocksize;
537 0 : if (tmp_len < blocksize) {
538 0 : ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
539 0 : goto err;
540 : }
541 0 : tmp_len -= blocksize;
542 : } else
543 : /*
544 : * last block gets whatever is left (this could be
545 : * more or less than 'blocksize'!)
546 : */
547 0 : wNAF_len[i] = tmp_len;
548 :
549 0 : wNAF[i + 1] = NULL;
550 0 : wNAF[i] = OPENSSL_malloc(wNAF_len[i]);
551 0 : if (wNAF[i] == NULL) {
552 0 : ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE);
553 0 : OPENSSL_free(tmp_wNAF);
554 0 : goto err;
555 : }
556 0 : memcpy(wNAF[i], pp, wNAF_len[i]);
557 0 : if (wNAF_len[i] > max_len)
558 : max_len = wNAF_len[i];
559 :
560 0 : if (*tmp_points == NULL) {
561 0 : ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
562 0 : OPENSSL_free(tmp_wNAF);
563 0 : goto err;
564 : }
565 0 : val_sub[i] = tmp_points;
566 0 : tmp_points += pre_points_per_block;
567 0 : pp += blocksize;
568 : }
569 0 : OPENSSL_free(tmp_wNAF);
570 : }
571 : }
572 : }
573 :
574 : /*
575 : * All points we precompute now go into a single array 'val'.
576 : * 'val_sub[i]' is a pointer to the subarray for the i-th point, or to a
577 : * subarray of 'pre_comp->points' if we already have precomputation.
578 : */
579 2352 : val = OPENSSL_malloc((num_val + 1) * sizeof val[0]);
580 2352 : if (val == NULL) {
581 0 : ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE);
582 0 : goto err;
583 : }
584 2352 : val[num_val] = NULL; /* pivot element */
585 :
586 : /* allocate points for precomputation */
587 : v = val;
588 4704 : for (i = 0; i < num + num_scalar; i++) {
589 2352 : val_sub[i] = v;
590 11760 : for (j = 0; j < ((size_t)1 << (wsize[i] - 1)); j++) {
591 9408 : *v = EC_POINT_new(group);
592 9408 : if (*v == NULL)
593 : goto err;
594 9408 : v++;
595 : }
596 : }
597 2352 : if (!(v == val + num_val)) {
598 0 : ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
599 0 : goto err;
600 : }
601 :
602 2352 : if (!(tmp = EC_POINT_new(group)))
603 : goto err;
604 :
605 : /*-
606 : * prepare precomputed values:
607 : * val_sub[i][0] := points[i]
608 : * val_sub[i][1] := 3 * points[i]
609 : * val_sub[i][2] := 5 * points[i]
610 : * ...
611 : */
612 2352 : for (i = 0; i < num + num_scalar; i++) {
613 2352 : if (i < num) {
614 737 : if (!EC_POINT_copy(val_sub[i][0], points[i]))
615 : goto err;
616 : } else {
617 1615 : if (!EC_POINT_copy(val_sub[i][0], generator))
618 : goto err;
619 : }
620 :
621 2352 : if (wsize[i] > 1) {
622 2352 : if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx))
623 : goto err;
624 7056 : for (j = 1; j < ((size_t)1 << (wsize[i] - 1)); j++) {
625 7056 : if (!EC_POINT_add
626 7056 : (group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx))
627 : goto err;
628 : }
629 : }
630 : }
631 :
632 : #if 1 /* optional; EC_window_bits_for_scalar_size
633 : * assumes we do this step */
634 2352 : if (!EC_POINTs_make_affine(group, num_val, val, ctx))
635 : goto err;
636 : #endif
637 :
638 : r_is_at_infinity = 1;
639 :
640 601143 : for (k = max_len - 1; k >= 0; k--) {
641 598791 : if (!r_is_at_infinity) {
642 596439 : if (!EC_POINT_dbl(group, r, r, ctx))
643 : goto err;
644 : }
645 :
646 598791 : for (i = 0; i < totalnum; i++) {
647 598791 : if (wNAF_len[i] > (size_t)k) {
648 598791 : int digit = wNAF[i][k];
649 : int is_neg;
650 :
651 598791 : if (digit) {
652 121443 : is_neg = digit < 0;
653 :
654 121443 : if (is_neg)
655 58920 : digit = -digit;
656 :
657 121443 : if (is_neg != r_is_inverted) {
658 59508 : if (!r_is_at_infinity) {
659 59508 : if (!EC_POINT_invert(group, r, ctx))
660 : goto err;
661 : }
662 59508 : r_is_inverted = !r_is_inverted;
663 : }
664 :
665 : /* digit > 0 */
666 :
667 121443 : if (r_is_at_infinity) {
668 2352 : if (!EC_POINT_copy(r, val_sub[i][digit >> 1]))
669 : goto err;
670 : r_is_at_infinity = 0;
671 : } else {
672 119091 : if (!EC_POINT_add
673 119091 : (group, r, r, val_sub[i][digit >> 1], ctx))
674 : goto err;
675 : }
676 : }
677 : }
678 : }
679 : }
680 :
681 2352 : if (r_is_at_infinity) {
682 0 : if (!EC_POINT_set_to_infinity(group, r))
683 : goto err;
684 : } else {
685 2352 : if (r_is_inverted)
686 1166 : if (!EC_POINT_invert(group, r, ctx))
687 : goto err;
688 : }
689 :
690 : ret = 1;
691 :
692 : err:
693 2352 : if (new_ctx != NULL)
694 0 : BN_CTX_free(new_ctx);
695 2352 : if (tmp != NULL)
696 2352 : EC_POINT_free(tmp);
697 2352 : if (wsize != NULL)
698 2352 : OPENSSL_free(wsize);
699 2352 : if (wNAF_len != NULL)
700 2352 : OPENSSL_free(wNAF_len);
701 2352 : if (wNAF != NULL) {
702 : signed char **w;
703 :
704 2352 : for (w = wNAF; *w != NULL; w++)
705 2352 : OPENSSL_free(*w);
706 :
707 2352 : OPENSSL_free(wNAF);
708 : }
709 2352 : if (val != NULL) {
710 9408 : for (v = val; *v != NULL; v++)
711 9408 : EC_POINT_clear_free(*v);
712 :
713 2352 : OPENSSL_free(val);
714 : }
715 2352 : if (val_sub != NULL) {
716 2352 : OPENSSL_free(val_sub);
717 : }
718 2352 : return ret;
719 : }
720 :
721 : /*-
722 : * ec_wNAF_precompute_mult()
723 : * creates an EC_PRE_COMP object with preprecomputed multiples of the generator
724 : * for use with wNAF splitting as implemented in ec_wNAF_mul().
725 : *
726 : * 'pre_comp->points' is an array of multiples of the generator
727 : * of the following form:
728 : * points[0] = generator;
729 : * points[1] = 3 * generator;
730 : * ...
731 : * points[2^(w-1)-1] = (2^(w-1)-1) * generator;
732 : * points[2^(w-1)] = 2^blocksize * generator;
733 : * points[2^(w-1)+1] = 3 * 2^blocksize * generator;
734 : * ...
735 : * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) * 2^(blocksize*(numblocks-2)) * generator
736 : * points[2^(w-1)*(numblocks-1)] = 2^(blocksize*(numblocks-1)) * generator
737 : * ...
738 : * points[2^(w-1)*numblocks-1] = (2^(w-1)) * 2^(blocksize*(numblocks-1)) * generator
739 : * points[2^(w-1)*numblocks] = NULL
740 : */
741 0 : int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
742 : {
743 : const EC_POINT *generator;
744 : EC_POINT *tmp_point = NULL, *base = NULL, **var;
745 : BN_CTX *new_ctx = NULL;
746 : BIGNUM *order;
747 : size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num;
748 : EC_POINT **points = NULL;
749 : EC_PRE_COMP *pre_comp;
750 : int ret = 0;
751 :
752 : /* if there is an old EC_PRE_COMP object, throw it away */
753 0 : EC_EX_DATA_free_data(&group->extra_data, ec_pre_comp_dup,
754 : ec_pre_comp_free, ec_pre_comp_clear_free);
755 :
756 0 : if ((pre_comp = ec_pre_comp_new(group)) == NULL)
757 : return 0;
758 :
759 0 : generator = EC_GROUP_get0_generator(group);
760 0 : if (generator == NULL) {
761 0 : ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR);
762 0 : goto err;
763 : }
764 :
765 0 : if (ctx == NULL) {
766 0 : ctx = new_ctx = BN_CTX_new();
767 0 : if (ctx == NULL)
768 : goto err;
769 : }
770 :
771 0 : BN_CTX_start(ctx);
772 0 : order = BN_CTX_get(ctx);
773 0 : if (order == NULL)
774 : goto err;
775 :
776 0 : if (!EC_GROUP_get_order(group, order, ctx))
777 : goto err;
778 0 : if (BN_is_zero(order)) {
779 0 : ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER);
780 0 : goto err;
781 : }
782 :
783 0 : bits = BN_num_bits(order);
784 : /*
785 : * The following parameters mean we precompute (approximately) one point
786 : * per bit. TBD: The combination 8, 4 is perfect for 160 bits; for other
787 : * bit lengths, other parameter combinations might provide better
788 : * efficiency.
789 : */
790 : blocksize = 8;
791 : w = 4;
792 0 : if (EC_window_bits_for_scalar_size(bits) > w) {
793 : /* let's not make the window too small ... */
794 0 : w = EC_window_bits_for_scalar_size(bits);
795 : }
796 :
797 0 : numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks
798 : * to use for wNAF
799 : * splitting */
800 :
801 0 : pre_points_per_block = (size_t)1 << (w - 1);
802 0 : num = pre_points_per_block * numblocks; /* number of points to compute
803 : * and store */
804 :
805 0 : points = OPENSSL_malloc(sizeof(EC_POINT *) * (num + 1));
806 0 : if (!points) {
807 0 : ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
808 0 : goto err;
809 : }
810 :
811 : var = points;
812 0 : var[num] = NULL; /* pivot */
813 0 : for (i = 0; i < num; i++) {
814 0 : if ((var[i] = EC_POINT_new(group)) == NULL) {
815 0 : ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
816 0 : goto err;
817 : }
818 : }
819 :
820 0 : if (!(tmp_point = EC_POINT_new(group)) || !(base = EC_POINT_new(group))) {
821 0 : ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
822 0 : goto err;
823 : }
824 :
825 0 : if (!EC_POINT_copy(base, generator))
826 : goto err;
827 :
828 : /* do the precomputation */
829 0 : for (i = 0; i < numblocks; i++) {
830 : size_t j;
831 :
832 0 : if (!EC_POINT_dbl(group, tmp_point, base, ctx))
833 : goto err;
834 :
835 0 : if (!EC_POINT_copy(*var++, base))
836 : goto err;
837 :
838 0 : for (j = 1; j < pre_points_per_block; j++, var++) {
839 : /*
840 : * calculate odd multiples of the current base point
841 : */
842 0 : if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx))
843 : goto err;
844 : }
845 :
846 0 : if (i < numblocks - 1) {
847 : /*
848 : * get the next base (multiply current one by 2^blocksize)
849 : */
850 : size_t k;
851 :
852 : if (blocksize <= 2) {
853 : ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_INTERNAL_ERROR);
854 : goto err;
855 : }
856 :
857 0 : if (!EC_POINT_dbl(group, base, tmp_point, ctx))
858 : goto err;
859 0 : for (k = 2; k < blocksize; k++) {
860 0 : if (!EC_POINT_dbl(group, base, base, ctx))
861 : goto err;
862 : }
863 : }
864 : }
865 :
866 0 : if (!EC_POINTs_make_affine(group, num, points, ctx))
867 : goto err;
868 :
869 0 : pre_comp->group = group;
870 0 : pre_comp->blocksize = blocksize;
871 0 : pre_comp->numblocks = numblocks;
872 0 : pre_comp->w = w;
873 0 : pre_comp->points = points;
874 : points = NULL;
875 0 : pre_comp->num = num;
876 :
877 0 : if (!EC_EX_DATA_set_data(&group->extra_data, pre_comp,
878 : ec_pre_comp_dup, ec_pre_comp_free,
879 : ec_pre_comp_clear_free))
880 : goto err;
881 : pre_comp = NULL;
882 :
883 : ret = 1;
884 : err:
885 0 : if (ctx != NULL)
886 0 : BN_CTX_end(ctx);
887 0 : if (new_ctx != NULL)
888 0 : BN_CTX_free(new_ctx);
889 0 : if (pre_comp)
890 0 : ec_pre_comp_free(pre_comp);
891 0 : if (points) {
892 : EC_POINT **p;
893 :
894 0 : for (p = points; *p != NULL; p++)
895 0 : EC_POINT_free(*p);
896 0 : OPENSSL_free(points);
897 : }
898 0 : if (tmp_point)
899 0 : EC_POINT_free(tmp_point);
900 0 : if (base)
901 0 : EC_POINT_free(base);
902 0 : return ret;
903 : }
904 :
905 0 : int ec_wNAF_have_precompute_mult(const EC_GROUP *group)
906 : {
907 0 : if (EC_EX_DATA_get_data
908 0 : (group->extra_data, ec_pre_comp_dup, ec_pre_comp_free,
909 : ec_pre_comp_clear_free) != NULL)
910 : return 1;
911 : else
912 0 : return 0;
913 : }
|
