64 #if defined( INC_ALL )
71 #pragma warning( disable: 4267 )
74 #if defined( USE_ECDH ) || defined( USE_ECDSA )
87 typedef struct ec_pre_comp_st {
99 static void *ec_pre_comp_dup(
void *);
100 static void ec_pre_comp_free(
void *);
101 static void ec_pre_comp_clear_free(
void *);
103 static EC_PRE_COMP *ec_pre_comp_new(
const EC_GROUP *group)
105 EC_PRE_COMP *ret = NULL;
110 ret = (EC_PRE_COMP *)
clBnAlloc(
"ec_pre_comp_new",
sizeof(EC_PRE_COMP));
126 static void *ec_pre_comp_dup(
void *src_)
130 CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP);
135 static void ec_pre_comp_free(
void *pre_)
138 EC_PRE_COMP *pre = pre_;
143 i =
CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP);
151 for (p = pre->points; *p != NULL; p++)
158 static void ec_pre_comp_clear_free(
void *pre_)
161 EC_PRE_COMP *pre = pre_;
166 i =
CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP);
174 for (p = pre->points; *p != NULL; p++)
194 static signed char *compute_wNAF(
const BIGNUM *scalar,
int w,
size_t *ret_len)
198 signed char *r = NULL;
200 int bit, next_bit, mask;
241 if (scalar->
d == NULL || scalar->
top == 0)
246 window_val = scalar->
d[0] & mask;
248 while ((window_val != 0) || (j + w + 1 < len))
258 if (window_val & bit)
260 digit = window_val - next_bit;
263 if (j + w + 1 >= len)
270 digit = window_val & (mask >> 1);
279 if (digit <= -bit || digit >= bit || !(digit & 1))
290 if (window_val != 0 && window_val != next_bit && window_val != bit)
297 r[j++] = sign * digit;
302 if (window_val > next_bit)
333 #define EC_window_bits_for_scalar_size(b) \
355 size_t blocksize = 0, numblocks = 0;
356 size_t pre_points_per_block = 0;
359 int r_is_inverted = 0;
360 int r_is_at_infinity = 1;
361 size_t *wsize = NULL;
362 signed char **wNAF = NULL;
363 size_t *wNAF_len = NULL;
369 const EC_PRE_COMP *pre_comp = NULL;
380 if ((scalar == NULL) && (num == 0))
385 for (i = 0; i < num; i++)
404 if (generator == NULL)
414 if (pre_comp && pre_comp->numblocks && (
EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) == 0))
416 blocksize = pre_comp->blocksize;
423 if (numblocks > pre_comp->numblocks)
424 numblocks = pre_comp->numblocks;
426 pre_points_per_block = 1u << (pre_comp->w - 1);
429 if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block))
444 totalnum = num + numblocks;
446 wsize =
clBnAlloc(
"ec_wNAF_mul", totalnum *
sizeof wsize[0]);
447 wNAF_len =
clBnAlloc(
"ec_wNAF_mul", totalnum *
sizeof wNAF_len[0]);
448 wNAF =
clBnAlloc(
"ec_wNAF_mul", (totalnum + 1) *
sizeof wNAF[0]);
449 val_sub =
clBnAlloc(
"ec_wNAF_mul", totalnum *
sizeof val_sub[0]);
451 if (!wsize || !wNAF_len || !wNAF || !val_sub)
462 for (i = 0; i < num + num_scalar; i++)
466 bits = i < num ?
BN_num_bits(scalars[i]) : BN_num_bits(scalar);
467 wsize[i] = EC_window_bits_for_scalar_size(bits);
468 num_val += 1u << (wsize[i] - 1);
470 wNAF[i] = compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], &wNAF_len[i]);
473 if (wNAF_len[i] > max_len)
474 max_len = wNAF_len[i];
481 if (pre_comp == NULL)
492 signed char *tmp_wNAF = NULL;
502 wsize[num] = pre_comp->w;
503 tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len);
507 if (tmp_len <= max_len)
515 wNAF[num] = tmp_wNAF;
516 wNAF[num + 1] = NULL;
517 wNAF_len[num] = tmp_len;
518 if (tmp_len > max_len)
521 val_sub[num] = pre_comp->points;
531 if (tmp_len < numblocks * blocksize)
534 numblocks = (tmp_len + blocksize - 1) / blocksize;
535 if (numblocks > pre_comp->numblocks)
540 totalnum = num + numblocks;
545 tmp_points = pre_comp->points;
547 for (i = num; i < totalnum; i++)
549 if (i < totalnum - 1)
551 wNAF_len[i] = blocksize;
552 if (tmp_len < blocksize)
557 tmp_len -= blocksize;
562 wNAF_len[i] = tmp_len;
565 wNAF[i] =
clBnAlloc(
"ec_wNAF_mul", wNAF_len[i]);
572 memcpy(wNAF[i], pp, wNAF_len[i]);
573 if (wNAF_len[i] > max_len)
574 max_len = wNAF_len[i];
576 if (*tmp_points == NULL)
582 val_sub[i] = tmp_points;
583 tmp_points += pre_points_per_block;
594 val =
clBnAlloc(
"ec_wNAF_mul", (num_val + 1) *
sizeof val[0]);
604 for (i = 0; i < num + num_scalar; i++)
607 for (j = 0; j < (1u << (wsize[i] - 1)); j++)
610 if (*v == NULL)
goto err;
614 if (!(v == val + num_val))
629 for (i = 0; i < num + num_scalar; i++)
642 if (!
EC_POINT_dbl(group, tmp, val_sub[i][0], ctx))
goto err;
643 for (j = 1; j < (1u << (wsize[i] - 1)); j++)
645 if (!
EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx))
goto err;
655 r_is_at_infinity = 1;
657 for (k = max_len - 1; k >= 0; k--)
659 if (!r_is_at_infinity)
664 for (i = 0; i < totalnum; i++)
666 if (wNAF_len[i] > (
size_t)k)
668 int digit = wNAF[i][k];
678 if (is_neg != r_is_inverted)
680 if (!r_is_at_infinity)
684 r_is_inverted = !r_is_inverted;
689 if (r_is_at_infinity)
692 r_is_at_infinity = 0;
696 if (!
EC_POINT_add(group, r, r, val_sub[i][digit >> 1], ctx))
goto err;
703 if (r_is_at_infinity)
722 if (wNAF_len != NULL)
728 for (w = wNAF; *w != NULL; w++)
735 for (v = val; *v != NULL; v++)
770 EC_POINT *tmp_point = NULL, *base = NULL, **var;
773 size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num;
775 EC_PRE_COMP *pre_comp;
781 if ((pre_comp = ec_pre_comp_new(group)) == NULL)
785 if (generator == NULL)
800 if (order == NULL)
goto err;
819 if (EC_window_bits_for_scalar_size(bits) > w)
822 w = EC_window_bits_for_scalar_size(bits);
825 numblocks = (bits + blocksize - 1) / blocksize;
827 pre_points_per_block = 1u << (w - 1);
828 num = pre_points_per_block * numblocks;
839 for (i = 0; i < num; i++)
858 for (i = 0; i < numblocks; i++)
868 for (j = 1; j < pre_points_per_block; j++, var++)
871 if (!
EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx))
875 if (i < numblocks - 1)
888 for (k = 2; k < blocksize; k++)
899 pre_comp->group = group;
900 pre_comp->blocksize = blocksize;
901 pre_comp->numblocks = numblocks;
903 pre_comp->points = points;
908 ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free))
919 ec_pre_comp_free(pre_comp);
924 for (p = points; *p != NULL; p++)