crypto/ec/ec_mult.c

   1 /* crypto/ec/ec_mult.c */
   2 /*
   3  * Originally written by Bodo Moeller for the OpenSSL project.
   4  */
   5 /* ====================================================================
   6  * Copyright (c) 1998-2002 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 <openssl/err.h>
  65
  66 #include "ec_lcl.h"
  67
  68
  69 /* TODO: optional precomputation of multiples of the generator */
  70
  71
  72
  73 /*
  74  * wNAF-based interleaving multi-exponentation method
  75  * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp>)
  76  */
  77
  78
  79 /* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
  80  * This is an array  r[]  of values that are either zero or odd with an
  81  * absolute value less than  2^w  satisfying
  82  *     scalar = \sum_j r[j]*2^j
  83  * where at most one of any  w+1  consecutive digits is non-zero
  84  * with the exception that the most significant digit may be only
  85  * w-1 zeros away from that next non-zero digit.
  86  */
  87 static signed char *compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
  88         {
  89         int window_val;
  90         int ok = 0;
  91         signed char *r = NULL;
  92         int sign = 1;
  93         int bit, next_bit, mask;
  94         size_t len = 0, j;
  95
  96         if (w <= 0 || w > 7) /* 'signed char' can represent integers with absolute values less than 2^7 */
  97                 {
  98                 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
  99                 goto err;
 100                 }
 101         bit = 1 << w; /* at most 128 */
 102         next_bit = bit << 1; /* at most 256 */
 103         mask = next_bit - 1; /* at most 255 */
 104
 105         if (scalar->neg)
 106                 {
 107                 sign = -1;
 108                 }
 109
 110         len = BN_num_bits(scalar);
 111         r = OPENSSL_malloc(len + 1); /* modified wNAF may be one digit longer than binary representation */
 112         if (r == NULL) goto err;
 113
 114         if (scalar->d == NULL || scalar->top == 0)
 115                 {
 116                 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 117                 goto err;
 118                 }
 119         window_val = scalar->d[0] & mask;
 120         j = 0;
 121         while ((window_val != 0) || (j + w + 1 < len)) /* if j+w+1 >= len, window_val will not increase */
 122                 {
 123                 int digit = 0;
 124
 125                 /* 0 <= window_val <= 2^(w+1) */
 126
 127                 if (window_val & 1)
 128                         {
 129                         /* 0 < window_val < 2^(w+1) */
 130
 131                         if (window_val & bit)
 132                                 {
 133                                 digit = window_val - next_bit; /* -2^w < digit < 0 */
 134
 135 #if 1 /* modified wNAF */
 136                                 if (j + w + 1 >= len)
 137                                         {
 138                                         /* special case for generating modified wNAFs:
 139                                          * no new bits will be added into window_val,
 140                                          * so using a positive digit here will decrease
 141                                          * the total length of the representation */
 142
 143                                         digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
 144                                         }
 145 #endif
 146                                 }
 147                         else
 148                                 {
 149                                 digit = window_val; /* 0 < digit < 2^w */
 150                                 }
 151
 152                         if (digit <= -bit || digit >= bit || !(digit & 1))
 153                                 {
 154                                 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 155                                 goto err;
 156                                 }
 157
 158                         window_val -= digit;
 159
 160                         /* now window_val is 0 or 2^(w+1) in standard wNAF generation;
 161                          * for modified window NAFs, it may also be 2^w
 162                          */
 163                         if (window_val != 0 && window_val != next_bit && window_val != bit)
 164                                 {
 165                                 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 166                                 goto err;
 167                                 }
 168                         }
 169
 170                 r[j++] = sign * digit;
 171
 172                 window_val >>= 1;
 173                 window_val += bit * BN_is_bit_set(scalar, j + w);
 174
 175                 if (window_val > next_bit)
 176                         {
 177                         ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 178                         goto err;
 179                         }
 180                 }
 181
 182         if (j > len + 1)
 183                 {
 184                 ECerr(EC_F_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
 185                 goto err;
 186                 }
 187         len = j;
 188         ok = 1;
 189
 190  err:
 191         if (!ok)
 192                 {
 193                 OPENSSL_free(r);
 194                 r = NULL;
 195                 }
 196         if (ok)
 197                 *ret_len = len;
 198         return r;
 199         }
 200
 201
 202 /* TODO: table should be optimised for the wNAF-based implementation,
 203  *       sometimes smaller windows will give better performance
 204  *       (thus the boundaries should be increased)
 205  */
 206 #define EC_window_bits_for_scalar_size(b) \
 207                 ((b) >= 2000 ? 6 : \
 208                  (b) >=  800 ? 5 : \
 209                  (b) >=  300 ? 4 : \
 210                  (b) >=   70 ? 3 : \
 211                  (b) >=   20 ? 2 : \
 212                   1)
 213
 214 /* Compute
 215  *      \sum scalars[i]*points[i],
 216  * also including
 217  *      scalar*generator
 218  * in the addition if scalar != NULL
 219  */
 220 int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 221         size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx)
 222         {
 223         BN_CTX *new_ctx = NULL;
 224         EC_POINT *generator = NULL;
 225         EC_POINT *tmp = NULL;
 226         size_t totalnum;
 227         size_t i, j;
 228         int k;
 229         int r_is_inverted = 0;
 230         int r_is_at_infinity = 1;
 231         size_t *wsize = NULL; /* individual window sizes */
 232         signed char **wNAF = NULL; /* individual wNAFs */
 233         size_t *wNAF_len = NULL;
 234         size_t max_len = 0;
 235         size_t num_val;
 236         EC_POINT **val = NULL; /* precomputation */
 237         EC_POINT **v;
 238         EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' */
 239         int ret = 0;
 240
 241         if (scalar != NULL)
 242                 {
 243                 generator = EC_GROUP_get0_generator(group);
 244                 if (generator == NULL)
 245                         {
 246                         ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR);
 247                         return 0;
 248                         }
 249                 }
 250
 251         for (i = 0; i < num; i++)
 252                 {
 253                 if (group->meth != points[i]->meth)
 254                         {
 255                         ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
 256                         return 0;
 257                         }
 258                 }
 259
 260         totalnum = num + (scalar != NULL);
 261
 262         wsize = OPENSSL_malloc(totalnum * sizeof wsize[0]);
 263         wNAF_len = OPENSSL_malloc(totalnum * sizeof wNAF_len[0]);
 264         wNAF = OPENSSL_malloc((totalnum + 1) * sizeof wNAF[0]);
 265         if (wNAF != NULL)
 266                 {
 267                 wNAF[0] = NULL; /* preliminary pivot */
 268                 }
 269         if (wsize == NULL || wNAF_len == NULL || wNAF == NULL) goto err;
 270
 271         /* num_val := total number of points to precompute */
 272         num_val = 0;
 273         for (i = 0; i < totalnum; i++)
 274                 {
 275                 size_t bits;
 276
 277                 bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar);
 278                 wsize[i] = EC_window_bits_for_scalar_size(bits);
 279                 num_val += 1u << (wsize[i] - 1);
 280                 }
 281
 282         /* all precomputed points go into a single array 'val',
 283          * 'val_sub[i]' is a pointer to the subarray for the i-th point */
 284         val = OPENSSL_malloc((num_val + 1) * sizeof val[0]);
 285         if (val == NULL) goto err;
 286         val[num_val] = NULL; /* pivot element */
 287
 288         val_sub = OPENSSL_malloc(totalnum * sizeof val_sub[0]);
 289         if (val_sub == NULL) goto err;
 290
 291         /* allocate points for precomputation */
 292         v = val;
 293         for (i = 0; i < totalnum; i++)
 294                 {
 295                 val_sub[i] = v;
 296                 for (j = 0; j < (1u << (wsize[i] - 1)); j++)
 297                         {
 298                         *v = EC_POINT_new(group);
 299                         if (*v == NULL) goto err;
 300                         v++;
 301                         }
 302                 }
 303         if (!(v == val + num_val))
 304                 {
 305                 ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
 306                 goto err;
 307                 }
 308
 309         if (ctx == NULL)
 310                 {
 311                 ctx = new_ctx = BN_CTX_new();
 312                 if (ctx == NULL)
 313                         goto err;
 314                 }
 315
 316         tmp = EC_POINT_new(group);
 317         if (tmp == NULL) goto err;
 318
 319         /* prepare precomputed values:
 320          *    val_sub[i][0] :=     points[i]
 321          *    val_sub[i][1] := 3 * points[i]
 322          *    val_sub[i][2] := 5 * points[i]
 323          *    ...
 324          */
 325         for (i = 0; i < totalnum; i++)
 326                 {
 327                 if (i < num)
 328                         {
 329                         if (!EC_POINT_copy(val_sub[i][0], points[i])) goto err;
 330                         }
 331                 else
 332                         {
 333                         if (!EC_POINT_copy(val_sub[i][0], generator)) goto err;
 334                         }
 335
 336                 if (wsize[i] > 1)
 337                         {
 338                         if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) goto err;
 339                         for (j = 1; j < (1u << (wsize[i] - 1)); j++)
 340                                 {
 341                                 if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) goto err;
 342                                 }
 343                         }
 344
 345                 wNAF[i + 1] = NULL; /* make sure we always have a pivot */
 346                 wNAF[i] = compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], &wNAF_len[i]);
 347                 if (wNAF[i] == NULL) goto err;
 348                 if (wNAF_len[i] > max_len)
 349                         max_len = wNAF_len[i];
 350                 }
 351
 352 #if 1 /* optional; EC_window_bits_for_scalar_size assumes we do this step */
 353         if (!EC_POINTs_make_affine(group, num_val, val, ctx)) goto err;
 354 #endif
 355
 356         r_is_at_infinity = 1;
 357
 358         for (k = max_len - 1; k >= 0; k--)
 359                 {
 360                 if (!r_is_at_infinity)
 361                         {
 362                         if (!EC_POINT_dbl(group, r, r, ctx)) goto err;
 363                         }
 364
 365                 for (i = 0; i < totalnum; i++)
 366                         {
 367                         if (wNAF_len[i] > (size_t)k)
 368                                 {
 369                                 int digit = wNAF[i][k];
 370                                 int is_neg;
 371
 372                                 if (digit)
 373                                         {
 374                                         is_neg = digit < 0;
 375
 376                                         if (is_neg)
 377                                                 digit = -digit;
 378
 379                                         if (is_neg != r_is_inverted)
 380                                                 {
 381                                                 if (!r_is_at_infinity)
 382                                                         {
 383                                                         if (!EC_POINT_invert(group, r, ctx)) goto err;
 384                                                         }
 385                                                 r_is_inverted = !r_is_inverted;
 386                                                 }
 387
 388                                         /* digit > 0 */
 389
 390                                         if (r_is_at_infinity)
 391                                                 {
 392                                                 if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) goto err;
 393                                                 r_is_at_infinity = 0;
 394                                                 }
 395                                         else
 396                                                 {
 397                                                 if (!EC_POINT_add(group, r, r, val_sub[i][digit >> 1], ctx)) goto err;
 398                                                 }
 399                                         }
 400                                 }
 401                         }
 402                 }
 403
 404         if (r_is_at_infinity)
 405                 {
 406                 if (!EC_POINT_set_to_infinity(group, r)) goto err;
 407                 }
 408         else
 409                 {
 410                 if (r_is_inverted)
 411                         if (!EC_POINT_invert(group, r, ctx)) goto err;
 412                 }
 413
 414         ret = 1;
 415
 416  err:
 417         if (new_ctx != NULL)
 418                 BN_CTX_free(new_ctx);
 419         if (tmp != NULL)
 420                 EC_POINT_free(tmp);
 421         if (wsize != NULL)
 422                 OPENSSL_free(wsize);
 423         if (wNAF_len != NULL)
 424                 OPENSSL_free(wNAF_len);
 425         if (wNAF != NULL)
 426                 {
 427                 signed char **w;
 428
 429                 for (w = wNAF; *w != NULL; w++)
 430                         OPENSSL_free(*w);
 431
 432                 OPENSSL_free(wNAF);
 433                 }
 434         if (val != NULL)
 435                 {
 436                 for (v = val; *v != NULL; v++)
 437                         EC_POINT_clear_free(*v);
 438
 439                 OPENSSL_free(val);
 440                 }
 441         if (val_sub != NULL)
 442                 {
 443                 OPENSSL_free(val_sub);
 444                 }
 445         return ret;
 446         }
 447
 448
 449 /* Generic multiplication method.
 450  * If group->meth does not provide a multiplication method, default to ec_wNAF_mul;
 451  * otherwise use the group->meth's multiplication.
 452  */
 453 int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 454         size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx)
 455         {
 456         if (group->meth->mul == 0)
 457                 return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
 458         else
 459                 return group->meth->mul(group, r, scalar, num, points, scalars, ctx);
 460         }
 461
 462
 463 int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar, const EC_POINT *point, const BIGNUM *p_scalar, BN_CTX *ctx)
 464         {
 465         const EC_POINT *points[1];
 466         const BIGNUM *scalars[1];
 467
 468         points[0] = point;
 469         scalars[0] = p_scalar;
 470
 471         return EC_POINTs_mul(group, r, g_scalar, (point != NULL && p_scalar != NULL), points, scalars, ctx);
 472         }
 473
 474
 475 int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
 476         {
 477         const EC_POINT *generator;
 478         BN_CTX *new_ctx = NULL;
 479         BIGNUM *order;
 480         int ret = 0;
 481
 482         generator = EC_GROUP_get0_generator(group);
 483         if (generator == NULL)
 484                 {
 485                 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR);
 486                 return 0;
 487                 }
 488
 489         if (ctx == NULL)
 490                 {
 491                 ctx = new_ctx = BN_CTX_new();
 492                 if (ctx == NULL)
 493                         return 0;
 494                 }
 495
 496         BN_CTX_start(ctx);
 497         order = BN_CTX_get(ctx);
 498         if (order == NULL) goto err;
 499
 500         if (!EC_GROUP_get_order(group, order, ctx)) return 0;
 501         if (BN_is_zero(order))
 502                 {
 503                 ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER);
 504                 goto err;
 505                 }
 506
 507         /* TODO */
 508
 509         ret = 1;
 510
 511  err:
 512         BN_CTX_end(ctx);
 513         if (new_ctx != NULL)
 514                 BN_CTX_free(new_ctx);
 515         return ret;
 516         }
 517
 518
 519 /* Generic multiplicaiton precomputation method.
 520  * If group->meth does not provide a multiplication method, default to ec_wNAF_mul and do its
 521  * precomputation; otherwise use the group->meth's precomputation if it exists.
 522  */
 523 int EC_GROUP_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
 524         {
 525         if (group->meth->mul == 0)
 526                 return ec_wNAF_precompute_mult(group, ctx);
 527         else if (group->meth->precompute_mult != 0)
 528                 return group->meth->precompute_mult(group, ctx);
 529         else
 530                 return 1;
 531         }