crypto/ec/ec2_smpl.c

   1 /*
   2  * Copyright 2002-2020 The OpenSSL Project Authors. All Rights Reserved.
   3  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
   4  *
   5  * Licensed under the Apache License 2.0 (the "License").  You may not use
   6  * this file except in compliance with the License.  You can obtain a copy
   7  * in the file LICENSE in the source distribution or at
   8  * https://www.openssl.org/source/license.html
   9  */
  10
  11 /*
  12  * ECDSA low level APIs are deprecated for public use, but still ok for
  13  * internal use.
  14  */
  15 #include "internal/deprecated.h"
  16
  17 #include <openssl/err.h>
  18
  19 #include "crypto/bn.h"
  20 #include "ec_local.h"
  21
  22 #ifndef OPENSSL_NO_EC2M
  23
  24 /*
  25  * Initialize a GF(2^m)-based EC_GROUP structure. Note that all other members
  26  * are handled by EC_GROUP_new.
  27  */
  28 int ec_GF2m_simple_group_init(EC_GROUP *group)
  29 {
  30     group->field = BN_new();
  31     group->a = BN_new();
  32     group->b = BN_new();
  33
  34     if (group->field == NULL || group->a == NULL || group->b == NULL) {
  35         BN_free(group->field);
  36         BN_free(group->a);
  37         BN_free(group->b);
  38         return 0;
  39     }
  40     return 1;
  41 }
  42
  43 /*
  44  * Free a GF(2^m)-based EC_GROUP structure. Note that all other members are
  45  * handled by EC_GROUP_free.
  46  */
  47 void ec_GF2m_simple_group_finish(EC_GROUP *group)
  48 {
  49     BN_free(group->field);
  50     BN_free(group->a);
  51     BN_free(group->b);
  52 }
  53
  54 /*
  55  * Clear and free a GF(2^m)-based EC_GROUP structure. Note that all other
  56  * members are handled by EC_GROUP_clear_free.
  57  */
  58 void ec_GF2m_simple_group_clear_finish(EC_GROUP *group)
  59 {
  60     BN_clear_free(group->field);
  61     BN_clear_free(group->a);
  62     BN_clear_free(group->b);
  63     group->poly[0] = 0;
  64     group->poly[1] = 0;
  65     group->poly[2] = 0;
  66     group->poly[3] = 0;
  67     group->poly[4] = 0;
  68     group->poly[5] = -1;
  69 }
  70
  71 /*
  72  * Copy a GF(2^m)-based EC_GROUP structure. Note that all other members are
  73  * handled by EC_GROUP_copy.
  74  */
  75 int ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
  76 {
  77     if (!BN_copy(dest->field, src->field))
  78         return 0;
  79     if (!BN_copy(dest->a, src->a))
  80         return 0;
  81     if (!BN_copy(dest->b, src->b))
  82         return 0;
  83     dest->poly[0] = src->poly[0];
  84     dest->poly[1] = src->poly[1];
  85     dest->poly[2] = src->poly[2];
  86     dest->poly[3] = src->poly[3];
  87     dest->poly[4] = src->poly[4];
  88     dest->poly[5] = src->poly[5];
  89     if (bn_wexpand(dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) ==
  90         NULL)
  91         return 0;
  92     if (bn_wexpand(dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) ==
  93         NULL)
  94         return 0;
  95     bn_set_all_zero(dest->a);
  96     bn_set_all_zero(dest->b);
  97     return 1;
  98 }
  99
 100 /* Set the curve parameters of an EC_GROUP structure. */
 101 int ec_GF2m_simple_group_set_curve(EC_GROUP *group,
 102                                    const BIGNUM *p, const BIGNUM *a,
 103                                    const BIGNUM *b, BN_CTX *ctx)
 104 {
 105     int ret = 0, i;
 106
 107     /* group->field */
 108     if (!BN_copy(group->field, p))
 109         goto err;
 110     i = BN_GF2m_poly2arr(group->field, group->poly, 6) - 1;
 111     if ((i != 5) && (i != 3)) {
 112         ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIELD);
 113         goto err;
 114     }
 115
 116     /* group->a */
 117     if (!BN_GF2m_mod_arr(group->a, a, group->poly))
 118         goto err;
 119     if (bn_wexpand(group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
 120         == NULL)
 121         goto err;
 122     bn_set_all_zero(group->a);
 123
 124     /* group->b */
 125     if (!BN_GF2m_mod_arr(group->b, b, group->poly))
 126         goto err;
 127     if (bn_wexpand(group->b, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2)
 128         == NULL)
 129         goto err;
 130     bn_set_all_zero(group->b);
 131
 132     ret = 1;
 133  err:
 134     return ret;
 135 }
 136
 137 /*
 138  * Get the curve parameters of an EC_GROUP structure. If p, a, or b are NULL
 139  * then there values will not be set but the method will return with success.
 140  */
 141 int ec_GF2m_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p,
 142                                    BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
 143 {
 144     int ret = 0;
 145
 146     if (p != NULL) {
 147         if (!BN_copy(p, group->field))
 148             return 0;
 149     }
 150
 151     if (a != NULL) {
 152         if (!BN_copy(a, group->a))
 153             goto err;
 154     }
 155
 156     if (b != NULL) {
 157         if (!BN_copy(b, group->b))
 158             goto err;
 159     }
 160
 161     ret = 1;
 162
 163  err:
 164     return ret;
 165 }
 166
 167 /*
 168  * Gets the degree of the field.  For a curve over GF(2^m) this is the value
 169  * m.
 170  */
 171 int ec_GF2m_simple_group_get_degree(const EC_GROUP *group)
 172 {
 173     return BN_num_bits(group->field) - 1;
 174 }
 175
 176 /*
 177  * Checks the discriminant of the curve. y^2 + x*y = x^3 + a*x^2 + b is an
 178  * elliptic curve <=> b != 0 (mod p)
 179  */
 180 int ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group,
 181                                             BN_CTX *ctx)
 182 {
 183     int ret = 0;
 184     BIGNUM *b;
 185 #ifndef FIPS_MODULE
 186     BN_CTX *new_ctx = NULL;
 187
 188     if (ctx == NULL) {
 189         ctx = new_ctx = BN_CTX_new();
 190         if (ctx == NULL) {
 191             ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT,
 192                   ERR_R_MALLOC_FAILURE);
 193             goto err;
 194         }
 195     }
 196 #endif
 197     BN_CTX_start(ctx);
 198     b = BN_CTX_get(ctx);
 199     if (b == NULL)
 200         goto err;
 201
 202     if (!BN_GF2m_mod_arr(b, group->b, group->poly))
 203         goto err;
 204
 205     /*
 206      * check the discriminant: y^2 + x*y = x^3 + a*x^2 + b is an elliptic
 207      * curve <=> b != 0 (mod p)
 208      */
 209     if (BN_is_zero(b))
 210         goto err;
 211
 212     ret = 1;
 213
 214  err:
 215     BN_CTX_end(ctx);
 216 #ifndef FIPS_MODULE
 217     BN_CTX_free(new_ctx);
 218 #endif
 219     return ret;
 220 }
 221
 222 /* Initializes an EC_POINT. */
 223 int ec_GF2m_simple_point_init(EC_POINT *point)
 224 {
 225     point->X = BN_new();
 226     point->Y = BN_new();
 227     point->Z = BN_new();
 228
 229     if (point->X == NULL || point->Y == NULL || point->Z == NULL) {
 230         BN_free(point->X);
 231         BN_free(point->Y);
 232         BN_free(point->Z);
 233         return 0;
 234     }
 235     return 1;
 236 }
 237
 238 /* Frees an EC_POINT. */
 239 void ec_GF2m_simple_point_finish(EC_POINT *point)
 240 {
 241     BN_free(point->X);
 242     BN_free(point->Y);
 243     BN_free(point->Z);
 244 }
 245
 246 /* Clears and frees an EC_POINT. */
 247 void ec_GF2m_simple_point_clear_finish(EC_POINT *point)
 248 {
 249     BN_clear_free(point->X);
 250     BN_clear_free(point->Y);
 251     BN_clear_free(point->Z);
 252     point->Z_is_one = 0;
 253 }
 254
 255 /*
 256  * Copy the contents of one EC_POINT into another.  Assumes dest is
 257  * initialized.
 258  */
 259 int ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
 260 {
 261     if (!BN_copy(dest->X, src->X))
 262         return 0;
 263     if (!BN_copy(dest->Y, src->Y))
 264         return 0;
 265     if (!BN_copy(dest->Z, src->Z))
 266         return 0;
 267     dest->Z_is_one = src->Z_is_one;
 268     dest->curve_name = src->curve_name;
 269
 270     return 1;
 271 }
 272
 273 /*
 274  * Set an EC_POINT to the point at infinity. A point at infinity is
 275  * represented by having Z=0.
 276  */
 277 int ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group,
 278                                          EC_POINT *point)
 279 {
 280     point->Z_is_one = 0;
 281     BN_zero(point->Z);
 282     return 1;
 283 }
 284
 285 /*
 286  * Set the coordinates of an EC_POINT using affine coordinates. Note that
 287  * the simple implementation only uses affine coordinates.
 288  */
 289 int ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group,
 290                                                 EC_POINT *point,
 291                                                 const BIGNUM *x,
 292                                                 const BIGNUM *y, BN_CTX *ctx)
 293 {
 294     int ret = 0;
 295     if (x == NULL || y == NULL) {
 296         ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES,
 297               ERR_R_PASSED_NULL_PARAMETER);
 298         return 0;
 299     }
 300
 301     if (!BN_copy(point->X, x))
 302         goto err;
 303     BN_set_negative(point->X, 0);
 304     if (!BN_copy(point->Y, y))
 305         goto err;
 306     BN_set_negative(point->Y, 0);
 307     if (!BN_copy(point->Z, BN_value_one()))
 308         goto err;
 309     BN_set_negative(point->Z, 0);
 310     point->Z_is_one = 1;
 311     ret = 1;
 312
 313  err:
 314     return ret;
 315 }
 316
 317 /*
 318  * Gets the affine coordinates of an EC_POINT. Note that the simple
 319  * implementation only uses affine coordinates.
 320  */
 321 int ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group,
 322                                                 const EC_POINT *point,
 323                                                 BIGNUM *x, BIGNUM *y,
 324                                                 BN_CTX *ctx)
 325 {
 326     int ret = 0;
 327
 328     if (EC_POINT_is_at_infinity(group, point)) {
 329         ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES,
 330               EC_R_POINT_AT_INFINITY);
 331         return 0;
 332     }
 333
 334     if (BN_cmp(point->Z, BN_value_one())) {
 335         ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES,
 336               ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
 337         return 0;
 338     }
 339     if (x != NULL) {
 340         if (!BN_copy(x, point->X))
 341             goto err;
 342         BN_set_negative(x, 0);
 343     }
 344     if (y != NULL) {
 345         if (!BN_copy(y, point->Y))
 346             goto err;
 347         BN_set_negative(y, 0);
 348     }
 349     ret = 1;
 350
 351  err:
 352     return ret;
 353 }
 354
 355 /*
 356  * Computes a + b and stores the result in r.  r could be a or b, a could be
 357  * b. Uses algorithm A.10.2 of IEEE P1363.
 358  */
 359 int ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
 360                        const EC_POINT *b, BN_CTX *ctx)
 361 {
 362     BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t;
 363     int ret = 0;
 364 #ifndef FIPS_MODULE
 365     BN_CTX *new_ctx = NULL;
 366 #endif
 367
 368     if (EC_POINT_is_at_infinity(group, a)) {
 369         if (!EC_POINT_copy(r, b))
 370             return 0;
 371         return 1;
 372     }
 373
 374     if (EC_POINT_is_at_infinity(group, b)) {
 375         if (!EC_POINT_copy(r, a))
 376             return 0;
 377         return 1;
 378     }
 379
 380 #ifndef FIPS_MODULE
 381     if (ctx == NULL) {
 382         ctx = new_ctx = BN_CTX_new();
 383         if (ctx == NULL)
 384             return 0;
 385     }
 386 #endif
 387
 388     BN_CTX_start(ctx);
 389     x0 = BN_CTX_get(ctx);
 390     y0 = BN_CTX_get(ctx);
 391     x1 = BN_CTX_get(ctx);
 392     y1 = BN_CTX_get(ctx);
 393     x2 = BN_CTX_get(ctx);
 394     y2 = BN_CTX_get(ctx);
 395     s = BN_CTX_get(ctx);
 396     t = BN_CTX_get(ctx);
 397     if (t == NULL)
 398         goto err;
 399
 400     if (a->Z_is_one) {
 401         if (!BN_copy(x0, a->X))
 402             goto err;
 403         if (!BN_copy(y0, a->Y))
 404             goto err;
 405     } else {
 406         if (!EC_POINT_get_affine_coordinates(group, a, x0, y0, ctx))
 407             goto err;
 408     }
 409     if (b->Z_is_one) {
 410         if (!BN_copy(x1, b->X))
 411             goto err;
 412         if (!BN_copy(y1, b->Y))
 413             goto err;
 414     } else {
 415         if (!EC_POINT_get_affine_coordinates(group, b, x1, y1, ctx))
 416             goto err;
 417     }
 418
 419     if (BN_GF2m_cmp(x0, x1)) {
 420         if (!BN_GF2m_add(t, x0, x1))
 421             goto err;
 422         if (!BN_GF2m_add(s, y0, y1))
 423             goto err;
 424         if (!group->meth->field_div(group, s, s, t, ctx))
 425             goto err;
 426         if (!group->meth->field_sqr(group, x2, s, ctx))
 427             goto err;
 428         if (!BN_GF2m_add(x2, x2, group->a))
 429             goto err;
 430         if (!BN_GF2m_add(x2, x2, s))
 431             goto err;
 432         if (!BN_GF2m_add(x2, x2, t))
 433             goto err;
 434     } else {
 435         if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) {
 436             if (!EC_POINT_set_to_infinity(group, r))
 437                 goto err;
 438             ret = 1;
 439             goto err;
 440         }
 441         if (!group->meth->field_div(group, s, y1, x1, ctx))
 442             goto err;
 443         if (!BN_GF2m_add(s, s, x1))
 444             goto err;
 445
 446         if (!group->meth->field_sqr(group, x2, s, ctx))
 447             goto err;
 448         if (!BN_GF2m_add(x2, x2, s))
 449             goto err;
 450         if (!BN_GF2m_add(x2, x2, group->a))
 451             goto err;
 452     }
 453
 454     if (!BN_GF2m_add(y2, x1, x2))
 455         goto err;
 456     if (!group->meth->field_mul(group, y2, y2, s, ctx))
 457         goto err;
 458     if (!BN_GF2m_add(y2, y2, x2))
 459         goto err;
 460     if (!BN_GF2m_add(y2, y2, y1))
 461         goto err;
 462
 463     if (!EC_POINT_set_affine_coordinates(group, r, x2, y2, ctx))
 464         goto err;
 465
 466     ret = 1;
 467
 468  err:
 469     BN_CTX_end(ctx);
 470 #ifndef FIPS_MODULE
 471     BN_CTX_free(new_ctx);
 472 #endif
 473     return ret;
 474 }
 475
 476 /*
 477  * Computes 2 * a and stores the result in r.  r could be a. Uses algorithm
 478  * A.10.2 of IEEE P1363.
 479  */
 480 int ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
 481                        BN_CTX *ctx)
 482 {
 483     return ec_GF2m_simple_add(group, r, a, a, ctx);
 484 }
 485
 486 int ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
 487 {
 488     if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
 489         /* point is its own inverse */
 490         return 1;
 491
 492     if (group->meth->make_affine == NULL
 493         || !group->meth->make_affine(group, point, ctx))
 494         return 0;
 495     return BN_GF2m_add(point->Y, point->X, point->Y);
 496 }
 497
 498 /* Indicates whether the given point is the point at infinity. */
 499 int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group,
 500                                   const EC_POINT *point)
 501 {
 502     return BN_is_zero(point->Z);
 503 }
 504
 505 /*-
 506  * Determines whether the given EC_POINT is an actual point on the curve defined
 507  * in the EC_GROUP.  A point is valid if it satisfies the Weierstrass equation:
 508  *      y^2 + x*y = x^3 + a*x^2 + b.
 509  */
 510 int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
 511                                BN_CTX *ctx)
 512 {
 513     int ret = -1;
 514     BIGNUM *lh, *y2;
 515     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
 516                       const BIGNUM *, BN_CTX *);
 517     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 518 #ifndef FIPS_MODULE
 519     BN_CTX *new_ctx = NULL;
 520 #endif
 521
 522     if (EC_POINT_is_at_infinity(group, point))
 523         return 1;
 524
 525     field_mul = group->meth->field_mul;
 526     field_sqr = group->meth->field_sqr;
 527
 528     /* only support affine coordinates */
 529     if (!point->Z_is_one)
 530         return -1;
 531
 532 #ifndef FIPS_MODULE
 533     if (ctx == NULL) {
 534         ctx = new_ctx = BN_CTX_new();
 535         if (ctx == NULL)
 536             return -1;
 537     }
 538 #endif
 539
 540     BN_CTX_start(ctx);
 541     y2 = BN_CTX_get(ctx);
 542     lh = BN_CTX_get(ctx);
 543     if (lh == NULL)
 544         goto err;
 545
 546     /*-
 547      * We have a curve defined by a Weierstrass equation
 548      *      y^2 + x*y = x^3 + a*x^2 + b.
 549      *  <=> x^3 + a*x^2 + x*y + b + y^2 = 0
 550      *  <=> ((x + a) * x + y ) * x + b + y^2 = 0
 551      */
 552     if (!BN_GF2m_add(lh, point->X, group->a))
 553         goto err;
 554     if (!field_mul(group, lh, lh, point->X, ctx))
 555         goto err;
 556     if (!BN_GF2m_add(lh, lh, point->Y))
 557         goto err;
 558     if (!field_mul(group, lh, lh, point->X, ctx))
 559         goto err;
 560     if (!BN_GF2m_add(lh, lh, group->b))
 561         goto err;
 562     if (!field_sqr(group, y2, point->Y, ctx))
 563         goto err;
 564     if (!BN_GF2m_add(lh, lh, y2))
 565         goto err;
 566     ret = BN_is_zero(lh);
 567
 568  err:
 569     BN_CTX_end(ctx);
 570 #ifndef FIPS_MODULE
 571     BN_CTX_free(new_ctx);
 572 #endif
 573     return ret;
 574 }
 575
 576 /*-
 577  * Indicates whether two points are equal.
 578  * Return values:
 579  *  -1   error
 580  *   0   equal (in affine coordinates)
 581  *   1   not equal
 582  */
 583 int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
 584                        const EC_POINT *b, BN_CTX *ctx)
 585 {
 586     BIGNUM *aX, *aY, *bX, *bY;
 587     int ret = -1;
 588 #ifndef FIPS_MODULE
 589     BN_CTX *new_ctx = NULL;
 590 #endif
 591
 592     if (EC_POINT_is_at_infinity(group, a)) {
 593         return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
 594     }
 595
 596     if (EC_POINT_is_at_infinity(group, b))
 597         return 1;
 598
 599     if (a->Z_is_one && b->Z_is_one) {
 600         return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
 601     }
 602
 603 #ifndef FIPS_MODULE
 604     if (ctx == NULL) {
 605         ctx = new_ctx = BN_CTX_new();
 606         if (ctx == NULL)
 607             return -1;
 608     }
 609 #endif
 610
 611     BN_CTX_start(ctx);
 612     aX = BN_CTX_get(ctx);
 613     aY = BN_CTX_get(ctx);
 614     bX = BN_CTX_get(ctx);
 615     bY = BN_CTX_get(ctx);
 616     if (bY == NULL)
 617         goto err;
 618
 619     if (!EC_POINT_get_affine_coordinates(group, a, aX, aY, ctx))
 620         goto err;
 621     if (!EC_POINT_get_affine_coordinates(group, b, bX, bY, ctx))
 622         goto err;
 623     ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
 624
 625  err:
 626     BN_CTX_end(ctx);
 627 #ifndef FIPS_MODULE
 628     BN_CTX_free(new_ctx);
 629 #endif
 630     return ret;
 631 }
 632
 633 /* Forces the given EC_POINT to internally use affine coordinates. */
 634 int ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
 635                                BN_CTX *ctx)
 636 {
 637     BIGNUM *x, *y;
 638     int ret = 0;
 639 #ifndef FIPS_MODULE
 640     BN_CTX *new_ctx = NULL;
 641 #endif
 642
 643     if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
 644         return 1;
 645
 646 #ifndef FIPS_MODULE
 647     if (ctx == NULL) {
 648         ctx = new_ctx = BN_CTX_new();
 649         if (ctx == NULL)
 650             return 0;
 651     }
 652 #endif
 653
 654     BN_CTX_start(ctx);
 655     x = BN_CTX_get(ctx);
 656     y = BN_CTX_get(ctx);
 657     if (y == NULL)
 658         goto err;
 659
 660     if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
 661         goto err;
 662     if (!BN_copy(point->X, x))
 663         goto err;
 664     if (!BN_copy(point->Y, y))
 665         goto err;
 666     if (!BN_one(point->Z))
 667         goto err;
 668     point->Z_is_one = 1;
 669
 670     ret = 1;
 671
 672  err:
 673     BN_CTX_end(ctx);
 674 #ifndef FIPS_MODULE
 675     BN_CTX_free(new_ctx);
 676 #endif
 677     return ret;
 678 }
 679
 680 /*
 681  * Forces each of the EC_POINTs in the given array to use affine coordinates.
 682  */
 683 int ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num,
 684                                       EC_POINT *points[], BN_CTX *ctx)
 685 {
 686     size_t i;
 687
 688     for (i = 0; i < num; i++) {
 689         if (!group->meth->make_affine(group, points[i], ctx))
 690             return 0;
 691     }
 692
 693     return 1;
 694 }
 695
 696 /* Wrapper to simple binary polynomial field multiplication implementation. */
 697 int ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r,
 698                              const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 699 {
 700     return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
 701 }
 702
 703 /* Wrapper to simple binary polynomial field squaring implementation. */
 704 int ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r,
 705                              const BIGNUM *a, BN_CTX *ctx)
 706 {
 707     return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
 708 }
 709
 710 /* Wrapper to simple binary polynomial field division implementation. */
 711 int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r,
 712                              const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 713 {
 714     return BN_GF2m_mod_div(r, a, b, group->field, ctx);
 715 }
 716
 717 /*-
 718  * Lopez-Dahab ladder, pre step.
 719  * See e.g. "Guide to ECC" Alg 3.40.
 720  * Modified to blind s and r independently.
 721  * s:= p, r := 2p
 722  */
 723 static
 724 int ec_GF2m_simple_ladder_pre(const EC_GROUP *group,
 725                               EC_POINT *r, EC_POINT *s,
 726                               EC_POINT *p, BN_CTX *ctx)
 727 {
 728     /* if p is not affine, something is wrong */
 729     if (p->Z_is_one == 0)
 730         return 0;
 731
 732     /* s blinding: make sure lambda (s->Z here) is not zero */
 733     do {
 734         if (!BN_priv_rand_ex(s->Z, BN_num_bits(group->field) - 1,
 735                              BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, ctx)) {
 736             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
 737             return 0;
 738         }
 739     } while (BN_is_zero(s->Z));
 740
 741     /* if field_encode defined convert between representations */
 742     if ((group->meth->field_encode != NULL
 743          && !group->meth->field_encode(group, s->Z, s->Z, ctx))
 744         || !group->meth->field_mul(group, s->X, p->X, s->Z, ctx))
 745         return 0;
 746
 747     /* r blinding: make sure lambda (r->Y here for storage) is not zero */
 748     do {
 749         if (!BN_priv_rand_ex(r->Y, BN_num_bits(group->field) - 1,
 750                              BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, ctx)) {
 751             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
 752             return 0;
 753         }
 754     } while (BN_is_zero(r->Y));
 755
 756     if ((group->meth->field_encode != NULL
 757          && !group->meth->field_encode(group, r->Y, r->Y, ctx))
 758         || !group->meth->field_sqr(group, r->Z, p->X, ctx)
 759         || !group->meth->field_sqr(group, r->X, r->Z, ctx)
 760         || !BN_GF2m_add(r->X, r->X, group->b)
 761         || !group->meth->field_mul(group, r->Z, r->Z, r->Y, ctx)
 762         || !group->meth->field_mul(group, r->X, r->X, r->Y, ctx))
 763         return 0;
 764
 765     s->Z_is_one = 0;
 766     r->Z_is_one = 0;
 767
 768     return 1;
 769 }
 770
 771 /*-
 772  * Ladder step: differential addition-and-doubling, mixed Lopez-Dahab coords.
 773  * http://www.hyperelliptic.org/EFD/g12o/auto-code/shortw/xz/ladder/mladd-2003-s.op3
 774  * s := r + s, r := 2r
 775  */
 776 static
 777 int ec_GF2m_simple_ladder_step(const EC_GROUP *group,
 778                                EC_POINT *r, EC_POINT *s,
 779                                EC_POINT *p, BN_CTX *ctx)
 780 {
 781     if (!group->meth->field_mul(group, r->Y, r->Z, s->X, ctx)
 782         || !group->meth->field_mul(group, s->X, r->X, s->Z, ctx)
 783         || !group->meth->field_sqr(group, s->Y, r->Z, ctx)
 784         || !group->meth->field_sqr(group, r->Z, r->X, ctx)
 785         || !BN_GF2m_add(s->Z, r->Y, s->X)
 786         || !group->meth->field_sqr(group, s->Z, s->Z, ctx)
 787         || !group->meth->field_mul(group, s->X, r->Y, s->X, ctx)
 788         || !group->meth->field_mul(group, r->Y, s->Z, p->X, ctx)
 789         || !BN_GF2m_add(s->X, s->X, r->Y)
 790         || !group->meth->field_sqr(group, r->Y, r->Z, ctx)
 791         || !group->meth->field_mul(group, r->Z, r->Z, s->Y, ctx)
 792         || !group->meth->field_sqr(group, s->Y, s->Y, ctx)
 793         || !group->meth->field_mul(group, s->Y, s->Y, group->b, ctx)
 794         || !BN_GF2m_add(r->X, r->Y, s->Y))
 795         return 0;
 796
 797     return 1;
 798 }
 799
 800 /*-
 801  * Recover affine (x,y) result from Lopez-Dahab r and s, affine p.
 802  * See e.g. "Fast Multiplication on Elliptic Curves over GF(2**m)
 803  * without Precomputation" (Lopez and Dahab, CHES 1999),
 804  * Appendix Alg Mxy.
 805  */
 806 static
 807 int ec_GF2m_simple_ladder_post(const EC_GROUP *group,
 808                                EC_POINT *r, EC_POINT *s,
 809                                EC_POINT *p, BN_CTX *ctx)
 810 {
 811     int ret = 0;
 812     BIGNUM *t0, *t1, *t2 = NULL;
 813
 814     if (BN_is_zero(r->Z))
 815         return EC_POINT_set_to_infinity(group, r);
 816
 817     if (BN_is_zero(s->Z)) {
 818         if (!EC_POINT_copy(r, p)
 819             || !EC_POINT_invert(group, r, ctx)) {
 820             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_EC_LIB);
 821             return 0;
 822         }
 823         return 1;
 824     }
 825
 826     BN_CTX_start(ctx);
 827     t0 = BN_CTX_get(ctx);
 828     t1 = BN_CTX_get(ctx);
 829     t2 = BN_CTX_get(ctx);
 830     if (t2 == NULL) {
 831         ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_MALLOC_FAILURE);
 832         goto err;
 833     }
 834
 835     if (!group->meth->field_mul(group, t0, r->Z, s->Z, ctx)
 836         || !group->meth->field_mul(group, t1, p->X, r->Z, ctx)
 837         || !BN_GF2m_add(t1, r->X, t1)
 838         || !group->meth->field_mul(group, t2, p->X, s->Z, ctx)
 839         || !group->meth->field_mul(group, r->Z, r->X, t2, ctx)
 840         || !BN_GF2m_add(t2, t2, s->X)
 841         || !group->meth->field_mul(group, t1, t1, t2, ctx)
 842         || !group->meth->field_sqr(group, t2, p->X, ctx)
 843         || !BN_GF2m_add(t2, p->Y, t2)
 844         || !group->meth->field_mul(group, t2, t2, t0, ctx)
 845         || !BN_GF2m_add(t1, t2, t1)
 846         || !group->meth->field_mul(group, t2, p->X, t0, ctx)
 847         || !group->meth->field_inv(group, t2, t2, ctx)
 848         || !group->meth->field_mul(group, t1, t1, t2, ctx)
 849         || !group->meth->field_mul(group, r->X, r->Z, t2, ctx)
 850         || !BN_GF2m_add(t2, p->X, r->X)
 851         || !group->meth->field_mul(group, t2, t2, t1, ctx)
 852         || !BN_GF2m_add(r->Y, p->Y, t2)
 853         || !BN_one(r->Z))
 854         goto err;
 855
 856     r->Z_is_one = 1;
 857
 858     /* GF(2^m) field elements should always have BIGNUM::neg = 0 */
 859     BN_set_negative(r->X, 0);
 860     BN_set_negative(r->Y, 0);
 861
 862     ret = 1;
 863
 864  err:
 865     BN_CTX_end(ctx);
 866     return ret;
 867 }
 868
 869 static
 870 int ec_GF2m_simple_points_mul(const EC_GROUP *group, EC_POINT *r,
 871                               const BIGNUM *scalar, size_t num,
 872                               const EC_POINT *points[],
 873                               const BIGNUM *scalars[],
 874                               BN_CTX *ctx)
 875 {
 876     int ret = 0;
 877     EC_POINT *t = NULL;
 878
 879     /*-
 880      * We limit use of the ladder only to the following cases:
 881      * - r := scalar * G
 882      *   Fixed point mul: scalar != NULL && num == 0;
 883      * - r := scalars[0] * points[0]
 884      *   Variable point mul: scalar == NULL && num == 1;
 885      * - r := scalar * G + scalars[0] * points[0]
 886      *   used, e.g., in ECDSA verification: scalar != NULL && num == 1
 887      *
 888      * In any other case (num > 1) we use the default wNAF implementation.
 889      *
 890      * We also let the default implementation handle degenerate cases like group
 891      * order or cofactor set to 0.
 892      */
 893     if (num > 1 || BN_is_zero(group->order) || BN_is_zero(group->cofactor))
 894         return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
 895
 896     if (scalar != NULL && num == 0)
 897         /* Fixed point multiplication */
 898         return ec_scalar_mul_ladder(group, r, scalar, NULL, ctx);
 899
 900     if (scalar == NULL && num == 1)
 901         /* Variable point multiplication */
 902         return ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx);
 903
 904     /*-
 905      * Double point multiplication:
 906      *  r := scalar * G + scalars[0] * points[0]
 907      */
 908
 909     if ((t = EC_POINT_new(group)) == NULL) {
 910         ECerr(EC_F_EC_GF2M_SIMPLE_POINTS_MUL, ERR_R_MALLOC_FAILURE);
 911         return 0;
 912     }
 913
 914     if (!ec_scalar_mul_ladder(group, t, scalar, NULL, ctx)
 915         || !ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx)
 916         || !EC_POINT_add(group, r, t, r, ctx))
 917         goto err;
 918
 919     ret = 1;
 920
 921  err:
 922     EC_POINT_free(t);
 923     return ret;
 924 }
 925
 926 /*-
 927  * Computes the multiplicative inverse of a in GF(2^m), storing the result in r.
 928  * If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error.
 929  * SCA hardening is with blinding: BN_GF2m_mod_inv does that.
 930  */
 931 static int ec_GF2m_simple_field_inv(const EC_GROUP *group, BIGNUM *r,
 932                                     const BIGNUM *a, BN_CTX *ctx)
 933 {
 934     int ret;
 935
 936     if (!(ret = BN_GF2m_mod_inv(r, a, group->field, ctx)))
 937         ECerr(EC_F_EC_GF2M_SIMPLE_FIELD_INV, EC_R_CANNOT_INVERT);
 938     return ret;
 939 }
 940
 941 const EC_METHOD *EC_GF2m_simple_method(void)
 942 {
 943     static const EC_METHOD ret = {
 944         EC_FLAGS_DEFAULT_OCT,
 945         NID_X9_62_characteristic_two_field,
 946         ec_GF2m_simple_group_init,
 947         ec_GF2m_simple_group_finish,
 948         ec_GF2m_simple_group_clear_finish,
 949         ec_GF2m_simple_group_copy,
 950         ec_GF2m_simple_group_set_curve,
 951         ec_GF2m_simple_group_get_curve,
 952         ec_GF2m_simple_group_get_degree,
 953         ec_group_simple_order_bits,
 954         ec_GF2m_simple_group_check_discriminant,
 955         ec_GF2m_simple_point_init,
 956         ec_GF2m_simple_point_finish,
 957         ec_GF2m_simple_point_clear_finish,
 958         ec_GF2m_simple_point_copy,
 959         ec_GF2m_simple_point_set_to_infinity,
 960         ec_GF2m_simple_point_set_affine_coordinates,
 961         ec_GF2m_simple_point_get_affine_coordinates,
 962         0, /* point_set_compressed_coordinates */
 963         0, /* point2oct */
 964         0, /* oct2point */
 965         ec_GF2m_simple_add,
 966         ec_GF2m_simple_dbl,
 967         ec_GF2m_simple_invert,
 968         ec_GF2m_simple_is_at_infinity,
 969         ec_GF2m_simple_is_on_curve,
 970         ec_GF2m_simple_cmp,
 971         ec_GF2m_simple_make_affine,
 972         ec_GF2m_simple_points_make_affine,
 973         ec_GF2m_simple_points_mul,
 974         0, /* precompute_mult */
 975         0, /* have_precompute_mult */
 976         ec_GF2m_simple_field_mul,
 977         ec_GF2m_simple_field_sqr,
 978         ec_GF2m_simple_field_div,
 979         ec_GF2m_simple_field_inv,
 980         0, /* field_encode */
 981         0, /* field_decode */
 982         0, /* field_set_to_one */
 983         ec_key_simple_priv2oct,
 984         ec_key_simple_oct2priv,
 985         0, /* set private */
 986         ec_key_simple_generate_key,
 987         ec_key_simple_check_key,
 988         ec_key_simple_generate_public_key,
 989         0, /* keycopy */
 990         0, /* keyfinish */
 991         ecdh_simple_compute_key,
 992         ecdsa_simple_sign_setup,
 993         ecdsa_simple_sign_sig,
 994         ecdsa_simple_verify_sig,
 995         0, /* field_inverse_mod_ord */
 996         0, /* blind_coordinates */
 997         ec_GF2m_simple_ladder_pre,
 998         ec_GF2m_simple_ladder_step,
 999         ec_GF2m_simple_ladder_post
1000     };
1001
1002     return &ret;
1003 }
1004
1005 #endif