crypto/ec/ecp_smpl.c

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