crypto/openssl/crypto/ec/ecp_smpl.c

   1 /* crypto/ec/ecp_smpl.c */
   2 /*
   3  * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
   4  * for the OpenSSL project. Includes code written by Bodo Moeller for the
   5  * OpenSSL project.
   6  */
   7 /* ====================================================================
   8  * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  *
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  *
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in
  19  *    the documentation and/or other materials provided with the
  20  *    distribution.
  21  *
  22  * 3. All advertising materials mentioning features or use of this
  23  *    software must display the following acknowledgment:
  24  *    "This product includes software developed by the OpenSSL Project
  25  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  26  *
  27  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  28  *    endorse or promote products derived from this software without
  29  *    prior written permission. For written permission, please contact
  30  *    openssl-core@openssl.org.
  31  *
  32  * 5. Products derived from this software may not be called "OpenSSL"
  33  *    nor may "OpenSSL" appear in their names without prior written
  34  *    permission of the OpenSSL Project.
  35  *
  36  * 6. Redistributions of any form whatsoever must retain the following
  37  *    acknowledgment:
  38  *    "This product includes software developed by the OpenSSL Project
  39  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  40  *
  41  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  42  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  44  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  45  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  46  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  47  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  48  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  49  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  50  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  51  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  52  * OF THE POSSIBILITY OF SUCH DAMAGE.
  53  * ====================================================================
  54  *
  55  * This product includes cryptographic software written by Eric Young
  56  * (eay@cryptsoft.com).  This product includes software written by Tim
  57  * Hudson (tjh@cryptsoft.com).
  58  *
  59  */
  60 /* ====================================================================
  61  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  62  * Portions of this software developed by SUN MICROSYSTEMS, INC.,
  63  * and contributed to the OpenSSL project.
  64  */
  65
  66 #include <openssl/err.h>
  67 #include <openssl/symhacks.h>
  68
  69 #include "ec_lcl.h"
  70
  71 const EC_METHOD *EC_GFp_simple_method(void)
  72 {
  73     static const EC_METHOD ret = {
  74         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         ec_GFp_simple_set_compressed_coordinates,
  93         ec_GFp_simple_point2oct,
  94         ec_GFp_simple_oct2point,
  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
 114     return &ret;
 115 }
 116
 117 /*
 118  * Most method functions in this file are designed to work with
 119  * non-trivial representations of field elements if necessary
 120  * (see ecp_mont.c): while standard modular addition and subtraction
 121  * are used, the field_mul and field_sqr methods will be used for
 122  * multiplication, and field_encode and field_decode (if defined)
 123  * will be used for converting between representations.
 124  *
 125  * Functions ec_GFp_simple_points_make_affine() and
 126  * ec_GFp_simple_point_get_affine_coordinates() specifically assume
 127  * that if a non-trivial representation is used, it is a Montgomery
 128  * representation (i.e. 'encoding' means multiplying by some factor R).
 129  */
 130
 131 int ec_GFp_simple_group_init(EC_GROUP *group)
 132 {
 133     BN_init(&group->field);
 134     BN_init(&group->a);
 135     BN_init(&group->b);
 136     group->a_is_minus3 = 0;
 137     return 1;
 138 }
 139
 140 void ec_GFp_simple_group_finish(EC_GROUP *group)
 141 {
 142     BN_free(&group->field);
 143     BN_free(&group->a);
 144     BN_free(&group->b);
 145 }
 146
 147 void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
 148 {
 149     BN_clear_free(&group->field);
 150     BN_clear_free(&group->a);
 151     BN_clear_free(&group->b);
 152 }
 153
 154 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
 155 {
 156     if (!BN_copy(&dest->field, &src->field))
 157         return 0;
 158     if (!BN_copy(&dest->a, &src->a))
 159         return 0;
 160     if (!BN_copy(&dest->b, &src->b))
 161         return 0;
 162
 163     dest->a_is_minus3 = src->a_is_minus3;
 164
 165     return 1;
 166 }
 167
 168 int ec_GFp_simple_group_set_curve(EC_GROUP *group,
 169                                   const BIGNUM *p, const BIGNUM *a,
 170                                   const BIGNUM *b, BN_CTX *ctx)
 171 {
 172     int ret = 0;
 173     BN_CTX *new_ctx = NULL;
 174     BIGNUM *tmp_a;
 175
 176     /* p must be a prime > 3 */
 177     if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) {
 178         ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD);
 179         return 0;
 180     }
 181
 182     if (ctx == NULL) {
 183         ctx = new_ctx = BN_CTX_new();
 184         if (ctx == NULL)
 185             return 0;
 186     }
 187
 188     BN_CTX_start(ctx);
 189     tmp_a = BN_CTX_get(ctx);
 190     if (tmp_a == NULL)
 191         goto err;
 192
 193     /* group->field */
 194     if (!BN_copy(&group->field, p))
 195         goto err;
 196     BN_set_negative(&group->field, 0);
 197
 198     /* group->a */
 199     if (!BN_nnmod(tmp_a, a, p, ctx))
 200         goto err;
 201     if (group->meth->field_encode) {
 202         if (!group->meth->field_encode(group, &group->a, tmp_a, ctx))
 203             goto err;
 204     } else if (!BN_copy(&group->a, tmp_a))
 205         goto err;
 206
 207     /* group->b */
 208     if (!BN_nnmod(&group->b, b, p, ctx))
 209         goto err;
 210     if (group->meth->field_encode)
 211         if (!group->meth->field_encode(group, &group->b, &group->b, ctx))
 212             goto err;
 213
 214     /* group->a_is_minus3 */
 215     if (!BN_add_word(tmp_a, 3))
 216         goto err;
 217     group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
 218
 219     ret = 1;
 220
 221  err:
 222     BN_CTX_end(ctx);
 223     if (new_ctx != NULL)
 224         BN_CTX_free(new_ctx);
 225     return ret;
 226 }
 227
 228 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
 229                                   BIGNUM *b, BN_CTX *ctx)
 230 {
 231     int ret = 0;
 232     BN_CTX *new_ctx = NULL;
 233
 234     if (p != NULL) {
 235         if (!BN_copy(p, &group->field))
 236             return 0;
 237     }
 238
 239     if (a != NULL || b != NULL) {
 240         if (group->meth->field_decode) {
 241             if (ctx == NULL) {
 242                 ctx = new_ctx = BN_CTX_new();
 243                 if (ctx == NULL)
 244                     return 0;
 245             }
 246             if (a != NULL) {
 247                 if (!group->meth->field_decode(group, a, &group->a, ctx))
 248                     goto err;
 249             }
 250             if (b != NULL) {
 251                 if (!group->meth->field_decode(group, b, &group->b, ctx))
 252                     goto err;
 253             }
 254         } else {
 255             if (a != NULL) {
 256                 if (!BN_copy(a, &group->a))
 257                     goto err;
 258             }
 259             if (b != NULL) {
 260                 if (!BN_copy(b, &group->b))
 261                     goto err;
 262             }
 263         }
 264     }
 265
 266     ret = 1;
 267
 268  err:
 269     if (new_ctx)
 270         BN_CTX_free(new_ctx);
 271     return ret;
 272 }
 273
 274 int ec_GFp_simple_group_get_degree(const EC_GROUP *group)
 275 {
 276     return BN_num_bits(&group->field);
 277 }
 278
 279 int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
 280 {
 281     int ret = 0;
 282     BIGNUM *a, *b, *order, *tmp_1, *tmp_2;
 283     const BIGNUM *p = &group->field;
 284     BN_CTX *new_ctx = NULL;
 285
 286     if (ctx == NULL) {
 287         ctx = new_ctx = BN_CTX_new();
 288         if (ctx == NULL) {
 289             ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT,
 290                   ERR_R_MALLOC_FAILURE);
 291             goto err;
 292         }
 293     }
 294     BN_CTX_start(ctx);
 295     a = BN_CTX_get(ctx);
 296     b = BN_CTX_get(ctx);
 297     tmp_1 = BN_CTX_get(ctx);
 298     tmp_2 = BN_CTX_get(ctx);
 299     order = BN_CTX_get(ctx);
 300     if (order == NULL)
 301         goto err;
 302
 303     if (group->meth->field_decode) {
 304         if (!group->meth->field_decode(group, a, &group->a, ctx))
 305             goto err;
 306         if (!group->meth->field_decode(group, b, &group->b, ctx))
 307             goto err;
 308     } else {
 309         if (!BN_copy(a, &group->a))
 310             goto err;
 311         if (!BN_copy(b, &group->b))
 312             goto err;
 313     }
 314
 315     /*-
 316      * check the discriminant:
 317      * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p)
 318      * 0 =< a, b < p
 319      */
 320     if (BN_is_zero(a)) {
 321         if (BN_is_zero(b))
 322             goto err;
 323     } else if (!BN_is_zero(b)) {
 324         if (!BN_mod_sqr(tmp_1, a, p, ctx))
 325             goto err;
 326         if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx))
 327             goto err;
 328         if (!BN_lshift(tmp_1, tmp_2, 2))
 329             goto err;
 330         /* tmp_1 = 4*a^3 */
 331
 332         if (!BN_mod_sqr(tmp_2, b, p, ctx))
 333             goto err;
 334         if (!BN_mul_word(tmp_2, 27))
 335             goto err;
 336         /* tmp_2 = 27*b^2 */
 337
 338         if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx))
 339             goto err;
 340         if (BN_is_zero(a))
 341             goto err;
 342     }
 343     ret = 1;
 344
 345  err:
 346     if (ctx != NULL)
 347         BN_CTX_end(ctx);
 348     if (new_ctx != NULL)
 349         BN_CTX_free(new_ctx);
 350     return ret;
 351 }
 352
 353 int ec_GFp_simple_point_init(EC_POINT *point)
 354 {
 355     BN_init(&point->X);
 356     BN_init(&point->Y);
 357     BN_init(&point->Z);
 358     point->Z_is_one = 0;
 359
 360     return 1;
 361 }
 362
 363 void ec_GFp_simple_point_finish(EC_POINT *point)
 364 {
 365     BN_free(&point->X);
 366     BN_free(&point->Y);
 367     BN_free(&point->Z);
 368 }
 369
 370 void ec_GFp_simple_point_clear_finish(EC_POINT *point)
 371 {
 372     BN_clear_free(&point->X);
 373     BN_clear_free(&point->Y);
 374     BN_clear_free(&point->Z);
 375     point->Z_is_one = 0;
 376 }
 377
 378 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
 379 {
 380     if (!BN_copy(&dest->X, &src->X))
 381         return 0;
 382     if (!BN_copy(&dest->Y, &src->Y))
 383         return 0;
 384     if (!BN_copy(&dest->Z, &src->Z))
 385         return 0;
 386     dest->Z_is_one = src->Z_is_one;
 387
 388     return 1;
 389 }
 390
 391 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group,
 392                                         EC_POINT *point)
 393 {
 394     point->Z_is_one = 0;
 395     BN_zero(&point->Z);
 396     return 1;
 397 }
 398
 399 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group,
 400                                                   EC_POINT *point,
 401                                                   const BIGNUM *x,
 402                                                   const BIGNUM *y,
 403                                                   const BIGNUM *z,
 404                                                   BN_CTX *ctx)
 405 {
 406     BN_CTX *new_ctx = NULL;
 407     int ret = 0;
 408
 409     if (ctx == NULL) {
 410         ctx = new_ctx = BN_CTX_new();
 411         if (ctx == NULL)
 412             return 0;
 413     }
 414
 415     if (x != NULL) {
 416         if (!BN_nnmod(&point->X, x, &group->field, ctx))
 417             goto err;
 418         if (group->meth->field_encode) {
 419             if (!group->meth->field_encode(group, &point->X, &point->X, ctx))
 420                 goto err;
 421         }
 422     }
 423
 424     if (y != NULL) {
 425         if (!BN_nnmod(&point->Y, y, &group->field, ctx))
 426             goto err;
 427         if (group->meth->field_encode) {
 428             if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx))
 429                 goto err;
 430         }
 431     }
 432
 433     if (z != NULL) {
 434         int Z_is_one;
 435
 436         if (!BN_nnmod(&point->Z, z, &group->field, ctx))
 437             goto err;
 438         Z_is_one = BN_is_one(&point->Z);
 439         if (group->meth->field_encode) {
 440             if (Z_is_one && (group->meth->field_set_to_one != 0)) {
 441                 if (!group->meth->field_set_to_one(group, &point->Z, ctx))
 442                     goto err;
 443             } else {
 444                 if (!group->
 445                     meth->field_encode(group, &point->Z, &point->Z, ctx))
 446                     goto err;
 447             }
 448         }
 449         point->Z_is_one = Z_is_one;
 450     }
 451
 452     ret = 1;
 453
 454  err:
 455     if (new_ctx != NULL)
 456         BN_CTX_free(new_ctx);
 457     return ret;
 458 }
 459
 460 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group,
 461                                                   const EC_POINT *point,
 462                                                   BIGNUM *x, BIGNUM *y,
 463                                                   BIGNUM *z, BN_CTX *ctx)
 464 {
 465     BN_CTX *new_ctx = NULL;
 466     int ret = 0;
 467
 468     if (group->meth->field_decode != 0) {
 469         if (ctx == NULL) {
 470             ctx = new_ctx = BN_CTX_new();
 471             if (ctx == NULL)
 472                 return 0;
 473         }
 474
 475         if (x != NULL) {
 476             if (!group->meth->field_decode(group, x, &point->X, ctx))
 477                 goto err;
 478         }
 479         if (y != NULL) {
 480             if (!group->meth->field_decode(group, y, &point->Y, ctx))
 481                 goto err;
 482         }
 483         if (z != NULL) {
 484             if (!group->meth->field_decode(group, z, &point->Z, ctx))
 485                 goto err;
 486         }
 487     } else {
 488         if (x != NULL) {
 489             if (!BN_copy(x, &point->X))
 490                 goto err;
 491         }
 492         if (y != NULL) {
 493             if (!BN_copy(y, &point->Y))
 494                 goto err;
 495         }
 496         if (z != NULL) {
 497             if (!BN_copy(z, &point->Z))
 498                 goto err;
 499         }
 500     }
 501
 502     ret = 1;
 503
 504  err:
 505     if (new_ctx != NULL)
 506         BN_CTX_free(new_ctx);
 507     return ret;
 508 }
 509
 510 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group,
 511                                                EC_POINT *point,
 512                                                const BIGNUM *x,
 513                                                const BIGNUM *y, BN_CTX *ctx)
 514 {
 515     if (x == NULL || y == NULL) {
 516         /*
 517          * unlike for projective coordinates, we do not tolerate this
 518          */
 519         ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES,
 520               ERR_R_PASSED_NULL_PARAMETER);
 521         return 0;
 522     }
 523
 524     return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y,
 525                                                     BN_value_one(), ctx);
 526 }
 527
 528 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group,
 529                                                const EC_POINT *point,
 530                                                BIGNUM *x, BIGNUM *y,
 531                                                BN_CTX *ctx)
 532 {
 533     BN_CTX *new_ctx = NULL;
 534     BIGNUM *Z, *Z_1, *Z_2, *Z_3;
 535     const BIGNUM *Z_;
 536     int ret = 0;
 537
 538     if (EC_POINT_is_at_infinity(group, point)) {
 539         ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
 540               EC_R_POINT_AT_INFINITY);
 541         return 0;
 542     }
 543
 544     if (ctx == NULL) {
 545         ctx = new_ctx = BN_CTX_new();
 546         if (ctx == NULL)
 547             return 0;
 548     }
 549
 550     BN_CTX_start(ctx);
 551     Z = BN_CTX_get(ctx);
 552     Z_1 = BN_CTX_get(ctx);
 553     Z_2 = BN_CTX_get(ctx);
 554     Z_3 = BN_CTX_get(ctx);
 555     if (Z_3 == NULL)
 556         goto err;
 557
 558     /* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
 559
 560     if (group->meth->field_decode) {
 561         if (!group->meth->field_decode(group, Z, &point->Z, ctx))
 562             goto err;
 563         Z_ = Z;
 564     } else {
 565         Z_ = &point->Z;
 566     }
 567
 568     if (BN_is_one(Z_)) {
 569         if (group->meth->field_decode) {
 570             if (x != NULL) {
 571                 if (!group->meth->field_decode(group, x, &point->X, ctx))
 572                     goto err;
 573             }
 574             if (y != NULL) {
 575                 if (!group->meth->field_decode(group, y, &point->Y, ctx))
 576                     goto err;
 577             }
 578         } else {
 579             if (x != NULL) {
 580                 if (!BN_copy(x, &point->X))
 581                     goto err;
 582             }
 583             if (y != NULL) {
 584                 if (!BN_copy(y, &point->Y))
 585                     goto err;
 586             }
 587         }
 588     } else {
 589         if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx)) {
 590             ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES,
 591                   ERR_R_BN_LIB);
 592             goto err;
 593         }
 594
 595         if (group->meth->field_encode == 0) {
 596             /* field_sqr works on standard representation */
 597             if (!group->meth->field_sqr(group, Z_2, Z_1, ctx))
 598                 goto err;
 599         } else {
 600             if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx))
 601                 goto err;
 602         }
 603
 604         if (x != NULL) {
 605             /*
 606              * in the Montgomery case, field_mul will cancel out Montgomery
 607              * factor in X:
 608              */
 609             if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx))
 610                 goto err;
 611         }
 612
 613         if (y != NULL) {
 614             if (group->meth->field_encode == 0) {
 615                 /*
 616                  * field_mul works on standard representation
 617                  */
 618                 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx))
 619                     goto err;
 620             } else {
 621                 if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx))
 622                     goto err;
 623             }
 624
 625             /*
 626              * in the Montgomery case, field_mul will cancel out Montgomery
 627              * factor in Y:
 628              */
 629             if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx))
 630                 goto err;
 631         }
 632     }
 633
 634     ret = 1;
 635
 636  err:
 637     BN_CTX_end(ctx);
 638     if (new_ctx != NULL)
 639         BN_CTX_free(new_ctx);
 640     return ret;
 641 }
 642
 643 int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group,
 644                                              EC_POINT *point,
 645                                              const BIGNUM *x_, int y_bit,
 646                                              BN_CTX *ctx)
 647 {
 648     BN_CTX *new_ctx = NULL;
 649     BIGNUM *tmp1, *tmp2, *x, *y;
 650     int ret = 0;
 651
 652     /* clear error queue */
 653     ERR_clear_error();
 654
 655     if (ctx == NULL) {
 656         ctx = new_ctx = BN_CTX_new();
 657         if (ctx == NULL)
 658             return 0;
 659     }
 660
 661     y_bit = (y_bit != 0);
 662
 663     BN_CTX_start(ctx);
 664     tmp1 = BN_CTX_get(ctx);
 665     tmp2 = BN_CTX_get(ctx);
 666     x = BN_CTX_get(ctx);
 667     y = BN_CTX_get(ctx);
 668     if (y == NULL)
 669         goto err;
 670
 671     /*-
 672      * Recover y.  We have a Weierstrass equation
 673      *     y^2 = x^3 + a*x + b,
 674      * so  y  is one of the square roots of  x^3 + a*x + b.
 675      */
 676
 677     /* tmp1 := x^3 */
 678     if (!BN_nnmod(x, x_, &group->field, ctx))
 679         goto err;
 680     if (group->meth->field_decode == 0) {
 681         /* field_{sqr,mul} work on standard representation */
 682         if (!group->meth->field_sqr(group, tmp2, x_, ctx))
 683             goto err;
 684         if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx))
 685             goto err;
 686     } else {
 687         if (!BN_mod_sqr(tmp2, x_, &group->field, ctx))
 688             goto err;
 689         if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx))
 690             goto err;
 691     }
 692
 693     /* tmp1 := tmp1 + a*x */
 694     if (group->a_is_minus3) {
 695         if (!BN_mod_lshift1_quick(tmp2, x, &group->field))
 696             goto err;
 697         if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field))
 698             goto err;
 699         if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field))
 700             goto err;
 701     } else {
 702         if (group->meth->field_decode) {
 703             if (!group->meth->field_decode(group, tmp2, &group->a, ctx))
 704                 goto err;
 705             if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx))
 706                 goto err;
 707         } else {
 708             /* field_mul works on standard representation */
 709             if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx))
 710                 goto err;
 711         }
 712
 713         if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field))
 714             goto err;
 715     }
 716
 717     /* tmp1 := tmp1 + b */
 718     if (group->meth->field_decode) {
 719         if (!group->meth->field_decode(group, tmp2, &group->b, ctx))
 720             goto err;
 721         if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field))
 722             goto err;
 723     } else {
 724         if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field))
 725             goto err;
 726     }
 727
 728     if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) {
 729         unsigned long err = ERR_peek_last_error();
 730
 731         if (ERR_GET_LIB(err) == ERR_LIB_BN
 732             && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) {
 733             ERR_clear_error();
 734             ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 735                   EC_R_INVALID_COMPRESSED_POINT);
 736         } else
 737             ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 738                   ERR_R_BN_LIB);
 739         goto err;
 740     }
 741
 742     if (y_bit != BN_is_odd(y)) {
 743         if (BN_is_zero(y)) {
 744             int kron;
 745
 746             kron = BN_kronecker(x, &group->field, ctx);
 747             if (kron == -2)
 748                 goto err;
 749
 750             if (kron == 1)
 751                 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 752                       EC_R_INVALID_COMPRESSION_BIT);
 753             else
 754                 /*
 755                  * BN_mod_sqrt() should have cought this error (not a square)
 756                  */
 757                 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 758                       EC_R_INVALID_COMPRESSED_POINT);
 759             goto err;
 760         }
 761         if (!BN_usub(y, &group->field, y))
 762             goto err;
 763     }
 764     if (y_bit != BN_is_odd(y)) {
 765         ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 766               ERR_R_INTERNAL_ERROR);
 767         goto err;
 768     }
 769
 770     if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
 771         goto err;
 772
 773     ret = 1;
 774
 775  err:
 776     BN_CTX_end(ctx);
 777     if (new_ctx != NULL)
 778         BN_CTX_free(new_ctx);
 779     return ret;
 780 }
 781
 782 size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point,
 783                                point_conversion_form_t form,
 784                                unsigned char *buf, size_t len, BN_CTX *ctx)
 785 {
 786     size_t ret;
 787     BN_CTX *new_ctx = NULL;
 788     int used_ctx = 0;
 789     BIGNUM *x, *y;
 790     size_t field_len, i, skip;
 791
 792     if ((form != POINT_CONVERSION_COMPRESSED)
 793         && (form != POINT_CONVERSION_UNCOMPRESSED)
 794         && (form != POINT_CONVERSION_HYBRID)) {
 795         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
 796         goto err;
 797     }
 798
 799     if (EC_POINT_is_at_infinity(group, point)) {
 800         /* encodes to a single 0 octet */
 801         if (buf != NULL) {
 802             if (len < 1) {
 803                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
 804                 return 0;
 805             }
 806             buf[0] = 0;
 807         }
 808         return 1;
 809     }
 810
 811     /* ret := required output buffer length */
 812     field_len = BN_num_bytes(&group->field);
 813     ret =
 814         (form ==
 815          POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
 816
 817     /* if 'buf' is NULL, just return required length */
 818     if (buf != NULL) {
 819         if (len < ret) {
 820             ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
 821             goto err;
 822         }
 823
 824         if (ctx == NULL) {
 825             ctx = new_ctx = BN_CTX_new();
 826             if (ctx == NULL)
 827                 return 0;
 828         }
 829
 830         BN_CTX_start(ctx);
 831         used_ctx = 1;
 832         x = BN_CTX_get(ctx);
 833         y = BN_CTX_get(ctx);
 834         if (y == NULL)
 835             goto err;
 836
 837         if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
 838             goto err;
 839
 840         if ((form == POINT_CONVERSION_COMPRESSED
 841              || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y))
 842             buf[0] = form + 1;
 843         else
 844             buf[0] = form;
 845
 846         i = 1;
 847
 848         skip = field_len - BN_num_bytes(x);
 849         if (skip > field_len) {
 850             ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 851             goto err;
 852         }
 853         while (skip > 0) {
 854             buf[i++] = 0;
 855             skip--;
 856         }
 857         skip = BN_bn2bin(x, buf + i);
 858         i += skip;
 859         if (i != 1 + field_len) {
 860             ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 861             goto err;
 862         }
 863
 864         if (form == POINT_CONVERSION_UNCOMPRESSED
 865             || form == POINT_CONVERSION_HYBRID) {
 866             skip = field_len - BN_num_bytes(y);
 867             if (skip > field_len) {
 868                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 869                 goto err;
 870             }
 871             while (skip > 0) {
 872                 buf[i++] = 0;
 873                 skip--;
 874             }
 875             skip = BN_bn2bin(y, buf + i);
 876             i += skip;
 877         }
 878
 879         if (i != ret) {
 880             ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 881             goto err;
 882         }
 883     }
 884
 885     if (used_ctx)
 886         BN_CTX_end(ctx);
 887     if (new_ctx != NULL)
 888         BN_CTX_free(new_ctx);
 889     return ret;
 890
 891  err:
 892     if (used_ctx)
 893         BN_CTX_end(ctx);
 894     if (new_ctx != NULL)
 895         BN_CTX_free(new_ctx);
 896     return 0;
 897 }
 898
 899 int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
 900                             const unsigned char *buf, size_t len, BN_CTX *ctx)
 901 {
 902     point_conversion_form_t form;
 903     int y_bit;
 904     BN_CTX *new_ctx = NULL;
 905     BIGNUM *x, *y;
 906     size_t field_len, enc_len;
 907     int ret = 0;
 908
 909     if (len == 0) {
 910         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
 911         return 0;
 912     }
 913     form = buf[0];
 914     y_bit = form & 1;
 915     form = form & ~1U;
 916     if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
 917         && (form != POINT_CONVERSION_UNCOMPRESSED)
 918         && (form != POINT_CONVERSION_HYBRID)) {
 919         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 920         return 0;
 921     }
 922     if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) {
 923         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 924         return 0;
 925     }
 926
 927     if (form == 0) {
 928         if (len != 1) {
 929             ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 930             return 0;
 931         }
 932
 933         return EC_POINT_set_to_infinity(group, point);
 934     }
 935
 936     field_len = BN_num_bytes(&group->field);
 937     enc_len =
 938         (form ==
 939          POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
 940
 941     if (len != enc_len) {
 942         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 943         return 0;
 944     }
 945
 946     if (ctx == NULL) {
 947         ctx = new_ctx = BN_CTX_new();
 948         if (ctx == NULL)
 949             return 0;
 950     }
 951
 952     BN_CTX_start(ctx);
 953     x = BN_CTX_get(ctx);
 954     y = BN_CTX_get(ctx);
 955     if (y == NULL)
 956         goto err;
 957
 958     if (!BN_bin2bn(buf + 1, field_len, x))
 959         goto err;
 960     if (BN_ucmp(x, &group->field) >= 0) {
 961         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 962         goto err;
 963     }
 964
 965     if (form == POINT_CONVERSION_COMPRESSED) {
 966         if (!EC_POINT_set_compressed_coordinates_GFp
 967             (group, point, x, y_bit, ctx))
 968             goto err;
 969     } else {
 970         if (!BN_bin2bn(buf + 1 + field_len, field_len, y))
 971             goto err;
 972         if (BN_ucmp(y, &group->field) >= 0) {
 973             ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 974             goto err;
 975         }
 976         if (form == POINT_CONVERSION_HYBRID) {
 977             if (y_bit != BN_is_odd(y)) {
 978                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 979                 goto err;
 980             }
 981         }
 982
 983         if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
 984             goto err;
 985     }
 986
 987     /* test required by X9.62 */
 988     if (EC_POINT_is_on_curve(group, point, ctx) <= 0) {
 989         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
 990         goto err;
 991     }
 992
 993     ret = 1;
 994
 995  err:
 996     BN_CTX_end(ctx);
 997     if (new_ctx != NULL)
 998         BN_CTX_free(new_ctx);
 999     return ret;
1000 }
1001
1002 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
1003                       const EC_POINT *b, BN_CTX *ctx)
1004 {
1005     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
1006                       const BIGNUM *, BN_CTX *);
1007     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1008     const BIGNUM *p;
1009     BN_CTX *new_ctx = NULL;
1010     BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
1011     int ret = 0;
1012
1013     if (a == b)
1014         return EC_POINT_dbl(group, r, a, ctx);
1015     if (EC_POINT_is_at_infinity(group, a))
1016         return EC_POINT_copy(r, b);
1017     if (EC_POINT_is_at_infinity(group, b))
1018         return EC_POINT_copy(r, a);
1019
1020     field_mul = group->meth->field_mul;
1021     field_sqr = group->meth->field_sqr;
1022     p = &group->field;
1023
1024     if (ctx == NULL) {
1025         ctx = new_ctx = BN_CTX_new();
1026         if (ctx == NULL)
1027             return 0;
1028     }
1029
1030     BN_CTX_start(ctx);
1031     n0 = BN_CTX_get(ctx);
1032     n1 = BN_CTX_get(ctx);
1033     n2 = BN_CTX_get(ctx);
1034     n3 = BN_CTX_get(ctx);
1035     n4 = BN_CTX_get(ctx);
1036     n5 = BN_CTX_get(ctx);
1037     n6 = BN_CTX_get(ctx);
1038     if (n6 == NULL)
1039         goto end;
1040
1041     /*
1042      * Note that in this function we must not read components of 'a' or 'b'
1043      * once we have written the corresponding components of 'r'. ('r' might
1044      * be one of 'a' or 'b'.)
1045      */
1046
1047     /* n1, n2 */
1048     if (b->Z_is_one) {
1049         if (!BN_copy(n1, &a->X))
1050             goto end;
1051         if (!BN_copy(n2, &a->Y))
1052             goto end;
1053         /* n1 = X_a */
1054         /* n2 = Y_a */
1055     } else {
1056         if (!field_sqr(group, n0, &b->Z, ctx))
1057             goto end;
1058         if (!field_mul(group, n1, &a->X, n0, ctx))
1059             goto end;
1060         /* n1 = X_a * Z_b^2 */
1061
1062         if (!field_mul(group, n0, n0, &b->Z, ctx))
1063             goto end;
1064         if (!field_mul(group, n2, &a->Y, n0, ctx))
1065             goto end;
1066         /* n2 = Y_a * Z_b^3 */
1067     }
1068
1069     /* n3, n4 */
1070     if (a->Z_is_one) {
1071         if (!BN_copy(n3, &b->X))
1072             goto end;
1073         if (!BN_copy(n4, &b->Y))
1074             goto end;
1075         /* n3 = X_b */
1076         /* n4 = Y_b */
1077     } else {
1078         if (!field_sqr(group, n0, &a->Z, ctx))
1079             goto end;
1080         if (!field_mul(group, n3, &b->X, n0, ctx))
1081             goto end;
1082         /* n3 = X_b * Z_a^2 */
1083
1084         if (!field_mul(group, n0, n0, &a->Z, ctx))
1085             goto end;
1086         if (!field_mul(group, n4, &b->Y, n0, ctx))
1087             goto end;
1088         /* n4 = Y_b * Z_a^3 */
1089     }
1090
1091     /* n5, n6 */
1092     if (!BN_mod_sub_quick(n5, n1, n3, p))
1093         goto end;
1094     if (!BN_mod_sub_quick(n6, n2, n4, p))
1095         goto end;
1096     /* n5 = n1 - n3 */
1097     /* n6 = n2 - n4 */
1098
1099     if (BN_is_zero(n5)) {
1100         if (BN_is_zero(n6)) {
1101             /* a is the same point as b */
1102             BN_CTX_end(ctx);
1103             ret = EC_POINT_dbl(group, r, a, ctx);
1104             ctx = NULL;
1105             goto end;
1106         } else {
1107             /* a is the inverse of b */
1108             BN_zero(&r->Z);
1109             r->Z_is_one = 0;
1110             ret = 1;
1111             goto end;
1112         }
1113     }
1114
1115     /* 'n7', 'n8' */
1116     if (!BN_mod_add_quick(n1, n1, n3, p))
1117         goto end;
1118     if (!BN_mod_add_quick(n2, n2, n4, p))
1119         goto end;
1120     /* 'n7' = n1 + n3 */
1121     /* 'n8' = n2 + n4 */
1122
1123     /* Z_r */
1124     if (a->Z_is_one && b->Z_is_one) {
1125         if (!BN_copy(&r->Z, n5))
1126             goto end;
1127     } else {
1128         if (a->Z_is_one) {
1129             if (!BN_copy(n0, &b->Z))
1130                 goto end;
1131         } else if (b->Z_is_one) {
1132             if (!BN_copy(n0, &a->Z))
1133                 goto end;
1134         } else {
1135             if (!field_mul(group, n0, &a->Z, &b->Z, ctx))
1136                 goto end;
1137         }
1138         if (!field_mul(group, &r->Z, n0, n5, ctx))
1139             goto end;
1140     }
1141     r->Z_is_one = 0;
1142     /* Z_r = Z_a * Z_b * n5 */
1143
1144     /* X_r */
1145     if (!field_sqr(group, n0, n6, ctx))
1146         goto end;
1147     if (!field_sqr(group, n4, n5, ctx))
1148         goto end;
1149     if (!field_mul(group, n3, n1, n4, ctx))
1150         goto end;
1151     if (!BN_mod_sub_quick(&r->X, n0, n3, p))
1152         goto end;
1153     /* X_r = n6^2 - n5^2 * 'n7' */
1154
1155     /* 'n9' */
1156     if (!BN_mod_lshift1_quick(n0, &r->X, p))
1157         goto end;
1158     if (!BN_mod_sub_quick(n0, n3, n0, p))
1159         goto end;
1160     /* n9 = n5^2 * 'n7' - 2 * X_r */
1161
1162     /* Y_r */
1163     if (!field_mul(group, n0, n0, n6, ctx))
1164         goto end;
1165     if (!field_mul(group, n5, n4, n5, ctx))
1166         goto end;               /* now n5 is n5^3 */
1167     if (!field_mul(group, n1, n2, n5, ctx))
1168         goto end;
1169     if (!BN_mod_sub_quick(n0, n0, n1, p))
1170         goto end;
1171     if (BN_is_odd(n0))
1172         if (!BN_add(n0, n0, p))
1173             goto end;
1174     /* now  0 <= n0 < 2*p,  and n0 is even */
1175     if (!BN_rshift1(&r->Y, n0))
1176         goto end;
1177     /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
1178
1179     ret = 1;
1180
1181  end:
1182     if (ctx)                    /* otherwise we already called BN_CTX_end */
1183         BN_CTX_end(ctx);
1184     if (new_ctx != NULL)
1185         BN_CTX_free(new_ctx);
1186     return ret;
1187 }
1188
1189 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
1190                       BN_CTX *ctx)
1191 {
1192     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
1193                       const BIGNUM *, BN_CTX *);
1194     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1195     const BIGNUM *p;
1196     BN_CTX *new_ctx = NULL;
1197     BIGNUM *n0, *n1, *n2, *n3;
1198     int ret = 0;
1199
1200     if (EC_POINT_is_at_infinity(group, a)) {
1201         BN_zero(&r->Z);
1202         r->Z_is_one = 0;
1203         return 1;
1204     }
1205
1206     field_mul = group->meth->field_mul;
1207     field_sqr = group->meth->field_sqr;
1208     p = &group->field;
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     n0 = BN_CTX_get(ctx);
1218     n1 = BN_CTX_get(ctx);
1219     n2 = BN_CTX_get(ctx);
1220     n3 = BN_CTX_get(ctx);
1221     if (n3 == NULL)
1222         goto err;
1223
1224     /*
1225      * Note that in this function we must not read components of 'a' once we
1226      * have written the corresponding components of 'r'. ('r' might the same
1227      * as 'a'.)
1228      */
1229
1230     /* n1 */
1231     if (a->Z_is_one) {
1232         if (!field_sqr(group, n0, &a->X, ctx))
1233             goto err;
1234         if (!BN_mod_lshift1_quick(n1, n0, p))
1235             goto err;
1236         if (!BN_mod_add_quick(n0, n0, n1, p))
1237             goto err;
1238         if (!BN_mod_add_quick(n1, n0, &group->a, p))
1239             goto err;
1240         /* n1 = 3 * X_a^2 + a_curve */
1241     } else if (group->a_is_minus3) {
1242         if (!field_sqr(group, n1, &a->Z, ctx))
1243             goto err;
1244         if (!BN_mod_add_quick(n0, &a->X, n1, p))
1245             goto err;
1246         if (!BN_mod_sub_quick(n2, &a->X, n1, p))
1247             goto err;
1248         if (!field_mul(group, n1, n0, n2, ctx))
1249             goto err;
1250         if (!BN_mod_lshift1_quick(n0, n1, p))
1251             goto err;
1252         if (!BN_mod_add_quick(n1, n0, n1, p))
1253             goto err;
1254         /*-
1255          * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
1256          *    = 3 * X_a^2 - 3 * Z_a^4
1257          */
1258     } else {
1259         if (!field_sqr(group, n0, &a->X, ctx))
1260             goto err;
1261         if (!BN_mod_lshift1_quick(n1, n0, p))
1262             goto err;
1263         if (!BN_mod_add_quick(n0, n0, n1, p))
1264             goto err;
1265         if (!field_sqr(group, n1, &a->Z, ctx))
1266             goto err;
1267         if (!field_sqr(group, n1, n1, ctx))
1268             goto err;
1269         if (!field_mul(group, n1, n1, &group->a, ctx))
1270             goto err;
1271         if (!BN_mod_add_quick(n1, n1, n0, p))
1272             goto err;
1273         /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
1274     }
1275
1276     /* Z_r */
1277     if (a->Z_is_one) {
1278         if (!BN_copy(n0, &a->Y))
1279             goto err;
1280     } else {
1281         if (!field_mul(group, n0, &a->Y, &a->Z, ctx))
1282             goto err;
1283     }
1284     if (!BN_mod_lshift1_quick(&r->Z, n0, p))
1285         goto err;
1286     r->Z_is_one = 0;
1287     /* Z_r = 2 * Y_a * Z_a */
1288
1289     /* n2 */
1290     if (!field_sqr(group, n3, &a->Y, ctx))
1291         goto err;
1292     if (!field_mul(group, n2, &a->X, n3, ctx))
1293         goto err;
1294     if (!BN_mod_lshift_quick(n2, n2, 2, p))
1295         goto err;
1296     /* n2 = 4 * X_a * Y_a^2 */
1297
1298     /* X_r */
1299     if (!BN_mod_lshift1_quick(n0, n2, p))
1300         goto err;
1301     if (!field_sqr(group, &r->X, n1, ctx))
1302         goto err;
1303     if (!BN_mod_sub_quick(&r->X, &r->X, n0, p))
1304         goto err;
1305     /* X_r = n1^2 - 2 * n2 */
1306
1307     /* n3 */
1308     if (!field_sqr(group, n0, n3, ctx))
1309         goto err;
1310     if (!BN_mod_lshift_quick(n3, n0, 3, p))
1311         goto err;
1312     /* n3 = 8 * Y_a^4 */
1313
1314     /* Y_r */
1315     if (!BN_mod_sub_quick(n0, n2, &r->X, p))
1316         goto err;
1317     if (!field_mul(group, n0, n1, n0, ctx))
1318         goto err;
1319     if (!BN_mod_sub_quick(&r->Y, n0, n3, p))
1320         goto err;
1321     /* Y_r = n1 * (n2 - X_r) - n3 */
1322
1323     ret = 1;
1324
1325  err:
1326     BN_CTX_end(ctx);
1327     if (new_ctx != NULL)
1328         BN_CTX_free(new_ctx);
1329     return ret;
1330 }
1331
1332 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1333 {
1334     if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
1335         /* point is its own inverse */
1336         return 1;
1337
1338     return BN_usub(&point->Y, &group->field, &point->Y);
1339 }
1340
1341 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
1342 {
1343     return BN_is_zero(&point->Z);
1344 }
1345
1346 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
1347                               BN_CTX *ctx)
1348 {
1349     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
1350                       const BIGNUM *, BN_CTX *);
1351     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1352     const BIGNUM *p;
1353     BN_CTX *new_ctx = NULL;
1354     BIGNUM *rh, *tmp, *Z4, *Z6;
1355     int ret = -1;
1356
1357     if (EC_POINT_is_at_infinity(group, point))
1358         return 1;
1359
1360     field_mul = group->meth->field_mul;
1361     field_sqr = group->meth->field_sqr;
1362     p = &group->field;
1363
1364     if (ctx == NULL) {
1365         ctx = new_ctx = BN_CTX_new();
1366         if (ctx == NULL)
1367             return -1;
1368     }
1369
1370     BN_CTX_start(ctx);
1371     rh = BN_CTX_get(ctx);
1372     tmp = BN_CTX_get(ctx);
1373     Z4 = BN_CTX_get(ctx);
1374     Z6 = BN_CTX_get(ctx);
1375     if (Z6 == NULL)
1376         goto err;
1377
1378     /*-
1379      * We have a curve defined by a Weierstrass equation
1380      *      y^2 = x^3 + a*x + b.
1381      * The point to consider is given in Jacobian projective coordinates
1382      * where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
1383      * Substituting this and multiplying by  Z^6  transforms the above equation into
1384      *      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
1385      * To test this, we add up the right-hand side in 'rh'.
1386      */
1387
1388     /* rh := X^2 */
1389     if (!field_sqr(group, rh, &point->X, ctx))
1390         goto err;
1391
1392     if (!point->Z_is_one) {
1393         if (!field_sqr(group, tmp, &point->Z, ctx))
1394             goto err;
1395         if (!field_sqr(group, Z4, tmp, ctx))
1396             goto err;
1397         if (!field_mul(group, Z6, Z4, tmp, ctx))
1398             goto err;
1399
1400         /* rh := (rh + a*Z^4)*X */
1401         if (group->a_is_minus3) {
1402             if (!BN_mod_lshift1_quick(tmp, Z4, p))
1403                 goto err;
1404             if (!BN_mod_add_quick(tmp, tmp, Z4, p))
1405                 goto err;
1406             if (!BN_mod_sub_quick(rh, rh, tmp, p))
1407                 goto err;
1408             if (!field_mul(group, rh, rh, &point->X, ctx))
1409                 goto err;
1410         } else {
1411             if (!field_mul(group, tmp, Z4, &group->a, ctx))
1412                 goto err;
1413             if (!BN_mod_add_quick(rh, rh, tmp, p))
1414                 goto err;
1415             if (!field_mul(group, rh, rh, &point->X, ctx))
1416                 goto err;
1417         }
1418
1419         /* rh := rh + b*Z^6 */
1420         if (!field_mul(group, tmp, &group->b, Z6, ctx))
1421             goto err;
1422         if (!BN_mod_add_quick(rh, rh, tmp, p))
1423             goto err;
1424     } else {
1425         /* point->Z_is_one */
1426
1427         /* rh := (rh + a)*X */
1428         if (!BN_mod_add_quick(rh, rh, &group->a, p))
1429             goto err;
1430         if (!field_mul(group, rh, rh, &point->X, ctx))
1431             goto err;
1432         /* rh := rh + b */
1433         if (!BN_mod_add_quick(rh, rh, &group->b, p))
1434             goto err;
1435     }
1436
1437     /* 'lh' := Y^2 */
1438     if (!field_sqr(group, tmp, &point->Y, ctx))
1439         goto err;
1440
1441     ret = (0 == BN_ucmp(tmp, rh));
1442
1443  err:
1444     BN_CTX_end(ctx);
1445     if (new_ctx != NULL)
1446         BN_CTX_free(new_ctx);
1447     return ret;
1448 }
1449
1450 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
1451                       const EC_POINT *b, BN_CTX *ctx)
1452 {
1453     /*-
1454      * return values:
1455      *  -1   error
1456      *   0   equal (in affine coordinates)
1457      *   1   not equal
1458      */
1459
1460     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
1461                       const BIGNUM *, BN_CTX *);
1462     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1463     BN_CTX *new_ctx = NULL;
1464     BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1465     const BIGNUM *tmp1_, *tmp2_;
1466     int ret = -1;
1467
1468     if (EC_POINT_is_at_infinity(group, a)) {
1469         return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
1470     }
1471
1472     if (EC_POINT_is_at_infinity(group, b))
1473         return 1;
1474
1475     if (a->Z_is_one && b->Z_is_one) {
1476         return ((BN_cmp(&a->X, &b->X) == 0)
1477                 && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
1478     }
1479
1480     field_mul = group->meth->field_mul;
1481     field_sqr = group->meth->field_sqr;
1482
1483     if (ctx == NULL) {
1484         ctx = new_ctx = BN_CTX_new();
1485         if (ctx == NULL)
1486             return -1;
1487     }
1488
1489     BN_CTX_start(ctx);
1490     tmp1 = BN_CTX_get(ctx);
1491     tmp2 = BN_CTX_get(ctx);
1492     Za23 = BN_CTX_get(ctx);
1493     Zb23 = BN_CTX_get(ctx);
1494     if (Zb23 == NULL)
1495         goto end;
1496
1497     /*-
1498      * We have to decide whether
1499      *     (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1500      * or equivalently, whether
1501      *     (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1502      */
1503
1504     if (!b->Z_is_one) {
1505         if (!field_sqr(group, Zb23, &b->Z, ctx))
1506             goto end;
1507         if (!field_mul(group, tmp1, &a->X, Zb23, ctx))
1508             goto end;
1509         tmp1_ = tmp1;
1510     } else
1511         tmp1_ = &a->X;
1512     if (!a->Z_is_one) {
1513         if (!field_sqr(group, Za23, &a->Z, ctx))
1514             goto end;
1515         if (!field_mul(group, tmp2, &b->X, Za23, ctx))
1516             goto end;
1517         tmp2_ = tmp2;
1518     } else
1519         tmp2_ = &b->X;
1520
1521     /* compare  X_a*Z_b^2  with  X_b*Z_a^2 */
1522     if (BN_cmp(tmp1_, tmp2_) != 0) {
1523         ret = 1;                /* points differ */
1524         goto end;
1525     }
1526
1527     if (!b->Z_is_one) {
1528         if (!field_mul(group, Zb23, Zb23, &b->Z, ctx))
1529             goto end;
1530         if (!field_mul(group, tmp1, &a->Y, Zb23, ctx))
1531             goto end;
1532         /* tmp1_ = tmp1 */
1533     } else
1534         tmp1_ = &a->Y;
1535     if (!a->Z_is_one) {
1536         if (!field_mul(group, Za23, Za23, &a->Z, ctx))
1537             goto end;
1538         if (!field_mul(group, tmp2, &b->Y, Za23, ctx))
1539             goto end;
1540         /* tmp2_ = tmp2 */
1541     } else
1542         tmp2_ = &b->Y;
1543
1544     /* compare  Y_a*Z_b^3  with  Y_b*Z_a^3 */
1545     if (BN_cmp(tmp1_, tmp2_) != 0) {
1546         ret = 1;                /* points differ */
1547         goto end;
1548     }
1549
1550     /* points are equal */
1551     ret = 0;
1552
1553  end:
1554     BN_CTX_end(ctx);
1555     if (new_ctx != NULL)
1556         BN_CTX_free(new_ctx);
1557     return ret;
1558 }
1559
1560 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
1561                               BN_CTX *ctx)
1562 {
1563     BN_CTX *new_ctx = NULL;
1564     BIGNUM *x, *y;
1565     int ret = 0;
1566
1567     if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1568         return 1;
1569
1570     if (ctx == NULL) {
1571         ctx = new_ctx = BN_CTX_new();
1572         if (ctx == NULL)
1573             return 0;
1574     }
1575
1576     BN_CTX_start(ctx);
1577     x = BN_CTX_get(ctx);
1578     y = BN_CTX_get(ctx);
1579     if (y == NULL)
1580         goto err;
1581
1582     if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
1583         goto err;
1584     if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
1585         goto err;
1586     if (!point->Z_is_one) {
1587         ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1588         goto err;
1589     }
1590
1591     ret = 1;
1592
1593  err:
1594     BN_CTX_end(ctx);
1595     if (new_ctx != NULL)
1596         BN_CTX_free(new_ctx);
1597     return ret;
1598 }
1599
1600 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num,
1601                                      EC_POINT *points[], BN_CTX *ctx)
1602 {
1603     BN_CTX *new_ctx = NULL;
1604     BIGNUM *tmp, *tmp_Z;
1605     BIGNUM **prod_Z = NULL;
1606     size_t i;
1607     int ret = 0;
1608
1609     if (num == 0)
1610         return 1;
1611
1612     if (ctx == NULL) {
1613         ctx = new_ctx = BN_CTX_new();
1614         if (ctx == NULL)
1615             return 0;
1616     }
1617
1618     BN_CTX_start(ctx);
1619     tmp = BN_CTX_get(ctx);
1620     tmp_Z = BN_CTX_get(ctx);
1621     if (tmp == NULL || tmp_Z == NULL)
1622         goto err;
1623
1624     prod_Z = OPENSSL_malloc(num * sizeof prod_Z[0]);
1625     if (prod_Z == NULL)
1626         goto err;
1627     for (i = 0; i < num; i++) {
1628         prod_Z[i] = BN_new();
1629         if (prod_Z[i] == NULL)
1630             goto err;
1631     }
1632
1633     /*
1634      * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z,
1635      * skipping any zero-valued inputs (pretend that they're 1).
1636      */
1637
1638     if (!BN_is_zero(&points[0]->Z)) {
1639         if (!BN_copy(prod_Z[0], &points[0]->Z))
1640             goto err;
1641     } else {
1642         if (group->meth->field_set_to_one != 0) {
1643             if (!group->meth->field_set_to_one(group, prod_Z[0], ctx))
1644                 goto err;
1645         } else {
1646             if (!BN_one(prod_Z[0]))
1647                 goto err;
1648         }
1649     }
1650
1651     for (i = 1; i < num; i++) {
1652         if (!BN_is_zero(&points[i]->Z)) {
1653             if (!group->meth->field_mul(group, prod_Z[i], prod_Z[i - 1],
1654                                         &points[i]->Z, ctx))
1655                 goto err;
1656         } else {
1657             if (!BN_copy(prod_Z[i], prod_Z[i - 1]))
1658                 goto err;
1659         }
1660     }
1661
1662     /*
1663      * Now use a single explicit inversion to replace every non-zero
1664      * points[i]->Z by its inverse.
1665      */
1666
1667     if (!BN_mod_inverse(tmp, prod_Z[num - 1], &group->field, ctx)) {
1668         ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1669         goto err;
1670     }
1671     if (group->meth->field_encode != 0) {
1672         /*
1673          * In the Montgomery case, we just turned R*H (representing H) into
1674          * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to
1675          * multiply by the Montgomery factor twice.
1676          */
1677         if (!group->meth->field_encode(group, tmp, tmp, ctx))
1678             goto err;
1679         if (!group->meth->field_encode(group, tmp, tmp, ctx))
1680             goto err;
1681     }
1682
1683     for (i = num - 1; i > 0; --i) {
1684         /*
1685          * Loop invariant: tmp is the product of the inverses of points[0]->Z
1686          * .. points[i]->Z (zero-valued inputs skipped).
1687          */
1688         if (!BN_is_zero(&points[i]->Z)) {
1689             /*
1690              * Set tmp_Z to the inverse of points[i]->Z (as product of Z
1691              * inverses 0 .. i, Z values 0 .. i - 1).
1692              */
1693             if (!group->
1694                 meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx))
1695                 goto err;
1696             /*
1697              * Update tmp to satisfy the loop invariant for i - 1.
1698              */
1699             if (!group->meth->field_mul(group, tmp, tmp, &points[i]->Z, ctx))
1700                 goto err;
1701             /* Replace points[i]->Z by its inverse. */
1702             if (!BN_copy(&points[i]->Z, tmp_Z))
1703                 goto err;
1704         }
1705     }
1706
1707     if (!BN_is_zero(&points[0]->Z)) {
1708         /* Replace points[0]->Z by its inverse. */
1709         if (!BN_copy(&points[0]->Z, tmp))
1710             goto err;
1711     }
1712
1713     /* Finally, fix up the X and Y coordinates for all points. */
1714
1715     for (i = 0; i < num; i++) {
1716         EC_POINT *p = points[i];
1717
1718         if (!BN_is_zero(&p->Z)) {
1719             /* turn  (X, Y, 1/Z)  into  (X/Z^2, Y/Z^3, 1) */
1720
1721             if (!group->meth->field_sqr(group, tmp, &p->Z, ctx))
1722                 goto err;
1723             if (!group->meth->field_mul(group, &p->X, &p->X, tmp, ctx))
1724                 goto err;
1725
1726             if (!group->meth->field_mul(group, tmp, tmp, &p->Z, ctx))
1727                 goto err;
1728             if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp, ctx))
1729                 goto err;
1730
1731             if (group->meth->field_set_to_one != 0) {
1732                 if (!group->meth->field_set_to_one(group, &p->Z, ctx))
1733                     goto err;
1734             } else {
1735                 if (!BN_one(&p->Z))
1736                     goto err;
1737             }
1738             p->Z_is_one = 1;
1739         }
1740     }
1741
1742     ret = 1;
1743
1744  err:
1745     BN_CTX_end(ctx);
1746     if (new_ctx != NULL)
1747         BN_CTX_free(new_ctx);
1748     if (prod_Z != NULL) {
1749         for (i = 0; i < num; i++) {
1750             if (prod_Z[i] == NULL)
1751                 break;
1752             BN_clear_free(prod_Z[i]);
1753         }
1754         OPENSSL_free(prod_Z);
1755     }
1756     return ret;
1757 }
1758
1759 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1760                             const BIGNUM *b, BN_CTX *ctx)
1761 {
1762     return BN_mod_mul(r, a, b, &group->field, ctx);
1763 }
1764
1765 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
1766                             BN_CTX *ctx)
1767 {
1768     return BN_mod_sqr(r, a, &group->field, ctx);
1769 }