crypto/libressl/crypto/ec/ec_mult.c

   1 /* $OpenBSD: ec_mult.c,v 1.18 2015/02/15 08:44:35 miod Exp $ */
   2 /*
   3  * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project.
   4  */
   5 /* ====================================================================
   6  * Copyright (c) 1998-2007 The OpenSSL Project.  All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  *
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in
  17  *    the documentation and/or other materials provided with the
  18  *    distribution.
  19  *
  20  * 3. All advertising materials mentioning features or use of this
  21  *    software must display the following acknowledgment:
  22  *    "This product includes software developed by the OpenSSL Project
  23  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  24  *
  25  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  26  *    endorse or promote products derived from this software without
  27  *    prior written permission. For written permission, please contact
  28  *    openssl-core@openssl.org.
  29  *
  30  * 5. Products derived from this software may not be called "OpenSSL"
  31  *    nor may "OpenSSL" appear in their names without prior written
  32  *    permission of the OpenSSL Project.
  33  *
  34  * 6. Redistributions of any form whatsoever must retain the following
  35  *    acknowledgment:
  36  *    "This product includes software developed by the OpenSSL Project
  37  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  38  *
  39  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  40  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  41  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  42  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  43  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  44  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  45  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  46  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  48  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  49  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  50  * OF THE POSSIBILITY OF SUCH DAMAGE.
  51  * ====================================================================
  52  *
  53  * This product includes cryptographic software written by Eric Young
  54  * (eay@cryptsoft.com).  This product includes software written by Tim
  55  * Hudson (tjh@cryptsoft.com).
  56  *
  57  */
  58 /* ====================================================================
  59  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  60  * Portions of this software developed by SUN MICROSYSTEMS, INC.,
  61  * and contributed to the OpenSSL project.
  62  */
  63
  64 #include <string.h>
  65
  66 #include <openssl/err.h>
  67
  68 #include "ec_lcl.h"
  69
  70
  71 /*
  72  * This file implements the wNAF-based interleaving multi-exponentation method
  73  * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp>);
  74  * for multiplication with precomputation, we use wNAF splitting
  75  * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp>).
  76  */
  77
  78
  79
  80
  81 /* structure for precomputed multiples of the generator */
  82 typedef struct ec_pre_comp_st {
  83         const EC_GROUP *group;  /* parent EC_GROUP object */
  84         size_t blocksize;       /* block size for wNAF splitting */
  85         size_t numblocks;       /* max. number of blocks for which we have
  86                                  * precomputation */
  87         size_t w;               /* window size */
  88         EC_POINT **points;      /* array with pre-calculated multiples of
  89                                  * generator: 'num' pointers to EC_POINT
  90                                  * objects followed by a NULL */
  91         size_t num;             /* numblocks * 2^(w-1) */
  92         int references;
  93 } EC_PRE_COMP;
  94
  95 /* functions to manage EC_PRE_COMP within the EC_GROUP extra_data framework */
  96 static void *ec_pre_comp_dup(void *);
  97 static void ec_pre_comp_free(void *);
  98 static void ec_pre_comp_clear_free(void *);
  99
 100 static EC_PRE_COMP *
 101 ec_pre_comp_new(const EC_GROUP * group)
 102 {
 103         EC_PRE_COMP *ret = NULL;
 104
 105         if (!group)
 106                 return NULL;
 107
 108         ret = malloc(sizeof(EC_PRE_COMP));
 109         if (!ret) {
 110                 ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE);
 111                 return ret;
 112         }
 113         ret->group = group;
 114         ret->blocksize = 8;     /* default */
 115         ret->numblocks = 0;
 116         ret->w = 4;             /* default */
 117         ret->points = NULL;
 118         ret->num = 0;
 119         ret->references = 1;
 120         return ret;
 121 }
 122
 123 static void *
 124 ec_pre_comp_dup(void *src_)
 125 {
 126         EC_PRE_COMP *src = src_;
 127
 128         /* no need to actually copy, these objects never change! */
 129
 130         CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP);
 131
 132         return src_;
 133 }
 134
 135 static void
 136 ec_pre_comp_free(void *pre_)
 137 {
 138         int i;
 139         EC_PRE_COMP *pre = pre_;
 140
 141         if (!pre)
 142                 return;
 143
 144         i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP);
 145         if (i > 0)
 146                 return;
 147
 148         if (pre->points) {
 149                 EC_POINT **p;
 150
 151                 for (p = pre->points; *p != NULL; p++)
 152                         EC_POINT_free(*p);
 153                 free(pre->points);
 154         }
 155         free(pre);
 156 }
 157
 158 static void
 159 ec_pre_comp_clear_free(void *pre_)
 160 {
 161         int i;
 162         EC_PRE_COMP *pre = pre_;
 163
 164         if (!pre)
 165                 return;
 166
 167         i = CRYPTO_add(&pre->references, -1, CRYPTO_LOCK_EC_PRE_COMP);
 168         if (i > 0)
 169                 return;
 170
 171         if (pre->points) {
 172                 EC_POINT **p;
 173
 174                 for (p = pre->points; *p != NULL; p++) {
 175                         EC_POINT_clear_free(*p);
 176                         explicit_bzero(p, sizeof *p);
 177                 }
 178                 free(pre->points);
 179         }
 180         explicit_bzero(pre, sizeof *pre);
 181         free(pre);
 182 }
 183
 184
 185
 186
 187 /* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
 188  * This is an array  r[]  of values that are either zero or odd with an
 189  * absolute value less than  2^w  satisfying
 190  *     scalar = \sum_j r[j]*2^j
 191  * where at most one of any  w+1  consecutive digits is non-zero
 192  * with the exception that the most significant digit may be only
 193  * w-1 zeros away from that next non-zero digit.
 194  */
 195 static signed char *
 196 compute_wNAF(const BIGNUM * scalar, int w, size_t * ret_len)
 197 {
 198         int window_val;
 199         int ok = 0;
 200         signed char *r = NULL;
 201         int sign = 1;
 202         int bit, next_bit, mask;
 203         size_t len = 0, j;
 204
 205         if (BN_is_zero(scalar)) {
 206                 r = malloc(1);
 207                 if (!r) {
 208                         ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
 209                         goto err;
 210                 }
 211                 r[0] = 0;
 212                 *ret_len = 1;
 213                 return r;
 214         }
 215         if (w <= 0 || w > 7) {
 216                 /* 'signed char' can represent integers with
 217                  * absolute values less than 2^7 */
 218                 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 219                 goto err;
 220         }
 221         bit = 1 << w;           /* at most 128 */
 222         next_bit = bit << 1;    /* at most 256 */
 223         mask = next_bit - 1;    /* at most 255 */
 224
 225         if (BN_is_negative(scalar)) {
 226                 sign = -1;
 227         }
 228         if (scalar->d == NULL || scalar->top == 0) {
 229                 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 230                 goto err;
 231         }
 232         len = BN_num_bits(scalar);
 233         r = malloc(len + 1);    /* modified wNAF may be one digit longer than
 234                                  * binary representation (*ret_len will be
 235                                  * set to the actual length, i.e. at most
 236                                  * BN_num_bits(scalar) + 1) */
 237         if (r == NULL) {
 238                 ECerr(EC_F_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
 239                 goto err;
 240         }
 241         window_val = scalar->d[0] & mask;
 242         j = 0;
 243         while ((window_val != 0) || (j + w + 1 < len)) {
 244                 /* if j+w+1 >= len, window_val will not increase */
 245                 int digit = 0;
 246
 247                 /* 0 <= window_val <= 2^(w+1) */
 248                 if (window_val & 1) {
 249                         /* 0 < window_val < 2^(w+1) */
 250                         if (window_val & bit) {
 251                                 digit = window_val - next_bit;  /* -2^w < digit < 0 */
 252
 253 #if 1                           /* modified wNAF */
 254                                 if (j + w + 1 >= len) {
 255                                         /*
 256                                          * special case for generating
 257                                          * modified wNAFs: no new bits will
 258                                          * be added into window_val, so using
 259                                          * a positive digit here will
 260                                          * decrease the total length of the
 261                                          * representation
 262                                          */
 263
 264                                         digit = window_val & (mask >> 1);       /* 0 < digit < 2^w */
 265                                 }
 266 #endif
 267                         } else {
 268                                 digit = window_val;     /* 0 < digit < 2^w */
 269                         }
 270
 271                         if (digit <= -bit || digit >= bit || !(digit & 1)) {
 272                                 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 273                                 goto err;
 274                         }
 275                         window_val -= digit;
 276
 277                         /*
 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
 281                          */
 282                         if (window_val != 0 && window_val != next_bit && window_val != bit) {
 283                                 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 284                                 goto err;
 285                         }
 286                 }
 287                 r[j++] = sign * digit;
 288
 289                 window_val >>= 1;
 290                 window_val += bit * BN_is_bit_set(scalar, j + w);
 291
 292                 if (window_val > next_bit) {
 293                         ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 294                         goto err;
 295                 }
 296         }
 297
 298         if (j > len + 1) {
 299                 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 300                 goto err;
 301         }
 302         len = j;
 303         ok = 1;
 304
 305 err:
 306         if (!ok) {
 307                 free(r);
 308                 r = NULL;
 309         }
 310         if (ok)
 311                 *ret_len = len;
 312         return r;
 313 }
 314
 315
 316 /* TODO: table should be optimised for the wNAF-based implementation,
 317  *       sometimes smaller windows will give better performance
 318  *       (thus the boundaries should be increased)
 319  */
 320 #define EC_window_bits_for_scalar_size(b) \
 321                 ((size_t) \
 322                  ((b) >= 2000 ? 6 : \
 323                   (b) >=  800 ? 5 : \
 324                   (b) >=  300 ? 4 : \
 325                   (b) >=   70 ? 3 : \
 326                   (b) >=   20 ? 2 : \
 327                   1))
 328
 329 /* Compute
 330  *      \sum scalars[i]*points[i],
 331  * also including
 332  *      scalar*generator
 333  * in the addition if scalar != NULL
 334  */
 335 int
 336 ec_wNAF_mul(const EC_GROUP * group, EC_POINT * r, const BIGNUM * scalar,
 337     size_t num, const EC_POINT * points[], const BIGNUM * scalars[], BN_CTX * ctx)
 338 {
 339         BN_CTX *new_ctx = NULL;
 340         const EC_POINT *generator = NULL;
 341         EC_POINT *tmp = NULL;
 342         size_t totalnum;
 343         size_t blocksize = 0, numblocks = 0;    /* for wNAF splitting */
 344         size_t pre_points_per_block = 0;
 345         size_t i, j;
 346         int k;
 347         int r_is_inverted = 0;
 348         int r_is_at_infinity = 1;
 349         size_t *wsize = NULL;   /* individual window sizes */
 350         signed char **wNAF = NULL;      /* individual wNAFs */
 351         signed char *tmp_wNAF = NULL;
 352         size_t *wNAF_len = NULL;
 353         size_t max_len = 0;
 354         size_t num_val;
 355         EC_POINT **val = NULL;  /* precomputation */
 356         EC_POINT **v;
 357         EC_POINT ***val_sub = NULL;     /* pointers to sub-arrays of 'val' or
 358                                          * 'pre_comp->points' */
 359         const EC_PRE_COMP *pre_comp = NULL;
 360         int num_scalar = 0;     /* flag: will be set to 1 if 'scalar' must be
 361                                  * treated like other scalars, i.e.
 362                                  * precomputation is not available */
 363         int ret = 0;
 364
 365         if (group->meth != r->meth) {
 366                 ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
 367                 return 0;
 368         }
 369         if ((scalar == NULL) && (num == 0)) {
 370                 return EC_POINT_set_to_infinity(group, r);
 371         }
 372         for (i = 0; i < num; i++) {
 373                 if (group->meth != points[i]->meth) {
 374                         ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
 375                         return 0;
 376                 }
 377         }
 378
 379         if (ctx == NULL) {
 380                 ctx = new_ctx = BN_CTX_new();
 381                 if (ctx == NULL)
 382                         goto err;
 383         }
 384         if (scalar != NULL) {
 385                 generator = EC_GROUP_get0_generator(group);
 386                 if (generator == NULL) {
 387                         ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR);
 388                         goto err;
 389                 }
 390                 /* look if we can use precomputed multiples of generator */
 391
 392                 pre_comp = EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free);
 393
 394                 if (pre_comp && pre_comp->numblocks &&
 395                     (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) == 0)) {
 396                         blocksize = pre_comp->blocksize;
 397
 398                         /*
 399                          * determine maximum number of blocks that wNAF
 400                          * splitting may yield (NB: maximum wNAF length is
 401                          * bit length plus one)
 402                          */
 403                         numblocks = (BN_num_bits(scalar) / blocksize) + 1;
 404
 405                         /*
 406                          * we cannot use more blocks than we have
 407                          * precomputation for
 408                          */
 409                         if (numblocks > pre_comp->numblocks)
 410                                 numblocks = pre_comp->numblocks;
 411
 412                         pre_points_per_block = (size_t) 1 << (pre_comp->w - 1);
 413
 414                         /* check that pre_comp looks sane */
 415                         if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block)) {
 416                                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 417                                 goto err;
 418                         }
 419                 } else {
 420                         /* can't use precomputation */
 421                         pre_comp = NULL;
 422                         numblocks = 1;
 423                         num_scalar = 1; /* treat 'scalar' like 'num'-th
 424                                          * element of 'scalars' */
 425                 }
 426         }
 427         totalnum = num + numblocks;
 428
 429         /* includes space for pivot */
 430         wNAF = reallocarray(NULL, (totalnum + 1), sizeof wNAF[0]);
 431         if (wNAF == NULL) {
 432                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE);
 433                 goto err;
 434         }
 435
 436         wNAF[0] = NULL;         /* preliminary pivot */
 437
 438         wsize = reallocarray(NULL, totalnum, sizeof wsize[0]);
 439         wNAF_len = reallocarray(NULL, totalnum, sizeof wNAF_len[0]);
 440         val_sub = reallocarray(NULL, totalnum, sizeof val_sub[0]);
 441
 442         if (wsize == NULL || wNAF_len == NULL || val_sub == NULL) {
 443                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE);
 444                 goto err;
 445         }
 446
 447         /* num_val will be the total number of temporarily precomputed points */
 448         num_val = 0;
 449
 450         for (i = 0; i < num + num_scalar; i++) {
 451                 size_t bits;
 452
 453                 bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar);
 454                 wsize[i] = EC_window_bits_for_scalar_size(bits);
 455                 num_val += (size_t) 1 << (wsize[i] - 1);
 456                 wNAF[i + 1] = NULL;     /* make sure we always have a pivot */
 457                 wNAF[i] = compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], &wNAF_len[i]);
 458                 if (wNAF[i] == NULL)
 459                         goto err;
 460                 if (wNAF_len[i] > max_len)
 461                         max_len = wNAF_len[i];
 462         }
 463
 464         if (numblocks) {
 465                 /* we go here iff scalar != NULL */
 466
 467                 if (pre_comp == NULL) {
 468                         if (num_scalar != 1) {
 469                                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 470                                 goto err;
 471                         }
 472                         /* we have already generated a wNAF for 'scalar' */
 473                 } else {
 474                         size_t tmp_len = 0;
 475
 476                         if (num_scalar != 0) {
 477                                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 478                                 goto err;
 479                         }
 480                         /*
 481                          * use the window size for which we have
 482                          * precomputation
 483                          */
 484                         wsize[num] = pre_comp->w;
 485                         tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len);
 486                         if (tmp_wNAF == NULL)
 487                                 goto err;
 488
 489                         if (tmp_len <= max_len) {
 490                                 /*
 491                                  * One of the other wNAFs is at least as long
 492                                  * as the wNAF belonging to the generator, so
 493                                  * wNAF splitting will not buy us anything.
 494                                  */
 495
 496                                 numblocks = 1;
 497                                 totalnum = num + 1;     /* don't use wNAF
 498                                                          * splitting */
 499                                 wNAF[num] = tmp_wNAF;
 500                                 tmp_wNAF = NULL;
 501                                 wNAF[num + 1] = NULL;
 502                                 wNAF_len[num] = tmp_len;
 503                                 if (tmp_len > max_len)
 504                                         max_len = tmp_len;
 505                                 /*
 506                                  * pre_comp->points starts with the points
 507                                  * that we need here:
 508                                  */
 509                                 val_sub[num] = pre_comp->points;
 510                         } else {
 511                                 /*
 512                                  * don't include tmp_wNAF directly into wNAF
 513                                  * array - use wNAF splitting and include the
 514                                  * blocks
 515                                  */
 516
 517                                 signed char *pp;
 518                                 EC_POINT **tmp_points;
 519
 520                                 if (tmp_len < numblocks * blocksize) {
 521                                         /*
 522                                          * possibly we can do with fewer
 523                                          * blocks than estimated
 524                                          */
 525                                         numblocks = (tmp_len + blocksize - 1) / blocksize;
 526                                         if (numblocks > pre_comp->numblocks) {
 527                                                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 528                                                 goto err;
 529                                         }
 530                                         totalnum = num + numblocks;
 531                                 }
 532                                 /* split wNAF in 'numblocks' parts */
 533                                 pp = tmp_wNAF;
 534                                 tmp_points = pre_comp->points;
 535
 536                                 for (i = num; i < totalnum; i++) {
 537                                         if (i < totalnum - 1) {
 538                                                 wNAF_len[i] = blocksize;
 539                                                 if (tmp_len < blocksize) {
 540                                                         ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 541                                                         goto err;
 542                                                 }
 543                                                 tmp_len -= blocksize;
 544                                         } else
 545                                                 /*
 546                                                  * last block gets whatever
 547                                                  * is left (this could be
 548                                                  * more or less than
 549                                                  * 'blocksize'!)
 550                                                  */
 551                                                 wNAF_len[i] = tmp_len;
 552
 553                                         wNAF[i + 1] = NULL;
 554                                         wNAF[i] = malloc(wNAF_len[i]);
 555                                         if (wNAF[i] == NULL) {
 556                                                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE);
 557                                                 goto err;
 558                                         }
 559                                         memcpy(wNAF[i], pp, wNAF_len[i]);
 560                                         if (wNAF_len[i] > max_len)
 561                                                 max_len = wNAF_len[i];
 562
 563                                         if (*tmp_points == NULL) {
 564                                                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 565                                                 goto err;
 566                                         }
 567                                         val_sub[i] = tmp_points;
 568                                         tmp_points += pre_points_per_block;
 569                                         pp += blocksize;
 570                                 }
 571                         }
 572                 }
 573         }
 574         /*
 575          * All points we precompute now go into a single array 'val'.
 576          * 'val_sub[i]' is a pointer to the subarray for the i-th point, or
 577          * to a subarray of 'pre_comp->points' if we already have
 578          * precomputation.
 579          */
 580         val = reallocarray(NULL, (num_val + 1), sizeof val[0]);
 581         if (val == NULL) {
 582                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_MALLOC_FAILURE);
 583                 goto err;
 584         }
 585         val[num_val] = NULL;    /* pivot element */
 586
 587         /* allocate points for precomputation */
 588         v = val;
 589         for (i = 0; i < num + num_scalar; i++) {
 590                 val_sub[i] = v;
 591                 for (j = 0; j < ((size_t) 1 << (wsize[i] - 1)); j++) {
 592                         *v = EC_POINT_new(group);
 593                         if (*v == NULL)
 594                                 goto err;
 595                         v++;
 596                 }
 597         }
 598         if (!(v == val + num_val)) {
 599                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 600                 goto err;
 601         }
 602         if (!(tmp = EC_POINT_new(group)))
 603                 goto err;
 604
 605         /*
 606          * prepare precomputed values: val_sub[i][0] :=     points[i]
 607          * val_sub[i][1] := 3 * points[i] val_sub[i][2] := 5 * points[i] ...
 608          */
 609         for (i = 0; i < num + num_scalar; i++) {
 610                 if (i < num) {
 611                         if (!EC_POINT_copy(val_sub[i][0], points[i]))
 612                                 goto err;
 613                 } else {
 614                         if (!EC_POINT_copy(val_sub[i][0], generator))
 615                                 goto err;
 616                 }
 617
 618                 if (wsize[i] > 1) {
 619                         if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx))
 620                                 goto err;
 621                         for (j = 1; j < ((size_t) 1 << (wsize[i] - 1)); j++) {
 622                                 if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx))
 623                                         goto err;
 624                         }
 625                 }
 626         }
 627
 628         if (!EC_POINTs_make_affine(group, num_val, val, ctx))
 629                 goto err;
 630
 631         r_is_at_infinity = 1;
 632
 633         for (k = max_len - 1; k >= 0; k--) {
 634                 if (!r_is_at_infinity) {
 635                         if (!EC_POINT_dbl(group, r, r, ctx))
 636                                 goto err;
 637                 }
 638                 for (i = 0; i < totalnum; i++) {
 639                         if (wNAF_len[i] > (size_t) k) {
 640                                 int digit = wNAF[i][k];
 641                                 int is_neg;
 642
 643                                 if (digit) {
 644                                         is_neg = digit < 0;
 645
 646                                         if (is_neg)
 647                                                 digit = -digit;
 648
 649                                         if (is_neg != r_is_inverted) {
 650                                                 if (!r_is_at_infinity) {
 651                                                         if (!EC_POINT_invert(group, r, ctx))
 652                                                                 goto err;
 653                                                 }
 654                                                 r_is_inverted = !r_is_inverted;
 655                                         }
 656                                         /* digit > 0 */
 657
 658                                         if (r_is_at_infinity) {
 659                                                 if (!EC_POINT_copy(r, val_sub[i][digit >> 1]))
 660                                                         goto err;
 661                                                 r_is_at_infinity = 0;
 662                                         } else {
 663                                                 if (!EC_POINT_add(group, r, r, val_sub[i][digit >> 1], ctx))
 664                                                         goto err;
 665                                         }
 666                                 }
 667                         }
 668                 }
 669         }
 670
 671         if (r_is_at_infinity) {
 672                 if (!EC_POINT_set_to_infinity(group, r))
 673                         goto err;
 674         } else {
 675                 if (r_is_inverted)
 676                         if (!EC_POINT_invert(group, r, ctx))
 677                                 goto err;
 678         }
 679
 680         ret = 1;
 681
 682 err:
 683         BN_CTX_free(new_ctx);
 684         EC_POINT_free(tmp);
 685         free(wsize);
 686         free(wNAF_len);
 687         free(tmp_wNAF);
 688         if (wNAF != NULL) {
 689                 signed char **w;
 690
 691                 for (w = wNAF; *w != NULL; w++)
 692                         free(*w);
 693
 694                 free(wNAF);
 695         }
 696         if (val != NULL) {
 697                 for (v = val; *v != NULL; v++)
 698                         EC_POINT_clear_free(*v);
 699                 free(val);
 700         }
 701         free(val_sub);
 702         return ret;
 703 }
 704
 705
 706 /* ec_wNAF_precompute_mult()
 707  * creates an EC_PRE_COMP object with preprecomputed multiples of the generator
 708  * for use with wNAF splitting as implemented in ec_wNAF_mul().
 709  *
 710  * 'pre_comp->points' is an array of multiples of the generator
 711  * of the following form:
 712  * points[0] =     generator;
 713  * points[1] = 3 * generator;
 714  * ...
 715  * points[2^(w-1)-1] =     (2^(w-1)-1) * generator;
 716  * points[2^(w-1)]   =     2^blocksize * generator;
 717  * points[2^(w-1)+1] = 3 * 2^blocksize * generator;
 718  * ...
 719  * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) *  2^(blocksize*(numblocks-2)) * generator
 720  * points[2^(w-1)*(numblocks-1)]   =              2^(blocksize*(numblocks-1)) * generator
 721  * ...
 722  * points[2^(w-1)*numblocks-1]     = (2^(w-1)) *  2^(blocksize*(numblocks-1)) * generator
 723  * points[2^(w-1)*numblocks]       = NULL
 724  */
 725 int
 726 ec_wNAF_precompute_mult(EC_GROUP * group, BN_CTX * ctx)
 727 {
 728         const EC_POINT *generator;
 729         EC_POINT *tmp_point = NULL, *base = NULL, **var;
 730         BN_CTX *new_ctx = NULL;
 731         BIGNUM *order;
 732         size_t i, bits, w, pre_points_per_block, blocksize, numblocks,
 733          num;
 734         EC_POINT **points = NULL;
 735         EC_PRE_COMP *pre_comp;
 736         int ret = 0;
 737
 738         /* if there is an old EC_PRE_COMP object, throw it away */
 739         EC_EX_DATA_free_data(&group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free);
 740
 741         if ((pre_comp = ec_pre_comp_new(group)) == NULL)
 742                 return 0;
 743
 744         generator = EC_GROUP_get0_generator(group);
 745         if (generator == NULL) {
 746                 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR);
 747                 goto err;
 748         }
 749         if (ctx == NULL) {
 750                 ctx = new_ctx = BN_CTX_new();
 751                 if (ctx == NULL)
 752                         goto err;
 753         }
 754         BN_CTX_start(ctx);
 755         if ((order = BN_CTX_get(ctx)) == NULL)
 756                 goto err;
 757
 758         if (!EC_GROUP_get_order(group, order, ctx))
 759                 goto err;
 760         if (BN_is_zero(order)) {
 761                 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER);
 762                 goto err;
 763         }
 764         bits = BN_num_bits(order);
 765         /*
 766          * The following parameters mean we precompute (approximately) one
 767          * point per bit.
 768          *
 769          * TBD: The combination  8, 4  is perfect for 160 bits; for other bit
 770          * lengths, other parameter combinations might provide better
 771          * efficiency.
 772          */
 773         blocksize = 8;
 774         w = 4;
 775         if (EC_window_bits_for_scalar_size(bits) > w) {
 776                 /* let's not make the window too small ... */
 777                 w = EC_window_bits_for_scalar_size(bits);
 778         }
 779         numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks
 780                                                          * to use for wNAF
 781                                                          * splitting */
 782
 783         pre_points_per_block = (size_t) 1 << (w - 1);
 784         num = pre_points_per_block * numblocks; /* number of points to
 785                                                  * compute and store */
 786
 787         points = reallocarray(NULL, (num + 1), sizeof(EC_POINT *));
 788         if (!points) {
 789                 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
 790                 goto err;
 791         }
 792         var = points;
 793         var[num] = NULL;        /* pivot */
 794         for (i = 0; i < num; i++) {
 795                 if ((var[i] = EC_POINT_new(group)) == NULL) {
 796                         ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
 797                         goto err;
 798                 }
 799         }
 800
 801         if (!(tmp_point = EC_POINT_new(group)) || !(base = EC_POINT_new(group))) {
 802                 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
 803                 goto err;
 804         }
 805         if (!EC_POINT_copy(base, generator))
 806                 goto err;
 807
 808         /* do the precomputation */
 809         for (i = 0; i < numblocks; i++) {
 810                 size_t j;
 811
 812                 if (!EC_POINT_dbl(group, tmp_point, base, ctx))
 813                         goto err;
 814
 815                 if (!EC_POINT_copy(*var++, base))
 816                         goto err;
 817
 818                 for (j = 1; j < pre_points_per_block; j++, var++) {
 819                         /* calculate odd multiples of the current base point */
 820                         if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx))
 821                                 goto err;
 822                 }
 823
 824                 if (i < numblocks - 1) {
 825                         /*
 826                          * get the next base (multiply current one by
 827                          * 2^blocksize)
 828                          */
 829                         size_t k;
 830
 831                         if (blocksize <= 2) {
 832                                 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_INTERNAL_ERROR);
 833                                 goto err;
 834                         }
 835                         if (!EC_POINT_dbl(group, base, tmp_point, ctx))
 836                                 goto err;
 837                         for (k = 2; k < blocksize; k++) {
 838                                 if (!EC_POINT_dbl(group, base, base, ctx))
 839                                         goto err;
 840                         }
 841                 }
 842         }
 843
 844         if (!EC_POINTs_make_affine(group, num, points, ctx))
 845                 goto err;
 846
 847         pre_comp->group = group;
 848         pre_comp->blocksize = blocksize;
 849         pre_comp->numblocks = numblocks;
 850         pre_comp->w = w;
 851         pre_comp->points = points;
 852         points = NULL;
 853         pre_comp->num = num;
 854
 855         if (!EC_EX_DATA_set_data(&group->extra_data, pre_comp,
 856                 ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free))
 857                 goto err;
 858         pre_comp = NULL;
 859
 860         ret = 1;
 861 err:
 862         if (ctx != NULL)
 863                 BN_CTX_end(ctx);
 864         BN_CTX_free(new_ctx);
 865         ec_pre_comp_free(pre_comp);
 866         if (points) {
 867                 EC_POINT **p;
 868
 869                 for (p = points; *p != NULL; p++)
 870                         EC_POINT_free(*p);
 871                 free(points);
 872         }
 873         EC_POINT_free(tmp_point);
 874         EC_POINT_free(base);
 875         return ret;
 876 }
 877
 878
 879 int
 880 ec_wNAF_have_precompute_mult(const EC_GROUP * group)
 881 {
 882         if (EC_EX_DATA_get_data(group->extra_data, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free) != NULL)
 883                 return 1;
 884         else
 885                 return 0;
 886 }