crypto/ec/ecp_smpl.c

   1 /*
   2  * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
   3  * for the OpenSSL project. Includes code written by Bodo Moeller for the
   4  * OpenSSL project.
   5  */
   6 /* ====================================================================
   7  * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  *
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in
  18  *    the documentation and/or other materials provided with the
  19  *    distribution.
  20  *
  21  * 3. All advertising materials mentioning features or use of this
  22  *    software must display the following acknowledgment:
  23  *    "This product includes software developed by the OpenSSL Project
  24  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  25  *
  26  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  27  *    endorse or promote products derived from this software without
  28  *    prior written permission. For written permission, please contact
  29  *    openssl-core@openssl.org.
  30  *
  31  * 5. Products derived from this software may not be called "OpenSSL"
  32  *    nor may "OpenSSL" appear in their names without prior written
  33  *    permission of the OpenSSL Project.
  34  *
  35  * 6. Redistributions of any form whatsoever must retain the following
  36  *    acknowledgment:
  37  *    "This product includes software developed by the OpenSSL Project
  38  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  41  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  43  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  44  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  45  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  46  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  47  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  49  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  50  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  51  * OF THE POSSIBILITY OF SUCH DAMAGE.
  52  * ====================================================================
  53  *
  54  * This product includes cryptographic software written by Eric Young
  55  * (eay@cryptsoft.com).  This product includes software written by Tim
  56  * Hudson (tjh@cryptsoft.com).
  57  *
  58  */
  59 /* ====================================================================
  60  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  61  * Portions of this software developed by SUN MICROSYSTEMS, INC.,
  62  * and contributed to the OpenSSL project.
  63  */
  64
  65 #include <openssl/err.h>
  66 #include <openssl/symhacks.h>
  67
  68 #include "ec_lcl.h"
  69
  70 const EC_METHOD *EC_GFp_simple_method(void)
  71 {
  72     static const EC_METHOD ret = {
  73         EC_FLAGS_DEFAULT_OCT,
  74         NID_X9_62_prime_field,
  75         ec_GFp_simple_group_init,
  76         ec_GFp_simple_group_finish,
  77         ec_GFp_simple_group_clear_finish,
  78         ec_GFp_simple_group_copy,
  79         ec_GFp_simple_group_set_curve,
  80         ec_GFp_simple_group_get_curve,
  81         ec_GFp_simple_group_get_degree,
  82         ec_group_simple_order_bits,
  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         ec_key_simple_priv2oct,
 112         ec_key_simple_oct2priv,
 113         0, /* set private */
 114         ec_key_simple_generate_key,
 115         ec_key_simple_check_key,
 116         ec_key_simple_generate_public_key,
 117         0, /* keycopy */
 118         0, /* keyfinish */
 119         ecdh_simple_compute_key
 120     };
 121
 122     return &ret;
 123 }
 124
 125 /*
 126  * Most method functions in this file are designed to work with
 127  * non-trivial representations of field elements if necessary
 128  * (see ecp_mont.c): while standard modular addition and subtraction
 129  * are used, the field_mul and field_sqr methods will be used for
 130  * multiplication, and field_encode and field_decode (if defined)
 131  * will be used for converting between representations.
 132  *
 133  * Functions ec_GFp_simple_points_make_affine() and
 134  * ec_GFp_simple_point_get_affine_coordinates() specifically assume
 135  * that if a non-trivial representation is used, it is a Montgomery
 136  * representation (i.e. 'encoding' means multiplying by some factor R).
 137  */
 138
 139 int ec_GFp_simple_group_init(EC_GROUP *group)
 140 {
 141     group->field = BN_new();
 142     group->a = BN_new();
 143     group->b = BN_new();
 144     if (group->field == NULL || group->a == NULL || group->b == NULL) {
 145         BN_free(group->field);
 146         BN_free(group->a);
 147         BN_free(group->b);
 148         return 0;
 149     }
 150     group->a_is_minus3 = 0;
 151     return 1;
 152 }
 153
 154 void ec_GFp_simple_group_finish(EC_GROUP *group)
 155 {
 156     BN_free(group->field);
 157     BN_free(group->a);
 158     BN_free(group->b);
 159 }
 160
 161 void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
 162 {
 163     BN_clear_free(group->field);
 164     BN_clear_free(group->a);
 165     BN_clear_free(group->b);
 166 }
 167
 168 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
 169 {
 170     if (!BN_copy(dest->field, src->field))
 171         return 0;
 172     if (!BN_copy(dest->a, src->a))
 173         return 0;
 174     if (!BN_copy(dest->b, src->b))
 175         return 0;
 176
 177     dest->a_is_minus3 = src->a_is_minus3;
 178
 179     return 1;
 180 }
 181
 182 int ec_GFp_simple_group_set_curve(EC_GROUP *group,
 183                                   const BIGNUM *p, const BIGNUM *a,
 184                                   const BIGNUM *b, BN_CTX *ctx)
 185 {
 186     int ret = 0;
 187     BN_CTX *new_ctx = NULL;
 188     BIGNUM *tmp_a;
 189
 190     /* p must be a prime > 3 */
 191     if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) {
 192         ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD);
 193         return 0;
 194     }
 195
 196     if (ctx == NULL) {
 197         ctx = new_ctx = BN_CTX_new();
 198         if (ctx == NULL)
 199             return 0;
 200     }
 201
 202     BN_CTX_start(ctx);
 203     tmp_a = BN_CTX_get(ctx);
 204     if (tmp_a == NULL)
 205         goto err;
 206
 207     /* group->field */
 208     if (!BN_copy(group->field, p))
 209         goto err;
 210     BN_set_negative(group->field, 0);
 211
 212     /* group->a */
 213     if (!BN_nnmod(tmp_a, a, p, ctx))
 214         goto err;
 215     if (group->meth->field_encode) {
 216         if (!group->meth->field_encode(group, group->a, tmp_a, ctx))
 217             goto err;
 218     } else if (!BN_copy(group->a, tmp_a))
 219         goto err;
 220
 221     /* group->b */
 222     if (!BN_nnmod(group->b, b, p, ctx))
 223         goto err;
 224     if (group->meth->field_encode)
 225         if (!group->meth->field_encode(group, group->b, group->b, ctx))
 226             goto err;
 227
 228     /* group->a_is_minus3 */
 229     if (!BN_add_word(tmp_a, 3))
 230         goto err;
 231     group->a_is_minus3 = (0 == BN_cmp(tmp_a, group->field));
 232
 233     ret = 1;
 234
 235  err:
 236     BN_CTX_end(ctx);
 237     BN_CTX_free(new_ctx);
 238     return ret;
 239 }
 240
 241 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
 242                                   BIGNUM *b, BN_CTX *ctx)
 243 {
 244     int ret = 0;
 245     BN_CTX *new_ctx = NULL;
 246
 247     if (p != NULL) {
 248         if (!BN_copy(p, group->field))
 249             return 0;
 250     }
 251
 252     if (a != NULL || b != NULL) {
 253         if (group->meth->field_decode) {
 254             if (ctx == NULL) {
 255                 ctx = new_ctx = BN_CTX_new();
 256                 if (ctx == NULL)
 257                     return 0;
 258             }
 259             if (a != NULL) {
 260                 if (!group->meth->field_decode(group, a, group->a, ctx))
 261                     goto err;
 262             }
 263             if (b != NULL) {
 264                 if (!group->meth->field_decode(group, b, group->b, ctx))
 265                     goto err;
 266             }
 267         } else {
 268             if (a != NULL) {
 269                 if (!BN_copy(a, group->a))
 270                     goto err;
 271             }
 272             if (b != NULL) {
 273                 if (!BN_copy(b, group->b))
 274                     goto err;
 275             }
 276         }
 277     }
 278
 279     ret = 1;
 280
 281  err:
 282     BN_CTX_free(new_ctx);
 283     return ret;
 284 }
 285
 286 int ec_GFp_simple_group_get_degree(const EC_GROUP *group)
 287 {
 288     return BN_num_bits(group->field);
 289 }
 290
 291 int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
 292 {
 293     int ret = 0;
 294     BIGNUM *a, *b, *order, *tmp_1, *tmp_2;
 295     const BIGNUM *p = group->field;
 296     BN_CTX *new_ctx = NULL;
 297
 298     if (ctx == NULL) {
 299         ctx = new_ctx = BN_CTX_new();
 300         if (ctx == NULL) {
 301             ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT,
 302                   ERR_R_MALLOC_FAILURE);
 303             goto err;
 304         }
 305     }
 306     BN_CTX_start(ctx);
 307     a = BN_CTX_get(ctx);
 308     b = BN_CTX_get(ctx);
 309     tmp_1 = BN_CTX_get(ctx);
 310     tmp_2 = BN_CTX_get(ctx);
 311     order = BN_CTX_get(ctx);
 312     if (order == NULL)
 313         goto err;
 314
 315     if (group->meth->field_decode) {
 316         if (!group->meth->field_decode(group, a, group->a, ctx))
 317             goto err;
 318         if (!group->meth->field_decode(group, b, group->b, ctx))
 319             goto err;
 320     } else {
 321         if (!BN_copy(a, group->a))
 322             goto err;
 323         if (!BN_copy(b, group->b))
 324             goto err;
 325     }
 326
 327     /*-
 328      * check the discriminant:
 329      * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
 330      * 0 =< a, b < p
 331      */
 332     if (BN_is_zero(a)) {
 333         if (BN_is_zero(b))
 334             goto err;
 335     } else if (!BN_is_zero(b)) {
 336         if (!BN_mod_sqr(tmp_1, a, p, ctx))
 337             goto err;
 338         if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx))
 339             goto err;
 340         if (!BN_lshift(tmp_1, tmp_2, 2))
 341             goto err;
 342         /* tmp_1 = 4*a^3 */
 343
 344         if (!BN_mod_sqr(tmp_2, b, p, ctx))
 345             goto err;
 346         if (!BN_mul_word(tmp_2, 27))
 347             goto err;
 348         /* tmp_2 = 27*b^2 */
 349
 350         if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx))
 351             goto err;
 352         if (BN_is_zero(a))
 353             goto err;
 354     }
 355     ret = 1;
 356
 357  err:
 358     if (ctx != NULL)
 359         BN_CTX_end(ctx);
 360     BN_CTX_free(new_ctx);
 361     return ret;
 362 }
 363
 364 int ec_GFp_simple_point_init(EC_POINT *point)
 365 {
 366     point->X = BN_new();
 367     point->Y = BN_new();
 368     point->Z = BN_new();
 369     point->Z_is_one = 0;
 370
 371     if (point->X == NULL || point->Y == NULL || point->Z == NULL) {
 372         BN_free(point->X);
 373         BN_free(point->Y);
 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     BN_CTX_free(new_ctx);
 473     return ret;
 474 }
 475
 476 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group,
 477                                                   const EC_POINT *point,
 478                                                   BIGNUM *x, BIGNUM *y,
 479                                                   BIGNUM *z, BN_CTX *ctx)
 480 {
 481     BN_CTX *new_ctx = NULL;
 482     int ret = 0;
 483
 484     if (group->meth->field_decode != 0) {
 485         if (ctx == NULL) {
 486             ctx = new_ctx = BN_CTX_new();
 487             if (ctx == NULL)
 488                 return 0;
 489         }
 490
 491         if (x != NULL) {
 492             if (!group->meth->field_decode(group, x, point->X, ctx))
 493                 goto err;
 494         }
 495         if (y != NULL) {
 496             if (!group->meth->field_decode(group, y, point->Y, ctx))
 497                 goto err;
 498         }
 499         if (z != NULL) {
 500             if (!group->meth->field_decode(group, z, point->Z, ctx))
 501                 goto err;
 502         }
 503     } else {
 504         if (x != NULL) {
 505             if (!BN_copy(x, point->X))
 506                 goto err;
 507         }
 508         if (y != NULL) {
 509             if (!BN_copy(y, point->Y))
 510                 goto err;
 511         }
 512         if (z != NULL) {
 513             if (!BN_copy(z, point->Z))
 514                 goto err;
 515         }
 516     }
 517
 518     ret = 1;
 519
 520  err:
 521     BN_CTX_free(new_ctx);
 522     return ret;
 523 }
 524
 525 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group,
 526                                                EC_POINT *point,
 527                                                const BIGNUM *x,
 528                                                const BIGNUM *y, BN_CTX *ctx)
 529 {
 530     if (x == NULL || y == NULL) {
 531         /*
 532          * unlike for projective coordinates, we do not tolerate this
 533          */
 534         ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES,
 535               ERR_R_PASSED_NULL_PARAMETER);
 536         return 0;
 537     }
 538
 539     return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y,
 540                                                     BN_value_one(), ctx);
 541 }
 542
 543 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
 544                                                const EC_POINT *point,
 545                                                BIGNUM *x, BIGNUM *y,
 546                                                BN_CTX *ctx)
 547 {
 548     BN_CTX *new_ctx = NULL;
 549     BIGNUM *Z, *Z_1, *Z_2, *Z_3;
 550     const BIGNUM *Z_;
 551     int ret = 0;
 552
 553     if (EC_POINT_is_at_infinity(group, point)) {
 554         ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
 555               EC_R_POINT_AT_INFINITY);
 556         return 0;
 557     }
 558
 559     if (ctx == NULL) {
 560         ctx = new_ctx = BN_CTX_new();
 561         if (ctx == NULL)
 562             return 0;
 563     }
 564
 565     BN_CTX_start(ctx);
 566     Z = BN_CTX_get(ctx);
 567     Z_1 = BN_CTX_get(ctx);
 568     Z_2 = BN_CTX_get(ctx);
 569     Z_3 = BN_CTX_get(ctx);
 570     if (Z_3 == NULL)
 571         goto err;
 572
 573     /* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
 574
 575     if (group->meth->field_decode) {
 576         if (!group->meth->field_decode(group, Z, point->Z, ctx))
 577             goto err;
 578         Z_ = Z;
 579     } else {
 580         Z_ = point->Z;
 581     }
 582
 583     if (BN_is_one(Z_)) {
 584         if (group->meth->field_decode) {
 585             if (x != NULL) {
 586                 if (!group->meth->field_decode(group, x, point->X, ctx))
 587                     goto err;
 588             }
 589             if (y != NULL) {
 590                 if (!group->meth->field_decode(group, y, point->Y, ctx))
 591                     goto err;
 592             }
 593         } else {
 594             if (x != NULL) {
 595                 if (!BN_copy(x, point->X))
 596                     goto err;
 597             }
 598             if (y != NULL) {
 599                 if (!BN_copy(y, point->Y))
 600                     goto err;
 601             }
 602         }
 603     } else {
 604         if (!BN_mod_inverse(Z_1, Z_, group->field, ctx)) {
 605             ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
 606                   ERR_R_BN_LIB);
 607             goto err;
 608         }
 609
 610         if (group->meth->field_encode == 0) {
 611             /* field_sqr works on standard representation */
 612             if (!group->meth->field_sqr(group, Z_2, Z_1, ctx))
 613                 goto err;
 614         } else {
 615             if (!BN_mod_sqr(Z_2, Z_1, group->field, ctx))
 616                 goto err;
 617         }
 618
 619         if (x != NULL) {
 620             /*
 621              * in the Montgomery case, field_mul will cancel out Montgomery
 622              * factor in X:
 623              */
 624             if (!group->meth->field_mul(group, x, point->X, Z_2, ctx))
 625                 goto err;
 626         }
 627
 628         if (y != NULL) {
 629             if (group->meth->field_encode == 0) {
 630                 /*
 631                  * field_mul works on standard representation
 632                  */
 633                 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx))
 634                     goto err;
 635             } else {
 636                 if (!BN_mod_mul(Z_3, Z_2, Z_1, group->field, ctx))
 637                     goto err;
 638             }
 639
 640             /*
 641              * in the Montgomery case, field_mul will cancel out Montgomery
 642              * factor in Y:
 643              */
 644             if (!group->meth->field_mul(group, y, point->Y, Z_3, ctx))
 645                 goto err;
 646         }
 647     }
 648
 649     ret = 1;
 650
 651  err:
 652     BN_CTX_end(ctx);
 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     BN_CTX_free(new_ctx);
 840     return ret;
 841 }
 842
 843 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
 844                       BN_CTX *ctx)
 845 {
 846     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
 847                       const BIGNUM *, BN_CTX *);
 848     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 849     const BIGNUM *p;
 850     BN_CTX *new_ctx = NULL;
 851     BIGNUM *n0, *n1, *n2, *n3;
 852     int ret = 0;
 853
 854     if (EC_POINT_is_at_infinity(group, a)) {
 855         BN_zero(r->Z);
 856         r->Z_is_one = 0;
 857         return 1;
 858     }
 859
 860     field_mul = group->meth->field_mul;
 861     field_sqr = group->meth->field_sqr;
 862     p = group->field;
 863
 864     if (ctx == NULL) {
 865         ctx = new_ctx = BN_CTX_new();
 866         if (ctx == NULL)
 867             return 0;
 868     }
 869
 870     BN_CTX_start(ctx);
 871     n0 = BN_CTX_get(ctx);
 872     n1 = BN_CTX_get(ctx);
 873     n2 = BN_CTX_get(ctx);
 874     n3 = BN_CTX_get(ctx);
 875     if (n3 == NULL)
 876         goto err;
 877
 878     /*
 879      * Note that in this function we must not read components of 'a' once we
 880      * have written the corresponding components of 'r'. ('r' might the same
 881      * as 'a'.)
 882      */
 883
 884     /* n1 */
 885     if (a->Z_is_one) {
 886         if (!field_sqr(group, n0, a->X, ctx))
 887             goto err;
 888         if (!BN_mod_lshift1_quick(n1, n0, p))
 889             goto err;
 890         if (!BN_mod_add_quick(n0, n0, n1, p))
 891             goto err;
 892         if (!BN_mod_add_quick(n1, n0, group->a, p))
 893             goto err;
 894         /* n1 = 3 * X_a^2 + a_curve */
 895     } else if (group->a_is_minus3) {
 896         if (!field_sqr(group, n1, a->Z, ctx))
 897             goto err;
 898         if (!BN_mod_add_quick(n0, a->X, n1, p))
 899             goto err;
 900         if (!BN_mod_sub_quick(n2, a->X, n1, p))
 901             goto err;
 902         if (!field_mul(group, n1, n0, n2, ctx))
 903             goto err;
 904         if (!BN_mod_lshift1_quick(n0, n1, p))
 905             goto err;
 906         if (!BN_mod_add_quick(n1, n0, n1, p))
 907             goto err;
 908         /*-
 909          * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
 910          *    = 3 * X_a^2 - 3 * Z_a^4
 911          */
 912     } else {
 913         if (!field_sqr(group, n0, a->X, ctx))
 914             goto err;
 915         if (!BN_mod_lshift1_quick(n1, n0, p))
 916             goto err;
 917         if (!BN_mod_add_quick(n0, n0, n1, p))
 918             goto err;
 919         if (!field_sqr(group, n1, a->Z, ctx))
 920             goto err;
 921         if (!field_sqr(group, n1, n1, ctx))
 922             goto err;
 923         if (!field_mul(group, n1, n1, group->a, ctx))
 924             goto err;
 925         if (!BN_mod_add_quick(n1, n1, n0, p))
 926             goto err;
 927         /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
 928     }
 929
 930     /* Z_r */
 931     if (a->Z_is_one) {
 932         if (!BN_copy(n0, a->Y))
 933             goto err;
 934     } else {
 935         if (!field_mul(group, n0, a->Y, a->Z, ctx))
 936             goto err;
 937     }
 938     if (!BN_mod_lshift1_quick(r->Z, n0, p))
 939         goto err;
 940     r->Z_is_one = 0;
 941     /* Z_r = 2 * Y_a * Z_a */
 942
 943     /* n2 */
 944     if (!field_sqr(group, n3, a->Y, ctx))
 945         goto err;
 946     if (!field_mul(group, n2, a->X, n3, ctx))
 947         goto err;
 948     if (!BN_mod_lshift_quick(n2, n2, 2, p))
 949         goto err;
 950     /* n2 = 4 * X_a * Y_a^2 */
 951
 952     /* X_r */
 953     if (!BN_mod_lshift1_quick(n0, n2, p))
 954         goto err;
 955     if (!field_sqr(group, r->X, n1, ctx))
 956         goto err;
 957     if (!BN_mod_sub_quick(r->X, r->X, n0, p))
 958         goto err;
 959     /* X_r = n1^2 - 2 * n2 */
 960
 961     /* n3 */
 962     if (!field_sqr(group, n0, n3, ctx))
 963         goto err;
 964     if (!BN_mod_lshift_quick(n3, n0, 3, p))
 965         goto err;
 966     /* n3 = 8 * Y_a^4 */
 967
 968     /* Y_r */
 969     if (!BN_mod_sub_quick(n0, n2, r->X, p))
 970         goto err;
 971     if (!field_mul(group, n0, n1, n0, ctx))
 972         goto err;
 973     if (!BN_mod_sub_quick(r->Y, n0, n3, p))
 974         goto err;
 975     /* Y_r = n1 * (n2 - X_r) - n3 */
 976
 977     ret = 1;
 978
 979  err:
 980     BN_CTX_end(ctx);
 981     BN_CTX_free(new_ctx);
 982     return ret;
 983 }
 984
 985 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
 986 {
 987     if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
 988         /* point is its own inverse */
 989         return 1;
 990
 991     return BN_usub(point->Y, group->field, point->Y);
 992 }
 993
 994 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
 995 {
 996     return BN_is_zero(point->Z);
 997 }
 998
 999 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
