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