crypto/ec/ecp_smpl.c

   1 /* crypto/ec/ecp_smpl.c */
   2 /*
   3  * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
   4  * for the OpenSSL project. Includes code written by Bodo Moeller for the
   5  * OpenSSL project.
   6  */
   7 /* ====================================================================
   8  * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  *
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  *
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in
  19  *    the documentation and/or other materials provided with the
  20  *    distribution.
  21  *
  22  * 3. All advertising materials mentioning features or use of this
  23  *    software must display the following acknowledgment:
  24  *    "This product includes software developed by the OpenSSL Project
  25  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  26  *
  27  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  28  *    endorse or promote products derived from this software without
  29  *    prior written permission. For written permission, please contact
  30  *    openssl-core@openssl.org.
  31  *
  32  * 5. Products derived from this software may not be called "OpenSSL"
  33  *    nor may "OpenSSL" appear in their names without prior written
  34  *    permission of the OpenSSL Project.
  35  *
  36  * 6. Redistributions of any form whatsoever must retain the following
  37  *    acknowledgment:
  38  *    "This product includes software developed by the OpenSSL Project
  39  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  40  *
  41  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  42  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  44  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  45  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  46  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  47  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  48  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  49  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  50  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  51  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  52  * OF THE POSSIBILITY OF SUCH DAMAGE.
  53  * ====================================================================
  54  *
  55  * This product includes cryptographic software written by Eric Young
  56  * (eay@cryptsoft.com).  This product includes software written by Tim
  57  * Hudson (tjh@cryptsoft.com).
  58  *
  59  */
  60 /* ====================================================================
  61  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  62  * Portions of this software developed by SUN MICROSYSTEMS, INC.,
  63  * and contributed to the OpenSSL project.
  64  */
  65
  66 #include <openssl/err.h>
  67 #include <openssl/symhacks.h>
  68
  69 #ifdef OPENSSL_FIPS
  70 # include <openssl/fips.h>
  71 #endif
  72
  73 #include "ec_lcl.h"
  74
  75 const EC_METHOD *EC_GFp_simple_method(void)
  76 {
  77     static const EC_METHOD ret = {
  78         EC_FLAGS_DEFAULT_OCT,
  79         NID_X9_62_prime_field,
  80         ec_GFp_simple_group_init,
  81         ec_GFp_simple_group_finish,
  82         ec_GFp_simple_group_clear_finish,
  83         ec_GFp_simple_group_copy,
  84         ec_GFp_simple_group_set_curve,
  85         ec_GFp_simple_group_get_curve,
  86         ec_GFp_simple_group_get_degree,
  87         ec_GFp_simple_group_check_discriminant,
  88         ec_GFp_simple_point_init,
  89         ec_GFp_simple_point_finish,
  90         ec_GFp_simple_point_clear_finish,
  91         ec_GFp_simple_point_copy,
  92         ec_GFp_simple_point_set_to_infinity,
  93         ec_GFp_simple_set_Jprojective_coordinates_GFp,
  94         ec_GFp_simple_get_Jprojective_coordinates_GFp,
  95         ec_GFp_simple_point_set_affine_coordinates,
  96         ec_GFp_simple_point_get_affine_coordinates,
  97         0, 0, 0,
  98         ec_GFp_simple_add,
  99         ec_GFp_simple_dbl,
 100         ec_GFp_simple_invert,
 101         ec_GFp_simple_is_at_infinity,
 102         ec_GFp_simple_is_on_curve,
 103         ec_GFp_simple_cmp,
 104         ec_GFp_simple_make_affine,
 105         ec_GFp_simple_points_make_affine,
 106         0 /* mul */ ,
 107         0 /* precompute_mult */ ,
 108         0 /* have_precompute_mult */ ,
 109         ec_GFp_simple_field_mul,
 110         ec_GFp_simple_field_sqr,
 111         0 /* field_div */ ,
 112         0 /* field_encode */ ,
 113         0 /* field_decode */ ,
 114         0                       /* field_set_to_one */
 115     };
 116
 117 #ifdef OPENSSL_FIPS
 118     if (FIPS_mode())
 119         return fips_ec_gfp_simple_method();
 120 #endif
 121
 122     return &ret;
 123 }
 124
 125 /*
 126  * Most method functions in this file are designed to work with
 127  * non-trivial representations of field elements if necessary
 128  * (see ecp_mont.c): while standard modular addition and subtraction
 129  * are used, the field_mul and field_sqr methods will be used for
 130  * multiplication, and field_encode and field_decode (if defined)
 131  * will be used for converting between representations.
 132  *
 133  * Functions ec_GFp_simple_points_make_affine() and
 134  * ec_GFp_simple_point_get_affine_coordinates() specifically assume
 135  * that if a non-trivial representation is used, it is a Montgomery
 136  * representation (i.e. 'encoding' means multiplying by some factor R).
 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 void ec_GFp_simple_group_finish(EC_GROUP *group)
 149 {
 150     BN_free(&group->field);
 151     BN_free(&group->a);
 152     BN_free(&group->b);
 153 }
 154
 155 void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
 156 {
 157     BN_clear_free(&group->field);
 158     BN_clear_free(&group->a);
 159     BN_clear_free(&group->b);
 160 }
 161
 162 int 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 int ec_GFp_simple_group_set_curve(EC_GROUP *group,
 177                                   const BIGNUM *p, const BIGNUM *a,
 178                                   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         ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD);
 187         return 0;
 188     }
 189
 190     if (ctx == NULL) {
 191         ctx = new_ctx = BN_CTX_new();
 192         if (ctx == NULL)
 193             return 0;
 194     }
 195
 196     BN_CTX_start(ctx);
 197     tmp_a = BN_CTX_get(ctx);
 198     if (tmp_a == NULL)
 199         goto err;
 200
 201     /* group->field */
 202     if (!BN_copy(&group->field, p))
 203         goto err;
 204     BN_set_negative(&group->field, 0);
 205
 206     /* group->a */
 207     if (!BN_nnmod(tmp_a, a, p, ctx))
 208         goto err;
 209     if (group->meth->field_encode) {
 210         if (!group->meth->field_encode(group, &group->a, tmp_a, ctx))
 211             goto err;
 212     } else if (!BN_copy(&group->a, tmp_a))
 213         goto err;
 214
 215     /* group->b */
 216     if (!BN_nnmod(&group->b, b, p, ctx))
 217         goto err;
 218     if (group->meth->field_encode)
 219         if (!group->meth->field_encode(group, &group->b, &group->b, ctx))
 220             goto err;
 221
 222     /* group->a_is_minus3 */
 223     if (!BN_add_word(tmp_a, 3))
 224         goto err;
 225     group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
 226
 227     ret = 1;
 228
 229  err:
 230     BN_CTX_end(ctx);
 231     if (new_ctx != NULL)
 232         BN_CTX_free(new_ctx);
 233     return ret;
 234 }
 235
 236 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
 237                                   BIGNUM *b, BN_CTX *ctx)
 238 {
 239     int ret = 0;
 240     BN_CTX *new_ctx = NULL;
 241
 242     if (p != NULL) {
 243         if (!BN_copy(p, &group->field))
 244             return 0;
 245     }
 246
 247     if (a != NULL || b != NULL) {
 248         if (group->meth->field_decode) {
 249             if (ctx == NULL) {
 250                 ctx = new_ctx = BN_CTX_new();
 251                 if (ctx == NULL)
 252                     return 0;
 253             }
 254             if (a != NULL) {
 255                 if (!group->meth->field_decode(group, a, &group->a, ctx))
 256                     goto err;
 257             }
 258             if (b != NULL) {
 259                 if (!group->meth->field_decode(group, b, &group->b, ctx))
 260                     goto err;
 261             }
 262         } else {
 263             if (a != NULL) {
 264                 if (!BN_copy(a, &group->a))
 265                     goto err;
 266             }
 267             if (b != NULL) {
 268                 if (!BN_copy(b, &group->b))
 269                     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 int ec_GFp_simple_group_get_degree(const EC_GROUP *group)
 283 {
 284     return BN_num_bits(&group->field);
 285 }
 286
 287 int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
 288 {
 289     int ret = 0;
 290     BIGNUM *a, *b, *order, *tmp_1, *tmp_2;
 291     const BIGNUM *p = &group->field;
 292     BN_CTX *new_ctx = NULL;
 293
 294     if (ctx == NULL) {
 295         ctx = new_ctx = BN_CTX_new();
 296         if (ctx == NULL) {
 297             ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT,
 298                   ERR_R_MALLOC_FAILURE);
 299             goto err;
 300         }
 301     }
 302     BN_CTX_start(ctx);
 303     a = BN_CTX_get(ctx);
 304     b = BN_CTX_get(ctx);
 305     tmp_1 = BN_CTX_get(ctx);
 306     tmp_2 = BN_CTX_get(ctx);
 307     order = BN_CTX_get(ctx);
 308     if (order == NULL)
 309         goto err;
 310
 311     if (group->meth->field_decode) {
 312         if (!group->meth->field_decode(group, a, &group->a, ctx))
 313             goto err;
 314         if (!group->meth->field_decode(group, b, &group->b, ctx))
 315             goto err;
 316     } else {
 317         if (!BN_copy(a, &group->a))
 318             goto err;
 319         if (!BN_copy(b, &group->b))
 320             goto err;
 321     }
 322
 323         /*-
 324          * check the discriminant:
 325          * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
 326          * 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     if (new_ctx != NULL)
 357         BN_CTX_free(new_ctx);
 358     return ret;
 359 }
 360
 361 int ec_GFp_simple_point_init(EC_POINT *point)
 362 {
 363     BN_init(&point->X);
 364     BN_init(&point->Y);
 365     BN_init(&point->Z);
 366     point->Z_is_one = 0;
 367
 368     return 1;
 369 }
 370
 371 void ec_GFp_simple_point_finish(EC_POINT *point)
 372 {
 373     BN_free(&point->X);
 374     BN_free(&point->Y);
 375     BN_free(&point->Z);
 376 }
 377
 378 void ec_GFp_simple_point_clear_finish(EC_POINT *point)
 379 {
 380     BN_clear_free(&point->X);
 381     BN_clear_free(&point->Y);
 382     BN_clear_free(&point->Z);
 383     point->Z_is_one = 0;
 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))
 389         return 0;
 390     if (!BN_copy(&dest->Y, &src->Y))
 391         return 0;
 392     if (!BN_copy(&dest->Z, &src->Z))
 393         return 0;
 394     dest->Z_is_one = src->Z_is_one;
 395
 396     return 1;
 397 }
 398
 399 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group,
 400                                         EC_POINT *point)
 401 {
 402     point->Z_is_one = 0;
 403     BN_zero(&point->Z);
 404     return 1;
 405 }
 406
 407 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group,
 408                                                   EC_POINT *point,
 409                                                   const BIGNUM *x,
 410                                                   const BIGNUM *y,
 411                                                   const BIGNUM *z,
 412                                                   BN_CTX *ctx)
 413 {
 414     BN_CTX *new_ctx = NULL;
 415     int ret = 0;
 416
 417     if (ctx == NULL) {
 418         ctx = new_ctx = BN_CTX_new();
 419         if (ctx == NULL)
 420             return 0;
 421     }
 422
 423     if (x != NULL) {
 424         if (!BN_nnmod(&point->X, x, &group->field, ctx))
 425             goto err;
 426         if (group->meth->field_encode) {
 427             if (!group->meth->field_encode(group, &point->X, &point->X, ctx))
 428                 goto err;
 429         }
 430     }
 431
 432     if (y != NULL) {
 433         if (!BN_nnmod(&point->Y, y, &group->field, ctx))
 434             goto err;
 435         if (group->meth->field_encode) {
 436             if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx))
 437                 goto err;
 438         }
 439     }
 440
 441     if (z != NULL) {
 442         int Z_is_one;
 443
 444         if (!BN_nnmod(&point->Z, z, &group->field, ctx))
 445             goto err;
 446         Z_is_one = BN_is_one(&point->Z);
 447         if (group->meth->field_encode) {
 448             if (Z_is_one && (group->meth->field_set_to_one != 0)) {
 449                 if (!group->meth->field_set_to_one(group, &point->Z, ctx))
 450                     goto err;
 451             } else {
 452                 if (!group->
 453                     meth->field_encode(group, &point->Z, &point->Z, ctx))
 454                     goto err;
 455             }
 456         }
 457         point->Z_is_one = Z_is_one;
 458     }
 459
 460     ret = 1;
 461
 462  err:
 463     if (new_ctx != NULL)
 464         BN_CTX_free(new_ctx);
 465     return ret;
 466 }
 467
 468 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group,
 469                                                   const EC_POINT *point,
 470                                                   BIGNUM *x, BIGNUM *y,
 471                                                   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
 483         if (x != NULL) {
 484             if (!group->meth->field_decode(group, x, &point->X, ctx))
 485                 goto err;
 486         }
 487         if (y != NULL) {
 488             if (!group->meth->field_decode(group, y, &point->Y, ctx))
 489                 goto err;
 490         }
 491         if (z != NULL) {
 492             if (!group->meth->field_decode(group, z, &point->Z, ctx))
 493                 goto err;
 494         }
 495     } else {
 496         if (x != NULL) {
 497             if (!BN_copy(x, &point->X))
 498                 goto err;
 499         }
 500         if (y != NULL) {
 501             if (!BN_copy(y, &point->Y))
 502                 goto err;
 503         }
 504         if (z != NULL) {
 505             if (!BN_copy(z, &point->Z))
 506                 goto err;
 507         }
 508     }
 509
 510     ret = 1;
 511
 512  err:
 513     if (new_ctx != NULL)
 514         BN_CTX_free(new_ctx);
 515     return ret;
 516 }
 517
 518 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group,
 519                                                EC_POINT *point,
 520                                                const BIGNUM *x,
 521                                                const BIGNUM *y, BN_CTX *ctx)
 522 {
 523     if (x == NULL || y == NULL) {
 524         /*
 525          * unlike for projective coordinates, we do not tolerate this
 526          */
 527         ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES,
 528               ERR_R_PASSED_NULL_PARAMETER);
 529         return 0;
 530     }
 531
 532     return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y,
 533                                                     BN_value_one(), ctx);
 534 }
 535
 536 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
 537                                                const EC_POINT *point,
 538                                                BIGNUM *x, BIGNUM *y,
 539                                                BN_CTX *ctx)
 540 {
 541     BN_CTX *new_ctx = NULL;
 542     BIGNUM *Z, *Z_1, *Z_2, *Z_3;
 543     const BIGNUM *Z_;
 544     int ret = 0;
 545
 546     if (EC_POINT_is_at_infinity(group, point)) {
 547         ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
 548               EC_R_POINT_AT_INFINITY);
 549         return 0;
 550     }
 551
 552     if (ctx == NULL) {
 553         ctx = new_ctx = BN_CTX_new();
 554         if (ctx == NULL)
 555             return 0;
 556     }
 557
 558     BN_CTX_start(ctx);
 559     Z = BN_CTX_get(ctx);
 560     Z_1 = BN_CTX_get(ctx);
 561     Z_2 = BN_CTX_get(ctx);
 562     Z_3 = BN_CTX_get(ctx);
 563     if (Z_3 == NULL)
 564         goto err;
 565
 566     /* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
 567
 568     if (group->meth->field_decode) {
 569         if (!group->meth->field_decode(group, Z, &point->Z, ctx))
 570             goto err;
 571         Z_ = Z;
 572     } else {
 573         Z_ = &point->Z;
 574     }
 575
 576     if (BN_is_one(Z_)) {
 577         if (group->meth->field_decode) {
 578             if (x != NULL) {
 579                 if (!group->meth->field_decode(group, x, &point->X, ctx))
 580                     goto err;
 581             }
 582             if (y != NULL) {
 583                 if (!group->meth->field_decode(group, y, &point->Y, ctx))
 584                     goto err;
 585             }
 586         } else {
 587             if (x != NULL) {
 588                 if (!BN_copy(x, &point->X))
 589                     goto err;
 590             }
 591             if (y != NULL) {
 592                 if (!BN_copy(y, &point->Y))
 593                     goto err;
 594             }
 595         }
 596     } else {
 597         if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx)) {
 598             ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
 599                   ERR_R_BN_LIB);
 600             goto err;
 601         }
 602
 603         if (group->meth->field_encode == 0) {
 604             /* field_sqr works on standard representation */
 605             if (!group->meth->field_sqr(group, Z_2, Z_1, ctx))
 606                 goto err;
 607         } else {
 608             if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx))
 609                 goto err;
 610         }
 611
 612         if (x != NULL) {
 613             /*
 614              * in the Montgomery case, field_mul will cancel out Montgomery
 615              * factor in X:
 616              */
 617             if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx))
 618                 goto err;
 619         }
 620
 621         if (y != NULL) {
 622             if (group->meth->field_encode == 0) {
 623                 /*
 624                  * field_mul works on standard representation
 625                  */
 626                 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx))
 627                     goto err;
 628             } else {
 629                 if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx))
 630                     goto err;
 631             }
 632
 633             /*
 634              * in the Montgomery case, field_mul will cancel out Montgomery
 635              * factor in Y:
 636              */
 637             if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx))
 638                 goto err;
 639         }
 640     }
 641
 642     ret = 1;
 643
 644  err:
 645     BN_CTX_end(ctx);
 646     if (new_ctx != NULL)
 647         BN_CTX_free(new_ctx);
 648     return ret;
 649 }
 650
 651 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
 652                       const EC_POINT *b, BN_CTX *ctx)
 653 {
 654     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
 655                       const BIGNUM *, BN_CTX *);
 656     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 657     const BIGNUM *p;
 658     BN_CTX *new_ctx = NULL;
 659     BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
 660     int ret = 0;
 661
 662     if (a == b)
 663         return EC_POINT_dbl(group, r, a, ctx);
 664     if (EC_POINT_is_at_infinity(group, a))
 665         return EC_POINT_copy(r, b);
 666     if (EC_POINT_is_at_infinity(group, b))
 667         return EC_POINT_copy(r, a);
 668
 669     field_mul = group->meth->field_mul;
 670     field_sqr = group->meth->field_sqr;
 671     p = &group->field;
 672
 673     if (ctx == NULL) {
 674         ctx = new_ctx = BN_CTX_new();
 675         if (ctx == NULL)
 676             return 0;
 677     }
 678
 679     BN_CTX_start(ctx);
 680     n0 = BN_CTX_get(ctx);
 681     n1 = BN_CTX_get(ctx);
 682     n2 = BN_CTX_get(ctx);
 683     n3 = BN_CTX_get(ctx);
 684     n4 = BN_CTX_get(ctx);
 685     n5 = BN_CTX_get(ctx);
 686     n6 = BN_CTX_get(ctx);
 687     if (n6 == NULL)
 688         goto end;
 689
 690     /*
 691      * Note that in this function we must not read components of 'a' or 'b'
 692      * once we have written the corresponding components of 'r'. ('r' might
 693      * be one of 'a' or 'b'.)
 694      */
 695
 696     /* n1, n2 */
 697     if (b->Z_is_one) {
 698         if (!BN_copy(n1, &a->X))
 699             goto end;
 700         if (!BN_copy(n2, &a->Y))
 701             goto end;
 702         /* n1 = X_a */
 703         /* n2 = Y_a */
 704     } else {
 705         if (!field_sqr(group, n0, &b->Z, ctx))
 706             goto end;
 707         if (!field_mul(group, n1, &a->X, n0, ctx))
 708             goto end;
 709         /* n1 = X_a * Z_b^2 */
 710
 711         if (!field_mul(group, n0, n0, &b->Z, ctx))
 712             goto end;
 713         if (!field_mul(group, n2, &a->Y, n0, ctx))
 714             goto end;
 715         /* n2 = Y_a * Z_b^3 */
 716     }
 717
 718     /* n3, n4 */
 719     if (a->Z_is_one) {
 720         if (!BN_copy(n3, &b->X))
 721             goto end;
 722         if (!BN_copy(n4, &b->Y))
 723             goto end;
 724         /* n3 = X_b */
 725         /* n4 = Y_b */
 726     } else {
 727         if (!field_sqr(group, n0, &a->Z, ctx))
 728             goto end;
 729         if (!field_mul(group, n3, &b->X, n0, ctx))
 730             goto end;
 731         /* n3 = X_b * Z_a^2 */
 732
 733         if (!field_mul(group, n0, n0, &a->Z, ctx))
 734             goto end;
 735         if (!field_mul(group, n4, &b->Y, n0, ctx))
 736             goto end;
 737         /* n4 = Y_b * Z_a^3 */
 738     }
 739
 740     /* n5, n6 */
 741     if (!BN_mod_sub_quick(n5, n1, n3, p))
 742         goto end;
 743     if (!BN_mod_sub_quick(n6, n2, n4, p))
 744         goto end;
 745     /* n5 = n1 - n3 */
 746     /* n6 = n2 - n4 */
 747
 748     if (BN_is_zero(n5)) {
 749         if (BN_is_zero(n6)) {
 750             /* a is the same point as b */
 751             BN_CTX_end(ctx);
 752             ret = EC_POINT_dbl(group, r, a, ctx);
 753             ctx = NULL;
 754             goto end;
 755         } else {
 756             /* a is the inverse of b */
 757             BN_zero(&r->Z);
 758             r->Z_is_one = 0;
 759             ret = 1;
 760             goto end;
 761         }
 762     }
 763
 764     /* 'n7', 'n8' */
 765     if (!BN_mod_add_quick(n1, n1, n3, p))
 766         goto end;
 767     if (!BN_mod_add_quick(n2, n2, n4, p))
 768         goto end;
 769     /* 'n7' = n1 + n3 */
 770     /* 'n8' = n2 + n4 */
 771
 772     /* Z_r */
 773     if (a->Z_is_one && b->Z_is_one) {
 774         if (!BN_copy(&r->Z, n5))
 775             goto end;
 776     } else {
 777         if (a->Z_is_one) {
 778             if (!BN_copy(n0, &b->Z))
 779                 goto end;
 780         } else if (b->Z_is_one) {
 781             if (!BN_copy(n0, &a->Z))
 782                 goto end;
 783         } else {
 784             if (!field_mul(group, n0, &a->Z, &b->Z, ctx))
 785                 goto end;
 786         }
 787         if (!field_mul(group, &r->Z, n0, n5, ctx))
 788             goto end;
 789     }
 790     r->Z_is_one = 0;
 791     /* Z_r = Z_a * Z_b * n5 */
 792
 793     /* X_r */
 794     if (!field_sqr(group, n0, n6, ctx))
 795         goto end;
 796     if (!field_sqr(group, n4, n5, ctx))
 797         goto end;
 798     if (!field_mul(group, n3, n1, n4, ctx))
 799         goto end;
 800     if (!BN_mod_sub_quick(&r->X, n0, n3, p))
 801         goto end;
 802     /* X_r = n6^2 - n5^2 * 'n7' */
 803
 804     /* 'n9' */
 805     if (!BN_mod_lshift1_quick(n0, &r->X, p))
 806         goto end;
 807     if (!BN_mod_sub_quick(n0, n3, n0, p))
 808         goto end;
 809     /* n9 = n5^2 * 'n7' - 2 * X_r */
 810
 811     /* Y_r */
 812     if (!field_mul(group, n0, n0, n6, ctx))
 813         goto end;
 814     if (!field_mul(group, n5, n4, n5, ctx))
 815         goto end;               /* now n5 is n5^3 */
 816     if (!field_mul(group, n1, n2, n5, ctx))
 817         goto end;
 818     if (!BN_mod_sub_quick(n0, n0, n1, p))
 819         goto end;
 820     if (BN_is_odd(n0))
 821         if (!BN_add(n0, n0, p))
 822             goto end;
 823     /* now  0 <= n0 < 2*p,  and n0 is even */
 824     if (!BN_rshift1(&r->Y, n0))
 825         goto end;
 826     /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
 827
 828     ret = 1;
 829
 830  end:
 831     if (ctx)                    /* otherwise we already called BN_CTX_end */
 832         BN_CTX_end(ctx);
 833     if (new_ctx != NULL)
 834         BN_CTX_free(new_ctx);
 835     return ret;
 836 }
 837
 838 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
 839                       BN_CTX *ctx)
 840 {
 841     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
 842                       const BIGNUM *, BN_CTX *);
 843     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 844     const BIGNUM *p;
 845     BN_CTX *new_ctx = NULL;
 846     BIGNUM *n0, *n1, *n2, *n3;
 847     int ret = 0;
 848
 849     if (EC_POINT_is_at_infinity(group, a)) {
 850         BN_zero(&r->Z);
 851         r->Z_is_one = 0;
 852         return 1;
 853     }
 854
 855     field_mul = group->meth->field_mul;
 856     field_sqr = group->meth->field_sqr;
 857     p = &group->field;
 858
 859     if (ctx == NULL) {
 860         ctx = new_ctx = BN_CTX_new();
 861         if (ctx == NULL)
 862             return 0;
 863     }
 864
 865     BN_CTX_start(ctx);
 866     n0 = BN_CTX_get(ctx);
 867     n1 = BN_CTX_get(ctx);
 868     n2 = BN_CTX_get(ctx);
 869     n3 = BN_CTX_get(ctx);
 870     if (n3 == NULL)
 871         goto err;
 872
 873     /*
 874      * Note that in this function we must not read components of 'a' once we
 875      * have written the corresponding components of 'r'. ('r' might the same
 876      * as 'a'.)
 877      */
 878
 879     /* n1 */
 880     if (a->Z_is_one) {
 881         if (!field_sqr(group, n0, &a->X, ctx))
 882             goto err;
 883         if (!BN_mod_lshift1_quick(n1, n0, p))
 884             goto err;
 885         if (!BN_mod_add_quick(n0, n0, n1, p))
 886             goto err;
 887         if (!BN_mod_add_quick(n1, n0, &group->a, p))
 888             goto err;
 889         /* n1 = 3 * X_a^2 + a_curve */
 890     } else if (group->a_is_minus3) {
 891         if (!field_sqr(group, n1, &a->Z, ctx))
 892             goto err;
 893         if (!BN_mod_add_quick(n0, &a->X, n1, p))
 894             goto err;
 895         if (!BN_mod_sub_quick(n2, &a->X, n1, p))
 896             goto err;
 897         if (!field_mul(group, n1, n0, n2, ctx))
 898             goto err;
 899         if (!BN_mod_lshift1_quick(n0, n1, p))
 900             goto err;
 901         if (!BN_mod_add_quick(n1, n0, n1, p))
 902             goto err;
 903                 /*-
 904                  * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
 905                  *    = 3 * X_a^2 - 3 * Z_a^4
 906                  */
 907     } else {
 908         if (!field_sqr(group, n0, &a->X, ctx))
 909             goto err;
 910         if (!BN_mod_lshift1_quick(n1, n0, p))
 911             goto err;
 912         if (!BN_mod_add_quick(n0, n0, n1, p))
 913             goto err;
 914         if (!field_sqr(group, n1, &a->Z, ctx))
 915             goto err;
 916         if (!field_sqr(group, n1, n1, ctx))
 917             goto err;
 918         if (!field_mul(group, n1, n1, &group->a, ctx))
 919             goto err;
 920         if (!BN_mod_add_quick(n1, n1, n0, p))
 921             goto err;
 922         /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
 923     }
 924
 925     /* Z_r */
 926     if (a->Z_is_one) {
 927         if (!BN_copy(n0, &a->Y))
 928             goto err;
 929     } else {
 930         if (!field_mul(group, n0, &a->Y, &a->Z, ctx))
 931             goto err;
 932     }
 933     if (!BN_mod_lshift1_quick(&r->Z, n0, p))
 934         goto err;
 935     r->Z_is_one = 0;
 936     /* Z_r = 2 * Y_a * Z_a */
 937
 938     /* n2 */
 939     if (!field_sqr(group, n3, &a->Y, ctx))
 940         goto err;
 941     if (!field_mul(group, n2, &a->X, n3, ctx))
 942         goto err;
 943     if (!BN_mod_lshift_quick(n2, n2, 2, p))
 944         goto err;
 945     /* n2 = 4 * X_a * Y_a^2 */
 946
 947     /* X_r */
 948     if (!BN_mod_lshift1_quick(n0, n2, p))
 949         goto err;
 950     if (!field_sqr(group, &r->X, n1, ctx))
 951         goto err;
 952     if (!BN_mod_sub_quick(&r->X, &r->X, n0, p))
 953         goto err;
 954     /* X_r = n1^2 - 2 * n2 */
 955
 956     /* n3 */
 957     if (!field_sqr(group, n0, n3, ctx))
 958         goto err;
 959     if (!BN_mod_lshift_quick(n3, n0, 3, p))
 960         goto err;
 961     /* n3 = 8 * Y_a^4 */
 962
 963     /* Y_r */
 964     if (!BN_mod_sub_quick(n0, n2, &r->X, p))
 965         goto err;
 966     if (!field_mul(group, n0, n1, n0, ctx))
 967         goto err;
 968     if (!BN_mod_sub_quick(&r->Y, n0, n3, p))
 969         goto err;
 970     /* Y_r = n1 * (n2 - X_r) - n3 */
 971
 972     ret = 1;
 973
 974  err:
 975     BN_CTX_end(ctx);
 976     if (new_ctx != NULL)
 977         BN_CTX_free(new_ctx);
 978     return ret;
 979 }
 980
 981 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
 982 {
 983     if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
 984         /* point is its own inverse */
 985         return 1;
 986
 987     return BN_usub(&point->Y, &group->field, &point->Y);
 988 }
 989
 990 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
 991 {
 992     return BN_is_zero(&point->Z);
 993 }
 994
 995 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
 996                               BN_CTX *ctx)
 997 {
 998     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
 999                       const BIGNUM *, BN_CTX *);
