[331] | 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 | }
|
---|