crypto/ec/ec2_smpl.c

   1 /* crypto/ec/ec2_smpl.c */
   2 /* ====================================================================
   3  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
   4  *
   5  * The Elliptic Curve Public-Key Crypto Library (ECC Code) included
   6  * herein is developed by SUN MICROSYSTEMS, INC., and is contributed
   7  * to the OpenSSL project.
   8  *
   9  * The ECC Code is licensed pursuant to the OpenSSL open source
  10  * license provided below.
  11  *
  12  * The software is originally written by Sheueling Chang Shantz and
  13  * Douglas Stebila of Sun Microsystems Laboratories.
  14  *
  15  */
  16 /* ====================================================================
  17  * Copyright (c) 1998-2003 The OpenSSL Project.  All rights reserved.
  18  *
  19  * Redistribution and use in source and binary forms, with or without
  20  * modification, are permitted provided that the following conditions
  21  * are met:
  22  *
  23  * 1. Redistributions of source code must retain the above copyright
  24  *    notice, this list of conditions and the following disclaimer.
  25  *
  26  * 2. Redistributions in binary form must reproduce the above copyright
  27  *    notice, this list of conditions and the following disclaimer in
  28  *    the documentation and/or other materials provided with the
  29  *    distribution.
  30  *
  31  * 3. All advertising materials mentioning features or use of this
  32  *    software must display the following acknowledgment:
  33  *    "This product includes software developed by the OpenSSL Project
  34  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  35  *
  36  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  37  *    endorse or promote products derived from this software without
  38  *    prior written permission. For written permission, please contact
  39  *    openssl-core@openssl.org.
  40  *
  41  * 5. Products derived from this software may not be called "OpenSSL"
  42  *    nor may "OpenSSL" appear in their names without prior written
  43  *    permission of the OpenSSL Project.
  44  *
  45  * 6. Redistributions of any form whatsoever must retain the following
  46  *    acknowledgment:
  47  *    "This product includes software developed by the OpenSSL Project
  48  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  49  *
  50  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  51  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  52  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  53  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  54  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  55  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  56  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  57  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  58  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  59  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  60  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  61  * OF THE POSSIBILITY OF SUCH DAMAGE.
  62  * ====================================================================
  63  *
  64  * This product includes cryptographic software written by Eric Young
  65  * (eay@cryptsoft.com).  This product includes software written by Tim
  66  * Hudson (tjh@cryptsoft.com).
  67  *
  68  */
  69
  70 #include <openssl/err.h>
  71
  72 #include "ec_lcl.h"
  73
  74 const EC_METHOD *EC_GF2m_simple_method(void)
  75 {
  76     static const EC_METHOD ret = {
  77         NID_X9_62_characteristic_two_field,
  78         ec_GF2m_simple_group_init,
  79         ec_GF2m_simple_group_finish,
  80         ec_GF2m_simple_group_clear_finish,
  81         ec_GF2m_simple_group_copy,
  82         ec_GF2m_simple_group_set_curve,
  83         ec_GF2m_simple_group_get_curve,
  84         ec_GF2m_simple_group_get_degree,
  85         ec_GF2m_simple_group_check_discriminant,
  86         ec_GF2m_simple_point_init,
  87         ec_GF2m_simple_point_finish,
  88         ec_GF2m_simple_point_clear_finish,
  89         ec_GF2m_simple_point_copy,
  90         ec_GF2m_simple_point_set_to_infinity,
  91         0 /* set_Jprojective_coordinates_GFp */ ,
  92         0 /* get_Jprojective_coordinates_GFp */ ,
  93         ec_GF2m_simple_point_set_affine_coordinates,
  94         ec_GF2m_simple_point_get_affine_coordinates,
  95         ec_GF2m_simple_set_compressed_coordinates,
  96         ec_GF2m_simple_point2oct,
  97         ec_GF2m_simple_oct2point,
  98         ec_GF2m_simple_add,
  99         ec_GF2m_simple_dbl,
 100         ec_GF2m_simple_invert,
 101         ec_GF2m_simple_is_at_infinity,
 102         ec_GF2m_simple_is_on_curve,
 103         ec_GF2m_simple_cmp,
 104         ec_GF2m_simple_make_affine,
 105         ec_GF2m_simple_points_make_affine,
 106
 107         /*
 108          * the following three method functions are defined in ec2_mult.c
 109          */
 110         ec_GF2m_simple_mul,
 111         ec_GF2m_precompute_mult,
 112         ec_GF2m_have_precompute_mult,
 113
 114         ec_GF2m_simple_field_mul,
 115         ec_GF2m_simple_field_sqr,
 116         ec_GF2m_simple_field_div,
 117         0 /* field_encode */ ,
 118         0 /* field_decode */ ,
 119         0                       /* field_set_to_one */
 120     };
 121
 122     return &ret;
 123 }
 124
 125 /*
 126  * Initialize a GF(2^m)-based EC_GROUP structure. Note that all other members
 127  * are handled by EC_GROUP_new.
 128  */
 129 int ec_GF2m_simple_group_init(EC_GROUP *group)
 130 {
 131     BN_init(&group->field);
 132     BN_init(&group->a);
 133     BN_init(&group->b);
 134     return 1;
 135 }
 136
 137 /*
 138  * Free a GF(2^m)-based EC_GROUP structure. Note that all other members are
 139  * handled by EC_GROUP_free.
 140  */
 141 void ec_GF2m_simple_group_finish(EC_GROUP *group)
 142 {
 143     BN_free(&group->field);
 144     BN_free(&group->a);
 145     BN_free(&group->b);
 146 }
 147
 148 /*
 149  * Clear and free a GF(2^m)-based EC_GROUP structure. Note that all other
 150  * members are handled by EC_GROUP_clear_free.
 151  */
 152 void ec_GF2m_simple_group_clear_finish(EC_GROUP *group)
 153 {
 154     BN_clear_free(&group->field);
 155     BN_clear_free(&group->a);
 156     BN_clear_free(&group->b);
 157     group->poly[0] = 0;
 158     group->poly[1] = 0;
 159     group->poly[2] = 0;
 160     group->poly[3] = 0;
 161     group->poly[4] = 0;
 162 }
 163
 164 /*
 165  * Copy a GF(2^m)-based EC_GROUP structure. Note that all other members are
 166  * handled by EC_GROUP_copy.
 167  */
 168 int ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
 169 {
 170     int i;
 171     if (!BN_copy(&dest->field, &src->field))
 172         return 0;
 173     if (!BN_copy(&dest->a, &src->a))
 174         return 0;
 175     if (!BN_copy(&dest->b, &src->b))
 176         return 0;
 177     dest->poly[0] = src->poly[0];
 178     dest->poly[1] = src->poly[1];
 179     dest->poly[2] = src->poly[2];
 180     dest->poly[3] = src->poly[3];
 181     dest->poly[4] = src->poly[4];
 182     if (bn_wexpand(&dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2)
 183         == NULL)
 184         return 0;
 185     if (bn_wexpand(&dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2)
 186         == NULL)
 187         return 0;
 188     for (i = dest->a.top; i < dest->a.dmax; i++)
 189         dest->a.d[i] = 0;
 190     for (i = dest->b.top; i < dest->b.dmax; i++)
 191         dest->b.d[i] = 0;
 192     return 1;
 193 }
 194
 195 /* Set the curve parameters of an EC_GROUP structure. */
 196 int ec_GF2m_simple_group_set_curve(EC_GROUP *group,
 197                                    const BIGNUM *p, const BIGNUM *a,
 198                                    const BIGNUM *b, BN_CTX *ctx)
 199 {
 200     int ret = 0, i;
 201
 202     /* group->field */
 203     if (!BN_copy(&group->field, p))
 204         goto err;
 205     i = BN_GF2m_poly2arr(&group->field, group->poly, 5);
 206     if ((i != 5) && (i != 3)) {
 207         ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIELD);
 208         goto err;
 209     }
 210
 211     /* group->a */
 212     if (!BN_GF2m_mod_arr(&group->a, a, group->poly))
 213         goto err;
 214     if (bn_wexpand(&group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
 215         == NULL)
 216         goto err;
 217     for (i = group->a.top; i < group->a.dmax; i++)
 218         group->a.d[i] = 0;
 219
 220     /* group->b */
 221     if (!BN_GF2m_mod_arr(&group->b, b, group->poly))
 222         goto err;
 223     if (bn_wexpand(&group->b, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
 224         == NULL)
 225         goto err;
 226     for (i = group->b.top; i < group->b.dmax; i++)
 227         group->b.d[i] = 0;
 228
 229     ret = 1;
 230  err:
 231     return ret;
 232 }
 233
 234 /*
 235  * Get the curve parameters of an EC_GROUP structure. If p, a, or b are NULL
 236  * then there values will not be set but the method will return with success.
 237  */
 238 int ec_GF2m_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p,
 239                                    BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
 240 {
 241     int ret = 0;
 242
 243     if (p != NULL) {
 244         if (!BN_copy(p, &group->field))
 245             return 0;
 246     }
 247
 248     if (a != NULL) {
 249         if (!BN_copy(a, &group->a))
 250             goto err;
 251     }
 252
 253     if (b != NULL) {
 254         if (!BN_copy(b, &group->b))
 255             goto err;
 256     }
 257
 258     ret = 1;
 259
 260  err:
 261     return ret;
 262 }
 263
 264 /*
 265  * Gets the degree of the field.  For a curve over GF(2^m) this is the value
 266  * m.
 267  */
 268 int ec_GF2m_simple_group_get_degree(const EC_GROUP *group)
 269 {
 270     return BN_num_bits(&group->field) - 1;
 271 }
 272
 273 /*
 274  * Checks the discriminant of the curve. y^2 + x*y = x^3 + a*x^2 + b is an
 275  * elliptic curve <=> b != 0 (mod p)
 276  */
 277 int ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group,
 278                                             BN_CTX *ctx)
 279 {
 280     int ret = 0;
 281     BIGNUM *b;
 282     BN_CTX *new_ctx = NULL;
 283
 284     if (ctx == NULL) {
 285         ctx = new_ctx = BN_CTX_new();
 286         if (ctx == NULL) {
 287             ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT,
 288                   ERR_R_MALLOC_FAILURE);
 289             goto err;
 290         }
 291     }
 292     BN_CTX_start(ctx);
 293     b = BN_CTX_get(ctx);
 294     if (b == NULL)
 295         goto err;
 296
 297     if (!BN_GF2m_mod_arr(b, &group->b, group->poly))
 298         goto err;
 299
 300     /*
 301      * check the discriminant: y^2 + x*y = x^3 + a*x^2 + b is an elliptic
 302      * curve <=> b != 0 (mod p)
 303      */
 304     if (BN_is_zero(b))
 305         goto err;
 306
 307     ret = 1;
 308
 309  err:
 310     if (ctx != NULL)
 311         BN_CTX_end(ctx);
 312     if (new_ctx != NULL)
 313         BN_CTX_free(new_ctx);
 314     return ret;
 315 }
 316
 317 /* Initializes an EC_POINT. */
 318 int ec_GF2m_simple_point_init(EC_POINT *point)
 319 {
 320     BN_init(&point->X);
 321     BN_init(&point->Y);
 322     BN_init(&point->Z);
 323     return 1;
 324 }
 325
 326 /* Frees an EC_POINT. */
 327 void ec_GF2m_simple_point_finish(EC_POINT *point)
 328 {
 329     BN_free(&point->X);
 330     BN_free(&point->Y);
 331     BN_free(&point->Z);
 332 }
 333
 334 /* Clears and frees an EC_POINT. */
 335 void ec_GF2m_simple_point_clear_finish(EC_POINT *point)
 336 {
 337     BN_clear_free(&point->X);
 338     BN_clear_free(&point->Y);
 339     BN_clear_free(&point->Z);
 340     point->Z_is_one = 0;
 341 }
 342
 343 /*
 344  * Copy the contents of one EC_POINT into another.  Assumes dest is
 345  * initialized.
 346  */
 347 int ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
 348 {
 349     if (!BN_copy(&dest->X, &src->X))
 350         return 0;
 351     if (!BN_copy(&dest->Y, &src->Y))
 352         return 0;
 353     if (!BN_copy(&dest->Z, &src->Z))
 354         return 0;
 355     dest->Z_is_one = src->Z_is_one;
 356
 357     return 1;
 358 }
 359
 360 /*
 361  * Set an EC_POINT to the point at infinity. A point at infinity is
 362  * represented by having Z=0.
 363  */
 364 int ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group,
 365                                          EC_POINT *point)
 366 {
 367     point->Z_is_one = 0;
 368     BN_zero(&point->Z);
 369     return 1;
 370 }
 371
 372 /*
 373  * Set the coordinates of an EC_POINT using affine coordinates. Note that
 374  * the simple implementation only uses affine coordinates.
 375  */
 376 int ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group,
 377                                                 EC_POINT *point,
 378                                                 const BIGNUM *x,
 379                                                 const BIGNUM *y, BN_CTX *ctx)
 380 {
 381     int ret = 0;
 382     if (x == NULL || y == NULL) {
 383         ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES,
 384               ERR_R_PASSED_NULL_PARAMETER);
 385         return 0;
 386     }
 387
 388     if (!BN_copy(&point->X, x))
 389         goto err;
 390     BN_set_negative(&point->X, 0);
 391     if (!BN_copy(&point->Y, y))
 392         goto err;
 393     BN_set_negative(&point->Y, 0);
 394     if (!BN_copy(&point->Z, BN_value_one()))
 395         goto err;
 396     BN_set_negative(&point->Z, 0);
 397     point->Z_is_one = 1;
 398     ret = 1;
 399
 400  err:
 401     return ret;
 402 }
 403
 404 /*
 405  * Gets the affine coordinates of an EC_POINT. Note that the simple
 406  * implementation only uses affine coordinates.
 407  */
 408 int ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group,
 409                                                 const EC_POINT *point,
 410                                                 BIGNUM *x, BIGNUM *y,
 411                                                 BN_CTX *ctx)
 412 {
 413     int ret = 0;
 414
 415     if (EC_POINT_is_at_infinity(group, point)) {
 416         ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES,
 417               EC_R_POINT_AT_INFINITY);
 418         return 0;
 419     }
 420
 421     if (BN_cmp(&point->Z, BN_value_one())) {
 422         ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES,
 423               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
 424         return 0;
 425     }
 426     if (x != NULL) {
 427         if (!BN_copy(x, &point->X))
 428             goto err;
 429         BN_set_negative(x, 0);
 430     }
 431     if (y != NULL) {
 432         if (!BN_copy(y, &point->Y))
 433             goto err;
 434         BN_set_negative(y, 0);
 435     }
 436     ret = 1;
 437
 438  err:
 439     return ret;
 440 }
 441
 442 /* Include patented algorithms. */
 443 #include "ec2_smpt.c"
 444
 445 /*
 446  * Converts an EC_POINT to an octet string. If buf is NULL, the encoded
 447  * length will be returned. If the length len of buf is smaller than required
 448  * an error will be returned. The point compression section of this function
 449  * is patented by Certicom Corp. under US Patent 6,141,420.  Point
 450  * compression is disabled by default and can be enabled by defining the
 451  * preprocessor macro OPENSSL_EC_BIN_PT_COMP at Configure-time.
 452  */
 453 size_t ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point,
 454                                 point_conversion_form_t form,
 455                                 unsigned char *buf, size_t len, BN_CTX *ctx)
 456 {
 457     size_t ret;
 458     BN_CTX *new_ctx = NULL;
 459     int used_ctx = 0;
 460     BIGNUM *x, *y, *yxi;
 461     size_t field_len, i, skip;
 462
 463 #ifndef OPENSSL_EC_BIN_PT_COMP
 464     if ((form == POINT_CONVERSION_COMPRESSED)
 465         || (form == POINT_CONVERSION_HYBRID)) {
 466         ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_DISABLED);
 467         goto err;
 468     }
 469 #endif
 470
 471     if ((form != POINT_CONVERSION_COMPRESSED)
 472         && (form != POINT_CONVERSION_UNCOMPRESSED)
 473         && (form != POINT_CONVERSION_HYBRID)) {
 474         ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
 475         goto err;
 476     }
 477
 478     if (EC_POINT_is_at_infinity(group, point)) {
 479         /* encodes to a single 0 octet */
 480         if (buf != NULL) {
 481             if (len < 1) {
 482                 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
 483                 return 0;
 484             }
 485             buf[0] = 0;
 486         }
 487         return 1;
 488     }
 489
 490     /* ret := required output buffer length */
 491     field_len = (EC_GROUP_get_degree(group) + 7) / 8;
 492     ret =
 493         (form ==
 494          POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
 495
 496     /* if 'buf' is NULL, just return required length */
 497     if (buf != NULL) {
 498         if (len < ret) {
 499             ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
 500             goto err;
 501         }
 502
 503         if (ctx == NULL) {
 504             ctx = new_ctx = BN_CTX_new();
 505             if (ctx == NULL)
 506                 return 0;
 507         }
 508
 509         BN_CTX_start(ctx);
 510         used_ctx = 1;
 511         x = BN_CTX_get(ctx);
 512         y = BN_CTX_get(ctx);
 513         yxi = BN_CTX_get(ctx);
 514         if (yxi == NULL)
 515             goto err;
 516
 517         if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx))
 518             goto err;
 519
 520         buf[0] = form;
 521 #ifdef OPENSSL_EC_BIN_PT_COMP
 522         if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x)) {
 523             if (!group->meth->field_div(group, yxi, y, x, ctx))
 524                 goto err;
 525             if (BN_is_odd(yxi))
 526                 buf[0]++;
 527         }
 528 #endif
 529
 530         i = 1;
 531
 532         skip = field_len - BN_num_bytes(x);
 533         if (skip > field_len) {
 534             ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 535             goto err;
 536         }
 537         while (skip > 0) {
 538             buf[i++] = 0;
 539             skip--;
 540         }
 541         skip = BN_bn2bin(x, buf + i);
 542         i += skip;
 543         if (i != 1 + field_len) {
 544             ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 545             goto err;
 546         }
 547
 548         if (form == POINT_CONVERSION_UNCOMPRESSED
 549             || form == POINT_CONVERSION_HYBRID) {
 550             skip = field_len - BN_num_bytes(y);
 551             if (skip > field_len) {
 552                 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 553                 goto err;
 554             }
 555             while (skip > 0) {
 556                 buf[i++] = 0;
 557                 skip--;
 558             }
 559             skip = BN_bn2bin(y, buf + i);
 560             i += skip;
 561         }
 562
 563         if (i != ret) {
 564             ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 565             goto err;
 566         }
 567     }
 568
 569     if (used_ctx)
 570         BN_CTX_end(ctx);
 571     if (new_ctx != NULL)
 572         BN_CTX_free(new_ctx);
 573     return ret;
 574
 575  err:
 576     if (used_ctx)
 577         BN_CTX_end(ctx);
 578     if (new_ctx != NULL)
 579         BN_CTX_free(new_ctx);
 580     return 0;
 581 }
 582
 583 /*
 584  * Converts an octet string representation to an EC_POINT. Note that the
 585  * simple implementation only uses affine coordinates.
 586  */
 587 int ec_GF2m_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
 588                              const unsigned char *buf, size_t len,
 589                              BN_CTX *ctx)
 590 {
 591     point_conversion_form_t form;
 592     int y_bit;
 593     BN_CTX *new_ctx = NULL;
 594     BIGNUM *x, *y, *yxi;
 595     size_t field_len, enc_len;
 596     int ret = 0;
 597
 598     if (len == 0) {
 599         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
 600         return 0;
 601     }
 602     form = buf[0];
 603     y_bit = form & 1;
 604     form = form & ~1U;
 605     if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
 606         && (form != POINT_CONVERSION_UNCOMPRESSED)
 607         && (form != POINT_CONVERSION_HYBRID)) {
 608         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 609         return 0;
 610     }
 611     if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) {
 612         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 613         return 0;
 614     }
 615
 616     if (form == 0) {
 617         if (len != 1) {
 618             ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 619             return 0;
 620         }
 621
 622         return EC_POINT_set_to_infinity(group, point);
 623     }
 624
 625     field_len = (EC_GROUP_get_degree(group) + 7) / 8;
 626     enc_len =
 627         (form ==
 628          POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
 629
 630     if (len != enc_len) {
 631         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 632         return 0;
 633     }
 634
 635     if (ctx == NULL) {
 636         ctx = new_ctx = BN_CTX_new();
 637         if (ctx == NULL)
 638             return 0;
 639     }
 640
 641     BN_CTX_start(ctx);
 642     x = BN_CTX_get(ctx);
 643     y = BN_CTX_get(ctx);
 644     yxi = BN_CTX_get(ctx);
 645     if (yxi == NULL)
 646         goto err;
 647
 648     if (!BN_bin2bn(buf + 1, field_len, x))
 649         goto err;
 650     if (BN_ucmp(x, &group->field) >= 0) {
 651         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 652         goto err;
 653     }
 654
 655     if (form == POINT_CONVERSION_COMPRESSED) {
 656         if (!EC_POINT_set_compressed_coordinates_GF2m
 657             (group, point, x, y_bit, ctx))
 658             goto err;
 659     } else {
 660         if (!BN_bin2bn(buf + 1 + field_len, field_len, y))
 661             goto err;
 662         if (BN_ucmp(y, &group->field) >= 0) {
 663             ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 664             goto err;
 665         }
 666         if (form == POINT_CONVERSION_HYBRID) {
 667             if (!group->meth->field_div(group, yxi, y, x, ctx))
 668                 goto err;
 669             if (y_bit != BN_is_odd(yxi)) {
 670                 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 671                 goto err;
 672             }
 673         }
 674
 675         if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx))
 676             goto err;
 677     }
 678
 679     /* test required by X9.62 */
 680     if (!EC_POINT_is_on_curve(group, point, ctx)) {
 681         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
 682         goto err;
 683     }
 684
 685     ret = 1;
 686
 687  err:
 688     BN_CTX_end(ctx);
 689     if (new_ctx != NULL)
 690         BN_CTX_free(new_ctx);
 691     return ret;
 692 }
 693
 694 /*
 695  * Computes a + b and stores the result in r.  r could be a or b, a could be
 696  * b. Uses algorithm A.10.2 of IEEE P1363.
 697  */
 698 int ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
 699                        const EC_POINT *b, BN_CTX *ctx)
 700 {
 701     BN_CTX *new_ctx = NULL;
 702     BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t;
 703     int ret = 0;
 704
 705     if (EC_POINT_is_at_infinity(group, a)) {
 706         if (!EC_POINT_copy(r, b))
 707             return 0;
 708         return 1;
 709     }
 710
 711     if (EC_POINT_is_at_infinity(group, b)) {
 712         if (!EC_POINT_copy(r, a))
 713             return 0;
 714         return 1;
 715     }
 716
 717     if (ctx == NULL) {
 718         ctx = new_ctx = BN_CTX_new();
 719         if (ctx == NULL)
 720             return 0;
 721     }
 722
 723     BN_CTX_start(ctx);
 724     x0 = BN_CTX_get(ctx);
 725     y0 = BN_CTX_get(ctx);
 726     x1 = BN_CTX_get(ctx);
 727     y1 = BN_CTX_get(ctx);
 728     x2 = BN_CTX_get(ctx);
 729     y2 = BN_CTX_get(ctx);
 730     s = BN_CTX_get(ctx);
 731     t = BN_CTX_get(ctx);
 732     if (t == NULL)
 733         goto err;
 734
 735     if (a->Z_is_one) {
 736         if (!BN_copy(x0, &a->X))
 737             goto err;
 738         if (!BN_copy(y0, &a->Y))
 739             goto err;
 740     } else {
 741         if (!EC_POINT_get_affine_coordinates_GF2m(group, a, x0, y0, ctx))
 742             goto err;
 743     }
 744     if (b->Z_is_one) {
 745         if (!BN_copy(x1, &b->X))
 746             goto err;
 747         if (!BN_copy(y1, &b->Y))
 748             goto err;
 749     } else {
 750         if (!EC_POINT_get_affine_coordinates_GF2m(group, b, x1, y1, ctx))
 751             goto err;
 752     }
 753
 754     if (BN_GF2m_cmp(x0, x1)) {
 755         if (!BN_GF2m_add(t, x0, x1))
 756             goto err;
 757         if (!BN_GF2m_add(s, y0, y1))
 758             goto err;
 759         if (!group->meth->field_div(group, s, s, t, ctx))
 760             goto err;
 761         if (!group->meth->field_sqr(group, x2, s, ctx))
 762             goto err;
 763         if (!BN_GF2m_add(x2, x2, &group->a))
 764             goto err;
 765         if (!BN_GF2m_add(x2, x2, s))
 766             goto err;
 767         if (!BN_GF2m_add(x2, x2, t))
 768             goto err;
 769     } else {
 770         if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) {
 771             if (!EC_POINT_set_to_infinity(group, r))
 772                 goto err;
 773             ret = 1;
 774             goto err;
 775         }
 776         if (!group->meth->field_div(group, s, y1, x1, ctx))
 777             goto err;
 778         if (!BN_GF2m_add(s, s, x1))
 779             goto err;
 780
 781         if (!group->meth->field_sqr(group, x2, s, ctx))
 782             goto err;
 783         if (!BN_GF2m_add(x2, x2, s))
 784             goto err;
 785         if (!BN_GF2m_add(x2, x2, &group->a))
 786             goto err;
 787     }
 788
 789     if (!BN_GF2m_add(y2, x1, x2))
 790         goto err;
 791     if (!group->meth->field_mul(group, y2, y2, s, ctx))
 792         goto err;
 793     if (!BN_GF2m_add(y2, y2, x2))
 794         goto err;
 795     if (!BN_GF2m_add(y2, y2, y1))
 796         goto err;
 797
 798     if (!EC_POINT_set_affine_coordinates_GF2m(group, r, x2, y2, ctx))
 799         goto err;
 800
 801     ret = 1;
 802
 803  err:
 804     BN_CTX_end(ctx);
 805     if (new_ctx != NULL)
 806         BN_CTX_free(new_ctx);
 807     return ret;
 808 }
 809
 810 /*
 811  * Computes 2 * a and stores the result in r.  r could be a. Uses algorithm
 812  * A.10.2 of IEEE P1363.
 813  */
 814 int ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
 815                        BN_CTX *ctx)
 816 {
 817     return ec_GF2m_simple_add(group, r, a, a, ctx);
 818 }
 819
 820 int ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
 821 {
 822     if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
 823         /* point is its own inverse */
 824         return 1;
 825
 826     if (!EC_POINT_make_affine(group, point, ctx))
 827         return 0;
 828     return BN_GF2m_add(&point->Y, &point->X, &point->Y);
 829 }
 830
 831 /* Indicates whether the given point is the point at infinity. */
 832 int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group,
 833                                   const EC_POINT *point)
 834 {
 835     return BN_is_zero(&point->Z);
 836 }
 837
 838 /*-
 839  * Determines whether the given EC_POINT is an actual point on the curve defined
 840  * in the EC_GROUP.  A point is valid if it satisfies the Weierstrass equation:
 841  *      y^2 + x*y = x^3 + a*x^2 + b.
 842  */
 843 int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
 844                                BN_CTX *ctx)
 845 {
 846     int ret = -1;
 847     BN_CTX *new_ctx = NULL;
 848     BIGNUM *lh, *y2;
 849     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
 850                       const BIGNUM *, BN_CTX *);
 851     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 852
 853     if (EC_POINT_is_at_infinity(group, point))
 854         return 1;
 855
 856     field_mul = group->meth->field_mul;
 857     field_sqr = group->meth->field_sqr;
 858
 859     /* only support affine coordinates */
 860     if (!point->Z_is_one)
 861         return -1;
 862
 863     if (ctx == NULL) {
 864         ctx = new_ctx = BN_CTX_new();
 865         if (ctx == NULL)
 866             return -1;
 867     }
 868
 869     BN_CTX_start(ctx);
 870     y2 = BN_CTX_get(ctx);
 871     lh = BN_CTX_get(ctx);
 872     if (lh == NULL)
 873         goto err;
 874
 875         /*-
 876          * We have a curve defined by a Weierstrass equation
 877          *      y^2 + x*y = x^3 + a*x^2 + b.
 878          *  <=> x^3 + a*x^2 + x*y + b + y^2 = 0
 879          *  <=> ((x + a) * x + y ) * x + b + y^2 = 0
 880          */
 881     if (!BN_GF2m_add(lh, &point->X, &group->a))
 882         goto err;
 883     if (!field_mul(group, lh, lh, &point->X, ctx))
 884         goto err;
 885     if (!BN_GF2m_add(lh, lh, &point->Y))
 886         goto err;
 887     if (!field_mul(group, lh, lh, &point->X, ctx))
 888         goto err;
 889     if (!BN_GF2m_add(lh, lh, &group->b))
 890         goto err;
 891     if (!field_sqr(group, y2, &point->Y, ctx))
 892         goto err;
 893     if (!BN_GF2m_add(lh, lh, y2))
 894         goto err;
 895     ret = BN_is_zero(lh);
 896  err:
 897     if (ctx)
 898         BN_CTX_end(ctx);
 899     if (new_ctx)
 900         BN_CTX_free(new_ctx);
 901     return ret;
 902 }
 903
 904 /*-
 905  * Indicates whether two points are equal.
 906  * Return values:
 907  *  -1   error
 908  *   0   equal (in affine coordinates)
 909  *   1   not equal
 910  */
 911 int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
 912                        const EC_POINT *b, BN_CTX *ctx)
 913 {
 914     BIGNUM *aX, *aY, *bX, *bY;
 915     BN_CTX *new_ctx = NULL;
 916     int ret = -1;
 917
 918     if (EC_POINT_is_at_infinity(group, a)) {
 919         return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
 920     }
 921
 922     if (EC_POINT_is_at_infinity(group, b))
 923         return 1;
 924
 925     if (a->Z_is_one && b->Z_is_one) {
 926         return ((BN_cmp(&a->X, &b->X) == 0)
 927                 && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
 928     }
 929
 930     if (ctx == NULL) {
 931         ctx = new_ctx = BN_CTX_new();
 932         if (ctx == NULL)
 933             return -1;
 934     }
 935
 936     BN_CTX_start(ctx);
 937     aX = BN_CTX_get(ctx);
 938     aY = BN_CTX_get(ctx);
 939     bX = BN_CTX_get(ctx);
 940     bY = BN_CTX_get(ctx);
 941     if (bY == NULL)
 942         goto err;
 943
 944     if (!EC_POINT_get_affine_coordinates_GF2m(group, a, aX, aY, ctx))
 945         goto err;
 946     if (!EC_POINT_get_affine_coordinates_GF2m(group, b, bX, bY, ctx))
 947         goto err;
 948     ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
 949
 950  err:
 951     if (ctx)
 952         BN_CTX_end(ctx);
 953     if (new_ctx)
 954         BN_CTX_free(new_ctx);
 955     return ret;
 956 }
 957
 958 /* Forces the given EC_POINT to internally use affine coordinates. */
 959 int ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
 960                                BN_CTX *ctx)
 961 {
 962     BN_CTX *new_ctx = NULL;
 963     BIGNUM *x, *y;
 964     int ret = 0;
 965
 966     if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
 967         return 1;
 968
 969     if (ctx == NULL) {
 970         ctx = new_ctx = BN_CTX_new();
 971         if (ctx == NULL)
 972             return 0;
 973     }
 974
 975     BN_CTX_start(ctx);
 976     x = BN_CTX_get(ctx);
 977     y = BN_CTX_get(ctx);
 978     if (y == NULL)
 979         goto err;
 980
 981     if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx))
 982         goto err;
 983     if (!BN_copy(&point->X, x))
 984         goto err;
 985     if (!BN_copy(&point->Y, y))
 986         goto err;
 987     if (!BN_one(&point->Z))
 988         goto err;
 989
 990     ret = 1;
 991
 992  err:
 993     if (ctx)
 994         BN_CTX_end(ctx);
 995     if (new_ctx)
 996         BN_CTX_free(new_ctx);
 997     return ret;
 998 }
 999
1000 /*
1001  * Forces each of the EC_POINTs in the given array to use affine coordinates.
1002  */
1003 int ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num,
1004                                       EC_POINT *points[], BN_CTX *ctx)
1005 {
1006     size_t i;
1007
1008     for (i = 0; i < num; i++) {
1009         if (!group->meth->make_affine(group, points[i], ctx))
1010             return 0;
1011     }
1012
1013     return 1;
1014 }
1015
1016 /* Wrapper to simple binary polynomial field multiplication implementation. */
1017 int ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r,
1018                              const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
1019 {
1020     return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
1021 }
1022
1023 /* Wrapper to simple binary polynomial field squaring implementation. */
1024 int ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r,
1025                              const BIGNUM *a, BN_CTX *ctx)
1026 {
1027     return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
1028 }
1029
1030 /* Wrapper to simple binary polynomial field division implementation. */
1031 int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r,
1032                              const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
1033 {
1034     return BN_GF2m_mod_div(r, a, b, &group->field, ctx);
1035 }