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 #include "ec_lcl.h"
  70
  71 const EC_METHOD *EC_GFp_simple_method(void)
  72 {
  73     static const EC_METHOD ret = {
  74         EC_FLAGS_DEFAULT_OCT,
  75         NID_X9_62_prime_field,
  76         ec_GFp_simple_group_init,
  77         ec_GFp_simple_group_finish,
  78         ec_GFp_simple_group_clear_finish,
  79         ec_GFp_simple_group_copy,
  80         ec_GFp_simple_group_set_curve,
  81         ec_GFp_simple_group_get_curve,
  82         ec_GFp_simple_group_get_degree,
  83         ec_GFp_simple_group_check_discriminant,
  84         ec_GFp_simple_point_init,
  85         ec_GFp_simple_point_finish,
  86         ec_GFp_simple_point_clear_finish,
  87         ec_GFp_simple_point_copy,
  88         ec_GFp_simple_point_set_to_infinity,
  89         ec_GFp_simple_set_Jprojective_coordinates_GFp,
  90         ec_GFp_simple_get_Jprojective_coordinates_GFp,
  91         ec_GFp_simple_point_set_affine_coordinates,
  92         ec_GFp_simple_point_get_affine_coordinates,
  93         0, 0, 0,
  94         ec_GFp_simple_add,
  95         ec_GFp_simple_dbl,
  96         ec_GFp_simple_invert,
  97         ec_GFp_simple_is_at_infinity,
  98         ec_GFp_simple_is_on_curve,
  99         ec_GFp_simple_cmp,
 100         ec_GFp_simple_make_affine,
 101         ec_GFp_simple_points_make_affine,
 102         0 /* mul */ ,
 103         0 /* precompute_mult */ ,
 104         0 /* have_precompute_mult */ ,
 105         ec_GFp_simple_field_mul,
 106         ec_GFp_simple_field_sqr,
 107         0 /* field_div */ ,
 108         0 /* field_encode */ ,
 109         0 /* field_decode */ ,
 110         0                       /* field_set_to_one */
 111     };
 112
 113     return &ret;
 114 }
 115
 116 /*
 117  * Most method functions in this file are designed to work with
 118  * non-trivial representations of field elements if necessary
 119  * (see ecp_mont.c): while standard modular addition and subtraction
 120  * are used, the field_mul and field_sqr methods will be used for
 121  * multiplication, and field_encode and field_decode (if defined)
 122  * will be used for converting between representations.
 123  *
 124  * Functions ec_GFp_simple_points_make_affine() and
 125  * ec_GFp_simple_point_get_affine_coordinates() specifically assume
 126  * that if a non-trivial representation is used, it is a Montgomery
 127  * representation (i.e. 'encoding' means multiplying by some factor R).
 128  */
 129
 130 int ec_GFp_simple_group_init(EC_GROUP *group)
 131 {
 132     group->field = BN_new();
 133     group->a = BN_new();
 134     group->b = BN_new();
 135     if (!group->field || !group->a || !group->b) {
 136         if (!group->field)
 137             BN_free(group->field);
 138         if (!group->a)
 139             BN_free(group->a);
 140         if (!group->b)
 141             BN_free(group->b);
 142         return 0;
 143     }
 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     point->X = BN_new();
 364     point->Y = BN_new();
 365     point->Z = BN_new();
 366     point->Z_is_one = 0;
 367
 368     if (!point->X || !point->Y || !point->Z) {
 369         if (point->X)
 370             BN_free(point->X);
 371         if (point->Y)
 372             BN_free(point->Y);
 373         if (point->Z)
 374             BN_free(point->Z);
 375         return 0;
 376     }
 377     return 1;
 378 }
 379
 380 void ec_GFp_simple_point_finish(EC_POINT *point)
 381 {
 382     BN_free(point->X);
 383     BN_free(point->Y);
 384     BN_free(point->Z);
 385 }
 386
 387 void ec_GFp_simple_point_clear_finish(EC_POINT *point)
 388 {
 389     BN_clear_free(point->X);
 390     BN_clear_free(point->Y);
 391     BN_clear_free(point->Z);
 392     point->Z_is_one = 0;
 393 }
 394
 395 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
 396 {
 397     if (!BN_copy(dest->X, src->X))
 398         return 0;
 399     if (!BN_copy(dest->Y, src->Y))
 400         return 0;
 401     if (!BN_copy(dest->Z, src->Z))
 402         return 0;
 403     dest->Z_is_one = src->Z_is_one;
 404
 405     return 1;
 406 }
 407
 408 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group,
 409                                         EC_POINT *point)
 410 {
 411     point->Z_is_one = 0;
 412     BN_zero(point->Z);
 413     return 1;
 414 }
 415
 416 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group,
 417                                                   EC_POINT *point,
 418                                                   const BIGNUM *x,
 419                                                   const BIGNUM *y,
 420                                                   const BIGNUM *z,
 421                                                   BN_CTX *ctx)
 422 {
 423     BN_CTX *new_ctx = NULL;
 424     int ret = 0;
 425
 426     if (ctx == NULL) {
 427         ctx = new_ctx = BN_CTX_new();
 428         if (ctx == NULL)
 429             return 0;
 430     }
 431
 432     if (x != NULL) {
 433         if (!BN_nnmod(point->X, x, group->field, ctx))
 434             goto err;
 435         if (group->meth->field_encode) {
 436             if (!group->meth->field_encode(group, point->X, point->X, ctx))
 437                 goto err;
 438         }
 439     }
 440
 441     if (y != NULL) {
 442         if (!BN_nnmod(point->Y, y, group->field, ctx))
 443             goto err;
 444         if (group->meth->field_encode) {
 445             if (!group->meth->field_encode(group, point->Y, point->Y, ctx))
 446                 goto err;
 447         }
 448     }
 449
 450     if (z != NULL) {
 451         int Z_is_one;
 452
 453         if (!BN_nnmod(point->Z, z, group->field, ctx))
 454             goto err;
 455         Z_is_one = BN_is_one(point->Z);
 456         if (group->meth->field_encode) {
 457             if (Z_is_one && (group->meth->field_set_to_one != 0)) {
 458                 if (!group->meth->field_set_to_one(group, point->Z, ctx))
 459                     goto err;
 460             } else {
 461                 if (!group->
 462                     meth->field_encode(group, point->Z, point->Z, ctx))
 463                     goto err;
 464             }
 465         }
 466         point->Z_is_one = Z_is_one;
 467     }
 468
 469     ret = 1;
 470
 471  err:
 472     if (new_ctx != NULL)
 473         BN_CTX_free(new_ctx);
 474     return ret;
 475 }
 476
 477 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group,
 478                                                   const EC_POINT *point,
 479                                                   BIGNUM *x, BIGNUM *y,
 480                                                   BIGNUM *z, BN_CTX *ctx)
 481 {
 482     BN_CTX *new_ctx = NULL;
 483     int ret = 0;
 484
 485     if (group->meth->field_decode != 0) {
 486         if (ctx == NULL) {
 487             ctx = new_ctx = BN_CTX_new();
 488             if (ctx == NULL)
 489                 return 0;
 490         }
 491
 492         if (x != NULL) {
 493             if (!group->meth->field_decode(group, x, point->X, ctx))
 494                 goto err;
 495         }
 496         if (y != NULL) {
 497             if (!group->meth->field_decode(group, y, point->Y, ctx))
 498                 goto err;
 499         }
 500         if (z != NULL) {
 501             if (!group->meth->field_decode(group, z, point->Z, ctx))
 502                 goto err;
 503         }
 504     } else {
 505         if (x != NULL) {
 506             if (!BN_copy(x, point->X))
 507                 goto err;
 508         }
 509         if (y != NULL) {
 510             if (!BN_copy(y, point->Y))
 511                 goto err;
 512         }
 513         if (z != NULL) {
 514             if (!BN_copy(z, point->Z))
 515                 goto err;
 516         }
 517     }
 518
 519     ret = 1;
 520
 521  err:
 522     if (new_ctx != NULL)
 523         BN_CTX_free(new_ctx);
 524     return ret;
 525 }
 526
 527 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group,
 528                                                EC_POINT *point,
 529                                                const BIGNUM *x,
 530                                                const BIGNUM *y, BN_CTX *ctx)
 531 {
 532     if (x == NULL || y == NULL) {
 533         /*
 534          * unlike for projective coordinates, we do not tolerate this
 535          */
 536         ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES,
 537               ERR_R_PASSED_NULL_PARAMETER);
 538         return 0;
 539     }
 540
 541     return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y,
 542                                                     BN_value_one(), ctx);
 543 }
 544
 545 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
 546                                                const EC_POINT *point,
 547                                                BIGNUM *x, BIGNUM *y,
 548                                                BN_CTX *ctx)
 549 {
 550     BN_CTX *new_ctx = NULL;
 551     BIGNUM *Z, *Z_1, *Z_2, *Z_3;
 552     const BIGNUM *Z_;
 553     int ret = 0;
 554
 555     if (EC_POINT_is_at_infinity(group, point)) {
 556         ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
 557               EC_R_POINT_AT_INFINITY);
 558         return 0;
 559     }
 560
 561     if (ctx == NULL) {
 562         ctx = new_ctx = BN_CTX_new();
 563         if (ctx == NULL)
 564             return 0;
 565     }
 566
 567     BN_CTX_start(ctx);
 568     Z = BN_CTX_get(ctx);
 569     Z_1 = BN_CTX_get(ctx);
 570     Z_2 = BN_CTX_get(ctx);
 571     Z_3 = BN_CTX_get(ctx);
 572     if (Z_3 == NULL)
 573         goto err;
 574
 575     /* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
 576
 577     if (group->meth->field_decode) {
 578         if (!group->meth->field_decode(group, Z, point->Z, ctx))
 579             goto err;
 580         Z_ = Z;
 581     } else {
 582         Z_ = point->Z;
 583     }
 584
 585     if (BN_is_one(Z_)) {
 586         if (group->meth->field_decode) {
 587             if (x != NULL) {
 588                 if (!group->meth->field_decode(group, x, point->X, ctx))
 589                     goto err;
 590             }
 591             if (y != NULL) {
 592                 if (!group->meth->field_decode(group, y, point->Y, ctx))
 593                     goto err;
 594             }
 595         } else {
 596             if (x != NULL) {
 597                 if (!BN_copy(x, point->X))
 598                     goto err;
 599             }
 600             if (y != NULL) {
 601                 if (!BN_copy(y, point->Y))
 602                     goto err;
 603             }
 604         }
 605     } else {
 606         if (!BN_mod_inverse(Z_1, Z_, group->field, ctx)) {
 607             ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
 608                   ERR_R_BN_LIB);
 609             goto err;
 610         }
 611
 612         if (group->meth->field_encode == 0) {
 613             /* field_sqr works on standard representation */
 614             if (!group->meth->field_sqr(group, Z_2, Z_1, ctx))
 615                 goto err;
 616         } else {
 617             if (!BN_mod_sqr(Z_2, Z_1, group->field, ctx))
 618                 goto err;
 619         }
 620
 621         if (x != NULL) {
 622             /*
 623              * in the Montgomery case, field_mul will cancel out Montgomery
 624              * factor in X:
 625              */
 626             if (!group->meth->field_mul(group, x, point->X, Z_2, ctx))
 627                 goto err;
 628         }
 629
 630         if (y != NULL) {
 631             if (group->meth->field_encode == 0) {
 632                 /*
 633                  * field_mul works on standard representation
 634                  */
 635                 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx))
 636                     goto err;
 637             } else {
 638                 if (!BN_mod_mul(Z_3, Z_2, Z_1, group->field, ctx))
 639                     goto err;
 640             }
 641
 642             /*
 643              * in the Montgomery case, field_mul will cancel out Montgomery
 644              * factor in Y:
 645              */
 646             if (!group->meth->field_mul(group, y, point->Y, Z_3, ctx))
 647                 goto err;
 648         }
 649     }
 650
 651     ret = 1;
 652
 653  err:
 654     BN_CTX_end(ctx);
 655     if (new_ctx != NULL)
 656         BN_CTX_free(new_ctx);
 657     return ret;
 658 }
 659
 660 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
 661                       const EC_POINT *b, BN_CTX *ctx)
 662 {
 663     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
 664                       const BIGNUM *, BN_CTX *);
 665     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 666     const BIGNUM *p;
 667     BN_CTX *new_ctx = NULL;
 668     BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
 669     int ret = 0;
 670
 671     if (a == b)
 672         return EC_POINT_dbl(group, r, a, ctx);
 673     if (EC_POINT_is_at_infinity(group, a))
 674         return EC_POINT_copy(r, b);
 675     if (EC_POINT_is_at_infinity(group, b))
 676         return EC_POINT_copy(r, a);
 677
 678     field_mul = group->meth->field_mul;
 679     field_sqr = group->meth->field_sqr;
 680     p = group->field;
 681
 682     if (ctx == NULL) {
 683         ctx = new_ctx = BN_CTX_new();
 684         if (ctx == NULL)
 685             return 0;
 686     }
 687
 688     BN_CTX_start(ctx);
 689     n0 = BN_CTX_get(ctx);
 690     n1 = BN_CTX_get(ctx);
 691     n2 = BN_CTX_get(ctx);
 692     n3 = BN_CTX_get(ctx);
 693     n4 = BN_CTX_get(ctx);
 694     n5 = BN_CTX_get(ctx);
 695     n6 = BN_CTX_get(ctx);
 696     if (n6 == NULL)
 697         goto end;
 698
 699     /*
 700      * Note that in this function we must not read components of 'a' or 'b'
 701      * once we have written the corresponding components of 'r'. ('r' might
 702      * be one of 'a' or 'b'.)
 703      */
 704
 705     /* n1, n2 */
 706     if (b->Z_is_one) {
 707         if (!BN_copy(n1, a->X))
 708             goto end;
 709         if (!BN_copy(n2, a->Y))
 710             goto end;
 711         /* n1 = X_a */
 712         /* n2 = Y_a */
 713     } else {
 714         if (!field_sqr(group, n0, b->Z, ctx))
 715             goto end;
 716         if (!field_mul(group, n1, a->X, n0, ctx))
 717             goto end;
 718         /* n1 = X_a * Z_b^2 */
 719
 720         if (!field_mul(group, n0, n0, b->Z, ctx))
 721             goto end;
 722         if (!field_mul(group, n2, a->Y, n0, ctx))
 723             goto end;
 724         /* n2 = Y_a * Z_b^3 */
 725     }
 726
 727     /* n3, n4 */
 728     if (a->Z_is_one) {
 729         if (!BN_copy(n3, b->X))
 730             goto end;
 731         if (!BN_copy(n4, b->Y))
 732             goto end;
 733         /* n3 = X_b */
 734         /* n4 = Y_b */
 735     } else {
 736         if (!field_sqr(group, n0, a->Z, ctx))
 737             goto end;
 738         if (!field_mul(group, n3, b->X, n0, ctx))
 739             goto end;
 740         /* n3 = X_b * Z_a^2 */
 741
 742         if (!field_mul(group, n0, n0, a->Z, ctx))
 743             goto end;
 744         if (!field_mul(group, n4, b->Y, n0, ctx))
 745             goto end;
 746         /* n4 = Y_b * Z_a^3 */
 747     }
 748
 749     /* n5, n6 */
 750     if (!BN_mod_sub_quick(n5, n1, n3, p))
 751         goto end;
 752     if (!BN_mod_sub_quick(n6, n2, n4, p))
 753         goto end;
 754     /* n5 = n1 - n3 */
 755     /* n6 = n2 - n4 */
 756
 757     if (BN_is_zero(n5)) {
 758         if (BN_is_zero(n6)) {
 759             /* a is the same point as b */
 760             BN_CTX_end(ctx);
 761             ret = EC_POINT_dbl(group, r, a, ctx);
 762             ctx = NULL;
 763             goto end;
 764         } else {
 765             /* a is the inverse of b */
 766             BN_zero(r->Z);
 767             r->Z_is_one = 0;
 768             ret = 1;
 769             goto end;
 770         }
 771     }
 772
 773     /* 'n7', 'n8' */
 774     if (!BN_mod_add_quick(n1, n1, n3, p))
 775         goto end;
 776     if (!BN_mod_add_quick(n2, n2, n4, p))
 777         goto end;
 778     /* 'n7' = n1 + n3 */
 779     /* 'n8' = n2 + n4 */
 780
 781     /* Z_r */
 782     if (a->Z_is_one && b->Z_is_one) {
 783         if (!BN_copy(r->Z, n5))
 784             goto end;
 785     } else {
 786         if (a->Z_is_one) {
 787             if (!BN_copy(n0, b->Z))
 788                 goto end;
 789         } else if (b->Z_is_one) {
 790             if (!BN_copy(n0, a->Z))
 791                 goto end;
 792         } else {
 793             if (!field_mul(group, n0, a->Z, b->Z, ctx))
 794                 goto end;
 795         }
 796         if (!field_mul(group, r->Z, n0, n5, ctx))
 797             goto end;
 798     }
 799     r->Z_is_one = 0;
 800     /* Z_r = Z_a * Z_b * n5 */
 801
 802     /* X_r */
 803     if (!field_sqr(group, n0, n6, ctx))
 804         goto end;
 805     if (!field_sqr(group, n4, n5, ctx))
 806         goto end;
 807     if (!field_mul(group, n3, n1, n4, ctx))
 808         goto end;
 809     if (!BN_mod_sub_quick(r->X, n0, n3, p))
 810         goto end;
 811     /* X_r = n6^2 - n5^2 * 'n7' */
 812
 813     /* 'n9' */
 814     if (!BN_mod_lshift1_quick(n0, r->X, p))
 815         goto end;
 816     if (!BN_mod_sub_quick(n0, n3, n0, p))
 817         goto end;
 818     /* n9 = n5^2 * 'n7' - 2 * X_r */
 819
 820     /* Y_r */
 821     if (!field_mul(group, n0, n0, n6, ctx))
 822         goto end;
 823     if (!field_mul(group, n5, n4, n5, ctx))
 824         goto end;               /* now n5 is n5^3 */
 825     if (!field_mul(group, n1, n2, n5, ctx))
 826         goto end;
 827     if (!BN_mod_sub_quick(n0, n0, n1, p))
 828         goto end;
 829     if (BN_is_odd(n0))
 830         if (!BN_add(n0, n0, p))
 831             goto end;
 832     /* now  0 <= n0 < 2*p,  and n0 is even */
 833     if (!BN_rshift1(r->Y, n0))
 834         goto end;
 835     /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
 836
 837     ret = 1;
 838
 839  end:
 840     if (ctx)                    /* otherwise we already called BN_CTX_end */
 841         BN_CTX_end(ctx);
 842     if (new_ctx != NULL)
 843         BN_CTX_free(new_ctx);
 844     return ret;
 845 }
 846
 847 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
 848                       BN_CTX *ctx)
 849 {
 850     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
 851                       const BIGNUM *, BN_CTX *);
 852     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 853     const BIGNUM *p;
 854     BN_CTX *new_ctx = NULL;
 855     BIGNUM *n0, *n1, *n2, *n3;
 856     int ret = 0;
 857
 858     if (EC_POINT_is_at_infinity(group, a)) {
 859         BN_zero(r->Z);
 860         r->Z_is_one = 0;
 861         return 1;
 862     }
 863
 864     field_mul = group->meth->field_mul;
 865     field_sqr = group->meth->field_sqr;
 866     p = group->field;
 867
 868     if (ctx == NULL) {
 869         ctx = new_ctx = BN_CTX_new();
 870         if (ctx == NULL)
 871             return 0;
 872     }
 873
 874     BN_CTX_start(ctx);
 875     n0 = BN_CTX_get(ctx);
 876     n1 = BN_CTX_get(ctx);
 877     n2 = BN_CTX_get(ctx);
 878     n3 = BN_CTX_get(ctx);
 879     if (n3 == NULL)
 880         goto err;
 881
 882     /*
 883      * Note that in this function we must not read components of 'a' once we
 884      * have written the corresponding components of 'r'. ('r' might the same
 885      * as 'a'.)
 886      */
 887
 888     /* n1 */
 889     if (a->Z_is_one) {
 890         if (!field_sqr(group, n0, a->X, ctx))
 891             goto err;
 892         if (!BN_mod_lshift1_quick(n1, n0, p))
 893             goto err;
 894         if (!BN_mod_add_quick(n0, n0, n1, p))
 895             goto err;
 896         if (!BN_mod_add_quick(n1, n0, group->a, p))
 897             goto err;
 898         /* n1 = 3 * X_a^2 + a_curve */
 899     } else if (group->a_is_minus3) {
 900         if (!field_sqr(group, n1, a->Z, ctx))
 901             goto err;
 902         if (!BN_mod_add_quick(n0, a->X, n1, p))
 903             goto err;
 904         if (!BN_mod_sub_quick(n2, a->X, n1, p))
 905             goto err;
 906         if (!field_mul(group, n1, n0, n2, ctx))
 907             goto err;
 908         if (!BN_mod_lshift1_quick(n0, n1, p))
 909             goto err;
 910         if (!BN_mod_add_quick(n1, n0, n1, p))
 911             goto err;
 912                 /*-
 913                  * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
 914                  *    = 3 * X_a^2 - 3 * Z_a^4
 915                  */
 916     } else {
 917         if (!field_sqr(group, n0, a->X, ctx))
 918             goto err;
 919         if (!BN_mod_lshift1_quick(n1, n0, p))
 920             goto err;
 921         if (!BN_mod_add_quick(n0, n0, n1, p))
 922             goto err;
 923         if (!field_sqr(group, n1, a->Z, ctx))
 924             goto err;
 925         if (!field_sqr(group, n1, n1, ctx))
 926             goto err;
 927         if (!field_mul(group, n1, n1, group->a, ctx))
 928             goto err;
 929         if (!BN_mod_add_quick(n1, n1, n0, p))
 930             goto err;
 931         /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
 932     }
 933
 934     /* Z_r */
 935     if (a->Z_is_one) {
 936         if (!BN_copy(n0, a->Y))
 937             goto err;
 938     } else {
 939         if (!field_mul(group, n0, a->Y, a->Z, ctx))
 940             goto err;
 941     }
 942     if (!BN_mod_lshift1_quick(r->Z, n0, p))
 943         goto err;
 944     r->Z_is_one = 0;
 945     /* Z_r = 2 * Y_a * Z_a */
 946
 947     /* n2 */
 948     if (!field_sqr(group, n3, a->Y, ctx))
 949         goto err;
 950     if (!field_mul(group, n2, a->X, n3, ctx))
 951         goto err;
 952     if (!BN_mod_lshift_quick(n2, n2, 2, p))
 953         goto err;
 954     /* n2 = 4 * X_a * Y_a^2 */
 955
 956     /* X_r */
 957     if (!BN_mod_lshift1_quick(n0, n2, p))
 958         goto err;
 959     if (!field_sqr(group, r->X, n1, ctx))
 960         goto err;
 961     if (!BN_mod_sub_quick(r->X, r->X, n0, p))
 962         goto err;
 963     /* X_r = n1^2 - 2 * n2 */
 964
 965     /* n3 */
 966     if (!field_sqr(group, n0, n3, ctx))
 967         goto err;
 968     if (!BN_mod_lshift_quick(n3, n0, 3, p))
 969         goto err;
 970     /* n3 = 8 * Y_a^4 */
 971
 972     /* Y_r */
 973     if (!BN_mod_sub_quick(n0, n2, r->X, p))
 974         goto err;
 975     if (!field_mul(group, n0, n1, n0, ctx))
 976         goto err;
 977     if (!BN_mod_sub_quick(r->Y, n0, n3, p))
 978         goto err;
 979     /* Y_r = n1 * (n2 - X_r) - n3 */
 980
 981     ret = 1;
 982
 983  err:
 984     BN_CTX_end(ctx);
 985     if (new_ctx != NULL)
 986         BN_CTX_free(new_ctx);
 987     return ret;
 988 }
 989
 990 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
 991 {
 992     if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
 993         /* point is its own inverse */
 994         return 1;
 995
 996     return BN_usub(point->Y, group->field, point->Y);
 997 }
 998
 999 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
