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