| 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 |