1000     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1001     const BIGNUM *p;
1002     BN_CTX *new_ctx = NULL;
1003     BIGNUM *rh, *tmp, *Z4, *Z6;
1004     int ret = -1;
1005
1006     if (EC_POINT_is_at_infinity(group, point))
1007         return 1;
1008
1009     field_mul = group->meth->field_mul;
1010     field_sqr = group->meth->field_sqr;
1011     p = &group->field;
1012
1013     if (ctx == NULL) {
1014         ctx = new_ctx = BN_CTX_new();
1015         if (ctx == NULL)
1016             return -1;
1017     }
1018
1019     BN_CTX_start(ctx);
1020     rh = BN_CTX_get(ctx);
1021     tmp = BN_CTX_get(ctx);
1022     Z4 = BN_CTX_get(ctx);
1023     Z6 = BN_CTX_get(ctx);
1024     if (Z6 == NULL)
1025         goto err;
1026
1027         /*-
1028          * We have a curve defined by a Weierstrass equation
1029          *      y^2 = x^3 + a*x + b.
1030          * The point to consider is given in Jacobian projective coordinates
1031          * where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
1032          * Substituting this and multiplying by  Z^6  transforms the above equation into
1033          *      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
1034          * To test this, we add up the right-hand side in 'rh'.
1035          */
1036
1037     /* rh := X^2 */
1038     if (!field_sqr(group, rh, &point->X, ctx))
1039         goto err;
1040
1041     if (!point->Z_is_one) {
1042         if (!field_sqr(group, tmp, &point->Z, ctx))
1043             goto err;
1044         if (!field_sqr(group, Z4, tmp, ctx))
1045             goto err;
1046         if (!field_mul(group, Z6, Z4, tmp, ctx))
1047             goto err;
1048
1049         /* rh := (rh + a*Z^4)*X */
1050         if (group->a_is_minus3) {
1051             if (!BN_mod_lshift1_quick(tmp, Z4, p))
1052                 goto err;
1053             if (!BN_mod_add_quick(tmp, tmp, Z4, p))
1054                 goto err;
1055             if (!BN_mod_sub_quick(rh, rh, tmp, p))
1056                 goto err;
1057             if (!field_mul(group, rh, rh, &point->X, ctx))
1058                 goto err;
1059         } else {
1060             if (!field_mul(group, tmp, Z4, &group->a, ctx))
1061                 goto err;
1062             if (!BN_mod_add_quick(rh, rh, tmp, p))
1063                 goto err;
1064             if (!field_mul(group, rh, rh, &point->X, ctx))
1065                 goto err;
1066         }
1067
1068         /* rh := rh + b*Z^6 */
1069         if (!field_mul(group, tmp, &group->b, Z6, ctx))
1070             goto err;
1071         if (!BN_mod_add_quick(rh, rh, tmp, p))
1072             goto err;
1073     } else {
1074         /* point->Z_is_one */
1075
1076         /* rh := (rh + a)*X */
1077         if (!BN_mod_add_quick(rh, rh, &group->a, p))
1078             goto err;
1079         if (!field_mul(group, rh, rh, &point->X, ctx))
1080             goto err;
1081         /* rh := rh + b */
1082         if (!BN_mod_add_quick(rh, rh, &group->b, p))
1083             goto err;
1084     }
1085
1086     /* 'lh' := Y^2 */
1087     if (!field_sqr(group, tmp, &point->Y, ctx))
1088         goto err;
1089
1090     ret = (0 == BN_ucmp(tmp, rh));
1091
1092  err:
1093     BN_CTX_end(ctx);
1094     if (new_ctx != NULL)
1095         BN_CTX_free(new_ctx);
1096     return ret;
1097 }
1098
1099 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
1100                       const EC_POINT *b, BN_CTX *ctx)
1101 {
1102         /*-
1103          * return values:
1104          *  -1   error
1105          *   0   equal (in affine coordinates)
1106          *   1   not equal
1107          */
1108
1109     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
1110                       const BIGNUM *, BN_CTX *);
1111     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1112     BN_CTX *new_ctx = NULL;
1113     BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1114     const BIGNUM *tmp1_, *tmp2_;
1115     int ret = -1;
1116
1117     if (EC_POINT_is_at_infinity(group, a)) {
1118         return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
1119     }
1120
1121     if (EC_POINT_is_at_infinity(group, b))
1122         return 1;
1123
1124     if (a->Z_is_one && b->Z_is_one) {
1125         return ((BN_cmp(&a->X, &b->X) == 0)
1126                 && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
1127     }
1128
1129     field_mul = group->meth->field_mul;
1130     field_sqr = group->meth->field_sqr;
1131
1132     if (ctx == NULL) {
1133         ctx = new_ctx = BN_CTX_new();
1134         if (ctx == NULL)
1135             return -1;
1136     }
1137
1138     BN_CTX_start(ctx);
1139     tmp1 = BN_CTX_get(ctx);
1140     tmp2 = BN_CTX_get(ctx);
1141     Za23 = BN_CTX_get(ctx);
1142     Zb23 = BN_CTX_get(ctx);
1143     if (Zb23 == NULL)
1144         goto end;
1145
1146         /*-
1147          * We have to decide whether
1148          *     (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1149          * or equivalently, whether
1150          *     (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1151          */
1152
1153     if (!b->Z_is_one) {
1154         if (!field_sqr(group, Zb23, &b->Z, ctx))
1155             goto end;
1156         if (!field_mul(group, tmp1, &a->X, Zb23, ctx))
1157             goto end;
1158         tmp1_ = tmp1;
1159     } else
1160         tmp1_ = &a->X;
1161     if (!a->Z_is_one) {
1162         if (!field_sqr(group, Za23, &a->Z, ctx))
1163             goto end;
1164         if (!field_mul(group, tmp2, &b->X, Za23, ctx))
1165             goto end;
1166         tmp2_ = tmp2;
1167     } else
1168         tmp2_ = &b->X;
1169
1170     /* compare  X_a*Z_b^2  with  X_b*Z_a^2 */
1171     if (BN_cmp(tmp1_, tmp2_) != 0) {
1172         ret = 1;                /* points differ */
1173         goto end;
1174     }
1175
1176     if (!b->Z_is_one) {
1177         if (!field_mul(group, Zb23, Zb23, &b->Z, ctx))
1178             goto end;
1179         if (!field_mul(group, tmp1, &a->Y, Zb23, ctx))
1180             goto end;
1181         /* tmp1_ = tmp1 */
1182     } else
1183         tmp1_ = &a->Y;
1184     if (!a->Z_is_one) {
1185         if (!field_mul(group, Za23, Za23, &a->Z, ctx))
1186             goto end;
1187         if (!field_mul(group, tmp2, &b->Y, Za23, ctx))
1188             goto end;
1189         /* tmp2_ = tmp2 */
1190     } else
1191         tmp2_ = &b->Y;
1192
1193     /* compare  Y_a*Z_b^3  with  Y_b*Z_a^3 */
1194     if (BN_cmp(tmp1_, tmp2_) != 0) {
1195         ret = 1;                /* points differ */
1196         goto end;
1197     }
1198
1199     /* points are equal */
1200     ret = 0;
1201
1202  end:
1203     BN_CTX_end(ctx);
1204     if (new_ctx != NULL)
1205         BN_CTX_free(new_ctx);
1206     return ret;
1207 }
1208
1209 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
1210                               BN_CTX *ctx)
1211 {
1212     BN_CTX *new_ctx = NULL;
1213     BIGNUM *x, *y;
1214     int ret = 0;
1215
1216     if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1217         return 1;
1218
1219     if (ctx == NULL) {
1220         ctx = new_ctx = BN_CTX_new();
1221         if (ctx == NULL)
1222             return 0;
1223     }
1224
1225     BN_CTX_start(ctx);
1226     x = BN_CTX_get(ctx);
1227     y = BN_CTX_get(ctx);
1228     if (y == NULL)
1229         goto err;
1230
1231     if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
1232         goto err;
1233     if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
1234         goto err;
1235     if (!point->Z_is_one) {
1236         ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1237         goto err;
1238     }
1239
1240     ret = 1;
1241
1242  err:
1243     BN_CTX_end(ctx);
1244     if (new_ctx != NULL)
1245         BN_CTX_free(new_ctx);
1246     return ret;
1247 }
1248
1249 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num,
1250                                      EC_POINT *points[], BN_CTX *ctx)
1251 {
1252     BN_CTX *new_ctx = NULL;
1253     BIGNUM *tmp, *tmp_Z;
1254     BIGNUM **prod_Z = NULL;
1255     size_t i;
1256     int ret = 0;
1257
1258     if (num == 0)
1259         return 1;
1260
1261     if (ctx == NULL) {
1262         ctx = new_ctx = BN_CTX_new();
1263         if (ctx == NULL)
1264             return 0;
1265     }
1266
1267     BN_CTX_start(ctx);
1268     tmp = BN_CTX_get(ctx);
1269     tmp_Z = BN_CTX_get(ctx);
1270     if (tmp == NULL || tmp_Z == NULL)
1271         goto err;
1272
1273     prod_Z = OPENSSL_malloc(num * sizeof prod_Z[0]);
1274     if (prod_Z == NULL)
1275         goto err;
1276     for (i = 0; i < num; i++) {
1277         prod_Z[i] = BN_new();
1278         if (prod_Z[i] == NULL)
1279             goto err;
1280     }
1281
1282     /*
1283      * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z,
1284      * skipping any zero-valued inputs (pretend that they're 1).
1285      */
1286
1287     if (!BN_is_zero(&points[0]->Z)) {
1288         if (!BN_copy(prod_Z[0], &points[0]->Z))
1289             goto err;
1290     } else {
1291         if (group->meth->field_set_to_one != 0) {
1292             if (!group->meth->field_set_to_one(group, prod_Z[0], ctx))
1293                 goto err;
1294         } else {
1295             if (!BN_one(prod_Z[0]))
1296                 goto err;
1297         }
1298     }
1299
1300     for (i = 1; i < num; i++) {
1301         if (!BN_is_zero(&points[i]->Z)) {
1302             if (!group->meth->field_mul(group, prod_Z[i], prod_Z[i - 1],
1303                                         &points[i]->Z, ctx))
1304                 goto err;
1305         } else {
1306             if (!BN_copy(prod_Z[i], prod_Z[i - 1]))
1307                 goto err;
1308         }
1309     }
1310
1311     /*
1312      * Now use a single explicit inversion to replace every non-zero
1313      * points[i]->Z by its inverse.
1314      */
1315
1316     if (!BN_mod_inverse(tmp, prod_Z[num - 1], &group->field, ctx)) {
1317         ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1318         goto err;
1319     }
1320     if (group->meth->field_encode != 0) {
1321         /*
1322          * In the Montgomery case, we just turned R*H (representing H) into
1323          * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to
1324          * multiply by the Montgomery factor twice.
1325          */
1326         if (!group->meth->field_encode(group, tmp, tmp, ctx))
1327             goto err;
1328         if (!group->meth->field_encode(group, tmp, tmp, ctx))
1329             goto err;
1330     }
1331
1332     for (i = num - 1; i > 0; --i) {
1333         /*
1334          * Loop invariant: tmp is the product of the inverses of points[0]->Z
1335          * .. points[i]->Z (zero-valued inputs skipped).
1336          */
1337         if (!BN_is_zero(&points[i]->Z)) {
1338             /*
1339              * Set tmp_Z to the inverse of points[i]->Z (as product of Z
1340              * inverses 0 .. i, Z values 0 .. i - 1).
1341              */
1342             if (!group->
1343                 meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx))
1344                 goto err;
1345             /*
1346              * Update tmp to satisfy the loop invariant for i - 1.
1347              */
1348             if (!group->meth->field_mul(group, tmp, tmp, &points[i]->Z, ctx))
1349                 goto err;
1350             /* Replace points[i]->Z by its inverse. */
1351             if (!BN_copy(&points[i]->Z, tmp_Z))
1352                 goto err;
1353         }
1354     }
1355
1356     if (!BN_is_zero(&points[0]->Z)) {
1357         /* Replace points[0]->Z by its inverse. */
1358         if (!BN_copy(&points[0]->Z, tmp))
1359             goto err;
1360     }
1361
1362     /* Finally, fix up the X and Y coordinates for all points. */
1363
1364     for (i = 0; i < num; i++) {
1365         EC_POINT *p = points[i];
1366
1367         if (!BN_is_zero(&p->Z)) {
1368             /* turn  (X, Y, 1/Z)  into  (X/Z^2, Y/Z^3, 1) */
1369
1370             if (!group->meth->field_sqr(group, tmp, &p->Z, ctx))
1371                 goto err;
1372             if (!group->meth->field_mul(group, &p->X, &p->X, tmp, ctx))
1373                 goto err;
1374
1375             if (!group->meth->field_mul(group, tmp, tmp, &p->Z, ctx))
1376                 goto err;
1377             if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp, ctx))
1378                 goto err;
1379
1380             if (group->meth->field_set_to_one != 0) {
1381                 if (!group->meth->field_set_to_one(group, &p->Z, ctx))
1382                     goto err;
1383             } else {
1384                 if (!BN_one(&p->Z))
1385                     goto err;
1386             }
1387             p->Z_is_one = 1;
1388         }
1389     }
1390
1391     ret = 1;
1392
1393  err:
1394     BN_CTX_end(ctx);
1395     if (new_ctx != NULL)
1396         BN_CTX_free(new_ctx);
1397     if (prod_Z != NULL) {
1398         for (i = 0; i < num; i++) {
1399             if (prod_Z[i] == NULL)
1400                 break;
1401             BN_clear_free(prod_Z[i]);
1402         }
1403         OPENSSL_free(prod_Z);
1404     }
1405     return ret;
1406 }
1407
1408 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1409                             const BIGNUM *b, BN_CTX *ctx)
1410 {
1411     return BN_mod_mul(r, a, b, &group->field, ctx);
1412 }
1413
1414 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1415                             BN_CTX *ctx)
1416 {
1417     return BN_mod_sqr(r, a, &group->field, ctx);
1418 }