crypto/ec/ecp_smpl.c

   1 /* crypto/ec/ecp_smpl.c */
   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 #include <openssl/symhacks.h>
  67
  68 #ifdef OPENSSL_FIPS
  69 #include <openssl/fips.h>
  70 #endif
  71
  72 #include "ec_lcl.h"
  73
  74 const EC_METHOD *EC_GFp_simple_method(void)
  75         {
  76         static const EC_METHOD ret = {
  77                 EC_FLAGS_DEFAULT_OCT,
  78                 NID_X9_62_prime_field,
  79                 ec_GFp_simple_group_init,
  80                 ec_GFp_simple_group_finish,
  81                 ec_GFp_simple_group_clear_finish,
  82                 ec_GFp_simple_group_copy,
  83                 ec_GFp_simple_group_set_curve,
  84                 ec_GFp_simple_group_get_curve,
  85                 ec_GFp_simple_group_get_degree,
  86                 ec_GFp_simple_group_check_discriminant,
  87                 ec_GFp_simple_point_init,
  88                 ec_GFp_simple_point_finish,
  89                 ec_GFp_simple_point_clear_finish,
  90                 ec_GFp_simple_point_copy,
  91                 ec_GFp_simple_point_set_to_infinity,
  92                 ec_GFp_simple_set_Jprojective_coordinates_GFp,
  93                 ec_GFp_simple_get_Jprojective_coordinates_GFp,
  94                 ec_GFp_simple_point_set_affine_coordinates,
  95                 ec_GFp_simple_point_get_affine_coordinates,
  96                 0,0,0,
  97                 ec_GFp_simple_add,
  98                 ec_GFp_simple_dbl,
  99                 ec_GFp_simple_invert,
 100                 ec_GFp_simple_is_at_infinity,
 101                 ec_GFp_simple_is_on_curve,
 102                 ec_GFp_simple_cmp,
 103                 ec_GFp_simple_make_affine,
 104                 ec_GFp_simple_points_make_affine,
 105                 0 /* mul */,
 106                 0 /* precompute_mult */,
 107                 0 /* have_precompute_mult */,
 108                 ec_GFp_simple_field_mul,
 109                 ec_GFp_simple_field_sqr,
 110                 0 /* field_div */,
 111                 0 /* field_encode */,
 112                 0 /* field_decode */,
 113                 0 /* field_set_to_one */ };
 114
 115 #ifdef OPENSSL_FIPS
 116         if (FIPS_mode())
 117                 return fips_ec_gfp_simple_method();
 118 #endif
 119
 120         return &ret;
 121         }
 122
 123
 124 /*
 125  * Most method functions in this file are designed to work with
 126  * non-trivial representations of field elements if necessary
 127  * (see ecp_mont.c): while standard modular addition and subtraction
 128  * are used, the field_mul and field_sqr methods will be used for
 129  * multiplication, and field_encode and field_decode (if defined)
 130  * will be used for converting between representations.
 131  *
 132  * Functions ec_GFp_simple_points_make_affine() and
 133  * ec_GFp_simple_point_get_affine_coordinates() specifically assume
 134  * that if a non-trivial representation is used, it is a Montgomery
 135  * representation (i.e. 'encoding' means multiplying by some factor R).
 136  */
 137
 138
 139 int ec_GFp_simple_group_init(EC_GROUP *group)
 140         {
 141         BN_init(&group->field);
 142         BN_init(&group->a);
 143         BN_init(&group->b);
 144         group->a_is_minus3 = 0;
 145         return 1;
 146         }
 147
 148
 149 void ec_GFp_simple_group_finish(EC_GROUP *group)
 150         {
 151         BN_free(&group->field);
 152         BN_free(&group->a);
 153         BN_free(&group->b);
 154         }
 155
 156
 157 void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
 158         {
 159         BN_clear_free(&group->field);
 160         BN_clear_free(&group->a);
 161         BN_clear_free(&group->b);
 162         }
 163
 164
 165 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
 166         {
 167         if (!BN_copy(&dest->field, &src->field)) return 0;
 168         if (!BN_copy(&dest->a, &src->a)) return 0;
 169         if (!BN_copy(&dest->b, &src->b)) return 0;
 170
 171         dest->a_is_minus3 = src->a_is_minus3;
 172
 173         return 1;
 174         }
 175
 176
 177 int ec_GFp_simple_group_set_curve(EC_GROUP *group,
 178         const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 179         {
 180         int ret = 0;
 181         BN_CTX *new_ctx = NULL;
 182         BIGNUM *tmp_a;
 183
 184         /* p must be a prime > 3 */
 185         if (BN_num_bits(p) <= 2 || !BN_is_odd(p))
 186                 {
 187                 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD);
 188                 return 0;
 189                 }
 190
 191         if (ctx == NULL)
 192                 {
 193                 ctx = new_ctx = BN_CTX_new();
 194                 if (ctx == NULL)
 195                         return 0;
 196                 }
 197
 198         BN_CTX_start(ctx);
 199         tmp_a = BN_CTX_get(ctx);
 200         if (tmp_a == NULL) goto err;
 201
 202         /* group->field */
 203         if (!BN_copy(&group->field, p)) goto err;
 204         BN_set_negative(&group->field, 0);
 205
 206         /* group->a */
 207         if (!BN_nnmod(tmp_a, a, p, ctx)) goto err;
 208         if (group->meth->field_encode)
 209                 { if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) goto err; }
 210         else
 211                 if (!BN_copy(&group->a, tmp_a)) goto err;
 212
 213         /* group->b */
 214         if (!BN_nnmod(&group->b, b, p, ctx)) goto err;
 215         if (group->meth->field_encode)
 216                 if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) goto err;
 217
 218         /* group->a_is_minus3 */
 219         if (!BN_add_word(tmp_a, 3)) goto err;
 220         group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
 221
 222         ret = 1;
 223
 224  err:
 225         BN_CTX_end(ctx);
 226         if (new_ctx != NULL)
 227                 BN_CTX_free(new_ctx);
 228         return ret;
 229         }
 230
 231
 232 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
 233         {
 234         int ret = 0;
 235         BN_CTX *new_ctx = NULL;
 236
 237         if (p != NULL)
 238                 {
 239                 if (!BN_copy(p, &group->field)) return 0;
 240                 }
 241
 242         if (a != NULL || b != NULL)
 243                 {
 244                 if (group->meth->field_decode)
 245                         {
 246                         if (ctx == NULL)
 247                                 {
 248                                 ctx = new_ctx = BN_CTX_new();
 249                                 if (ctx == NULL)
 250                                         return 0;
 251                                 }
 252                         if (a != NULL)
 253                                 {
 254                                 if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
 255                                 }
 256                         if (b != NULL)
 257                                 {
 258                                 if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
 259                                 }
 260                         }
 261                 else
 262                         {
 263                         if (a != NULL)
 264                                 {
 265                                 if (!BN_copy(a, &group->a)) goto err;
 266                                 }
 267                         if (b != NULL)
 268                                 {
 269                                 if (!BN_copy(b, &group->b)) goto err;
 270                                 }
 271                         }
 272                 }
 273
 274         ret = 1;
 275
 276  err:
 277         if (new_ctx)
 278                 BN_CTX_free(new_ctx);
 279         return ret;
 280         }
 281
 282
 283 int ec_GFp_simple_group_get_degree(const EC_GROUP *group)
 284         {
 285         return BN_num_bits(&group->field);
 286         }
 287
 288
 289 int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
 290         {
 291         int ret = 0;
 292         BIGNUM *a,*b,*order,*tmp_1,*tmp_2;
 293         const BIGNUM *p = &group->field;
 294         BN_CTX *new_ctx = NULL;
 295
 296         if (ctx == NULL)
 297                 {
 298                 ctx = new_ctx = BN_CTX_new();
 299                 if (ctx == NULL)
 300                         {
 301                         ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE);
 302                         goto err;
 303                         }
 304                 }
 305         BN_CTX_start(ctx);
 306         a = BN_CTX_get(ctx);
 307         b = BN_CTX_get(ctx);
 308         tmp_1 = BN_CTX_get(ctx);
 309         tmp_2 = BN_CTX_get(ctx);
 310         order = BN_CTX_get(ctx);
 311         if (order == NULL) goto err;
 312
 313         if (group->meth->field_decode)
 314                 {
 315                 if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
 316                 if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
 317                 }
 318         else
 319                 {
 320                 if (!BN_copy(a, &group->a)) goto err;
 321                 if (!BN_copy(b, &group->b)) goto err;
 322                 }
 323
 324         /*-
 325          * check the discriminant:
 326          * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
 327          * 0 =< a, b < p
 328          */
 329         if (BN_is_zero(a))
 330                 {
 331                 if (BN_is_zero(b)) goto err;
 332                 }
 333         else if (!BN_is_zero(b))
 334                 {
 335                 if (!BN_mod_sqr(tmp_1, a, p, ctx)) goto err;
 336                 if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) goto err;
 337                 if (!BN_lshift(tmp_1, tmp_2, 2)) goto err;
 338                 /* tmp_1 = 4*a^3 */
 339
 340                 if (!BN_mod_sqr(tmp_2, b, p, ctx)) goto err;
 341                 if (!BN_mul_word(tmp_2, 27)) goto err;
 342                 /* tmp_2 = 27*b^2 */
 343
 344                 if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) goto err;
 345                 if (BN_is_zero(a)) goto err;
 346                 }
 347         ret = 1;
 348
 349 err:
 350         if (ctx != NULL)
 351                 BN_CTX_end(ctx);
 352         if (new_ctx != NULL)
 353                 BN_CTX_free(new_ctx);
 354         return ret;
 355         }
 356
 357
 358 int ec_GFp_simple_point_init(EC_POINT *point)
 359         {
 360         BN_init(&point->X);
 361         BN_init(&point->Y);
 362         BN_init(&point->Z);
 363         point->Z_is_one = 0;
 364
 365         return 1;
 366         }
 367
 368
 369 void ec_GFp_simple_point_finish(EC_POINT *point)
 370         {
 371         BN_free(&point->X);
 372         BN_free(&point->Y);
 373         BN_free(&point->Z);
 374         }
 375
 376
 377 void ec_GFp_simple_point_clear_finish(EC_POINT *point)
 378         {
 379         BN_clear_free(&point->X);
 380         BN_clear_free(&point->Y);
 381         BN_clear_free(&point->Z);
 382         point->Z_is_one = 0;
 383         }
 384
 385
 386 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
 387         {
 388         if (!BN_copy(&dest->X, &src->X)) return 0;
 389         if (!BN_copy(&dest->Y, &src->Y)) return 0;
 390         if (!BN_copy(&dest->Z, &src->Z)) return 0;
 391         dest->Z_is_one = src->Z_is_one;
 392
 393         return 1;
 394         }
 395
 396
 397 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
 398         {
 399         point->Z_is_one = 0;
 400         BN_zero(&point->Z);
 401         return 1;
 402         }
 403
 404
 405 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
 406         const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx)
 407         {
 408         BN_CTX *new_ctx = NULL;
 409         int ret = 0;
 410
 411         if (ctx == NULL)
 412                 {
 413                 ctx = new_ctx = BN_CTX_new();
 414                 if (ctx == NULL)
 415                         return 0;
 416                 }
 417
 418         if (x != NULL)
 419                 {
 420                 if (!BN_nnmod(&point->X, x, &group->field, ctx)) goto err;
 421                 if (group->meth->field_encode)
 422                         {
 423                         if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err;
 424                         }
 425                 }
 426
 427         if (y != NULL)
 428                 {
 429                 if (!BN_nnmod(&point->Y, y, &group->field, ctx)) goto err;
 430                 if (group->meth->field_encode)
 431                         {
 432                         if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err;
 433                         }
 434                 }
 435
 436         if (z != NULL)
 437                 {
 438                 int Z_is_one;
 439
 440                 if (!BN_nnmod(&point->Z, z, &group->field, ctx)) goto err;
 441                 Z_is_one = BN_is_one(&point->Z);
 442                 if (group->meth->field_encode)
 443                         {
 444                         if (Z_is_one && (group->meth->field_set_to_one != 0))
 445                                 {
 446                                 if (!group->meth->field_set_to_one(group, &point->Z, ctx)) goto err;
 447                                 }
 448                         else
 449                                 {
 450                                 if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
 451                                 }
 452                         }
 453                 point->Z_is_one = Z_is_one;
 454                 }
 455
 456         ret = 1;
 457
 458  err:
 459         if (new_ctx != NULL)
 460                 BN_CTX_free(new_ctx);
 461         return ret;
 462         }
 463
 464
 465 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point,
 466         BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx)
 467         {
 468         BN_CTX *new_ctx = NULL;
 469         int ret = 0;
 470
 471         if (group->meth->field_decode != 0)
 472                 {
 473                 if (ctx == NULL)
 474                         {
 475                         ctx = new_ctx = BN_CTX_new();
 476                         if (ctx == NULL)
 477                                 return 0;
 478                         }
 479
 480                 if (x != NULL)
 481                         {
 482                         if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
 483                         }
 484                 if (y != NULL)
 485                         {
 486                         if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
 487                         }
 488                 if (z != NULL)
 489                         {
 490                         if (!group->meth->field_decode(group, z, &point->Z, ctx)) goto err;
 491                         }
 492                 }
 493         else
 494                 {
 495                 if (x != NULL)
 496                         {
 497                         if (!BN_copy(x, &point->X)) goto err;
 498                         }
 499                 if (y != NULL)
 500                         {
 501                         if (!BN_copy(y, &point->Y)) goto err;
 502                         }
 503                 if (z != NULL)
 504                         {
 505                         if (!BN_copy(z, &point->Z)) goto err;
 506                         }
 507                 }
 508
 509         ret = 1;
 510
 511  err:
 512         if (new_ctx != NULL)
 513                 BN_CTX_free(new_ctx);
 514         return ret;
 515         }
 516
 517
 518 int 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                 {
 523                 /* unlike for projective coordinates, we do not tolerate this */
 524                 ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER);
 525                 return 0;
 526                 }
 527
 528         return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx);
 529         }
 530
 531
 532 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
 533         BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
 534         {
 535         BN_CTX *new_ctx = NULL;
 536         BIGNUM *Z, *Z_1, *Z_2, *Z_3;
 537         const BIGNUM *Z_;
 538         int ret = 0;
 539
 540         if (EC_POINT_is_at_infinity(group, point))
 541                 {
 542                 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY);
 543                 return 0;
 544                 }
 545
 546         if (ctx == NULL)
 547                 {
 548                 ctx = new_ctx = BN_CTX_new();
 549                 if (ctx == NULL)
 550                         return 0;
 551                 }
 552
 553         BN_CTX_start(ctx);
 554         Z = BN_CTX_get(ctx);
 555         Z_1 = BN_CTX_get(ctx);
 556         Z_2 = BN_CTX_get(ctx);
 557         Z_3 = BN_CTX_get(ctx);
 558         if (Z_3 == NULL) goto err;
 559
 560         /* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
 561
 562         if (group->meth->field_decode)
 563                 {
 564                 if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto err;
 565                 Z_ = Z;
 566                 }
 567         else
 568                 {
 569                 Z_ = &point->Z;
 570                 }
 571
 572         if (BN_is_one(Z_))
 573                 {
 574                 if (group->meth->field_decode)
 575                         {
 576                         if (x != NULL)
 577                                 {
 578                                 if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
 579                                 }
 580                         if (y != NULL)
 581                                 {
 582                                 if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
 583                                 }
 584                         }
 585                 else
 586                         {
 587                         if (x != NULL)
 588                                 {
 589                                 if (!BN_copy(x, &point->X)) goto err;
 590                                 }
 591                         if (y != NULL)
 592                                 {
 593                                 if (!BN_copy(y, &point->Y)) goto err;
 594                                 }
 595                         }
 596                 }
 597         else
 598                 {
 599                 if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx))
 600                         {
 601                         ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_BN_LIB);
 602                         goto err;
 603                         }
 604
 605                 if (group->meth->field_encode == 0)
 606                         {
 607                         /* field_sqr works on standard representation */
 608                         if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) goto err;
 609                         }
 610                 else
 611                         {
 612                         if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
 613                         }
 614
 615                 if (x != NULL)
 616                         {
 617                         /* in the Montgomery case, field_mul will cancel out Montgomery factor in X: */
 618                         if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) goto err;
 619                         }
 620
 621                 if (y != NULL)
 622                         {
 623                         if (group->meth->field_encode == 0)
 624                                 {
 625                                 /* field_mul works on standard representation */
 626                                 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) goto err;
 627                                 }
 628                         else
 629                                 {
 630                                 if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
 631                                 }
 632
 633                         /* in the Montgomery case, field_mul will cancel out Montgomery factor in Y: */
 634                         if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) goto err;
 635                         }
 636                 }
 637
 638         ret = 1;
 639
 640  err:
 641         BN_CTX_end(ctx);
 642         if (new_ctx != NULL)
 643                 BN_CTX_free(new_ctx);
 644         return ret;
 645         }
 646
 647 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
 648         {
 649         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
 650         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 651         const BIGNUM *p;
 652         BN_CTX *new_ctx = NULL;
 653         BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
 654         int ret = 0;
 655
 656         if (a == b)
 657                 return EC_POINT_dbl(group, r, a, ctx);
 658         if (EC_POINT_is_at_infinity(group, a))
 659                 return EC_POINT_copy(r, b);
 660         if (EC_POINT_is_at_infinity(group, b))
 661                 return EC_POINT_copy(r, a);
 662
 663         field_mul = group->meth->field_mul;
 664         field_sqr = group->meth->field_sqr;
 665         p = &group->field;
 666
 667         if (ctx == NULL)
 668                 {
 669                 ctx = new_ctx = BN_CTX_new();
 670                 if (ctx == NULL)
 671                         return 0;
 672                 }
 673
 674         BN_CTX_start(ctx);
 675         n0 = BN_CTX_get(ctx);
 676         n1 = BN_CTX_get(ctx);
 677         n2 = BN_CTX_get(ctx);
 678         n3 = BN_CTX_get(ctx);
 679         n4 = BN_CTX_get(ctx);
 680         n5 = BN_CTX_get(ctx);
 681         n6 = BN_CTX_get(ctx);
 682         if (n6 == NULL) goto end;
 683
 684         /* Note that in this function we must not read components of 'a' or 'b'
 685          * once we have written the corresponding components of 'r'.
 686          * ('r' might be one of 'a' or 'b'.)
 687          */
 688
 689         /* n1, n2 */
 690         if (b->Z_is_one)
 691                 {
 692                 if (!BN_copy(n1, &a->X)) goto end;
 693                 if (!BN_copy(n2, &a->Y)) goto end;
 694                 /* n1 = X_a */
 695                 /* n2 = Y_a */
 696                 }
 697         else
 698                 {
 699                 if (!field_sqr(group, n0, &b->Z, ctx)) goto end;
 700                 if (!field_mul(group, n1, &a->X, n0, ctx)) goto end;
 701                 /* n1 = X_a * Z_b^2 */
 702
 703                 if (!field_mul(group, n0, n0, &b->Z, ctx)) goto end;
 704                 if (!field_mul(group, n2, &a->Y, n0, ctx)) goto end;
 705                 /* n2 = Y_a * Z_b^3 */
 706                 }
 707
 708         /* n3, n4 */
 709         if (a->Z_is_one)
 710                 {
 711                 if (!BN_copy(n3, &b->X)) goto end;
 712                 if (!BN_copy(n4, &b->Y)) goto end;
 713                 /* n3 = X_b */
 714                 /* n4 = Y_b */
 715                 }
 716         else
 717                 {
 718                 if (!field_sqr(group, n0, &a->Z, ctx)) goto end;
 719                 if (!field_mul(group, n3, &b->X, n0, ctx)) goto end;
 720                 /* n3 = X_b * Z_a^2 */
 721
 722                 if (!field_mul(group, n0, n0, &a->Z, ctx)) goto end;
 723                 if (!field_mul(group, n4, &b->Y, n0, ctx)) goto end;
 724                 /* n4 = Y_b * Z_a^3 */
 725                 }
 726
 727         /* n5, n6 */
 728         if (!BN_mod_sub_quick(n5, n1, n3, p)) goto end;
 729         if (!BN_mod_sub_quick(n6, n2, n4, p)) goto end;
 730         /* n5 = n1 - n3 */
 731         /* n6 = n2 - n4 */
 732
 733         if (BN_is_zero(n5))
 734                 {
 735                 if (BN_is_zero(n6))
 736                         {
 737                         /* a is the same point as b */
 738                         BN_CTX_end(ctx);
 739                         ret = EC_POINT_dbl(group, r, a, ctx);
 740                         ctx = NULL;
 741                         goto end;
 742                         }
 743                 else
 744                         {
 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
 753         /* 'n7', 'n8' */
 754         if (!BN_mod_add_quick(n1, n1, n3, p)) goto end;
 755         if (!BN_mod_add_quick(n2, n2, n4, p)) goto end;
 756         /* 'n7' = n1 + n3 */
 757         /* 'n8' = n2 + n4 */
 758
 759         /* Z_r */
 760         if (a->Z_is_one && b->Z_is_one)
 761                 {
 762                 if (!BN_copy(&r->Z, n5)) goto end;
 763                 }
 764         else
 765                 {
 766                 if (a->Z_is_one)
 767                         { if (!BN_copy(n0, &b->Z)) goto end; }
 768                 else if (b->Z_is_one)
 769                         { if (!BN_copy(n0, &a->Z)) goto end; }
 770                 else
 771                         { if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) goto end; }
 772                 if (!field_mul(group, &r->Z, n0, n5, ctx)) goto end;
 773                 }
 774         r->Z_is_one = 0;
 775         /* Z_r = Z_a * Z_b * n5 */
 776
 777         /* X_r */
 778         if (!field_sqr(group, n0, n6, ctx)) goto end;
 779         if (!field_sqr(group, n4, n5, ctx)) goto end;
 780         if (!field_mul(group, n3, n1, n4, ctx)) goto end;
 781         if (!BN_mod_sub_quick(&r->X, n0, n3, p)) goto end;
 782         /* X_r = n6^2 - n5^2 * 'n7' */
 783
 784         /* 'n9' */
 785         if (!BN_mod_lshift1_quick(n0, &r->X, p)) goto end;
 786         if (!BN_mod_sub_quick(n0, n3, n0, p)) goto end;
 787         /* n9 = n5^2 * 'n7' - 2 * X_r */
 788
 789         /* Y_r */
 790         if (!field_mul(group, n0, n0, n6, ctx)) goto end;
 791         if (!field_mul(group, n5, n4, n5, ctx)) goto end; /* now n5 is n5^3 */
 792         if (!field_mul(group, n1, n2, n5, ctx)) goto end;
 793         if (!BN_mod_sub_quick(n0, n0, n1, p)) goto end;
 794         if (BN_is_odd(n0))
 795                 if (!BN_add(n0, n0, p)) goto end;
 796         /* now  0 <= n0 < 2*p,  and n0 is even */
 797         if (!BN_rshift1(&r->Y, n0)) goto end;
 798         /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
 799
 800         ret = 1;
 801
 802  end:
 803         if (ctx) /* otherwise we already called BN_CTX_end */
 804                 BN_CTX_end(ctx);
 805         if (new_ctx != NULL)
 806                 BN_CTX_free(new_ctx);
 807         return ret;
 808         }
 809
 810
 811 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
 812         {
 813         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
 814         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 815         const BIGNUM *p;
 816         BN_CTX *new_ctx = NULL;
 817         BIGNUM *n0, *n1, *n2, *n3;
 818         int ret = 0;
 819
 820         if (EC_POINT_is_at_infinity(group, a))
 821                 {
 822                 BN_zero(&r->Z);
 823                 r->Z_is_one = 0;
 824                 return 1;
 825                 }
 826
 827         field_mul = group->meth->field_mul;
 828         field_sqr = group->meth->field_sqr;
 829         p = &group->field;
 830
 831         if (ctx == NULL)
 832                 {
 833                 ctx = new_ctx = BN_CTX_new();
 834                 if (ctx == NULL)
 835                         return 0;
 836                 }
 837
 838         BN_CTX_start(ctx);
 839         n0 = BN_CTX_get(ctx);
 840         n1 = BN_CTX_get(ctx);
 841         n2 = BN_CTX_get(ctx);
 842         n3 = BN_CTX_get(ctx);
 843         if (n3 == NULL) goto err;
 844
 845         /* Note that in this function we must not read components of 'a'
 846          * once we have written the corresponding components of 'r'.
 847          * ('r' might the same as 'a'.)
 848          */
 849
 850         /* n1 */
 851         if (a->Z_is_one)
 852                 {
 853                 if (!field_sqr(group, n0, &a->X, ctx)) goto err;
 854                 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
 855                 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
 856                 if (!BN_mod_add_quick(n1, n0, &group->a, p)) goto err;
 857                 /* n1 = 3 * X_a^2 + a_curve */
 858                 }
 859         else if (group->a_is_minus3)
 860                 {
 861                 if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
 862                 if (!BN_mod_add_quick(n0, &a->X, n1, p)) goto err;
 863                 if (!BN_mod_sub_quick(n2, &a->X, n1, p)) goto err;
 864                 if (!field_mul(group, n1, n0, n2, ctx)) goto err;
 865                 if (!BN_mod_lshift1_quick(n0, n1, p)) goto err;
 866                 if (!BN_mod_add_quick(n1, n0, n1, p)) goto err;
 867                 /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
 868                  *    = 3 * X_a^2 - 3 * Z_a^4 */
 869                 }
 870         else
 871                 {
 872                 if (!field_sqr(group, n0, &a->X, ctx)) goto err;
 873                 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
 874                 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
 875                 if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
 876                 if (!field_sqr(group, n1, n1, ctx)) goto err;
 877                 if (!field_mul(group, n1, n1, &group->a, ctx)) goto err;
 878                 if (!BN_mod_add_quick(n1, n1, n0, p)) goto err;
 879                 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
 880                 }
 881
 882         /* Z_r */
 883         if (a->Z_is_one)
 884                 {
 885                 if (!BN_copy(n0, &a->Y)) goto err;
 886                 }
 887         else
 888                 {
 889                 if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) goto err;
 890                 }
 891         if (!BN_mod_lshift1_quick(&r->Z, n0, p)) goto err;
 892         r->Z_is_one = 0;
 893         /* Z_r = 2 * Y_a * Z_a */
 894
 895         /* n2 */
 896         if (!field_sqr(group, n3, &a->Y, ctx)) goto err;
 897         if (!field_mul(group, n2, &a->X, n3, ctx)) goto err;
 898         if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err;
 899         /* n2 = 4 * X_a * Y_a^2 */
 900
 901         /* X_r */
 902         if (!BN_mod_lshift1_quick(n0, n2, p)) goto err;
 903         if (!field_sqr(group, &r->X, n1, ctx)) goto err;
 904         if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) goto err;
 905         /* X_r = n1^2 - 2 * n2 */
 906
 907         /* n3 */
 908         if (!field_sqr(group, n0, n3, ctx)) goto err;
 909         if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err;
 910         /* n3 = 8 * Y_a^4 */
 911
 912         /* Y_r */
 913         if (!BN_mod_sub_quick(n0, n2, &r->X, p)) goto err;
 914         if (!field_mul(group, n0, n1, n0, ctx)) goto err;
 915         if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) goto err;
 916         /* Y_r = n1 * (n2 - X_r) - n3 */
 917
 918         ret = 1;
 919
 920  err:
 921         BN_CTX_end(ctx);
 922         if (new_ctx != NULL)
 923                 BN_CTX_free(new_ctx);
 924         return ret;
 925         }
 926
 927
 928 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
 929         {
 930         if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
 931                 /* point is its own inverse */
 932                 return 1;
 933
 934         return BN_usub(&point->Y, &group->field, &point->Y);
 935         }
 936
 937
 938 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
 939         {
 940         return BN_is_zero(&point->Z);
 941         }
 942
 943
 944 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
 945         {
 946         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
 947         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 948         const BIGNUM *p;
 949         BN_CTX *new_ctx = NULL;
 950         BIGNUM *rh, *tmp, *Z4, *Z6;
 951         int ret = -1;
 952
 953         if (EC_POINT_is_at_infinity(group, point))
 954                 return 1;
 955
 956         field_mul = group->meth->field_mul;
 957         field_sqr = group->meth->field_sqr;
 958         p = &group->field;
 959
 960         if (ctx == NULL)
 961                 {
 962                 ctx = new_ctx = BN_CTX_new();
 963                 if (ctx == NULL)
 964                         return -1;
 965                 }
 966
 967         BN_CTX_start(ctx);
 968         rh = BN_CTX_get(ctx);
 969         tmp = BN_CTX_get(ctx);
 970         Z4 = BN_CTX_get(ctx);
 971         Z6 = BN_CTX_get(ctx);
 972         if (Z6 == NULL) goto err;
 973
 974         /*-
 975          * We have a curve defined by a Weierstrass equation
 976          *      y^2 = x^3 + a*x + b.
 977          * The point to consider is given in Jacobian projective coordinates
 978          * where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
 979          * Substituting this and multiplying by  Z^6  transforms the above equation into
 980          *      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
 981          * To test this, we add up the right-hand side in 'rh'.
 982          */
 983
 984         /* rh := X^2 */
 985         if (!field_sqr(group, rh, &point->X, ctx)) goto err;
 986
 987         if (!point->Z_is_one)
 988                 {
 989                 if (!field_sqr(group, tmp, &point->Z, ctx)) goto err;
 990                 if (!field_sqr(group, Z4, tmp, ctx)) goto err;
 991                 if (!field_mul(group, Z6, Z4, tmp, ctx)) goto err;
 992
 993                 /* rh := (rh + a*Z^4)*X */
 994                 if (group->a_is_minus3)
 995                         {
 996                         if (!BN_mod_lshift1_quick(tmp, Z4, p)) goto err;
 997                         if (!BN_mod_add_quick(tmp, tmp, Z4, p)) goto err;
 998                         if (!BN_mod_sub_quick(rh, rh, tmp, p)) goto err;
 999                         if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1000                         }
1001                 else
1002                         {
1003                         if (!field_mul(group, tmp, Z4, &group->a, ctx)) goto err;
1004                         if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
1005                         if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1006                         }
1007
1008                 /* rh := rh + b*Z^6 */
1009                 if (!field_mul(group, tmp, &group->b, Z6, ctx)) goto err;
1010                 if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
1011                 }
1012         else
1013                 {
1014                 /* point->Z_is_one */
1015
1016                 /* rh := (rh + a)*X */
1017                 if (!BN_mod_add_quick(rh, rh, &group->a, p)) goto err;
1018                 if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1019                 /* rh := rh + b */
1020                 if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err;
1021                 }
1022
1023         /* 'lh' := Y^2 */
1024         if (!field_sqr(group, tmp, &point->Y, ctx)) goto err;
1025
1026         ret = (0 == BN_ucmp(tmp, rh));
1027
1028  err:
1029         BN_CTX_end(ctx);
1030         if (new_ctx != NULL)
1031                 BN_CTX_free(new_ctx);
1032         return ret;
1033         }
1034
1035
1036 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
1037         {
1038         /* return values:
1039          *  -1   error
1040          *   0   equal (in affine coordinates)
1041          *   1   not equal
1042          */
1043
1044         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1045         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1046         BN_CTX *new_ctx = NULL;
1047         BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1048         const BIGNUM *tmp1_, *tmp2_;
1049         int ret = -1;
1050
1051         if (EC_POINT_is_at_infinity(group, a))
1052                 {
1053                 return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
1054                 }
1055
1056         if (EC_POINT_is_at_infinity(group, b))
1057                 return 1;
1058
1059         if (a->Z_is_one && b->Z_is_one)
1060                 {
1061                 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
1062                 }
1063
1064         field_mul = group->meth->field_mul;
1065         field_sqr = group->meth->field_sqr;
1066
1067         if (ctx == NULL)
1068                 {
1069                 ctx = new_ctx = BN_CTX_new();
1070                 if (ctx == NULL)
1071                         return -1;
1072                 }
1073
1074         BN_CTX_start(ctx);
1075         tmp1 = BN_CTX_get(ctx);
1076         tmp2 = BN_CTX_get(ctx);
1077         Za23 = BN_CTX_get(ctx);
1078         Zb23 = BN_CTX_get(ctx);
1079         if (Zb23 == NULL) goto end;
1080
1081         /*-
1082          * We have to decide whether
1083          *     (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1084          * or equivalently, whether
1085          *     (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1086          */
1087
1088         if (!b->Z_is_one)
1089                 {
1090                 if (!field_sqr(group, Zb23, &b->Z, ctx)) goto end;
1091                 if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) goto end;
1092                 tmp1_ = tmp1;
1093                 }
1094         else
1095                 tmp1_ = &a->X;
1096         if (!a->Z_is_one)
1097                 {
1098                 if (!field_sqr(group, Za23, &a->Z, ctx)) goto end;
1099                 if (!field_mul(group, tmp2, &b->X, Za23, ctx)) goto end;
1100                 tmp2_ = tmp2;
1101                 }
1102         else
1103                 tmp2_ = &b->X;
1104
1105         /* compare  X_a*Z_b^2  with  X_b*Z_a^2 */
1106         if (BN_cmp(tmp1_, tmp2_) != 0)
1107                 {
1108                 ret = 1; /* points differ */
1109                 goto end;
1110                 }
1111
1112
1113         if (!b->Z_is_one)
1114                 {
1115                 if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) goto end;
1116                 if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) goto end;
1117                 /* tmp1_ = tmp1 */
1118                 }
1119         else
1120                 tmp1_ = &a->Y;
1121         if (!a->Z_is_one)
1122                 {
1123                 if (!field_mul(group, Za23, Za23, &a->Z, ctx)) goto end;
1124                 if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) goto end;
1125                 /* tmp2_ = tmp2 */
1126                 }
1127         else
1128                 tmp2_ = &b->Y;
1129
1130         /* compare  Y_a*Z_b^3  with  Y_b*Z_a^3 */
1131         if (BN_cmp(tmp1_, tmp2_) != 0)
1132                 {
1133                 ret = 1; /* points differ */
1134                 goto end;
1135                 }
1136
1137         /* points are equal */
1138         ret = 0;
1139
1140  end:
1141         BN_CTX_end(ctx);
1142         if (new_ctx != NULL)
1143                 BN_CTX_free(new_ctx);
1144         return ret;
1145         }
1146
1147
1148 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1149         {
1150         BN_CTX *new_ctx = NULL;
1151         BIGNUM *x, *y;
1152         int ret = 0;
1153
1154         if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1155                 return 1;
1156
1157         if (ctx == NULL)
1158                 {
1159                 ctx = new_ctx = BN_CTX_new();
1160                 if (ctx == NULL)
1161                         return 0;
1162                 }
1163
1164         BN_CTX_start(ctx);
1165         x = BN_CTX_get(ctx);
1166         y = BN_CTX_get(ctx);
1167         if (y == NULL) goto err;
1168
1169         if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1170         if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1171         if (!point->Z_is_one)
1172                 {
1173                 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1174                 goto err;
1175                 }
1176
1177         ret = 1;
1178
1179  err:
1180         BN_CTX_end(ctx);
1181         if (new_ctx != NULL)
1182                 BN_CTX_free(new_ctx);
1183         return ret;
1184         }
1185
1186
1187 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
1188         {
1189         BN_CTX *new_ctx = NULL;
1190         BIGNUM *tmp, *tmp_Z;
1191         BIGNUM **prod_Z = NULL;
1192         size_t i;
1193         int ret = 0;
1194
1195         if (num == 0)
1196                 return 1;
1197
1198         if (ctx == NULL)
1199                 {
1200                 ctx = new_ctx = BN_CTX_new();
1201                 if (ctx == NULL)
1202                         return 0;
1203                 }
1204
1205         BN_CTX_start(ctx);
1206         tmp = BN_CTX_get(ctx);
1207         tmp_Z = BN_CTX_get(ctx);
1208         if (tmp == NULL || tmp_Z == NULL) goto err;
1209
1210         prod_Z = OPENSSL_malloc(num * sizeof prod_Z[0]);
1211         if (prod_Z == NULL) goto err;
1212         for (i = 0; i < num; i++)
1213                 {
1214                 prod_Z[i] = BN_new();
1215                 if (prod_Z[i] == NULL) goto err;
1216                 }
1217
1218         /* Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z,
1219          * skipping any zero-valued inputs (pretend that they're 1). */
1220
1221         if (!BN_is_zero(&points[0]->Z))
1222                 {
1223                 if (!BN_copy(prod_Z[0], &points[0]->Z)) goto err;
1224                 }
1225         else
1226                 {
1227                 if (group->meth->field_set_to_one != 0)
1228                         {
1229                         if (!group->meth->field_set_to_one(group, prod_Z[0], ctx)) goto err;
1230                         }
1231                 else
1232                         {
1233                         if (!BN_one(prod_Z[0])) goto err;
1234                         }
1235                 }
1236
1237         for (i = 1; i < num; i++)
1238                 {
1239                 if (!BN_is_zero(&points[i]->Z))
1240                         {
1241                         if (!group->meth->field_mul(group, prod_Z[i], prod_Z[i - 1], &points[i]->Z, ctx)) goto err;
1242                         }
1243                 else
1244                         {
1245                         if (!BN_copy(prod_Z[i], prod_Z[i - 1])) goto err;
1246                         }
1247                 }
1248
1249         /* Now use a single explicit inversion to replace every
1250          * non-zero points[i]->Z by its inverse. */
1251
1252         if (!BN_mod_inverse(tmp, prod_Z[num - 1], &group->field, ctx))
1253                 {
1254                 ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1255                 goto err;
1256                 }
1257         if (group->meth->field_encode != 0)
1258                 {
1259                 /* In the Montgomery case, we just turned  R*H  (representing H)
1260                  * into  1/(R*H),  but we need  R*(1/H)  (representing 1/H);
1261                  * i.e. we need to multiply by the Montgomery factor twice. */
1262                 if (!group->meth->field_encode(group, tmp, tmp, ctx)) goto err;
1263                 if (!group->meth->field_encode(group, tmp, tmp, ctx)) goto err;
1264                 }
1265
1266         for (i = num - 1; i > 0; --i)
1267                 {
1268                 /* Loop invariant: tmp is the product of the inverses of
1269                  * points[0]->Z .. points[i]->Z (zero-valued inputs skipped). */
1270                 if (!BN_is_zero(&points[i]->Z))
1271                         {
1272                         /* Set tmp_Z to the inverse of points[i]->Z (as product
1273                          * of Z inverses 0 .. i, Z values 0 .. i - 1). */
1274                         if (!group->meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx)) goto err;
1275                         /* Update tmp to satisfy the loop invariant for i - 1. */
1276                         if (!group->meth->field_mul(group, tmp, tmp, &points[i]->Z, ctx)) goto err;
1277                         /* Replace points[i]->Z by its inverse. */
1278                         if (!BN_copy(&points[i]->Z, tmp_Z)) goto err;
1279                         }
1280                 }
1281
1282         if (!BN_is_zero(&points[0]->Z))
1283                 {
1284                 /* Replace points[0]->Z by its inverse. */
1285                 if (!BN_copy(&points[0]->Z, tmp)) goto err;
1286                 }
1287
1288         /* Finally, fix up the X and Y coordinates for all points. */
1289
1290         for (i = 0; i < num; i++)
1291                 {
1292                 EC_POINT *p = points[i];
1293
1294                 if (!BN_is_zero(&p->Z))
1295                         {
1296                         /* turn  (X, Y, 1/Z)  into  (X/Z^2, Y/Z^3, 1) */
1297
1298                         if (!group->meth->field_sqr(group, tmp, &p->Z, ctx)) goto err;
1299                         if (!group->meth->field_mul(group, &p->X, &p->X, tmp, ctx)) goto err;
1300
1301                         if (!group->meth->field_mul(group, tmp, tmp, &p->Z, ctx)) goto err;
1302                         if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp, ctx)) goto err;
1303
1304                         if (group->meth->field_set_to_one != 0)
1305                                 {
1306                                 if (!group->meth->field_set_to_one(group, &p->Z, ctx)) goto err;
1307                                 }
1308                         else
1309                                 {
1310                                 if (!BN_one(&p->Z)) goto err;
1311                                 }
1312                         p->Z_is_one = 1;
1313                         }
1314                 }
1315
1316         ret = 1;
1317
1318  err:
1319         BN_CTX_end(ctx);
1320         if (new_ctx != NULL)
1321                 BN_CTX_free(new_ctx);
1322         if (prod_Z != NULL)
1323                 {
1324                 for (i = 0; i < num; i++)
1325                         {
1326                         if (prod_Z[i] == NULL) break;
1327                         BN_clear_free(prod_Z[i]);
1328                         }
1329                 OPENSSL_free(prod_Z);
1330                 }
1331         return ret;
1332         }
1333
1334
1335 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
1336         {
1337         return BN_mod_mul(r, a, b, &group->field, ctx);
1338         }
1339
1340
1341 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
1342         {
1343         return BN_mod_sqr(r, a, &group->field, ctx);
1344         }