1000 {
1001     return BN_is_zero(point->Z);
1002 }
1003
1004 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
1005                               BN_CTX *ctx)
1006 {
1007     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
1008                       const BIGNUM *, BN_CTX *);
1009     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1010     const BIGNUM *p;
1011     BN_CTX *new_ctx = NULL;
1012     BIGNUM *rh, *tmp, *Z4, *Z6;
1013     int ret = -1;
1014
1015     if (EC_POINT_is_at_infinity(group, point))
1016         return 1;
1017
1018     field_mul = group->meth->field_mul;
1019     field_sqr = group->meth->field_sqr;
1020     p = group->field;
1021
1022     if (ctx == NULL) {
1023         ctx = new_ctx = BN_CTX_new();
1024         if (ctx == NULL)
1025             return -1;
1026     }
1027
1028     BN_CTX_start(ctx);
1029     rh = BN_CTX_get(ctx);
1030     tmp = BN_CTX_get(ctx);
1031     Z4 = BN_CTX_get(ctx);
1032     Z6 = BN_CTX_get(ctx);
1033     if (Z6 == NULL)
1034         goto err;
1035
1036         /*-
1037          * We have a curve defined by a Weierstrass equation
1038          *      y^2 = x^3 + a*x + b.
1039          * The point to consider is given in Jacobian projective coordinates
1040          * where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
1041          * Substituting this and multiplying by  Z^6  transforms the above equation into
1042          *      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
1043          * To test this, we add up the right-hand side in 'rh'.
1044          */
1045
1046     /* rh := X^2 */
1047     if (!field_sqr(group, rh, point->X, ctx))
1048         goto err;
1049
1050     if (!point->Z_is_one) {
1051         if (!field_sqr(group, tmp, point->Z, ctx))
1052             goto err;
1053         if (!field_sqr(group, Z4, tmp, ctx))
1054             goto err;
1055         if (!field_mul(group, Z6, Z4, tmp, ctx))
1056             goto err;
1057
1058         /* rh := (rh + a*Z^4)*X */
1059         if (group->a_is_minus3) {
1060             if (!BN_mod_lshift1_quick(tmp, Z4, p))
1061                 goto err;
1062             if (!BN_mod_add_quick(tmp, tmp, Z4, p))
1063                 goto err;
1064             if (!BN_mod_sub_quick(rh, rh, tmp, p))
1065                 goto err;
1066             if (!field_mul(group, rh, rh, point->X, ctx))
1067                 goto err;
1068         } else {
1069             if (!field_mul(group, tmp, Z4, group->a, ctx))
1070                 goto err;
1071             if (!BN_mod_add_quick(rh, rh, tmp, p))
1072                 goto err;
1073             if (!field_mul(group, rh, rh, point->X, ctx))
1074                 goto err;
1075         }
1076
1077         /* rh := rh + b*Z^6 */
1078         if (!field_mul(group, tmp, group->b, Z6, ctx))
1079             goto err;
1080         if (!BN_mod_add_quick(rh, rh, tmp, p))
1081             goto err;
1082     } else {
1083         /* point->Z_is_one */
1084
1085         /* rh := (rh + a)*X */
1086         if (!BN_mod_add_quick(rh, rh, group->a, p))
1087             goto err;
1088         if (!field_mul(group, rh, rh, point->X, ctx))
1089             goto err;
1090         /* rh := rh + b */
1091         if (!BN_mod_add_quick(rh, rh, group->b, p))
1092             goto err;
1093     }
1094
1095     /* 'lh' := Y^2 */
1096     if (!field_sqr(group, tmp, point->Y, ctx))
1097         goto err;
1098
1099     ret = (0 == BN_ucmp(tmp, rh));
1100
1101  err:
1102     BN_CTX_end(ctx);
1103     if (new_ctx != NULL)
1104         BN_CTX_free(new_ctx);
1105     return ret;
1106 }
1107
1108 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
1109                       const EC_POINT *b, BN_CTX *ctx)
1110 {
1111         /*-
1112          * return values:
1113          *  -1   error
1114          *   0   equal (in affine coordinates)
1115          *   1   not equal
1116          */
1117
1118     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
1119                       const BIGNUM *, BN_CTX *);
1120     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1121     BN_CTX *new_ctx = NULL;
1122     BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1123     const BIGNUM *tmp1_, *tmp2_;
1124     int ret = -1;
1125
1126     if (EC_POINT_is_at_infinity(group, a)) {
1127         return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
1128     }
1129
1130     if (EC_POINT_is_at_infinity(group, b))
1131         return 1;
1132
1133     if (a->Z_is_one && b->Z_is_one) {
1134         return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
1135     }
1136
1137     field_mul = group->meth->field_mul;
1138     field_sqr = group->meth->field_sqr;
1139
1140     if (ctx == NULL) {
1141         ctx = new_ctx = BN_CTX_new();
1142         if (ctx == NULL)
1143             return -1;
1144     }
1145
1146     BN_CTX_start(ctx);
1147     tmp1 = BN_CTX_get(ctx);
1148     tmp2 = BN_CTX_get(ctx);
1149     Za23 = BN_CTX_get(ctx);
1150     Zb23 = BN_CTX_get(ctx);
1151     if (Zb23 == NULL)
1152         goto end;
1153
1154         /*-
1155          * We have to decide whether
1156          *     (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1157          * or equivalently, whether
1158          *     (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1159          */
1160
1161     if (!b->Z_is_one) {
1162         if (!field_sqr(group, Zb23, b->Z, ctx))
1163             goto end;
1164         if (!field_mul(group, tmp1, a->X, Zb23, ctx))
1165             goto end;
1166         tmp1_ = tmp1;
1167     } else
1168         tmp1_ = a->X;
1169     if (!a->Z_is_one) {
1170         if (!field_sqr(group, Za23, a->Z, ctx))
1171             goto end;
1172         if (!field_mul(group, tmp2, b->X, Za23, ctx))
1173             goto end;
1174         tmp2_ = tmp2;
1175     } else
1176         tmp2_ = b->X;
1177
1178     /* compare  X_a*Z_b^2  with  X_b*Z_a^2 */
1179     if (BN_cmp(tmp1_, tmp2_) != 0) {
1180         ret = 1;                /* points differ */
1181         goto end;
1182     }
1183
1184     if (!b->Z_is_one) {
1185         if (!field_mul(group, Zb23, Zb23, b->Z, ctx))
1186             goto end;
1187         if (!field_mul(group, tmp1, a->Y, Zb23, ctx))
1188             goto end;
1189         /* tmp1_ = tmp1 */
1190     } else
1191         tmp1_ = a->Y;
1192     if (!a->Z_is_one) {
1193         if (!field_mul(group, Za23, Za23, a->Z, ctx))
1194             goto end;
1195         if (!field_mul(group, tmp2, b->Y, Za23, ctx))
1196             goto end;
1197         /* tmp2_ = tmp2 */
1198     } else
1199         tmp2_ = b->Y;
1200
1201     /* compare  Y_a*Z_b^3  with  Y_b*Z_a^3 */
1202     if (BN_cmp(tmp1_, tmp2_) != 0) {
1203         ret = 1;                /* points differ */
1204         goto end;
1205     }
1206
1207     /* points are equal */
1208     ret = 0;
1209
1210  end:
1211     BN_CTX_end(ctx);
1212     if (new_ctx != NULL)
1213         BN_CTX_free(new_ctx);
1214     return ret;
1215 }
1216
1217 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
1218                               BN_CTX *ctx)
1219 {
1220     BN_CTX *new_ctx = NULL;
1221     BIGNUM *x, *y;
1222     int ret = 0;
1223
1224     if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1225         return 1;
1226
1227     if (ctx == NULL) {
1228         ctx = new_ctx = BN_CTX_new();
1229         if (ctx == NULL)
1230             return 0;
1231     }
1232
1233     BN_CTX_start(ctx);
1234     x = BN_CTX_get(ctx);
1235     y = BN_CTX_get(ctx);
1236     if (y == NULL)
1237         goto err;
1238
1239     if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
1240         goto err;
1241     if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
1242         goto err;
1243     if (!point->Z_is_one) {
1244         ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1245         goto err;
1246     }
1247
1248     ret = 1;
1249
1250  err:
1251     BN_CTX_end(ctx);
1252     if (new_ctx != NULL)
1253         BN_CTX_free(new_ctx);
1254     return ret;
1255 }
1256
1257 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num,
1258                                      EC_POINT *points[], BN_CTX *ctx)
1259 {
1260     BN_CTX *new_ctx = NULL;
1261     BIGNUM *tmp, *tmp_Z;
1262     BIGNUM **prod_Z = NULL;
1263     size_t i;
1264     int ret = 0;
1265
1266     if (num == 0)
1267         return 1;
1268
1269     if (ctx == NULL) {
1270         ctx = new_ctx = BN_CTX_new();
1271         if (ctx == NULL)
1272             return 0;
1273     }
1274
1275     BN_CTX_start(ctx);
1276     tmp = BN_CTX_get(ctx);
1277     tmp_Z = BN_CTX_get(ctx);
1278     if (tmp == NULL || tmp_Z == NULL)
1279         goto err;
1280
1281     prod_Z = OPENSSL_malloc(num * sizeof prod_Z[0]);
1282     if (prod_Z == NULL)
1283         goto err;
1284     for (i = 0; i < num; i++) {
1285         prod_Z[i] = BN_new();
1286         if (prod_Z[i] == NULL)
1287             goto err;
1288     }
1289
1290     /*
1291      * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z,
1292      * skipping any zero-valued inputs (pretend that they're 1).
1293      */
1294
1295     if (!BN_is_zero(points[0]->Z)) {
1296         if (!BN_copy(prod_Z[0], points[0]->Z))
1297             goto err;
1298     } else {
1299         if (group->meth->field_set_to_one != 0) {
1300             if (!group->meth->field_set_to_one(group, prod_Z[0], ctx))
1301                 goto err;
1302         } else {
1303             if (!BN_one(prod_Z[0]))
1304                 goto err;
1305         }
1306     }
1307
1308     for (i = 1; i < num; i++) {
1309         if (!BN_is_zero(points[i]->Z)) {
1310             if (!group->
1311                 meth->field_mul(group, prod_Z[i], prod_Z[i - 1], points[i]->Z,
1312                                 ctx))
1313                 goto err;
1314         } else {
1315             if (!BN_copy(prod_Z[i], prod_Z[i - 1]))
1316                 goto err;
1317         }
1318     }
1319
1320     /*
1321      * Now use a single explicit inversion to replace every non-zero
1322      * points[i]->Z by its inverse.
1323      */
1324
1325     if (!BN_mod_inverse(tmp, prod_Z[num - 1], group->field, ctx)) {
1326         ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1327         goto err;
1328     }
1329     if (group->meth->field_encode != 0) {
1330         /*
1331          * In the Montgomery case, we just turned R*H (representing H) into
1332          * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to
1333          * multiply by the Montgomery factor twice.
1334          */
1335         if (!group->meth->field_encode(group, tmp, tmp, ctx))
1336             goto err;
1337         if (!group->meth->field_encode(group, tmp, tmp, ctx))
1338             goto err;
1339     }
1340
1341     for (i = num - 1; i > 0; --i) {
1342         /*
1343          * Loop invariant: tmp is the product of the inverses of points[0]->Z
1344          * .. points[i]->Z (zero-valued inputs skipped).
1345          */
1346         if (!BN_is_zero(points[i]->Z)) {
1347             /*
1348              * Set tmp_Z to the inverse of points[i]->Z (as product of Z
1349              * inverses 0 .. i, Z values 0 .. i - 1).
1350              */
1351             if (!group->
1352                 meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx))
1353                 goto err;
1354             /*
1355              * Update tmp to satisfy the loop invariant for i - 1.
1356              */
1357             if (!group->meth->field_mul(group, tmp, tmp, points[i]->Z, ctx))
1358                 goto err;
1359             /* Replace points[i]->Z by its inverse. */
1360             if (!BN_copy(points[i]->Z, tmp_Z))
1361                 goto err;
1362         }
1363     }
1364
1365     if (!BN_is_zero(points[0]->Z)) {
1366         /* Replace points[0]->Z by its inverse. */
1367         if (!BN_copy(points[0]->Z, tmp))
1368             goto err;
1369     }
1370
1371     /* Finally, fix up the X and Y coordinates for all points. */
1372
1373     for (i = 0; i < num; i++) {
1374         EC_POINT *p = points[i];
1375
1376         if (!BN_is_zero(p->Z)) {
1377             /* turn  (X, Y, 1/Z)  into  (X/Z^2, Y/Z^3, 1) */
1378
1379             if (!group->meth->field_sqr(group, tmp, p->Z, ctx))
1380                 goto err;
1381             if (!group->meth->field_mul(group, p->X, p->X, tmp, ctx))
1382                 goto err;
1383
1384             if (!group->meth->field_mul(group, tmp, tmp, p->Z, ctx))
1385                 goto err;
1386             if (!group->meth->field_mul(group, p->Y, p->Y, tmp, ctx))
1387                 goto err;
1388
1389             if (group->meth->field_set_to_one != 0) {
1390                 if (!group->meth->field_set_to_one(group, p->Z, ctx))
1391                     goto err;
1392             } else {
1393                 if (!BN_one(p->Z))
1394                     goto err;
1395             }
1396             p->Z_is_one = 1;
1397         }
1398     }
1399
1400     ret = 1;
1401
1402  err:
1403     BN_CTX_end(ctx);
1404     if (new_ctx != NULL)
1405         BN_CTX_free(new_ctx);
1406     if (prod_Z != NULL) {
1407         for (i = 0; i < num; i++) {
1408             if (prod_Z[i] == NULL)
1409                 break;
1410             BN_clear_free(prod_Z[i]);
1411         }
1412         OPENSSL_free(prod_Z);
1413     }
1414     return ret;
1415 }
1416
1417 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1418                             const BIGNUM *b, BN_CTX *ctx)
1419 {
1420     return BN_mod_mul(r, a, b, group->field, ctx);
1421 }
1422
1423 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1424                             BN_CTX *ctx)
1425 {
1426     return BN_mod_sqr(r, a, group->field, ctx);
1427 }