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