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