1000                               BN_CTX *ctx)
1001 {
1002     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
1003                       const BIGNUM *, BN_CTX *);
1004     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1005     const BIGNUM *p;
1006     BN_CTX *new_ctx = NULL;
1007     BIGNUM *rh, *tmp, *Z4, *Z6;
1008     int ret = -1;
1009
1010     if (EC_POINT_is_at_infinity(group, point))
1011         return 1;
1012
1013     field_mul = group->meth->field_mul;
1014     field_sqr = group->meth->field_sqr;
1015     p = group->field;
1016
1017     if (ctx == NULL) {
1018         ctx = new_ctx = BN_CTX_new();
1019         if (ctx == NULL)
1020             return -1;
1021     }
1022
1023     BN_CTX_start(ctx);
1024     rh = BN_CTX_get(ctx);
1025     tmp = BN_CTX_get(ctx);
1026     Z4 = BN_CTX_get(ctx);
1027     Z6 = BN_CTX_get(ctx);
1028     if (Z6 == NULL)
1029         goto err;
1030
1031     /*-
1032      * We have a curve defined by a Weierstrass equation
1033      *      y^2 = x^3 + a*x + b.
1034      * The point to consider is given in Jacobian projective coordinates
1035      * where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
1036      * Substituting this and multiplying by  Z^6  transforms the above equation into
1037      *      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
1038      * To test this, we add up the right-hand side in 'rh'.
1039      */
1040
1041     /* rh := X^2 */
1042     if (!field_sqr(group, rh, point->X, ctx))
1043         goto err;
1044
1045     if (!point->Z_is_one) {
1046         if (!field_sqr(group, tmp, point->Z, ctx))
1047             goto err;
1048         if (!field_sqr(group, Z4, tmp, ctx))
1049             goto err;
1050         if (!field_mul(group, Z6, Z4, tmp, ctx))
1051             goto err;
1052
1053         /* rh := (rh + a*Z^4)*X */
1054         if (group->a_is_minus3) {
1055             if (!BN_mod_lshift1_quick(tmp, Z4, p))
1056                 goto err;
1057             if (!BN_mod_add_quick(tmp, tmp, Z4, p))
1058                 goto err;
1059             if (!BN_mod_sub_quick(rh, rh, tmp, p))
1060                 goto err;
1061             if (!field_mul(group, rh, rh, point->X, ctx))
1062                 goto err;
1063         } else {
1064             if (!field_mul(group, tmp, Z4, group->a, ctx))
1065                 goto err;
1066             if (!BN_mod_add_quick(rh, rh, tmp, p))
1067                 goto err;
1068             if (!field_mul(group, rh, rh, point->X, ctx))
1069                 goto err;
1070         }
1071
1072         /* rh := rh + b*Z^6 */
1073         if (!field_mul(group, tmp, group->b, Z6, ctx))
1074             goto err;
1075         if (!BN_mod_add_quick(rh, rh, tmp, p))
1076             goto err;
1077     } else {
1078         /* point->Z_is_one */
1079
1080         /* rh := (rh + a)*X */
1081         if (!BN_mod_add_quick(rh, rh, group->a, p))
1082             goto err;
1083         if (!field_mul(group, rh, rh, point->X, ctx))
1084             goto err;
1085         /* rh := rh + b */
1086         if (!BN_mod_add_quick(rh, rh, group->b, p))
1087             goto err;
1088     }
1089
1090     /* 'lh' := Y^2 */
1091     if (!field_sqr(group, tmp, point->Y, ctx))
1092         goto err;
1093
1094     ret = (0 == BN_ucmp(tmp, rh));
1095
1096  err:
1097     BN_CTX_end(ctx);
1098     BN_CTX_free(new_ctx);
1099     return ret;
1100 }
1101
1102 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
1103                       const EC_POINT *b, BN_CTX *ctx)
1104 {
1105     /*-
1106      * return values:
1107      *  -1   error
1108      *   0   equal (in affine coordinates)
1109      *   1   not equal
1110      */
1111
1112     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
1113                       const BIGNUM *, BN_CTX *);
1114     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1115     BN_CTX *new_ctx = NULL;
1116     BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1117     const BIGNUM *tmp1_, *tmp2_;
1118     int ret = -1;
1119
1120     if (EC_POINT_is_at_infinity(group, a)) {
1121         return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
1122     }
1123
1124     if (EC_POINT_is_at_infinity(group, b))
1125         return 1;
1126
1127     if (a->Z_is_one && b->Z_is_one) {
1128         return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
1129     }
1130
1131     field_mul = group->meth->field_mul;
1132     field_sqr = group->meth->field_sqr;
1133
1134     if (ctx == NULL) {
1135         ctx = new_ctx = BN_CTX_new();
1136         if (ctx == NULL)
1137             return -1;
1138     }
1139
1140     BN_CTX_start(ctx);
1141     tmp1 = BN_CTX_get(ctx);
1142     tmp2 = BN_CTX_get(ctx);
1143     Za23 = BN_CTX_get(ctx);
1144     Zb23 = BN_CTX_get(ctx);
1145     if (Zb23 == NULL)
1146         goto end;
1147
1148     /*-
1149      * We have to decide whether
1150      *     (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1151      * or equivalently, whether
1152      *     (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1153      */
1154
1155     if (!b->Z_is_one) {
1156         if (!field_sqr(group, Zb23, b->Z, ctx))
1157             goto end;
1158         if (!field_mul(group, tmp1, a->X, Zb23, ctx))
1159             goto end;
1160         tmp1_ = tmp1;
1161     } else
1162         tmp1_ = a->X;
1163     if (!a->Z_is_one) {
1164         if (!field_sqr(group, Za23, a->Z, ctx))
1165             goto end;
1166         if (!field_mul(group, tmp2, b->X, Za23, ctx))
1167             goto end;
1168         tmp2_ = tmp2;
1169     } else
1170         tmp2_ = b->X;
1171
1172     /* compare  X_a*Z_b^2  with  X_b*Z_a^2 */
1173     if (BN_cmp(tmp1_, tmp2_) != 0) {
1174         ret = 1;                /* points differ */
1175         goto end;
1176     }
1177
1178     if (!b->Z_is_one) {
1179         if (!field_mul(group, Zb23, Zb23, b->Z, ctx))
1180             goto end;
1181         if (!field_mul(group, tmp1, a->Y, Zb23, ctx))
1182             goto end;
1183         /* tmp1_ = tmp1 */
1184     } else
1185         tmp1_ = a->Y;
1186     if (!a->Z_is_one) {
1187         if (!field_mul(group, Za23, Za23, a->Z, ctx))
1188             goto end;
1189         if (!field_mul(group, tmp2, b->Y, Za23, ctx))
1190             goto end;
1191         /* tmp2_ = tmp2 */
1192     } else
1193         tmp2_ = b->Y;
1194
1195     /* compare  Y_a*Z_b^3  with  Y_b*Z_a^3 */
1196     if (BN_cmp(tmp1_, tmp2_) != 0) {
1197         ret = 1;                /* points differ */
1198         goto end;
1199     }
1200
1201     /* points are equal */
1202     ret = 0;
1203
1204  end:
1205     BN_CTX_end(ctx);
1206     BN_CTX_free(new_ctx);
1207     return ret;
1208 }
1209
1210 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
1211                               BN_CTX *ctx)
1212 {
1213     BN_CTX *new_ctx = NULL;
1214     BIGNUM *x, *y;
1215     int ret = 0;
1216
1217     if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1218         return 1;
1219
1220     if (ctx == NULL) {
1221         ctx = new_ctx = BN_CTX_new();
1222         if (ctx == NULL)
1223             return 0;
1224     }
1225
1226     BN_CTX_start(ctx);
1227     x = BN_CTX_get(ctx);
1228     y = BN_CTX_get(ctx);
1229     if (y == NULL)
1230         goto err;
1231
1232     if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
1233         goto err;
1234     if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
1235         goto err;
1236     if (!point->Z_is_one) {
1237         ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1238         goto err;
1239     }
1240
1241     ret = 1;
1242
1243  err:
1244     BN_CTX_end(ctx);
1245     BN_CTX_free(new_ctx);
1246     return ret;
1247 }
1248
1249 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num,
1250                                      EC_POINT *points[], BN_CTX *ctx)
1251 {
1252     BN_CTX *new_ctx = NULL;
1253     BIGNUM *tmp, *tmp_Z;
1254     BIGNUM **prod_Z = NULL;
1255     size_t i;
1256     int ret = 0;
1257
1258     if (num == 0)
1259         return 1;
1260
1261     if (ctx == NULL) {
1262         ctx = new_ctx = BN_CTX_new();
1263         if (ctx == NULL)
1264             return 0;
1265     }
1266
1267     BN_CTX_start(ctx);
1268     tmp = BN_CTX_get(ctx);
1269     tmp_Z = BN_CTX_get(ctx);
1270     if (tmp == NULL || tmp_Z == NULL)
1271         goto err;
1272
1273     prod_Z = OPENSSL_malloc(num * sizeof prod_Z[0]);
1274     if (prod_Z == NULL)
1275         goto err;
1276     for (i = 0; i < num; i++) {
1277         prod_Z[i] = BN_new();
1278         if (prod_Z[i] == NULL)
1279             goto err;
1280     }
1281
1282     /*
1283      * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z,
1284      * skipping any zero-valued inputs (pretend that they're 1).
1285      */
1286
1287     if (!BN_is_zero(points[0]->Z)) {
1288         if (!BN_copy(prod_Z[0], points[0]->Z))
1289             goto err;
1290     } else {
1291         if (group->meth->field_set_to_one != 0) {
1292             if (!group->meth->field_set_to_one(group, prod_Z[0], ctx))
1293                 goto err;
1294         } else {
1295             if (!BN_one(prod_Z[0]))
1296                 goto err;
1297         }
1298     }
1299
1300     for (i = 1; i < num; i++) {
1301         if (!BN_is_zero(points[i]->Z)) {
1302             if (!group->
1303                 meth->field_mul(group, prod_Z[i], prod_Z[i - 1], points[i]->Z,
1304                                 ctx))
1305                 goto err;
1306         } else {
1307             if (!BN_copy(prod_Z[i], prod_Z[i - 1]))
1308                 goto err;
1309         }
1310     }
1311
1312     /*
1313      * Now use a single explicit inversion to replace every non-zero
1314      * points[i]->Z by its inverse.
1315      */
1316
1317     if (!BN_mod_inverse(tmp, prod_Z[num - 1], group->field, ctx)) {
1318         ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1319         goto err;
1320     }
1321     if (group->meth->field_encode != 0) {
1322         /*
1323          * In the Montgomery case, we just turned R*H (representing H) into
1324          * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to
1325          * multiply by the Montgomery factor twice.
1326          */
1327         if (!group->meth->field_encode(group, tmp, tmp, ctx))
1328             goto err;
1329         if (!group->meth->field_encode(group, tmp, tmp, ctx))
1330             goto err;
1331     }
1332
1333     for (i = num - 1; i > 0; --i) {
1334         /*
1335          * Loop invariant: tmp is the product of the inverses of points[0]->Z
1336          * .. points[i]->Z (zero-valued inputs skipped).
1337          */
1338         if (!BN_is_zero(points[i]->Z)) {
1339             /*
1340              * Set tmp_Z to the inverse of points[i]->Z (as product of Z
1341              * inverses 0 .. i, Z values 0 .. i - 1).
1342              */
1343             if (!group->
1344                 meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx))
1345                 goto err;
1346             /*
1347              * Update tmp to satisfy the loop invariant for i - 1.
1348              */
1349             if (!group->meth->field_mul(group, tmp, tmp, points[i]->Z, ctx))
1350                 goto err;
1351             /* Replace points[i]->Z by its inverse. */
1352             if (!BN_copy(points[i]->Z, tmp_Z))
1353                 goto err;
1354         }
1355     }
1356
1357     if (!BN_is_zero(points[0]->Z)) {
1358         /* Replace points[0]->Z by its inverse. */
1359         if (!BN_copy(points[0]->Z, tmp))
1360             goto err;
1361     }
1362
1363     /* Finally, fix up the X and Y coordinates for all points. */
1364
1365     for (i = 0; i < num; i++) {
1366         EC_POINT *p = points[i];
1367
1368         if (!BN_is_zero(p->Z)) {
1369             /* turn  (X, Y, 1/Z)  into  (X/Z^2, Y/Z^3, 1) */
1370
1371             if (!group->meth->field_sqr(group, tmp, p->Z, ctx))
1372                 goto err;
1373             if (!group->meth->field_mul(group, p->X, p->X, tmp, ctx))
1374                 goto err;
1375
1376             if (!group->meth->field_mul(group, tmp, tmp, p->Z, ctx))
1377                 goto err;
1378             if (!group->meth->field_mul(group, p->Y, p->Y, tmp, ctx))
1379                 goto err;
1380
1381             if (group->meth->field_set_to_one != 0) {
1382                 if (!group->meth->field_set_to_one(group, p->Z, ctx))
1383                     goto err;
1384             } else {
1385                 if (!BN_one(p->Z))
1386                     goto err;
1387             }
1388             p->Z_is_one = 1;
1389         }
1390     }
1391
1392     ret = 1;
1393
1394  err:
1395     BN_CTX_end(ctx);
1396     BN_CTX_free(new_ctx);
1397     if (prod_Z != NULL) {
1398         for (i = 0; i < num; i++) {
1399             if (prod_Z[i] == NULL)
1400                 break;
1401             BN_clear_free(prod_Z[i]);
1402         }
1403         OPENSSL_free(prod_Z);
1404     }
1405     return ret;
1406 }
1407
1408 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1409                             const BIGNUM *b, BN_CTX *ctx)
1410 {
1411     return BN_mod_mul(r, a, b, group->field, ctx);
1412 }
1413
1414 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1415                             BN_CTX *ctx)
1416 {
1417     return BN_mod_sqr(r, a, group->field, ctx);
1418 }