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