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