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 /* ====================================================================
   5  * Copyright (c) 1998-2001 The OpenSSL Project.  All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  *
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in
  16  *    the documentation and/or other materials provided with the
  17  *    distribution.
  18  *
  19  * 3. All advertising materials mentioning features or use of this
  20  *    software must display the following acknowledgment:
  21  *    "This product includes software developed by the OpenSSL Project
  22  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  23  *
  24  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  25  *    endorse or promote products derived from this software without
  26  *    prior written permission. For written permission, please contact
  27  *    openssl-core@openssl.org.
  28  *
  29  * 5. Products derived from this software may not be called "OpenSSL"
  30  *    nor may "OpenSSL" appear in their names without prior written
  31  *    permission of the OpenSSL Project.
  32  *
  33  * 6. Redistributions of any form whatsoever must retain the following
  34  *    acknowledgment:
  35  *    "This product includes software developed by the OpenSSL Project
  36  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  37  *
  38  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  39  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  40  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  41  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  42  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  43  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  44  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  45  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  46  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  47  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  48  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  49  * OF THE POSSIBILITY OF SUCH DAMAGE.
  50  * ====================================================================
  51  *
  52  * This product includes cryptographic software written by Eric Young
  53  * (eay@cryptsoft.com).  This product includes software written by Tim
  54  * Hudson (tjh@cryptsoft.com).
  55  *
  56  */
  57
  58 #include <openssl/err.h>
  59
  60 #include "ec_lcl.h"
  61
  62
  63 const EC_METHOD *EC_GFp_simple_method(void)
  64         {
  65         static const EC_METHOD ret = {
  66                 ec_GFp_simple_group_init,
  67                 ec_GFp_simple_group_set_curve_GFp,
  68                 ec_GFp_simple_group_finish,
  69                 ec_GFp_simple_group_clear_finish,
  70                 ec_GFp_simple_group_copy,
  71                 ec_GFp_simple_group_set_generator,
  72                 /* TODO: 'set' and 'get' functions for EC_GROUPs */
  73                 ec_GFp_simple_point_init,
  74                 ec_GFp_simple_point_finish,
  75                 ec_GFp_simple_point_clear_finish,
  76                 ec_GFp_simple_point_copy,
  77                 ec_GFp_simple_point_set_to_infinity,
  78                 ec_GFp_simple_point_set_affine_coordinates_GFp,
  79                 ec_GFp_simple_point_get_affine_coordinates_GFp,
  80                 /* TODO: other 'set' and 'get' functions for EC_POINTs */
  81                 ec_GFp_simple_point2oct,
  82                 ec_GFp_simple_oct2point,
  83                 ec_GFp_simple_add,
  84                 ec_GFp_simple_dbl,
  85                 ec_GFp_simple_is_at_infinity,
  86                 ec_GFp_simple_is_on_curve,
  87                 ec_GFp_simple_make_affine,
  88                 ec_GFp_simple_field_mul,
  89                 ec_GFp_simple_field_sqr,
  90                 0 /* field_encode */,
  91                 0 /* field_decode */ };
  92
  93         return &ret;
  94         }
  95
  96
  97 int ec_GFp_simple_group_init(EC_GROUP *group)
  98         {
  99         BN_init(&group->field);
 100         BN_init(&group->a);
 101         BN_init(&group->b);
 102         group->a_is_minus3 = 0;
 103         group->generator = NULL;
 104         BN_init(&group->order);
 105         BN_init(&group->cofactor);
 106         return 1;
 107         }
 108
 109
 110 int ec_GFp_simple_group_set_curve_GFp(EC_GROUP *group,
 111         const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 112         {
 113         int ret = 0;
 114         BN_CTX *new_ctx = NULL;
 115         BIGNUM *tmp_a;
 116
 117         if (ctx == NULL)
 118                 {
 119                 ctx = new_ctx = BN_CTX_new();
 120                 if (ctx == NULL)
 121                         return 0;
 122                 }
 123
 124         BN_CTX_start(ctx);
 125         tmp_a = BN_CTX_get(ctx);
 126         if (tmp_a == NULL) goto err;
 127
 128         /* group->field */
 129         if (!BN_copy(&group->field, p)) goto err;
 130         group->field.neg = 0;
 131
 132         /* group->a */
 133         if (!BN_nnmod(tmp_a, a, p, ctx)) goto err;
 134         if (group->meth->field_encode)
 135                 { if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) goto err; }
 136         else
 137                 if (!BN_copy(&group->a, tmp_a)) goto err;
 138
 139         /* group->b */
 140         if (!BN_nnmod(&group->b, b, p, ctx)) goto err;
 141         if (group->meth->field_encode)
 142                 if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) goto err;
 143
 144         /* group->a_is_minus3 */
 145         if (!BN_add_word(tmp_a, 3)) goto err;
 146         group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
 147
 148         ret = 1;
 149
 150  err:
 151         BN_CTX_end(ctx);
 152         if (new_ctx != NULL)
 153                 BN_CTX_free(new_ctx);
 154         return ret;
 155         }
 156
 157
 158 void ec_GFp_simple_group_finish(EC_GROUP *group)
 159         {
 160         BN_free(&group->field);
 161         BN_free(&group->a);
 162         BN_free(&group->b);
 163         if (group->generator != NULL)
 164                 EC_POINT_free(group->generator);
 165         BN_free(&group->order);
 166         BN_free(&group->cofactor);
 167         }
 168
 169
 170 void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
 171         {
 172         BN_clear_free(&group->field);
 173         BN_clear_free(&group->a);
 174         BN_clear_free(&group->b);
 175         if (group->generator != NULL)
 176                 {
 177                 EC_POINT_clear_free(group->generator);
 178                 group->generator = NULL;
 179                 }
 180         BN_clear_free(&group->order);
 181         BN_clear_free(&group->cofactor);
 182         }
 183
 184
 185 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
 186         {
 187         if (!BN_copy(&dest->field, &src->field)) return 0;
 188         if (!BN_copy(&dest->a, &src->a)) return 0;
 189         if (!BN_copy(&dest->b, &src->b)) return 0;
 190
 191         dest->a_is_minus3 = src->a_is_minus3;
 192
 193         if (src->generator != NULL)
 194                 {
 195                 if (dest->generator == NULL)
 196                         {
 197                         dest->generator = EC_POINT_new(dest);
 198                         if (dest->generator == NULL) return 0;
 199                         }
 200                 if (!EC_POINT_copy(dest->generator, src->generator)) return 0;
 201                 }
 202         else
 203                 {
 204                 /* src->generator == NULL */
 205                 if (dest->generator != NULL)
 206                         {
 207                         EC_POINT_clear_free(dest->generator);
 208                         dest->generator = NULL;
 209                         }
 210                 }
 211
 212         if (!BN_copy(&dest->order, &src->order)) return 0;
 213         if (!BN_copy(&dest->cofactor, &src->cofactor)) return 0;
 214
 215         return 1;
 216         }
 217
 218
 219 int ec_GFp_simple_group_set_generator(EC_GROUP *group, const EC_POINT *generator,
 220         const BIGNUM *order, const BIGNUM *cofactor)
 221         {
 222         if (generator)
 223                 {
 224                 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_GENERATOR, ERR_R_PASSED_NULL_PARAMETER);
 225                 return 0   ;
 226                 }
 227
 228         if (group->generator == NULL)
 229                 {
 230                 group->generator = EC_POINT_new(group);
 231                 if (group->generator == NULL) return 0;
 232                 }
 233         if (!EC_POINT_copy(group->generator, generator)) return 0;
 234
 235         if (order != NULL)
 236                 { if (!BN_copy(&group->order, order)) return 0; }
 237         else
 238                 { if (!BN_zero(&group->order)) return 0; }
 239
 240         if (cofactor != NULL)
 241                 { if (!BN_copy(&group->cofactor, cofactor)) return 0; }
 242         else
 243                 { if (!BN_zero(&group->cofactor)) return 0; }
 244
 245         return 1;
 246         }
 247
 248
 249 /* TODO: 'set' and 'get' functions for EC_GROUPs */
 250
 251
 252 int ec_GFp_simple_point_init(EC_POINT *point)
 253         {
 254         BN_init(&point->X);
 255         BN_init(&point->Y);
 256         BN_init(&point->Z);
 257         point->Z_is_one = 0;
 258
 259         return 1;
 260         }
 261
 262
 263 void ec_GFp_simple_point_finish(EC_POINT *point)
 264         {
 265         BN_free(&point->X);
 266         BN_free(&point->Y);
 267         BN_free(&point->Z);
 268         }
 269
 270
 271 void ec_GFp_simple_point_clear_finish(EC_POINT *point)
 272         {
 273         BN_clear_free(&point->X);
 274         BN_clear_free(&point->Y);
 275         BN_clear_free(&point->Z);
 276         point->Z_is_one = 0;
 277         }
 278
 279
 280 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
 281         {
 282         if (!BN_copy(&dest->X, &src->X)) return 0;
 283         if (!BN_copy(&dest->Y, &src->Y)) return 0;
 284         if (!BN_copy(&dest->Z, &src->Z)) return 0;
 285         dest->Z_is_one = src->Z_is_one;
 286
 287         return 1;
 288         }
 289
 290
 291 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
 292         {
 293         point->Z_is_one = 0;
 294         return (BN_zero(&point->Z));
 295         }
 296
 297
 298 int ec_GFp_simple_point_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
 299         const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
 300         {
 301         BN_CTX *new_ctx = NULL;
 302         int ret = 0;
 303
 304         if (!BN_copy(&point->X, x)) goto err;
 305         if (!BN_copy(&point->Y, y)) goto err;
 306         if (!BN_one(&point->Z)) goto err;
 307
 308         if (group->meth->field_encode)
 309                 {
 310                 if (ctx == NULL)
 311                         {
 312                         ctx = new_ctx = BN_CTX_new();
 313                         if (ctx == NULL)
 314                                 return 0;
 315                         }
 316
 317                 if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err;
 318                 if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err;
 319                 if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
 320                 }
 321
 322         point->Z_is_one = 1;
 323
 324  err:
 325         if (new_ctx != NULL)
 326                 BN_CTX_free(new_ctx);
 327         return ret;
 328         }
 329
 330
 331 int ec_GFp_simple_point_get_affine_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point,
 332         BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
 333         {
 334         BN_CTX *new_ctx = NULL;
 335         BIGNUM *X, *Y, *Z, *Z_1, *Z_2, *Z_3;
 336         const BIGNUM *X_, *Y_, *Z_;
 337         int ret = 0;
 338
 339         if (EC_POINT_is_at_infinity(group, point))
 340                 {
 341                 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES_GFP, EC_R_POINT_AT_INFINITY);
 342                 return 0;
 343                 }
 344
 345         if (ctx == NULL)
 346                 {
 347                 ctx = new_ctx = BN_CTX_new();
 348                 if (ctx == NULL)
 349                         return 0;
 350                 }
 351
 352         BN_CTX_start(ctx);
 353         X = BN_CTX_get(ctx);
 354         Y = BN_CTX_get(ctx);
 355         Z = BN_CTX_get(ctx);
 356         Z_1 = BN_CTX_get(ctx);
 357         Z_2 = BN_CTX_get(ctx);
 358         Z_3 = BN_CTX_get(ctx);
 359         if (Z_3 == NULL) goto err;
 360
 361         /* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
 362
 363         if (group->meth->field_decode)
 364                 {
 365                 if (!group->meth->field_decode(group, X, &point->X, ctx)) goto err;
 366                 if (!group->meth->field_decode(group, Y, &point->Y, ctx)) goto err;
 367                 if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto err;
 368                 X_ = X; Y_ = Y; Z_ = Z;
 369                 }
 370         else
 371                 {
 372                 X_ = &point->X;
 373                 Y_ = &point->Y;
 374                 Z_ = &point->Z;
 375                 }
 376
 377         if (BN_is_one(Z_))
 378                 {
 379                 if (!BN_copy(x, X_)) goto err;
 380                 if (!BN_copy(y, Y_)) goto err;
 381                 }
 382         else
 383                 {
 384                 if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx))
 385                         {
 386                         ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES_GFP, ERR_R_BN_LIB);
 387                         goto err;
 388                         }
 389                 if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
 390                 if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
 391
 392                 if (!BN_mod_mul(x, X_, Z_2, &group->field, ctx)) goto err;
 393                 if (!BN_mod_mul(y, Y_, Z_3, &group->field, ctx)) goto err;
 394                 }
 395
 396         ret = 1;
 397
 398  err:
 399         BN_CTX_end(ctx);
 400         if (new_ctx != NULL)
 401                 BN_CTX_free(new_ctx);
 402         return ret;
 403         }
 404
 405
 406 /* TODO: other 'set' and 'get' functions for EC_POINTs */
 407
 408
 409 size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form,
 410         unsigned char *buf, size_t len, BN_CTX *ctx)
 411         {
 412         size_t ret;
 413         BN_CTX *new_ctx = NULL;
 414         int used_ctx = 0;
 415         BIGNUM *x, *y;
 416         size_t field_len, i, skip;
 417
 418         if ((form != POINT_CONVERSION_COMPRESSED)
 419                 && (form != POINT_CONVERSION_UNCOMPRESSED)
 420                 && (form != POINT_CONVERSION_HYBRID))
 421                 {
 422                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
 423                 goto err;
 424                 }
 425
 426         if (EC_POINT_is_at_infinity(group, point))
 427                 {
 428                 /* encodes to a single 0 octet */
 429                 if (buf != NULL)
 430                         {
 431                         if (len < 1)
 432                                 {
 433                                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
 434                                 return 0;
 435                                 }
 436                         buf[0] = 0;
 437                         }
 438                 return 1;
 439                 }
 440
 441
 442         /* ret := required output buffer length */
 443         field_len = BN_num_bytes(&group->field);
 444         ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
 445
 446         /* if 'buf' is NULL, just return required length */
 447         if (buf != NULL)
 448                 {
 449                 if (len < ret)
 450                         {
 451                         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
 452                         goto err;
 453                         }
 454
 455                 if (ctx == NULL)
 456                         {
 457                         ctx = new_ctx = BN_CTX_new();
 458                         if (ctx == NULL)
 459                                 return 0;
 460                         }
 461
 462                 BN_CTX_start(ctx);
 463                 used_ctx = 1;
 464                 x = BN_CTX_get(ctx);
 465                 y = BN_CTX_get(ctx);
 466                 if (y == NULL) goto err;
 467
 468                 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
 469
 470                 if ((form == POINT_CONVERSION_COMPRESSED || form == POINT_CONVERSION_HYBRID) && BN_is_bit_set(y, 0))
 471                         buf[0] = form + 1;
 472                 else
 473                         buf[0] = form;
 474
 475                 i = 1;
 476
 477                 skip = field_len - BN_num_bytes(x);
 478                 if (skip > field_len)
 479                         {
 480                         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 481                         goto err;
 482                         }
 483                 while (skip > 0)
 484                         {
 485                         buf[i++] = 0;
 486                         skip--;
 487                         }
 488                 skip = BN_bn2bin(x, buf + i);
 489                 i += skip;
 490                 if (i != 1 + field_len)
 491                         {
 492                         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 493                         goto err;
 494                         }
 495
 496                 if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID)
 497                         {
 498                         skip = field_len - BN_num_bytes(y);
 499                         if (skip > field_len)
 500                                 {
 501                                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 502                                 goto err;
 503                                 }
 504                         while (skip > 0)
 505                                 {
 506                                 buf[i++] = 0;
 507                                 skip--;
 508                                 }
 509                         skip = BN_bn2bin(y, buf + i);
 510                         i += skip;
 511                         }
 512
 513                 if (i != ret)
 514                         {
 515                         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 516                         goto err;
 517                         }
 518                 }
 519
 520         if (used_ctx)
 521                 BN_CTX_end(ctx);
 522         if (new_ctx != NULL)
 523                 BN_CTX_free(new_ctx);
 524         return ret;
 525
 526  err:
 527         if (used_ctx)
 528                 BN_CTX_end(ctx);
 529         if (new_ctx != NULL)
 530                 BN_CTX_free(new_ctx);
 531         return 0;
 532         }
 533
 534
 535 int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
 536         const unsigned char *buf, size_t len, BN_CTX *ctx)
 537         {
 538         point_conversion_form_t form;
 539         int y_bit;
 540         BN_CTX *new_ctx = NULL;
 541         BIGNUM *x, *y;
 542         size_t field_len, enc_len;
 543         int ret = 0;
 544
 545         if (len <= 0)
 546                 {
 547                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
 548                 return 0;
 549                 }
 550         form = buf[0];
 551         y_bit = form & 1;
 552         form = form & ~1;
 553         if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
 554                 && (form != POINT_CONVERSION_UNCOMPRESSED)
 555                 && (form != POINT_CONVERSION_HYBRID))
 556                 {
 557                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 558                 return 0;
 559                 }
 560         if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit)
 561                 {
 562                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 563                 return 0;
 564                 }
 565
 566         if (form == 0)
 567                 {
 568                 if (len != 1)
 569                         {
 570                         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 571                         return 0;
 572                         }
 573
 574                 return EC_POINT_set_to_infinity(group, point);
 575                 }
 576
 577         field_len = BN_num_bytes(&group->field);
 578         enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
 579
 580         if (len != enc_len)
 581                 {
 582                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 583                 return 0;
 584                 }
 585
 586         if (ctx == NULL)
 587                 {
 588                 ctx = new_ctx = BN_CTX_new();
 589                 if (ctx == NULL)
 590                         return 0;
 591                 }
 592
 593         BN_CTX_start(ctx);
 594         x = BN_CTX_get(ctx);
 595         y = BN_CTX_get(ctx);
 596         if (y == NULL) goto err;
 597
 598         if (!BN_bin2bn(buf + 1, field_len, x)) goto err;
 599         if (BN_ucmp(x, &group->field) >= 0)
 600                 {
 601                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 602                 goto err;
 603                 }
 604
 605         if (form != POINT_CONVERSION_COMPRESSED)
 606                 {
 607                 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err;
 608                 if (BN_ucmp(y, &group->field) >= 0)
 609                         {
 610                         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 611                         goto err;
 612                         }
 613                 if (form == POINT_CONVERSION_HYBRID)
 614                         {
 615                         if (y_bit != BN_is_bit_set(y, 0))
 616                                 {
 617                                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 618                                 goto err;
 619                                 }
 620                         }
 621                 }
 622
 623         if (form == POINT_CONVERSION_COMPRESSED)
 624                 {
 625                 /* Recover y.  We have a Weierstrass equation
 626                  *     y^2 = x^3 + a*x + b,
 627                  * so  y  is one of the square roots of  x^3 + a*x + b.
 628                  */
 629
 630                 BIGNUM *tmp1, *tmp2;
 631
 632                 tmp1 = BN_CTX_get(ctx);
 633                 tmp2 = BN_CTX_get(ctx);
 634                 if (tmp2 == NULL) goto err;
 635
 636                 /* tmp1 := x^3 */
 637                 if (!BN_mod_sqr(tmp2, x, &group->field, ctx)) goto err;
 638                 if (!BN_mod_mul(tmp1, tmp2, x, &group->field, ctx)) goto err;
 639
 640                 /* tmp1 := tmp1 + a*x */
 641                 if (group->a_is_minus3)
 642                         {
 643                         if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) goto err;
 644                         if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) goto err;
 645                         if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
 646                         }
 647                 else
 648                         {
 649                         if (!BN_mod_mul(tmp2, &group->a, x, &group->field, ctx)) goto err;
 650                         if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
 651                         }
 652
 653                 /* tmp1 := tmp1 + b */
 654                 if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err;
 655
 656                 if (!BN_mod_sqrt(y, tmp1, &group->field, ctx))
 657                         {
 658                         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, ERR_R_BN_LIB);
 659                         goto err;
 660                         }
 661
 662                 if (y_bit != BN_is_bit_set(y, 0))
 663                         {
 664                         if (!BN_usub(y, &group->field, y)) goto err;
 665                         }
 666                 if (y_bit != BN_is_bit_set(y, 0))
 667                         {
 668                         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, ERR_R_INTERNAL_ERROR);
 669                         goto err;
 670                         }
 671                 }
 672
 673         if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
 674
 675         if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
 676                 {
 677                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
 678                 goto err;
 679                 }
 680
 681         ret = 1;
 682
 683  err:
 684         BN_CTX_end(ctx);
 685         if (new_ctx != NULL)
 686                 BN_CTX_free(new_ctx);
 687         return ret;
 688         }
 689
 690
 691 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
 692         {
 693         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
 694         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 695         const BIGNUM *p;
 696         BN_CTX *new_ctx = NULL;
 697         BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
 698         int ret = 0;
 699
 700         if (a == b)
 701                 return EC_POINT_dbl(group, r, a, ctx);
 702         if (EC_POINT_is_at_infinity(group, a))
 703                 return EC_POINT_copy(r, b);
 704         if (EC_POINT_is_at_infinity(group, b))
 705                 return EC_POINT_copy(r, a);
 706
 707         field_mul = group->meth->field_mul;
 708         field_sqr = group->meth->field_sqr;
 709         p = &group->field;
 710
 711         if (ctx == NULL)
 712                 {
 713                 ctx = new_ctx = BN_CTX_new();
 714                 if (ctx == NULL)
 715                         return 0;
 716                 }
 717
 718         BN_CTX_start(ctx);
 719         n0 = BN_CTX_get(ctx);
 720         n1 = BN_CTX_get(ctx);
 721         n2 = BN_CTX_get(ctx);
 722         n3 = BN_CTX_get(ctx);
 723         n4 = BN_CTX_get(ctx);
 724         n5 = BN_CTX_get(ctx);
 725         n6 = BN_CTX_get(ctx);
 726         if (n6 == NULL) goto end;
 727
 728         /* n1, n2 */
 729         if (b->Z_is_one)
 730                 {
 731                 if (!BN_copy(n1, &a->X)) goto end;
 732                 if (!BN_copy(n2, &a->Y)) goto end;
 733                 /* n1 = X_a */
 734                 /* n2 = Y_a */
 735                 }
 736         else
 737                 {
 738                 if (!field_sqr(group, n0, &b->Z, ctx)) goto end;
 739                 if (!field_mul(group, n1, &a->X, n0, ctx)) goto end;
 740                 /* n1 = X_a * Z_b^2 */
 741
 742                 if (!field_mul(group, n0, n0, &b->Z, ctx)) goto end;
 743                 if (!field_mul(group, n2, &a->Y, n0, ctx)) goto end;
 744                 /* n2 = Y_a * Z_b^3 */
 745                 }
 746
 747         /* n3, n4 */
 748         if (a->Z_is_one)
 749                 {
 750                 if (!BN_copy(n3, &b->X)) goto end;
 751                 if (!BN_copy(n4, &b->Y)) goto end;
 752                 /* n3 = X_b */
 753                 /* n4 = Y_b */
 754                 }
 755         else
 756                 {
 757                 if (!field_sqr(group, n0, &a->Z, ctx)) goto end;
 758                 if (!field_mul(group, n3, &b->X, n0, ctx)) goto end;
 759                 /* n3 = X_b * Z_a^2 */
 760
 761                 if (!field_mul(group, n0, n0, &a->Z, ctx)) goto end;
 762                 if (!field_mul(group, n4, &b->Y, n0, ctx)) goto end;
 763                 /* n4 = Y_b * Z_a^3 */
 764                 }
 765
 766         /* n5, n6 */
 767         if (!BN_mod_sub_quick(n5, n1, n3, p)) goto end;
 768         if (!BN_mod_sub_quick(n6, n2, n4, p)) goto end;
 769         /* n5 = n1 - n3 */
 770         /* n6 = n2 - n4 */
 771
 772         if (BN_is_zero(n5))
 773                 {
 774                 if (BN_is_zero(n6))
 775                         {
 776                         /* a is the same point as b */
 777                         BN_CTX_end(ctx);
 778                         ret = EC_POINT_dbl(group, r, a, ctx);
 779                         ctx = NULL;
 780                         goto end;
 781                         }
 782                 else
 783                         {
 784                         /* a is the inverse of b */
 785                         if (!BN_zero(&r->Z)) goto end;
 786                         r->Z_is_one = 0;
 787                         ret = 1;
 788                         goto end;
 789                         }
 790                 }
 791
 792         /* 'n7', 'n8' */
 793         if (!BN_mod_add_quick(n1, n1, n3, p)) goto end;
 794         if (!BN_mod_add_quick(n2, n2, n4, p)) goto end;
 795         /* 'n7' = n1 + n3 */
 796         /* 'n8' = n2 + n4 */
 797
 798         /* Z_r */
 799         if (a->Z_is_one && b->Z_is_one)
 800                 {
 801                 if (!BN_copy(&r->Z, n5)) goto end;
 802                 }
 803         else
 804                 {
 805                 if (a->Z_is_one)
 806                         { if (!BN_copy(n0, &b->Z)) goto end; }
 807                 else if (b->Z_is_one)
 808                         { if (!BN_copy(n0, &a->Z)) goto end; }
 809                 else
 810                         { if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) goto end; }
 811                 if (!field_mul(group, &r->Z, n0, n5, ctx)) goto end;
 812                 }
 813         r->Z_is_one = 0;
 814         /* Z_r = Z_a * Z_b * n5 */
 815
 816         /* X_r */
 817         if (!field_sqr(group, n0, n6, ctx)) goto end;
 818         if (!field_sqr(group, n4, n5, ctx)) goto end;
 819         if (!field_mul(group, n3, n1, n4, ctx)) goto end;
 820         if (!BN_mod_sub_quick(&r->X, n0, n3, p)) goto end;
 821         /* X_r = n6^2 - n5^2 * 'n7' */
 822
 823         /* 'n9' */
 824         if (!BN_mod_lshift1_quick(n0, &r->X, p)) goto end;
 825         if (!BN_mod_sub_quick(n0, n3, n0, p)) goto end;
 826         /* n9 = n5^2 * 'n7' - 2 * X_r */
 827
 828         /* Y_r */
 829         if (!field_mul(group, n0, n0, n6, ctx)) goto end;
 830         if (!field_mul(group, n5, n4, n5, ctx)) goto end; /* now n5 is n5^3 */
 831         if (!field_mul(group, n1, n2, n5, ctx)) goto end;
 832         if (!BN_mod_sub_quick(n0, n0, n1, p)) goto end;
 833         if (BN_is_odd(n0))
 834                 if (!BN_add(n0, n0, p)) goto end;
 835         /* now  0 <= n0 < 2*p,  and n0 is even */
 836         if (!BN_rshift1(&r->Y, n0)) goto end;
 837         /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
 838
 839         ret = 1;
 840
 841  end:
 842         if (ctx) /* otherwise we already called BN_CTX_end */
 843                 BN_CTX_end(ctx);
 844         if (new_ctx != NULL)
 845                 BN_CTX_free(new_ctx);
 846         return ret;
 847         }
 848
 849
 850 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
 851         {
 852         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
 853         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 854         const BIGNUM *p;
 855         BN_CTX *new_ctx = NULL;
 856         BIGNUM *n0, *n1, *n2, *n3;
 857         int ret = 0;
 858
 859         if (EC_POINT_is_at_infinity(group, a))
 860                 {
 861                 if (!BN_zero(&r->Z)) return 0;
 862                 r->Z_is_one = 0;
 863                 return 1;
 864                 }
 865
 866         field_mul = group->meth->field_mul;
 867         field_sqr = group->meth->field_sqr;
 868         p = &group->field;
 869
 870         if (ctx == NULL)
 871                 {
 872                 ctx = new_ctx = BN_CTX_new();
 873                 if (ctx == NULL)
 874                         return 0;
 875                 }
 876
 877         BN_CTX_start(ctx);
 878         n0 = BN_CTX_get(ctx);
 879         n1 = BN_CTX_get(ctx);
 880         n2 = BN_CTX_get(ctx);
 881         n3 = BN_CTX_get(ctx);
 882         if (n3 == NULL) goto err;
 883
 884         /* n1 */
 885         if (a->Z_is_one)
 886                 {
 887                 if (!field_sqr(group, n0, &a->X, ctx)) goto err;
 888                 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
 889                 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
 890                 if (!BN_mod_add_quick(n1, n0, &group->a, p)) goto err;
 891                 /* n1 = 3 * X_a^2 + a_curve */
 892                 }
 893         else if (group->a_is_minus3)
 894                 {
 895                 if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
 896                 if (!BN_mod_add_quick(n0, &a->X, n1, p)) goto err;
 897                 if (!BN_mod_sub_quick(n2, &a->X, n1, p)) goto err;
 898                 if (!field_mul(group, n1, n0, n2, ctx)) goto err;
 899                 if (!BN_mod_lshift1_quick(n0, n1, p)) goto err;
 900                 if (!BN_mod_add_quick(n1, n0, n1, p)) goto err;
 901                 /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
 902                  *    = 3 * X_a^2 - 3 * Z_a^4 */
 903                 }
 904         else
 905                 {
 906                 if (!field_sqr(group, n0, &a->X, ctx)) goto err;
 907                 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
 908                 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
 909                 if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
 910                 if (!field_sqr(group, n1, n1, ctx)) goto err;
 911                 if (!field_mul(group, n1, n1, &group->a, ctx)) goto err;
 912                 if (!BN_mod_add_quick(n1, n1, n0, p)) goto err;
 913                 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
 914                 }
 915
 916         /* Z_r */
 917         if (a->Z_is_one)
 918                 {
 919                 if (!BN_copy(n0, &a->Y)) goto err;
 920                 }
 921         else
 922                 {
 923                 if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) goto err;
 924                 }
 925         if (!BN_mod_lshift1_quick(&r->Z, n0, p)) goto err;
 926         r->Z_is_one = 0;
 927         /* Z_r = 2 * Y_a * Z_a */
 928
 929         /* n2 */
 930         if (!field_sqr(group, n3, &a->Y, ctx)) goto err;
 931         if (!field_mul(group, n2, &a->X, n3, ctx)) goto err;
 932         if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err;
 933         /* n2 = 4 * X_a * Y_a^2 */
 934
 935         /* X_r */
 936         if (!BN_mod_lshift1_quick(n0, n2, p)) goto err;
 937         if (!field_sqr(group, &r->X, n1, ctx)) goto err;
 938         if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) goto err;
 939         /* X_r = n1^2 - 2 * n2 */
 940
 941         /* n3 */
 942         if (!field_sqr(group, n0, n3, ctx)) goto err;
 943         if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err;
 944         /* n3 = 8 * Y_a^4 */
 945
 946         /* Y_r */
 947         if (!BN_mod_sub_quick(n0, n2, &r->X, p)) goto err;
 948         if (!field_mul(group, n0, n1, n0, ctx)) goto err;
 949         if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) goto err;
 950         /* Y_r = n1 * (n2 - X_r) - n3 */
 951
 952         ret = 1;
 953
 954  err:
 955         BN_CTX_end(ctx);
 956         if (new_ctx != NULL)
 957                 BN_CTX_free(new_ctx);
 958         return ret;
 959         }
 960
 961
 962 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
 963         {
 964         return BN_is_zero(&point->Z);
 965         }
 966
 967
 968 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
 969         {
 970         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
 971         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 972         const BIGNUM *p;
 973         BN_CTX *new_ctx = NULL;
 974         BIGNUM *rh, *tmp1, *tmp2, *Z4, *Z6;
 975         int ret = -1;
 976
 977         if (EC_POINT_is_at_infinity(group, point))
 978                 return 1;
 979
 980         field_mul = group->meth->field_mul;
 981         field_sqr = group->meth->field_sqr;
 982         p = &group->field;
 983
 984         if (ctx == NULL)
 985                 {
 986                 ctx = new_ctx = BN_CTX_new();
 987                 if (ctx == NULL)
 988                         return -1;
 989                 }
 990
 991         BN_CTX_start(ctx);
 992         rh = BN_CTX_get(ctx);
 993         tmp1 = BN_CTX_get(ctx);
 994         tmp2 = BN_CTX_get(ctx);
 995         Z4 = BN_CTX_get(ctx);
 996         Z6 = BN_CTX_get(ctx);
 997         if (Z6 == NULL) goto err;
 998
 999         /* We have a curve defined by a Weierstrass equation
1000          *      y^2 = x^3 + a*x + b.
1001          * The point to consider is given in Jacobian projective coordinates
1002          * where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
1003          * Substituting this and multiplying by  Z^6  transforms the above equation into
1004          *      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
1005          * To test this, we add up the right-hand side in 'rh'.
1006          */
1007
1008         /* rh := X^3 */
1009         if (!field_sqr(group, rh, &point->X, ctx)) goto err;
1010         if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1011
1012         if (!point->Z_is_one)
1013                 {
1014                 if (!field_sqr(group, tmp1, &point->Z, ctx)) goto err;
1015                 if (!field_sqr(group, Z4, tmp1, ctx)) goto err;
1016                 if (!field_mul(group, Z6, Z4, tmp1, ctx)) goto err;
1017
1018                 /* rh := rh + a*X*Z^4 */
1019                 if (!field_mul(group, tmp1, &point->X, Z4, ctx)) goto err;
1020                 if (&group->a_is_minus3)
1021                         {
1022                         if (!BN_mod_lshift1_quick(tmp2, tmp1, p)) goto err;
1023                         if (!BN_mod_add_quick(tmp2, tmp2, tmp1, p)) goto err;
1024                         if (!BN_mod_sub_quick(rh, rh, tmp2, p)) goto err;
1025                         }
1026                 else
1027                         {
1028                         if (!field_mul(group, tmp2, tmp1, &group->a, ctx)) goto err;
1029                         if (!BN_mod_add_quick(rh, rh, tmp2, p)) goto err;
1030                         }
1031
1032                 /* rh := rh + b*Z^6 */
1033                 if (!field_mul(group, tmp1, &group->b, Z6, ctx)) goto err;
1034                 if (!BN_mod_add_quick(rh, rh, tmp1, p)) goto err;
1035                 }
1036         else
1037                 {
1038                 /* point->Z_is_one */
1039
1040                 /* rh := rh + a*X */
1041                 if (&group->a_is_minus3)
1042                         {
1043                         if (!BN_mod_lshift1_quick(tmp2, &point->X, p)) goto err;
1044                         if (!BN_mod_add_quick(tmp2, tmp2, &point->X, p)) goto err;
1045                         if (!BN_mod_sub_quick(rh, rh, tmp2, p)) goto err;
1046                         }
1047                 else
1048                         {
1049                         if (!field_mul(group, tmp2, &point->X, &group->a, ctx)) goto err;
1050                         if (!BN_mod_add_quick(rh, rh, tmp2, p)) goto err;
1051                         }
1052
1053                 /* rh := rh + b */
1054                 if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err;
1055                 }
1056
1057         /* 'lh' := Y^2 */
1058         if (!field_sqr(group, tmp1, &point->Y, ctx)) goto err;
1059
1060         ret = (0 == BN_cmp(tmp1, rh));
1061
1062  err:
1063         BN_CTX_end(ctx);
1064         if (new_ctx != NULL)
1065                 BN_CTX_free(new_ctx);
1066         return ret;
1067         }
1068
1069
1070 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1071         {
1072         BN_CTX *new_ctx = NULL;
1073         BIGNUM *x, *y;
1074         int ret = 0;
1075
1076         if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1077                 return 1;
1078
1079         if (ctx == NULL)
1080                 {
1081                 ctx = new_ctx = BN_CTX_new();
1082                 if (ctx == NULL)
1083                         return 0;
1084                 }
1085
1086         BN_CTX_start(ctx);
1087         x = BN_CTX_get(ctx);
1088         y = BN_CTX_get(ctx);
1089         if (y == NULL) goto err;
1090
1091         if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1092         if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1093         if (!point->Z_is_one)
1094                 {
1095                 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1096                 goto err;
1097                 }
1098
1099         ret = 1;
1100
1101  err:
1102         BN_CTX_end(ctx);
1103         if (new_ctx != NULL)
1104                 BN_CTX_free(new_ctx);
1105         return ret;
1106         }
1107
1108
1109 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
1110         {
1111         return BN_mod_mul(r, a, b, &group->field, ctx);
1112         }
1113
1114
1115 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
1116         {
1117         return BN_mod_sqr(r, a, &group->field, ctx);
1118         }