crypto/libressl/crypto/ec/ecp_smpl.c

   1 /* $OpenBSD: ecp_smpl.c,v 1.29 2018/11/15 05:53:31 tb Exp $ */
   2 /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
   3  * for the OpenSSL project.
   4  * Includes code written by Bodo Moeller for the OpenSSL project.
   5 */
   6 /* ====================================================================
   7  * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  *
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in
  18  *    the documentation and/or other materials provided with the
  19  *    distribution.
  20  *
  21  * 3. All advertising materials mentioning features or use of this
  22  *    software must display the following acknowledgment:
  23  *    "This product includes software developed by the OpenSSL Project
  24  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  25  *
  26  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  27  *    endorse or promote products derived from this software without
  28  *    prior written permission. For written permission, please contact
  29  *    openssl-core@openssl.org.
  30  *
  31  * 5. Products derived from this software may not be called "OpenSSL"
  32  *    nor may "OpenSSL" appear in their names without prior written
  33  *    permission of the OpenSSL Project.
  34  *
  35  * 6. Redistributions of any form whatsoever must retain the following
  36  *    acknowledgment:
  37  *    "This product includes software developed by the OpenSSL Project
  38  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  41  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  43  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  44  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  45  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  46  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  47  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  49  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  50  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  51  * OF THE POSSIBILITY OF SUCH DAMAGE.
  52  * ====================================================================
  53  *
  54  * This product includes cryptographic software written by Eric Young
  55  * (eay@cryptsoft.com).  This product includes software written by Tim
  56  * Hudson (tjh@cryptsoft.com).
  57  *
  58  */
  59 /* ====================================================================
  60  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  61  * Portions of this software developed by SUN MICROSYSTEMS, INC.,
  62  * and contributed to the OpenSSL project.
  63  */
  64
  65 #include <openssl/err.h>
  66
  67 #include "bn_lcl.h"
  68 #include "ec_lcl.h"
  69
  70 const EC_METHOD *
  71 EC_GFp_simple_method(void)
  72 {
  73         static const EC_METHOD ret = {
  74                 .flags = EC_FLAGS_DEFAULT_OCT,
  75                 .field_type = NID_X9_62_prime_field,
  76                 .group_init = ec_GFp_simple_group_init,
  77                 .group_finish = ec_GFp_simple_group_finish,
  78                 .group_clear_finish = ec_GFp_simple_group_clear_finish,
  79                 .group_copy = ec_GFp_simple_group_copy,
  80                 .group_set_curve = ec_GFp_simple_group_set_curve,
  81                 .group_get_curve = ec_GFp_simple_group_get_curve,
  82                 .group_get_degree = ec_GFp_simple_group_get_degree,
  83                 .group_check_discriminant =
  84                 ec_GFp_simple_group_check_discriminant,
  85                 .point_init = ec_GFp_simple_point_init,
  86                 .point_finish = ec_GFp_simple_point_finish,
  87                 .point_clear_finish = ec_GFp_simple_point_clear_finish,
  88                 .point_copy = ec_GFp_simple_point_copy,
  89                 .point_set_to_infinity = ec_GFp_simple_point_set_to_infinity,
  90                 .point_set_Jprojective_coordinates_GFp =
  91                 ec_GFp_simple_set_Jprojective_coordinates_GFp,
  92                 .point_get_Jprojective_coordinates_GFp =
  93                 ec_GFp_simple_get_Jprojective_coordinates_GFp,
  94                 .point_set_affine_coordinates =
  95                 ec_GFp_simple_point_set_affine_coordinates,
  96                 .point_get_affine_coordinates =
  97                 ec_GFp_simple_point_get_affine_coordinates,
  98                 .add = ec_GFp_simple_add,
  99                 .dbl = ec_GFp_simple_dbl,
 100                 .invert = ec_GFp_simple_invert,
 101                 .is_at_infinity = ec_GFp_simple_is_at_infinity,
 102                 .is_on_curve = ec_GFp_simple_is_on_curve,
 103                 .point_cmp = ec_GFp_simple_cmp,
 104                 .make_affine = ec_GFp_simple_make_affine,
 105                 .points_make_affine = ec_GFp_simple_points_make_affine,
 106                 .mul_generator_ct = ec_GFp_simple_mul_generator_ct,
 107                 .mul_single_ct = ec_GFp_simple_mul_single_ct,
 108                 .mul_double_nonct = ec_GFp_simple_mul_double_nonct,
 109                 .field_mul = ec_GFp_simple_field_mul,
 110                 .field_sqr = ec_GFp_simple_field_sqr,
 111                 .blind_coordinates = ec_GFp_simple_blind_coordinates,
 112         };
 113
 114         return &ret;
 115 }
 116
 117
 118 /* Most method functions in this file are designed to work with
 119  * non-trivial representations of field elements if necessary
 120  * (see ecp_mont.c): while standard modular addition and subtraction
 121  * are used, the field_mul and field_sqr methods will be used for
 122  * multiplication, and field_encode and field_decode (if defined)
 123  * will be used for converting between representations.
 124
 125  * Functions ec_GFp_simple_points_make_affine() and
 126  * ec_GFp_simple_point_get_affine_coordinates() specifically assume
 127  * that if a non-trivial representation is used, it is a Montgomery
 128  * representation (i.e. 'encoding' means multiplying by some factor R).
 129  */
 130
 131
 132 int
 133 ec_GFp_simple_group_init(EC_GROUP * group)
 134 {
 135         BN_init(&group->field);
 136         BN_init(&group->a);
 137         BN_init(&group->b);
 138         group->a_is_minus3 = 0;
 139         return 1;
 140 }
 141
 142
 143 void
 144 ec_GFp_simple_group_finish(EC_GROUP * group)
 145 {
 146         BN_free(&group->field);
 147         BN_free(&group->a);
 148         BN_free(&group->b);
 149 }
 150
 151
 152 void
 153 ec_GFp_simple_group_clear_finish(EC_GROUP * group)
 154 {
 155         BN_clear_free(&group->field);
 156         BN_clear_free(&group->a);
 157         BN_clear_free(&group->b);
 158 }
 159
 160
 161 int
 162 ec_GFp_simple_group_copy(EC_GROUP * dest, const EC_GROUP * src)
 163 {
 164         if (!BN_copy(&dest->field, &src->field))
 165                 return 0;
 166         if (!BN_copy(&dest->a, &src->a))
 167                 return 0;
 168         if (!BN_copy(&dest->b, &src->b))
 169                 return 0;
 170
 171         dest->a_is_minus3 = src->a_is_minus3;
 172
 173         return 1;
 174 }
 175
 176
 177 int
 178 ec_GFp_simple_group_set_curve(EC_GROUP * group,
 179     const BIGNUM * p, const BIGNUM * a, const BIGNUM * b, BN_CTX * ctx)
 180 {
 181         int ret = 0;
 182         BN_CTX *new_ctx = NULL;
 183         BIGNUM *tmp_a;
 184
 185         /* p must be a prime > 3 */
 186         if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) {
 187                 ECerror(EC_R_INVALID_FIELD);
 188                 return 0;
 189         }
 190         if (ctx == NULL) {
 191                 ctx = new_ctx = BN_CTX_new();
 192                 if (ctx == NULL)
 193                         return 0;
 194         }
 195         BN_CTX_start(ctx);
 196         if ((tmp_a = BN_CTX_get(ctx)) == NULL)
 197                 goto err;
 198
 199         /* group->field */
 200         if (!BN_copy(&group->field, p))
 201                 goto err;
 202         BN_set_negative(&group->field, 0);
 203
 204         /* group->a */
 205         if (!BN_nnmod(tmp_a, a, p, ctx))
 206                 goto err;
 207         if (group->meth->field_encode) {
 208                 if (!group->meth->field_encode(group, &group->a, tmp_a, ctx))
 209                         goto err;
 210         } else if (!BN_copy(&group->a, tmp_a))
 211                 goto err;
 212
 213         /* group->b */
 214         if (!BN_nnmod(&group->b, b, p, ctx))
 215                 goto err;
 216         if (group->meth->field_encode)
 217                 if (!group->meth->field_encode(group, &group->b, &group->b, ctx))
 218                         goto err;
 219
 220         /* group->a_is_minus3 */
 221         if (!BN_add_word(tmp_a, 3))
 222                 goto err;
 223         group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
 224
 225         ret = 1;
 226
 227  err:
 228         BN_CTX_end(ctx);
 229         BN_CTX_free(new_ctx);
 230         return ret;
 231 }
 232
 233
 234 int
 235 ec_GFp_simple_group_get_curve(const EC_GROUP * group, BIGNUM * p, BIGNUM * a, BIGNUM * b, BN_CTX * ctx)
 236 {
 237         int ret = 0;
 238         BN_CTX *new_ctx = NULL;
 239
 240         if (p != NULL) {
 241                 if (!BN_copy(p, &group->field))
 242                         return 0;
 243         }
 244         if (a != NULL || b != NULL) {
 245                 if (group->meth->field_decode) {
 246                         if (ctx == NULL) {
 247                                 ctx = new_ctx = BN_CTX_new();
 248                                 if (ctx == NULL)
 249                                         return 0;
 250                         }
 251                         if (a != NULL) {
 252                                 if (!group->meth->field_decode(group, a, &group->a, ctx))
 253                                         goto err;
 254                         }
 255                         if (b != NULL) {
 256                                 if (!group->meth->field_decode(group, b, &group->b, ctx))
 257                                         goto err;
 258                         }
 259                 } else {
 260                         if (a != NULL) {
 261                                 if (!BN_copy(a, &group->a))
 262                                         goto err;
 263                         }
 264                         if (b != NULL) {
 265                                 if (!BN_copy(b, &group->b))
 266                                         goto err;
 267                         }
 268                 }
 269         }
 270         ret = 1;
 271
 272  err:
 273         BN_CTX_free(new_ctx);
 274         return ret;
 275 }
 276
 277
 278 int
 279 ec_GFp_simple_group_get_degree(const EC_GROUP * group)
 280 {
 281         return BN_num_bits(&group->field);
 282 }
 283
 284
 285 int
 286 ec_GFp_simple_group_check_discriminant(const EC_GROUP * group, BN_CTX * ctx)
 287 {
 288         int ret = 0;
 289         BIGNUM *a, *b, *order, *tmp_1, *tmp_2;
 290         const BIGNUM *p = &group->field;
 291         BN_CTX *new_ctx = NULL;
 292
 293         if (ctx == NULL) {
 294                 ctx = new_ctx = BN_CTX_new();
 295                 if (ctx == NULL) {
 296                         ECerror(ERR_R_MALLOC_FAILURE);
 297                         goto err;
 298                 }
 299         }
 300         BN_CTX_start(ctx);
 301         if ((a = BN_CTX_get(ctx)) == NULL)
 302                 goto err;
 303         if ((b = BN_CTX_get(ctx)) == NULL)
 304                 goto err;
 305         if ((tmp_1 = BN_CTX_get(ctx)) == NULL)
 306                 goto err;
 307         if ((tmp_2 = BN_CTX_get(ctx)) == NULL)
 308                 goto err;
 309         if ((order = BN_CTX_get(ctx)) == NULL)
 310                 goto err;
 311
 312         if (group->meth->field_decode) {
 313                 if (!group->meth->field_decode(group, a, &group->a, ctx))
 314                         goto err;
 315                 if (!group->meth->field_decode(group, b, &group->b, ctx))
 316                         goto err;
 317         } else {
 318                 if (!BN_copy(a, &group->a))
 319                         goto err;
 320                 if (!BN_copy(b, &group->b))
 321                         goto err;
 322         }
 323
 324         /*
 325          * check the discriminant: y^2 = x^3 + a*x + b is an elliptic curve
 326          * <=> 4*a^3 + 27*b^2 != 0 (mod p) 0 =< a, b < p
 327          */
 328         if (BN_is_zero(a)) {
 329                 if (BN_is_zero(b))
 330                         goto err;
 331         } else if (!BN_is_zero(b)) {
 332                 if (!BN_mod_sqr(tmp_1, a, p, ctx))
 333                         goto err;
 334                 if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx))
 335                         goto err;
 336                 if (!BN_lshift(tmp_1, tmp_2, 2))
 337                         goto err;
 338                 /* tmp_1 = 4*a^3 */
 339
 340                 if (!BN_mod_sqr(tmp_2, b, p, ctx))
 341                         goto err;
 342                 if (!BN_mul_word(tmp_2, 27))
 343                         goto err;
 344                 /* tmp_2 = 27*b^2 */
 345
 346                 if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx))
 347                         goto err;
 348                 if (BN_is_zero(a))
 349                         goto err;
 350         }
 351         ret = 1;
 352
 353  err:
 354         if (ctx != NULL)
 355                 BN_CTX_end(ctx);
 356         BN_CTX_free(new_ctx);
 357         return ret;
 358 }
 359
 360
 361 int
 362 ec_GFp_simple_point_init(EC_POINT * point)
 363 {
 364         BN_init(&point->X);
 365         BN_init(&point->Y);
 366         BN_init(&point->Z);
 367         point->Z_is_one = 0;
 368
 369         return 1;
 370 }
 371
 372
 373 void
 374 ec_GFp_simple_point_finish(EC_POINT * point)
 375 {
 376         BN_free(&point->X);
 377         BN_free(&point->Y);
 378         BN_free(&point->Z);
 379 }
 380
 381
 382 void
 383 ec_GFp_simple_point_clear_finish(EC_POINT * point)
 384 {
 385         BN_clear_free(&point->X);
 386         BN_clear_free(&point->Y);
 387         BN_clear_free(&point->Z);
 388         point->Z_is_one = 0;
 389 }
 390
 391
 392 int
 393 ec_GFp_simple_point_copy(EC_POINT * dest, const EC_POINT * src)
 394 {
 395         if (!BN_copy(&dest->X, &src->X))
 396                 return 0;
 397         if (!BN_copy(&dest->Y, &src->Y))
 398                 return 0;
 399         if (!BN_copy(&dest->Z, &src->Z))
 400                 return 0;
 401         dest->Z_is_one = src->Z_is_one;
 402
 403         return 1;
 404 }
 405
 406
 407 int
 408 ec_GFp_simple_point_set_to_infinity(const EC_GROUP * group, EC_POINT * point)
 409 {
 410         point->Z_is_one = 0;
 411         BN_zero(&point->Z);
 412         return 1;
 413 }
 414
 415
 416 int
 417 ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP * group, EC_POINT * point,
 418     const BIGNUM * x, const BIGNUM * y, const BIGNUM * z, BN_CTX * ctx)
 419 {
 420         BN_CTX *new_ctx = NULL;
 421         int ret = 0;
 422
 423         if (ctx == NULL) {
 424                 ctx = new_ctx = BN_CTX_new();
 425                 if (ctx == NULL)
 426                         return 0;
 427         }
 428         if (x != NULL) {
 429                 if (!BN_nnmod(&point->X, x, &group->field, ctx))
 430                         goto err;
 431                 if (group->meth->field_encode) {
 432                         if (!group->meth->field_encode(group, &point->X, &point->X, ctx))
 433                                 goto err;
 434                 }
 435         }
 436         if (y != NULL) {
 437                 if (!BN_nnmod(&point->Y, y, &group->field, ctx))
 438                         goto err;
 439                 if (group->meth->field_encode) {
 440                         if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx))
 441                                 goto err;
 442                 }
 443         }
 444         if (z != NULL) {
 445                 int Z_is_one;
 446
 447                 if (!BN_nnmod(&point->Z, z, &group->field, ctx))
 448                         goto err;
 449                 Z_is_one = BN_is_one(&point->Z);
 450                 if (group->meth->field_encode) {
 451                         if (Z_is_one && (group->meth->field_set_to_one != 0)) {
 452                                 if (!group->meth->field_set_to_one(group, &point->Z, ctx))
 453                                         goto err;
 454                         } else {
 455                                 if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx))
 456                                         goto err;
 457                         }
 458                 }
 459                 point->Z_is_one = Z_is_one;
 460         }
 461         ret = 1;
 462
 463  err:
 464         BN_CTX_free(new_ctx);
 465         return ret;
 466 }
 467
 468
 469 int
 470 ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP * group, const EC_POINT * point,
 471     BIGNUM * x, BIGNUM * y, BIGNUM * z, BN_CTX * ctx)
 472 {
 473         BN_CTX *new_ctx = NULL;
 474         int ret = 0;
 475
 476         if (group->meth->field_decode != 0) {
 477                 if (ctx == NULL) {
 478                         ctx = new_ctx = BN_CTX_new();
 479                         if (ctx == NULL)
 480                                 return 0;
 481                 }
 482                 if (x != NULL) {
 483                         if (!group->meth->field_decode(group, x, &point->X, ctx))
 484                                 goto err;
 485                 }
 486                 if (y != NULL) {
 487                         if (!group->meth->field_decode(group, y, &point->Y, ctx))
 488                                 goto err;
 489                 }
 490                 if (z != NULL) {
 491                         if (!group->meth->field_decode(group, z, &point->Z, ctx))
 492                                 goto err;
 493                 }
 494         } else {
 495                 if (x != NULL) {
 496                         if (!BN_copy(x, &point->X))
 497                                 goto err;
 498                 }
 499                 if (y != NULL) {
 500                         if (!BN_copy(y, &point->Y))
 501                                 goto err;
 502                 }
 503                 if (z != NULL) {
 504                         if (!BN_copy(z, &point->Z))
 505                                 goto err;
 506                 }
 507         }
 508
 509         ret = 1;
 510
 511  err:
 512         BN_CTX_free(new_ctx);
 513         return ret;
 514 }
 515
 516
 517 int
 518 ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP * group, EC_POINT * point,
 519     const BIGNUM * x, const BIGNUM * y, BN_CTX * ctx)
 520 {
 521         if (x == NULL || y == NULL) {
 522                 /* unlike for projective coordinates, we do not tolerate this */
 523                 ECerror(ERR_R_PASSED_NULL_PARAMETER);
 524                 return 0;
 525         }
 526         return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx);
 527 }
 528
 529
 530 int
 531 ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP * group, const EC_POINT * point,
 532     BIGNUM * x, BIGNUM * y, BN_CTX * ctx)
 533 {
 534         BN_CTX *new_ctx = NULL;
 535         BIGNUM *Z, *Z_1, *Z_2, *Z_3;
 536         const BIGNUM *Z_;
 537         int ret = 0;
 538
 539         if (EC_POINT_is_at_infinity(group, point) > 0) {
 540                 ECerror(EC_R_POINT_AT_INFINITY);
 541                 return 0;
 542         }
 543         if (ctx == NULL) {
 544                 ctx = new_ctx = BN_CTX_new();
 545                 if (ctx == NULL)
 546                         return 0;
 547         }
 548         BN_CTX_start(ctx);
 549         if ((Z = BN_CTX_get(ctx)) == NULL)
 550                 goto err;
 551         if ((Z_1 = BN_CTX_get(ctx)) == NULL)
 552                 goto err;
 553         if ((Z_2 = BN_CTX_get(ctx)) == NULL)
 554                 goto err;
 555         if ((Z_3 = BN_CTX_get(ctx)) == NULL)
 556                 goto err;
 557
 558         /* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
 559
 560         if (group->meth->field_decode) {
 561                 if (!group->meth->field_decode(group, Z, &point->Z, ctx))
 562                         goto err;
 563                 Z_ = Z;
 564         } else {
 565                 Z_ = &point->Z;
 566         }
 567
 568         if (BN_is_one(Z_)) {
 569                 if (group->meth->field_decode) {
 570                         if (x != NULL) {
 571                                 if (!group->meth->field_decode(group, x, &point->X, ctx))
 572                                         goto err;
 573                         }
 574                         if (y != NULL) {
 575                                 if (!group->meth->field_decode(group, y, &point->Y, ctx))
 576                                         goto err;
 577                         }
 578                 } else {
 579                         if (x != NULL) {
 580                                 if (!BN_copy(x, &point->X))
 581                                         goto err;
 582                         }
 583                         if (y != NULL) {
 584                                 if (!BN_copy(y, &point->Y))
 585                                         goto err;
 586                         }
 587                 }
 588         } else {
 589                 if (!BN_mod_inverse_ct(Z_1, Z_, &group->field, ctx)) {
 590                         ECerror(ERR_R_BN_LIB);
 591                         goto err;
 592                 }
 593                 if (group->meth->field_encode == 0) {
 594                         /* field_sqr works on standard representation */
 595                         if (!group->meth->field_sqr(group, Z_2, Z_1, ctx))
 596                                 goto err;
 597                 } else {
 598                         if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx))
 599                                 goto err;
 600                 }
 601
 602                 if (x != NULL) {
 603                         /*
 604                          * in the Montgomery case, field_mul will cancel out
 605                          * Montgomery factor in X:
 606                          */
 607                         if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx))
 608                                 goto err;
 609                 }
 610                 if (y != NULL) {
 611                         if (group->meth->field_encode == 0) {
 612                                 /* field_mul works on standard representation */
 613                                 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx))
 614                                         goto err;
 615                         } else {
 616                                 if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx))
 617                                         goto err;
 618                         }
 619
 620                         /*
 621                          * in the Montgomery case, field_mul will cancel out
 622                          * Montgomery factor in Y:
 623                          */
 624                         if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx))
 625                                 goto err;
 626                 }
 627         }
 628
 629         ret = 1;
 630
 631  err:
 632         BN_CTX_end(ctx);
 633         BN_CTX_free(new_ctx);
 634         return ret;
 635 }
 636
 637 int
 638 ec_GFp_simple_add(const EC_GROUP * group, EC_POINT * r, const EC_POINT * a, const EC_POINT * b, BN_CTX * ctx)
 639 {
 640         int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
 641         int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 642         const BIGNUM *p;
 643         BN_CTX *new_ctx = NULL;
 644         BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
 645         int ret = 0;
 646
 647         if (a == b)
 648                 return EC_POINT_dbl(group, r, a, ctx);
 649         if (EC_POINT_is_at_infinity(group, a) > 0)
 650                 return EC_POINT_copy(r, b);
 651         if (EC_POINT_is_at_infinity(group, b) > 0)
 652                 return EC_POINT_copy(r, a);
 653
 654         field_mul = group->meth->field_mul;
 655         field_sqr = group->meth->field_sqr;
 656         p = &group->field;
 657
 658         if (ctx == NULL) {
 659                 ctx = new_ctx = BN_CTX_new();
 660                 if (ctx == NULL)
 661                         return 0;
 662         }
 663         BN_CTX_start(ctx);
 664         if ((n0 = BN_CTX_get(ctx)) == NULL)
 665                 goto end;
 666         if ((n1 = BN_CTX_get(ctx)) == NULL)
 667                 goto end;
 668         if ((n2 = BN_CTX_get(ctx)) == NULL)
 669                 goto end;
 670         if ((n3 = BN_CTX_get(ctx)) == NULL)
 671                 goto end;
 672         if ((n4 = BN_CTX_get(ctx)) == NULL)
 673                 goto end;
 674         if ((n5 = BN_CTX_get(ctx)) == NULL)
 675                 goto end;
 676         if ((n6 = BN_CTX_get(ctx)) == NULL)
 677                 goto end;
 678
 679         /*
 680          * Note that in this function we must not read components of 'a' or
 681          * 'b' once we have written the corresponding components of 'r'. ('r'
 682          * might be one of 'a' or 'b'.)
 683          */
 684
 685         /* n1, n2 */
 686         if (b->Z_is_one) {
 687                 if (!BN_copy(n1, &a->X))
 688                         goto end;
 689                 if (!BN_copy(n2, &a->Y))
 690                         goto end;
 691                 /* n1 = X_a */
 692                 /* n2 = Y_a */
 693         } else {
 694                 if (!field_sqr(group, n0, &b->Z, ctx))
 695                         goto end;
 696                 if (!field_mul(group, n1, &a->X, n0, ctx))
 697                         goto end;
 698                 /* n1 = X_a * Z_b^2 */
 699
 700                 if (!field_mul(group, n0, n0, &b->Z, ctx))
 701                         goto end;
 702                 if (!field_mul(group, n2, &a->Y, n0, ctx))
 703                         goto end;
 704                 /* n2 = Y_a * Z_b^3 */
 705         }
 706
 707         /* n3, n4 */
 708         if (a->Z_is_one) {
 709                 if (!BN_copy(n3, &b->X))
 710                         goto end;
 711                 if (!BN_copy(n4, &b->Y))
 712                         goto end;
 713                 /* n3 = X_b */
 714                 /* n4 = Y_b */
 715         } else {
 716                 if (!field_sqr(group, n0, &a->Z, ctx))
 717                         goto end;
 718                 if (!field_mul(group, n3, &b->X, n0, ctx))
 719                         goto end;
 720                 /* n3 = X_b * Z_a^2 */
 721
 722                 if (!field_mul(group, n0, n0, &a->Z, ctx))
 723                         goto end;
 724                 if (!field_mul(group, n4, &b->Y, n0, ctx))
 725                         goto end;
 726                 /* n4 = Y_b * Z_a^3 */
 727         }
 728
 729         /* n5, n6 */
 730         if (!BN_mod_sub_quick(n5, n1, n3, p))
 731                 goto end;
 732         if (!BN_mod_sub_quick(n6, n2, n4, p))
 733                 goto end;
 734         /* n5 = n1 - n3 */
 735         /* n6 = n2 - n4 */
 736
 737         if (BN_is_zero(n5)) {
 738                 if (BN_is_zero(n6)) {
 739                         /* a is the same point as b */
 740                         BN_CTX_end(ctx);
 741                         ret = EC_POINT_dbl(group, r, a, ctx);
 742                         ctx = NULL;
 743                         goto end;
 744                 } else {
 745                         /* a is the inverse of b */
 746                         BN_zero(&r->Z);
 747                         r->Z_is_one = 0;
 748                         ret = 1;
 749                         goto end;
 750                 }
 751         }
 752         /* 'n7', 'n8' */
 753         if (!BN_mod_add_quick(n1, n1, n3, p))
 754                 goto end;
 755         if (!BN_mod_add_quick(n2, n2, n4, p))
 756                 goto end;
 757         /* 'n7' = n1 + n3 */
 758         /* 'n8' = n2 + n4 */
 759
 760         /* Z_r */
 761         if (a->Z_is_one && b->Z_is_one) {
 762                 if (!BN_copy(&r->Z, n5))
 763                         goto end;
 764         } else {
 765                 if (a->Z_is_one) {
 766                         if (!BN_copy(n0, &b->Z))
 767                                 goto end;
 768                 } else if (b->Z_is_one) {
 769                         if (!BN_copy(n0, &a->Z))
 770                                 goto end;
 771                 } else {
 772                         if (!field_mul(group, n0, &a->Z, &b->Z, ctx))
 773                                 goto end;
 774                 }
 775                 if (!field_mul(group, &r->Z, n0, n5, ctx))
 776                         goto end;
 777         }
 778         r->Z_is_one = 0;
 779         /* Z_r = Z_a * Z_b * n5 */
 780
 781         /* X_r */
 782         if (!field_sqr(group, n0, n6, ctx))
 783                 goto end;
 784         if (!field_sqr(group, n4, n5, ctx))
 785                 goto end;
 786         if (!field_mul(group, n3, n1, n4, ctx))
 787                 goto end;
 788         if (!BN_mod_sub_quick(&r->X, n0, n3, p))
 789                 goto end;
 790         /* X_r = n6^2 - n5^2 * 'n7' */
 791
 792         /* 'n9' */
 793         if (!BN_mod_lshift1_quick(n0, &r->X, p))
 794                 goto end;
 795         if (!BN_mod_sub_quick(n0, n3, n0, p))
 796                 goto end;
 797         /* n9 = n5^2 * 'n7' - 2 * X_r */
 798
 799         /* Y_r */
 800         if (!field_mul(group, n0, n0, n6, ctx))
 801                 goto end;
 802         if (!field_mul(group, n5, n4, n5, ctx))
 803                 goto end;       /* now n5 is n5^3 */
 804         if (!field_mul(group, n1, n2, n5, ctx))
 805                 goto end;
 806         if (!BN_mod_sub_quick(n0, n0, n1, p))
 807                 goto end;
 808         if (BN_is_odd(n0))
 809                 if (!BN_add(n0, n0, p))
 810                         goto end;
 811         /* now  0 <= n0 < 2*p,  and n0 is even */
 812         if (!BN_rshift1(&r->Y, n0))
 813                 goto end;
 814         /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
 815
 816         ret = 1;
 817
 818  end:
 819         if (ctx)                /* otherwise we already called BN_CTX_end */
 820                 BN_CTX_end(ctx);
 821         BN_CTX_free(new_ctx);
 822         return ret;
 823 }
 824
 825
 826 int
 827 ec_GFp_simple_dbl(const EC_GROUP * group, EC_POINT * r, const EC_POINT * a, BN_CTX * ctx)
 828 {
 829         int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
 830         int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 831         const BIGNUM *p;
 832         BN_CTX *new_ctx = NULL;
 833         BIGNUM *n0, *n1, *n2, *n3;
 834         int ret = 0;
 835
 836         if (EC_POINT_is_at_infinity(group, a) > 0) {
 837                 BN_zero(&r->Z);
 838                 r->Z_is_one = 0;
 839                 return 1;
 840         }
 841         field_mul = group->meth->field_mul;
 842         field_sqr = group->meth->field_sqr;
 843         p = &group->field;
 844
 845         if (ctx == NULL) {
 846                 ctx = new_ctx = BN_CTX_new();
 847                 if (ctx == NULL)
 848                         return 0;
 849         }
 850         BN_CTX_start(ctx);
 851         if ((n0 = BN_CTX_get(ctx)) == NULL)
 852                 goto err;
 853         if ((n1 = BN_CTX_get(ctx)) == NULL)
 854                 goto err;
 855         if ((n2 = BN_CTX_get(ctx)) == NULL)
 856                 goto err;
 857         if ((n3 = BN_CTX_get(ctx)) == NULL)
 858                 goto err;
 859
 860         /*
 861          * Note that in this function we must not read components of 'a' once
 862          * we have written the corresponding components of 'r'. ('r' might
 863          * the same as 'a'.)
 864          */
 865
 866         /* n1 */
 867         if (a->Z_is_one) {
 868                 if (!field_sqr(group, n0, &a->X, ctx))
 869                         goto err;
 870                 if (!BN_mod_lshift1_quick(n1, n0, p))
 871                         goto err;
 872                 if (!BN_mod_add_quick(n0, n0, n1, p))
 873                         goto err;
 874                 if (!BN_mod_add_quick(n1, n0, &group->a, p))
 875                         goto err;
 876                 /* n1 = 3 * X_a^2 + a_curve */
 877         } else if (group->a_is_minus3) {
 878                 if (!field_sqr(group, n1, &a->Z, ctx))
 879                         goto err;
 880                 if (!BN_mod_add_quick(n0, &a->X, n1, p))
 881                         goto err;
 882                 if (!BN_mod_sub_quick(n2, &a->X, n1, p))
 883                         goto err;
 884                 if (!field_mul(group, n1, n0, n2, ctx))
 885                         goto err;
 886                 if (!BN_mod_lshift1_quick(n0, n1, p))
 887                         goto err;
 888                 if (!BN_mod_add_quick(n1, n0, n1, p))
 889                         goto err;
 890                 /*
 891                  * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) = 3 * X_a^2 - 3 *
 892                  * Z_a^4
 893                  */
 894         } else {
 895                 if (!field_sqr(group, n0, &a->X, ctx))
 896                         goto err;
 897                 if (!BN_mod_lshift1_quick(n1, n0, p))
 898                         goto err;
 899                 if (!BN_mod_add_quick(n0, n0, n1, p))
 900                         goto err;
 901                 if (!field_sqr(group, n1, &a->Z, ctx))
 902                         goto err;
 903                 if (!field_sqr(group, n1, n1, ctx))
 904                         goto err;
 905                 if (!field_mul(group, n1, n1, &group->a, ctx))
 906                         goto err;
 907                 if (!BN_mod_add_quick(n1, n1, n0, p))
 908                         goto err;
 909                 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
 910         }
 911
 912         /* Z_r */
 913         if (a->Z_is_one) {
 914                 if (!BN_copy(n0, &a->Y))
 915                         goto err;
 916         } else {
 917                 if (!field_mul(group, n0, &a->Y, &a->Z, ctx))
 918                         goto err;
 919         }
 920         if (!BN_mod_lshift1_quick(&r->Z, n0, p))
 921                 goto err;
 922         r->Z_is_one = 0;
 923         /* Z_r = 2 * Y_a * Z_a */
 924
 925         /* n2 */
 926         if (!field_sqr(group, n3, &a->Y, ctx))
 927                 goto err;
 928         if (!field_mul(group, n2, &a->X, n3, ctx))
 929                 goto err;
 930         if (!BN_mod_lshift_quick(n2, n2, 2, p))
 931                 goto err;
 932         /* n2 = 4 * X_a * Y_a^2 */
 933
 934         /* X_r */
 935         if (!BN_mod_lshift1_quick(n0, n2, p))
 936                 goto err;
 937         if (!field_sqr(group, &r->X, n1, ctx))
 938                 goto err;
 939         if (!BN_mod_sub_quick(&r->X, &r->X, n0, p))
 940                 goto err;
 941         /* X_r = n1^2 - 2 * n2 */
 942
 943         /* n3 */
 944         if (!field_sqr(group, n0, n3, ctx))
 945                 goto err;
 946         if (!BN_mod_lshift_quick(n3, n0, 3, p))
 947                 goto err;
 948         /* n3 = 8 * Y_a^4 */
 949
 950         /* Y_r */
 951         if (!BN_mod_sub_quick(n0, n2, &r->X, p))
 952                 goto err;
 953         if (!field_mul(group, n0, n1, n0, ctx))
 954                 goto err;
 955         if (!BN_mod_sub_quick(&r->Y, n0, n3, p))
 956                 goto err;
 957         /* Y_r = n1 * (n2 - X_r) - n3 */
 958
 959         ret = 1;
 960
 961  err:
 962         BN_CTX_end(ctx);
 963         BN_CTX_free(new_ctx);
 964         return ret;
 965 }
 966
 967
 968 int
 969 ec_GFp_simple_invert(const EC_GROUP * group, EC_POINT * point, BN_CTX * ctx)
 970 {
 971         if (EC_POINT_is_at_infinity(group, point) > 0 || BN_is_zero(&point->Y))
 972                 /* point is its own inverse */
 973                 return 1;
 974
 975         return BN_usub(&point->Y, &group->field, &point->Y);
 976 }
 977
 978
 979 int
 980 ec_GFp_simple_is_at_infinity(const EC_GROUP * group, const EC_POINT * point)
 981 {
 982         return BN_is_zero(&point->Z);
 983 }
 984
 985
 986 int
 987 ec_GFp_simple_is_on_curve(const EC_GROUP * group, const EC_POINT * point, BN_CTX * ctx)
 988 {
 989         int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
 990         int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 991         const BIGNUM *p;
 992         BN_CTX *new_ctx = NULL;
 993         BIGNUM *rh, *tmp, *Z4, *Z6;
 994         int ret = -1;
 995
 996         if (EC_POINT_is_at_infinity(group, point) > 0)
 997                 return 1;
 998
 999         field_mul = group->meth->field_mul;
1000         field_sqr = group->meth->field_sqr;
1001         p = &group->field;
1002
1003         if (ctx == NULL) {
1004                 ctx = new_ctx = BN_CTX_new();
1005                 if (ctx == NULL)
1006                         return -1;
1007         }
1008         BN_CTX_start(ctx);
1009         if ((rh = BN_CTX_get(ctx)) == NULL)
1010                 goto err;
1011         if ((tmp = BN_CTX_get(ctx)) == NULL)
1012                 goto err;
1013         if ((Z4 = BN_CTX_get(ctx)) == NULL)
1014                 goto err;
1015         if ((Z6 = BN_CTX_get(ctx)) == NULL)
1016                 goto err;
1017
1018         /*
1019          * We have a curve defined by a Weierstrass equation y^2 = x^3 + a*x
1020          * + b. The point to consider is given in Jacobian projective
1021          * coordinates where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
1022          * Substituting this and multiplying by  Z^6  transforms the above
1023          * equation into Y^2 = X^3 + a*X*Z^4 + b*Z^6. To test this, we add up
1024          * the right-hand side in 'rh'.
1025          */
1026
1027         /* rh := X^2 */
1028         if (!field_sqr(group, rh, &point->X, ctx))
1029                 goto err;
1030
1031         if (!point->Z_is_one) {
1032                 if (!field_sqr(group, tmp, &point->Z, ctx))
1033                         goto err;
1034                 if (!field_sqr(group, Z4, tmp, ctx))
1035                         goto err;
1036                 if (!field_mul(group, Z6, Z4, tmp, ctx))
1037                         goto err;
1038
1039                 /* rh := (rh + a*Z^4)*X */
1040                 if (group->a_is_minus3) {
1041                         if (!BN_mod_lshift1_quick(tmp, Z4, p))
1042                                 goto err;
1043                         if (!BN_mod_add_quick(tmp, tmp, Z4, p))
1044                                 goto err;
1045                         if (!BN_mod_sub_quick(rh, rh, tmp, p))
1046                                 goto err;
1047                         if (!field_mul(group, rh, rh, &point->X, ctx))
1048                                 goto err;
1049                 } else {
1050                         if (!field_mul(group, tmp, Z4, &group->a, ctx))
1051                                 goto err;
1052                         if (!BN_mod_add_quick(rh, rh, tmp, p))
1053                                 goto err;
1054                         if (!field_mul(group, rh, rh, &point->X, ctx))
1055                                 goto err;
1056                 }
1057
1058                 /* rh := rh + b*Z^6 */
1059                 if (!field_mul(group, tmp, &group->b, Z6, ctx))
1060                         goto err;
1061                 if (!BN_mod_add_quick(rh, rh, tmp, p))
1062                         goto err;
1063         } else {
1064                 /* point->Z_is_one */
1065
1066                 /* rh := (rh + a)*X */
1067                 if (!BN_mod_add_quick(rh, rh, &group->a, p))
1068                         goto err;
1069                 if (!field_mul(group, rh, rh, &point->X, ctx))
1070                         goto err;
1071                 /* rh := rh + b */
1072                 if (!BN_mod_add_quick(rh, rh, &group->b, p))
1073                         goto err;
1074         }
1075
1076         /* 'lh' := Y^2 */
1077         if (!field_sqr(group, tmp, &point->Y, ctx))
1078                 goto err;
1079
1080         ret = (0 == BN_ucmp(tmp, rh));
1081
1082  err:
1083         BN_CTX_end(ctx);
1084         BN_CTX_free(new_ctx);
1085         return ret;
1086 }
1087
1088
1089 int
1090 ec_GFp_simple_cmp(const EC_GROUP * group, const EC_POINT * a, const EC_POINT * b, BN_CTX * ctx)
1091 {
1092         /*
1093          * return values: -1   error 0   equal (in affine coordinates) 1
1094          * not equal
1095          */
1096
1097         int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1098         int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1099         BN_CTX *new_ctx = NULL;
1100         BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1101         const BIGNUM *tmp1_, *tmp2_;
1102         int ret = -1;
1103
1104         if (EC_POINT_is_at_infinity(group, a) > 0) {
1105                 return EC_POINT_is_at_infinity(group, b) > 0 ? 0 : 1;
1106         }
1107         if (EC_POINT_is_at_infinity(group, b) > 0)
1108                 return 1;
1109
1110         if (a->Z_is_one && b->Z_is_one) {
1111                 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
1112         }
1113         field_mul = group->meth->field_mul;
1114         field_sqr = group->meth->field_sqr;
1115
1116         if (ctx == NULL) {
1117                 ctx = new_ctx = BN_CTX_new();
1118                 if (ctx == NULL)
1119                         return -1;
1120         }
1121         BN_CTX_start(ctx);
1122         if ((tmp1 = BN_CTX_get(ctx)) == NULL)
1123                 goto end;
1124         if ((tmp2 = BN_CTX_get(ctx)) == NULL)
1125                 goto end;
1126         if ((Za23 = BN_CTX_get(ctx)) == NULL)
1127                 goto end;
1128         if ((Zb23 = BN_CTX_get(ctx)) == NULL)
1129                 goto end;
1130
1131         /*
1132          * We have to decide whether (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2,
1133          * Y_b/Z_b^3), or equivalently, whether (X_a*Z_b^2, Y_a*Z_b^3) =
1134          * (X_b*Z_a^2, Y_b*Z_a^3).
1135          */
1136
1137         if (!b->Z_is_one) {
1138                 if (!field_sqr(group, Zb23, &b->Z, ctx))
1139                         goto end;
1140                 if (!field_mul(group, tmp1, &a->X, Zb23, ctx))
1141                         goto end;
1142                 tmp1_ = tmp1;
1143         } else
1144                 tmp1_ = &a->X;
1145         if (!a->Z_is_one) {
1146                 if (!field_sqr(group, Za23, &a->Z, ctx))
1147                         goto end;
1148                 if (!field_mul(group, tmp2, &b->X, Za23, ctx))
1149                         goto end;
1150                 tmp2_ = tmp2;
1151         } else
1152                 tmp2_ = &b->X;
1153
1154         /* compare  X_a*Z_b^2  with  X_b*Z_a^2 */
1155         if (BN_cmp(tmp1_, tmp2_) != 0) {
1156                 ret = 1;        /* points differ */
1157                 goto end;
1158         }
1159         if (!b->Z_is_one) {
1160                 if (!field_mul(group, Zb23, Zb23, &b->Z, ctx))
1161                         goto end;
1162                 if (!field_mul(group, tmp1, &a->Y, Zb23, ctx))
1163                         goto end;
1164                 /* tmp1_ = tmp1 */
1165         } else
1166                 tmp1_ = &a->Y;
1167         if (!a->Z_is_one) {
1168                 if (!field_mul(group, Za23, Za23, &a->Z, ctx))
1169                         goto end;
1170                 if (!field_mul(group, tmp2, &b->Y, Za23, ctx))
1171                         goto end;
1172                 /* tmp2_ = tmp2 */
1173         } else
1174                 tmp2_ = &b->Y;
1175
1176         /* compare  Y_a*Z_b^3  with  Y_b*Z_a^3 */
1177         if (BN_cmp(tmp1_, tmp2_) != 0) {
1178                 ret = 1;        /* points differ */
1179                 goto end;
1180         }
1181         /* points are equal */
1182         ret = 0;
1183
1184  end:
1185         BN_CTX_end(ctx);
1186         BN_CTX_free(new_ctx);
1187         return ret;
1188 }
1189
1190
1191 int
1192 ec_GFp_simple_make_affine(const EC_GROUP * group, EC_POINT * point, BN_CTX * ctx)
1193 {
1194         BN_CTX *new_ctx = NULL;
1195         BIGNUM *x, *y;
1196         int ret = 0;
1197
1198         if (point->Z_is_one || EC_POINT_is_at_infinity(group, point) > 0)
1199                 return 1;
1200
1201         if (ctx == NULL) {
1202                 ctx = new_ctx = BN_CTX_new();
1203                 if (ctx == NULL)
1204                         return 0;
1205         }
1206         BN_CTX_start(ctx);
1207         if ((x = BN_CTX_get(ctx)) == NULL)
1208                 goto err;
1209         if ((y = BN_CTX_get(ctx)) == NULL)
1210                 goto err;
1211
1212         if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
1213                 goto err;
1214         if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
1215                 goto err;
1216         if (!point->Z_is_one) {
1217                 ECerror(ERR_R_INTERNAL_ERROR);
1218                 goto err;
1219         }
1220         ret = 1;
1221
1222  err:
1223         BN_CTX_end(ctx);
1224         BN_CTX_free(new_ctx);
1225         return ret;
1226 }
1227
1228
1229 int
1230 ec_GFp_simple_points_make_affine(const EC_GROUP * group, size_t num, EC_POINT * points[], BN_CTX * ctx)
1231 {
1232         BN_CTX *new_ctx = NULL;
1233         BIGNUM *tmp0, *tmp1;
1234         size_t pow2 = 0;
1235         BIGNUM **heap = NULL;
1236         size_t i;
1237         int ret = 0;
1238
1239         if (num == 0)
1240                 return 1;
1241
1242         if (ctx == NULL) {
1243                 ctx = new_ctx = BN_CTX_new();
1244                 if (ctx == NULL)
1245                         return 0;
1246         }
1247         BN_CTX_start(ctx);
1248         if ((tmp0 = BN_CTX_get(ctx)) == NULL)
1249                 goto err;
1250         if ((tmp1 = BN_CTX_get(ctx)) == NULL)
1251                 goto err;
1252
1253         /*
1254          * Before converting the individual points, compute inverses of all Z
1255          * values. Modular inversion is rather slow, but luckily we can do
1256          * with a single explicit inversion, plus about 3 multiplications per
1257          * input value.
1258          */
1259
1260         pow2 = 1;
1261         while (num > pow2)
1262                 pow2 <<= 1;
1263         /*
1264          * Now pow2 is the smallest power of 2 satifsying pow2 >= num. We
1265          * need twice that.
1266          */
1267         pow2 <<= 1;
1268
1269         heap = reallocarray(NULL, pow2, sizeof heap[0]);
1270         if (heap == NULL)
1271                 goto err;
1272
1273         /*
1274          * The array is used as a binary tree, exactly as in heapsort:
1275          *
1276          * heap[1] heap[2]                     heap[3] heap[4]       heap[5]
1277          * heap[6]       heap[7] heap[8]heap[9] heap[10]heap[11]
1278          * heap[12]heap[13] heap[14] heap[15]
1279          *
1280          * We put the Z's in the last line; then we set each other node to the
1281          * product of its two child-nodes (where empty or 0 entries are
1282          * treated as ones); then we invert heap[1]; then we invert each
1283          * other node by replacing it by the product of its parent (after
1284          * inversion) and its sibling (before inversion).
1285          */
1286         heap[0] = NULL;
1287         for (i = pow2 / 2 - 1; i > 0; i--)
1288                 heap[i] = NULL;
1289         for (i = 0; i < num; i++)
1290                 heap[pow2 / 2 + i] = &points[i]->Z;
1291         for (i = pow2 / 2 + num; i < pow2; i++)
1292                 heap[i] = NULL;
1293
1294         /* set each node to the product of its children */
1295         for (i = pow2 / 2 - 1; i > 0; i--) {
1296                 heap[i] = BN_new();
1297                 if (heap[i] == NULL)
1298                         goto err;
1299
1300                 if (heap[2 * i] != NULL) {
1301                         if ((heap[2 * i + 1] == NULL) || BN_is_zero(heap[2 * i + 1])) {
1302                                 if (!BN_copy(heap[i], heap[2 * i]))
1303                                         goto err;
1304                         } else {
1305                                 if (BN_is_zero(heap[2 * i])) {
1306                                         if (!BN_copy(heap[i], heap[2 * i + 1]))
1307                                                 goto err;
1308                                 } else {
1309                                         if (!group->meth->field_mul(group, heap[i],
1310                                                 heap[2 * i], heap[2 * i + 1], ctx))
1311                                                 goto err;
1312                                 }
1313                         }
1314                 }
1315         }
1316
1317         /* invert heap[1] */
1318         if (!BN_is_zero(heap[1])) {
1319                 if (!BN_mod_inverse_ct(heap[1], heap[1], &group->field, ctx)) {
1320                         ECerror(ERR_R_BN_LIB);
1321                         goto err;
1322                 }
1323         }
1324         if (group->meth->field_encode != 0) {
1325                 /*
1326                  * in the Montgomery case, we just turned  R*H  (representing
1327                  * H) into  1/(R*H),  but we need  R*(1/H)  (representing
1328                  * 1/H); i.e. we have need to multiply by the Montgomery
1329                  * factor twice
1330                  */
1331                 if (!group->meth->field_encode(group, heap[1], heap[1], ctx))
1332                         goto err;
1333                 if (!group->meth->field_encode(group, heap[1], heap[1], ctx))
1334                         goto err;
1335         }
1336         /* set other heap[i]'s to their inverses */
1337         for (i = 2; i < pow2 / 2 + num; i += 2) {
1338                 /* i is even */
1339                 if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1])) {
1340                         if (!group->meth->field_mul(group, tmp0, heap[i / 2], heap[i + 1], ctx))
1341                                 goto err;
1342                         if (!group->meth->field_mul(group, tmp1, heap[i / 2], heap[i], ctx))
1343                                 goto err;
1344                         if (!BN_copy(heap[i], tmp0))
1345                                 goto err;
1346                         if (!BN_copy(heap[i + 1], tmp1))
1347                                 goto err;
1348                 } else {
1349                         if (!BN_copy(heap[i], heap[i / 2]))
1350                                 goto err;
1351                 }
1352         }
1353
1354         /*
1355          * we have replaced all non-zero Z's by their inverses, now fix up
1356          * all the points
1357          */
1358         for (i = 0; i < num; i++) {
1359                 EC_POINT *p = points[i];
1360
1361                 if (!BN_is_zero(&p->Z)) {
1362                         /* turn  (X, Y, 1/Z)  into  (X/Z^2, Y/Z^3, 1) */
1363
1364                         if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx))
1365                                 goto err;
1366                         if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx))
1367                                 goto err;
1368
1369                         if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx))
1370                                 goto err;
1371                         if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx))
1372                                 goto err;
1373
1374                         if (group->meth->field_set_to_one != 0) {
1375                                 if (!group->meth->field_set_to_one(group, &p->Z, ctx))
1376                                         goto err;
1377                         } else {
1378                                 if (!BN_one(&p->Z))
1379                                         goto err;
1380                         }
1381                         p->Z_is_one = 1;
1382                 }
1383         }
1384
1385         ret = 1;
1386
1387  err:
1388         BN_CTX_end(ctx);
1389         BN_CTX_free(new_ctx);
1390         if (heap != NULL) {
1391                 /*
1392                  * heap[pow2/2] .. heap[pow2-1] have not been allocated
1393                  * locally!
1394                  */
1395                 for (i = pow2 / 2 - 1; i > 0; i--) {
1396                         BN_clear_free(heap[i]);
1397                 }
1398                 free(heap);
1399         }
1400         return ret;
1401 }
1402
1403
1404 int
1405 ec_GFp_simple_field_mul(const EC_GROUP * group, BIGNUM * r, const BIGNUM * a, const BIGNUM * b, BN_CTX * ctx)
1406 {
1407         return BN_mod_mul(r, a, b, &group->field, ctx);
1408 }
1409
1410 int
1411 ec_GFp_simple_field_sqr(const EC_GROUP * group, BIGNUM * r, const BIGNUM * a, BN_CTX * ctx)
1412 {
1413         return BN_mod_sqr(r, a, &group->field, ctx);
1414 }
1415
1416 /*
1417  * Apply randomization of EC point projective coordinates:
1418  *
1419  *      (X, Y, Z) = (lambda^2 * X, lambda^3 * Y, lambda * Z)
1420  *
1421  * where lambda is in the interval [1, group->field).
1422  */
1423 int
1424 ec_GFp_simple_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx)
1425 {
1426         BIGNUM *lambda = NULL;
1427         BIGNUM *tmp = NULL;
1428         int ret = 0;
1429
1430         BN_CTX_start(ctx);
1431         if ((lambda = BN_CTX_get(ctx)) == NULL)
1432                 goto err;
1433         if ((tmp = BN_CTX_get(ctx)) == NULL)
1434                 goto err;
1435
1436         /* Generate lambda in [1, group->field - 1] */
1437         if (!bn_rand_interval(lambda, BN_value_one(), &group->field))
1438                 goto err;
1439
1440         if (group->meth->field_encode != NULL &&
1441             !group->meth->field_encode(group, lambda, lambda, ctx))
1442                 goto err;
1443
1444         /* Z = lambda * Z */
1445         if (!group->meth->field_mul(group, &p->Z, lambda, &p->Z, ctx))
1446                 goto err;
1447
1448         /* tmp = lambda^2 */
1449         if (!group->meth->field_sqr(group, tmp, lambda, ctx))
1450                 goto err;
1451
1452         /* X = lambda^2 * X */
1453         if (!group->meth->field_mul(group, &p->X, tmp, &p->X, ctx))
1454                 goto err;
1455
1456         /* tmp = lambda^3 */
1457         if (!group->meth->field_mul(group, tmp, tmp, lambda, ctx))
1458                 goto err;
1459
1460         /* Y = lambda^3 * Y */
1461         if (!group->meth->field_mul(group, &p->Y, tmp, &p->Y, ctx))
1462                 goto err;
1463
1464         /* Disable optimized arithmetics after replacing Z by lambda * Z. */
1465         p->Z_is_one = 0;
1466
1467         ret = 1;
1468
1469  err:
1470         BN_CTX_end(ctx);
1471         return ret;
1472 }
1473
1474
1475 #define EC_POINT_BN_set_flags(P, flags) do {                            \
1476         BN_set_flags(&(P)->X, (flags));                                 \
1477         BN_set_flags(&(P)->Y, (flags));                                 \
1478         BN_set_flags(&(P)->Z, (flags));                                 \
1479 } while(0)
1480
1481 #define EC_POINT_CSWAP(c, a, b, w, t) do {                              \
1482         if (!BN_swap_ct(c, &(a)->X, &(b)->X, w) ||                      \
1483             !BN_swap_ct(c, &(a)->Y, &(b)->Y, w) ||                      \
1484             !BN_swap_ct(c, &(a)->Z, &(b)->Z, w))                        \
1485                 goto err;                                               \
1486         t = ((a)->Z_is_one ^ (b)->Z_is_one) & (c);                      \
1487         (a)->Z_is_one ^= (t);                                           \
1488         (b)->Z_is_one ^= (t);                                           \
1489 } while(0)
1490
1491 /*
1492  * This function computes (in constant time) a point multiplication over the
1493  * EC group.
1494  *
1495  * At a high level, it is Montgomery ladder with conditional swaps.
1496  *
1497  * It performs either a fixed point multiplication
1498  *          (scalar * generator)
1499  * when point is NULL, or a variable point multiplication
1500  *          (scalar * point)
1501  * when point is not NULL.
1502  *
1503  * scalar should be in the range [0,n) otherwise all constant time bets are off.
1504  *
1505  * NB: This says nothing about EC_POINT_add and EC_POINT_dbl,
1506  * which of course are not constant time themselves.
1507  *
1508  * The product is stored in r.
1509  *
1510  * Returns 1 on success, 0 otherwise.
1511  */
1512 static int
1513 ec_GFp_simple_mul_ct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
1514     const EC_POINT *point, BN_CTX *ctx)
1515 {
1516         int i, cardinality_bits, group_top, kbit, pbit, Z_is_one;
1517         EC_POINT *s = NULL;
1518         BIGNUM *k = NULL;
1519         BIGNUM *lambda = NULL;
1520         BIGNUM *cardinality = NULL;
1521         BN_CTX *new_ctx = NULL;
1522         int ret = 0;
1523
1524         if (ctx == NULL && (ctx = new_ctx = BN_CTX_new()) == NULL)
1525                 return 0;
1526
1527         BN_CTX_start(ctx);
1528
1529         if ((s = EC_POINT_new(group)) == NULL)
1530                 goto err;
1531
1532         if (point == NULL) {
1533                 if (!EC_POINT_copy(s, group->generator))
1534                         goto err;
1535         } else {
1536                 if (!EC_POINT_copy(s, point))
1537                         goto err;
1538         }
1539
1540         EC_POINT_BN_set_flags(s, BN_FLG_CONSTTIME);
1541
1542         if ((cardinality = BN_CTX_get(ctx)) == NULL)
1543                 goto err;
1544         if ((lambda = BN_CTX_get(ctx)) == NULL)
1545                 goto err;
1546         if ((k = BN_CTX_get(ctx)) == NULL)
1547                 goto err;
1548         if (!BN_mul(cardinality, &group->order, &group->cofactor, ctx))
1549                 goto err;
1550
1551         /*
1552          * Group cardinalities are often on a word boundary.
1553          * So when we pad the scalar, some timing diff might
1554          * pop if it needs to be expanded due to carries.
1555          * So expand ahead of time.
1556          */
1557         cardinality_bits = BN_num_bits(cardinality);
1558         group_top = cardinality->top;
1559         if ((bn_wexpand(k, group_top + 2) == NULL) ||
1560             (bn_wexpand(lambda, group_top + 2) == NULL))
1561                 goto err;
1562
1563         if (!BN_copy(k, scalar))
1564                 goto err;
1565
1566         BN_set_flags(k, BN_FLG_CONSTTIME);
1567
1568         if (BN_num_bits(k) > cardinality_bits || BN_is_negative(k)) {
1569                 /*
1570                  * This is an unusual input, and we don't guarantee
1571                  * constant-timeness
1572                  */
1573                 if (!BN_nnmod(k, k, cardinality, ctx))
1574                         goto err;
1575         }
1576
1577         if (!BN_add(lambda, k, cardinality))
1578                 goto err;
1579         BN_set_flags(lambda, BN_FLG_CONSTTIME);
1580         if (!BN_add(k, lambda, cardinality))
1581                 goto err;
1582         /*
1583          * lambda := scalar + cardinality
1584          * k := scalar + 2*cardinality
1585          */
1586         kbit = BN_is_bit_set(lambda, cardinality_bits);
1587         if (!BN_swap_ct(kbit, k, lambda, group_top + 2))
1588                 goto err;
1589
1590         group_top = group->field.top;
1591         if ((bn_wexpand(&s->X, group_top) == NULL) ||
1592             (bn_wexpand(&s->Y, group_top) == NULL) ||
1593             (bn_wexpand(&s->Z, group_top) == NULL) ||
1594             (bn_wexpand(&r->X, group_top) == NULL) ||
1595             (bn_wexpand(&r->Y, group_top) == NULL) ||
1596             (bn_wexpand(&r->Z, group_top) == NULL))
1597                 goto err;
1598
1599         /*
1600          * Apply coordinate blinding for EC_POINT if the underlying EC_METHOD
1601          * implements it.
1602          */
1603         if (!ec_point_blind_coordinates(group, s, ctx))
1604                 goto err;
1605
1606         /* top bit is a 1, in a fixed pos */
1607         if (!EC_POINT_copy(r, s))
1608                 goto err;
1609
1610         EC_POINT_BN_set_flags(r, BN_FLG_CONSTTIME);
1611
1612         if (!EC_POINT_dbl(group, s, s, ctx))
1613                 goto err;
1614
1615         pbit = 0;
1616
1617         /*
1618          * The ladder step, with branches, is
1619          *
1620          * k[i] == 0: S = add(R, S), R = dbl(R)
1621          * k[i] == 1: R = add(S, R), S = dbl(S)
1622          *
1623          * Swapping R, S conditionally on k[i] leaves you with state
1624          *
1625          * k[i] == 0: T, U = R, S
1626          * k[i] == 1: T, U = S, R
1627          *
1628          * Then perform the ECC ops.
1629          *
1630          * U = add(T, U)
1631          * T = dbl(T)
1632          *
1633          * Which leaves you with state
1634          *
1635          * k[i] == 0: U = add(R, S), T = dbl(R)
1636          * k[i] == 1: U = add(S, R), T = dbl(S)
1637          *
1638          * Swapping T, U conditionally on k[i] leaves you with state
1639          *
1640          * k[i] == 0: R, S = T, U
1641          * k[i] == 1: R, S = U, T
1642          *
1643          * Which leaves you with state
1644          *
1645          * k[i] == 0: S = add(R, S), R = dbl(R)
1646          * k[i] == 1: R = add(S, R), S = dbl(S)
1647          *
1648          * So we get the same logic, but instead of a branch it's a
1649          * conditional swap, followed by ECC ops, then another conditional swap.
1650          *
1651          * Optimization: The end of iteration i and start of i-1 looks like
1652          *
1653          * ...
1654          * CSWAP(k[i], R, S)
1655          * ECC
1656          * CSWAP(k[i], R, S)
1657          * (next iteration)
1658          * CSWAP(k[i-1], R, S)
1659          * ECC
1660          * CSWAP(k[i-1], R, S)
1661          * ...
1662          *
1663          * So instead of two contiguous swaps, you can merge the condition
1664          * bits and do a single swap.
1665          *
1666          * k[i]   k[i-1]    Outcome
1667          * 0      0         No Swap
1668          * 0      1         Swap
1669          * 1      0         Swap
1670          * 1      1         No Swap
1671          *
1672          * This is XOR. pbit tracks the previous bit of k.
1673          */
1674
1675         for (i = cardinality_bits - 1; i >= 0; i--) {
1676                 kbit = BN_is_bit_set(k, i) ^ pbit;
1677                 EC_POINT_CSWAP(kbit, r, s, group_top, Z_is_one);
1678                 if (!EC_POINT_add(group, s, r, s, ctx))
1679                         goto err;
1680                 if (!EC_POINT_dbl(group, r, r, ctx))
1681                         goto err;
1682                 /*
1683                  * pbit logic merges this cswap with that of the
1684                  * next iteration
1685                  */
1686                 pbit ^= kbit;
1687         }
1688         /* one final cswap to move the right value into r */
1689         EC_POINT_CSWAP(pbit, r, s, group_top, Z_is_one);
1690
1691         ret = 1;
1692
1693  err:
1694         EC_POINT_free(s);
1695         if (ctx != NULL)
1696                 BN_CTX_end(ctx);
1697         BN_CTX_free(new_ctx);
1698
1699         return ret;
1700 }
1701
1702 #undef EC_POINT_BN_set_flags
1703 #undef EC_POINT_CSWAP
1704
1705 int
1706 ec_GFp_simple_mul_generator_ct(const EC_GROUP *group, EC_POINT *r,
1707     const BIGNUM *scalar, BN_CTX *ctx)
1708 {
1709         return ec_GFp_simple_mul_ct(group, r, scalar, NULL, ctx);
1710 }
1711
1712 int
1713 ec_GFp_simple_mul_single_ct(const EC_GROUP *group, EC_POINT *r,
1714     const BIGNUM *scalar, const EC_POINT *point, BN_CTX *ctx)
1715 {
1716         return ec_GFp_simple_mul_ct(group, r, scalar, point, ctx);
1717 }
1718
1719 int
1720 ec_GFp_simple_mul_double_nonct(const EC_GROUP *group, EC_POINT *r,
1721     const BIGNUM *g_scalar, const BIGNUM *p_scalar, const EC_POINT *point,
1722     BN_CTX *ctx)
1723 {
1724         return ec_wNAF_mul(group, r, g_scalar, 1, &point, &p_scalar, ctx);
1725 }