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