OLD | NEW |
1 /* crypto/ec/ec_mult.c */ | 1 /* crypto/ec/ec_mult.c */ |
2 /* | 2 /* |
3 * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project. | 3 * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project. |
4 */ | 4 */ |
5 /* ==================================================================== | 5 /* ==================================================================== |
6 * Copyright (c) 1998-2007 The OpenSSL Project. All rights reserved. | 6 * Copyright (c) 1998-2007 The OpenSSL Project. All rights reserved. |
7 * | 7 * |
8 * Redistribution and use in source and binary forms, with or without | 8 * Redistribution and use in source and binary forms, with or without |
9 * modification, are permitted provided that the following conditions | 9 * modification, are permitted provided that the following conditions |
10 * are met: | 10 * are met: |
(...skipping 151 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
162 | 162 |
163 i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); | 163 i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP); |
164 if (i > 0) | 164 if (i > 0) |
165 return; | 165 return; |
166 | 166 |
167 if (pre->points) | 167 if (pre->points) |
168 { | 168 { |
169 EC_POINT **p; | 169 EC_POINT **p; |
170 | 170 |
171 for (p = pre->points; *p != NULL; p++) | 171 for (p = pre->points; *p != NULL; p++) |
| 172 { |
172 EC_POINT_clear_free(*p); | 173 EC_POINT_clear_free(*p); |
173 » » OPENSSL_cleanse(pre->points, sizeof pre->points); | 174 » » » OPENSSL_cleanse(p, sizeof *p); |
| 175 » » » } |
174 OPENSSL_free(pre->points); | 176 OPENSSL_free(pre->points); |
175 } | 177 } |
176 » OPENSSL_cleanse(pre, sizeof pre); | 178 » OPENSSL_cleanse(pre, sizeof *pre); |
177 OPENSSL_free(pre); | 179 OPENSSL_free(pre); |
178 } | 180 } |
179 | 181 |
180 | 182 |
181 | 183 |
182 | 184 |
183 /* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'. | 185 /* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'. |
184 * This is an array r[] of values that are either zero or odd with an | 186 * This is an array r[] of values that are either zero or odd with an |
185 * absolute value less than 2^w satisfying | 187 * absolute value less than 2^w satisfying |
186 * scalar = \sum_j r[j]*2^j | 188 * scalar = \sum_j r[j]*2^j |
(...skipping 30 matching lines...) Expand all Loading... |
217 } | 219 } |
218 bit = 1 << w; /* at most 128 */ | 220 bit = 1 << w; /* at most 128 */ |
219 next_bit = bit << 1; /* at most 256 */ | 221 next_bit = bit << 1; /* at most 256 */ |
220 mask = next_bit - 1; /* at most 255 */ | 222 mask = next_bit - 1; /* at most 255 */ |
221 | 223 |
222 if (BN_is_negative(scalar)) | 224 if (BN_is_negative(scalar)) |
223 { | 225 { |
224 sign = -1; | 226 sign = -1; |
225 } | 227 } |
226 | 228 |
| 229 if (scalar->d == NULL || scalar->top == 0) |
| 230 { |
| 231 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); |
| 232 goto err; |
| 233 } |
| 234 |
227 len = BN_num_bits(scalar); | 235 len = BN_num_bits(scalar); |
228 r = OPENSSL_malloc(len + 1); /* modified wNAF may be one digit longer th
an binary representation | 236 r = OPENSSL_malloc(len + 1); /* modified wNAF may be one digit longer th
an binary representation |
229 * (*ret_len will be set to the actual leng
th, i.e. at most | 237 * (*ret_len will be set to the actual leng
th, i.e. at most |
230 * BN_num_bits(scalar) + 1) */ | 238 * BN_num_bits(scalar) + 1) */ |
231 if (r == NULL) | 239 if (r == NULL) |
232 { | 240 { |
233 ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); | 241 ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE); |
234 goto err; | 242 goto err; |
235 } | 243 } |
236 | |
237 if (scalar->d == NULL || scalar->top == 0) | |
238 { | |
239 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR); | |
240 goto err; | |
241 } | |
242 window_val = scalar->d[0] & mask; | 244 window_val = scalar->d[0] & mask; |
243 j = 0; | 245 j = 0; |
244 while ((window_val != 0) || (j + w + 1 < len)) /* if j+w+1 >= len, windo
w_val will not increase */ | 246 while ((window_val != 0) || (j + w + 1 < len)) /* if j+w+1 >= len, windo
w_val will not increase */ |
245 { | 247 { |
246 int digit = 0; | 248 int digit = 0; |
247 | 249 |
248 /* 0 <= window_val <= 2^(w+1) */ | 250 /* 0 <= window_val <= 2^(w+1) */ |
249 | 251 |
250 if (window_val & 1) | 252 if (window_val & 1) |
251 { | 253 { |
(...skipping 160 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
412 blocksize = pre_comp->blocksize; | 414 blocksize = pre_comp->blocksize; |
413 | 415 |
414 /* determine maximum number of blocks that wNAF splittin
g may yield | 416 /* determine maximum number of blocks that wNAF splittin
g may yield |
415 * (NB: maximum wNAF length is bit length plus one) */ | 417 * (NB: maximum wNAF length is bit length plus one) */ |
416 numblocks = (BN_num_bits(scalar) / blocksize) + 1; | 418 numblocks = (BN_num_bits(scalar) / blocksize) + 1; |
417 | 419 |
418 /* we cannot use more blocks than we have precomputation
for */ | 420 /* we cannot use more blocks than we have precomputation
for */ |
419 if (numblocks > pre_comp->numblocks) | 421 if (numblocks > pre_comp->numblocks) |
420 numblocks = pre_comp->numblocks; | 422 numblocks = pre_comp->numblocks; |
421 | 423 |
422 » » » pre_points_per_block = 1u << (pre_comp->w - 1); | 424 » » » pre_points_per_block = (size_t)1 << (pre_comp->w - 1); |
423 | 425 |
424 /* check that pre_comp looks sane */ | 426 /* check that pre_comp looks sane */ |
425 if (pre_comp->num != (pre_comp->numblocks * pre_points_p
er_block)) | 427 if (pre_comp->num != (pre_comp->numblocks * pre_points_p
er_block)) |
426 { | 428 { |
427 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); | 429 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); |
428 goto err; | 430 goto err; |
429 } | 431 } |
430 } | 432 } |
431 else | 433 else |
432 { | 434 { |
(...skipping 21 matching lines...) Expand all Loading... |
454 | 456 |
455 /* num_val will be the total number of temporarily precomputed points */ | 457 /* num_val will be the total number of temporarily precomputed points */ |
456 num_val = 0; | 458 num_val = 0; |
457 | 459 |
458 for (i = 0; i < num + num_scalar; i++) | 460 for (i = 0; i < num + num_scalar; i++) |
459 { | 461 { |
460 size_t bits; | 462 size_t bits; |
461 | 463 |
462 bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar); | 464 bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar); |
463 wsize[i] = EC_window_bits_for_scalar_size(bits); | 465 wsize[i] = EC_window_bits_for_scalar_size(bits); |
464 » » num_val += 1u << (wsize[i] - 1); | 466 » » num_val += (size_t)1 << (wsize[i] - 1); |
465 wNAF[i + 1] = NULL; /* make sure we always have a pivot */ | 467 wNAF[i + 1] = NULL; /* make sure we always have a pivot */ |
466 wNAF[i] = compute_wNAF((i < num ? scalars[i] : scalar), wsize[i]
, &wNAF_len[i]); | 468 wNAF[i] = compute_wNAF((i < num ? scalars[i] : scalar), wsize[i]
, &wNAF_len[i]); |
467 if (wNAF[i] == NULL) | 469 if (wNAF[i] == NULL) |
468 goto err; | 470 goto err; |
469 if (wNAF_len[i] > max_len) | 471 if (wNAF_len[i] > max_len) |
470 max_len = wNAF_len[i]; | 472 max_len = wNAF_len[i]; |
471 } | 473 } |
472 | 474 |
473 if (numblocks) | 475 if (numblocks) |
474 { | 476 { |
(...skipping 118 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
593 ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); | 595 ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE); |
594 goto err; | 596 goto err; |
595 } | 597 } |
596 val[num_val] = NULL; /* pivot element */ | 598 val[num_val] = NULL; /* pivot element */ |
597 | 599 |
598 /* allocate points for precomputation */ | 600 /* allocate points for precomputation */ |
599 v = val; | 601 v = val; |
600 for (i = 0; i < num + num_scalar; i++) | 602 for (i = 0; i < num + num_scalar; i++) |
601 { | 603 { |
602 val_sub[i] = v; | 604 val_sub[i] = v; |
603 » » for (j = 0; j < (1u << (wsize[i] - 1)); j++) | 605 » » for (j = 0; j < ((size_t)1 << (wsize[i] - 1)); j++) |
604 { | 606 { |
605 *v = EC_POINT_new(group); | 607 *v = EC_POINT_new(group); |
606 if (*v == NULL) goto err; | 608 if (*v == NULL) goto err; |
607 v++; | 609 v++; |
608 } | 610 } |
609 } | 611 } |
610 if (!(v == val + num_val)) | 612 if (!(v == val + num_val)) |
611 { | 613 { |
612 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); | 614 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR); |
613 goto err; | 615 goto err; |
(...skipping 15 matching lines...) Expand all Loading... |
629 if (!EC_POINT_copy(val_sub[i][0], points[i])) goto err; | 631 if (!EC_POINT_copy(val_sub[i][0], points[i])) goto err; |
630 } | 632 } |
631 else | 633 else |
632 { | 634 { |
633 if (!EC_POINT_copy(val_sub[i][0], generator)) goto err; | 635 if (!EC_POINT_copy(val_sub[i][0], generator)) goto err; |
634 } | 636 } |
635 | 637 |
636 if (wsize[i] > 1) | 638 if (wsize[i] > 1) |
637 { | 639 { |
638 if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) goto
err; | 640 if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) goto
err; |
639 » » » for (j = 1; j < (1u << (wsize[i] - 1)); j++) | 641 » » » for (j = 1; j < ((size_t)1 << (wsize[i] - 1)); j++) |
640 { | 642 { |
641 if (!EC_POINT_add(group, val_sub[i][j], val_sub[
i][j - 1], tmp, ctx)) goto err; | 643 if (!EC_POINT_add(group, val_sub[i][j], val_sub[
i][j - 1], tmp, ctx)) goto err; |
642 } | 644 } |
643 } | 645 } |
644 } | 646 } |
645 | 647 |
646 #if 1 /* optional; EC_window_bits_for_scalar_size assumes we do this step */ | 648 #if 1 /* optional; EC_window_bits_for_scalar_size assumes we do this step */ |
647 if (!EC_POINTs_make_affine(group, num_val, val, ctx)) | 649 if (!EC_POINTs_make_affine(group, num_val, val, ctx)) |
648 goto err; | 650 goto err; |
649 #endif | 651 #endif |
(...skipping 163 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
813 blocksize = 8; | 815 blocksize = 8; |
814 w = 4; | 816 w = 4; |
815 if (EC_window_bits_for_scalar_size(bits) > w) | 817 if (EC_window_bits_for_scalar_size(bits) > w) |
816 { | 818 { |
817 /* let's not make the window too small ... */ | 819 /* let's not make the window too small ... */ |
818 w = EC_window_bits_for_scalar_size(bits); | 820 w = EC_window_bits_for_scalar_size(bits); |
819 } | 821 } |
820 | 822 |
821 numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks
to use for wNAF splitting */ | 823 numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks
to use for wNAF splitting */ |
822 | 824 |
823 » pre_points_per_block = 1u << (w - 1); | 825 » pre_points_per_block = (size_t)1 << (w - 1); |
824 num = pre_points_per_block * numblocks; /* number of points to compute a
nd store */ | 826 num = pre_points_per_block * numblocks; /* number of points to compute a
nd store */ |
825 | 827 |
826 points = OPENSSL_malloc(sizeof (EC_POINT*)*(num + 1)); | 828 points = OPENSSL_malloc(sizeof (EC_POINT*)*(num + 1)); |
827 if (!points) | 829 if (!points) |
828 { | 830 { |
829 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); | 831 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE); |
830 goto err; | 832 goto err; |
831 } | 833 } |
832 | 834 |
833 var = points; | 835 var = points; |
(...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
929 } | 931 } |
930 | 932 |
931 | 933 |
932 int ec_wNAF_have_precompute_mult(const EC_GROUP *group) | 934 int ec_wNAF_have_precompute_mult(const EC_GROUP *group) |
933 { | 935 { |
934 if (EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_
free, ec_pre_comp_clear_free) != NULL) | 936 if (EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_
free, ec_pre_comp_clear_free) != NULL) |
935 return 1; | 937 return 1; |
936 else | 938 else |
937 return 0; | 939 return 0; |
938 } | 940 } |
OLD | NEW |