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 (!EC_POINT_make_affine(group, point, ctx))
 493         return 0;
 494     return BN_GF2m_add(point->Y, point->X, point->Y);
 495 }
 496
 497 /* Indicates whether the given point is the point at infinity. */
 498 int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group,
 499                                   const EC_POINT *point)
 500 {
 501     return BN_is_zero(point->Z);
 502 }
 503
 504 /*-
 505  * Determines whether the given EC_POINT is an actual point on the curve defined
 506  * in the EC_GROUP.  A point is valid if it satisfies the Weierstrass equation:
 507  *      y^2 + x*y = x^3 + a*x^2 + b.
 508  */
 509 int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
 510                                BN_CTX *ctx)
 511 {
 512     int ret = -1;
 513     BIGNUM *lh, *y2;
 514     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
 515                       const BIGNUM *, BN_CTX *);
 516     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 517 #ifndef FIPS_MODULE
 518     BN_CTX *new_ctx = NULL;
 519 #endif
 520
 521     if (EC_POINT_is_at_infinity(group, point))
 522         return 1;
 523
 524     field_mul = group->meth->field_mul;
 525     field_sqr = group->meth->field_sqr;
 526
 527     /* only support affine coordinates */
 528     if (!point->Z_is_one)
 529         return -1;
 530
 531 #ifndef FIPS_MODULE
 532     if (ctx == NULL) {
 533         ctx = new_ctx = BN_CTX_new();
 534         if (ctx == NULL)
 535             return -1;
 536     }
 537 #endif
 538
 539     BN_CTX_start(ctx);
 540     y2 = BN_CTX_get(ctx);
 541     lh = BN_CTX_get(ctx);
 542     if (lh == NULL)
 543         goto err;
 544
 545     /*-
 546      * We have a curve defined by a Weierstrass equation
 547      *      y^2 + x*y = x^3 + a*x^2 + b.
 548      *  <=> x^3 + a*x^2 + x*y + b + y^2 = 0
 549      *  <=> ((x + a) * x + y ) * x + b + y^2 = 0
 550      */
 551     if (!BN_GF2m_add(lh, point->X, group->a))
 552         goto err;
 553     if (!field_mul(group, lh, lh, point->X, ctx))
 554         goto err;
 555     if (!BN_GF2m_add(lh, lh, point->Y))
 556         goto err;
 557     if (!field_mul(group, lh, lh, point->X, ctx))
 558         goto err;
 559     if (!BN_GF2m_add(lh, lh, group->b))
 560         goto err;
 561     if (!field_sqr(group, y2, point->Y, ctx))
 562         goto err;
 563     if (!BN_GF2m_add(lh, lh, y2))
 564         goto err;
 565     ret = BN_is_zero(lh);
 566
 567  err:
 568     BN_CTX_end(ctx);
 569 #ifndef FIPS_MODULE
 570     BN_CTX_free(new_ctx);
 571 #endif
 572     return ret;
 573 }
 574
 575 /*-
 576  * Indicates whether two points are equal.
 577  * Return values:
 578  *  -1   error
 579  *   0   equal (in affine coordinates)
 580  *   1   not equal
 581  */
 582 int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
 583                        const EC_POINT *b, BN_CTX *ctx)
 584 {
 585     BIGNUM *aX, *aY, *bX, *bY;
 586     int ret = -1;
 587 #ifndef FIPS_MODULE
 588     BN_CTX *new_ctx = NULL;
 589 #endif
 590
 591     if (EC_POINT_is_at_infinity(group, a)) {
 592         return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
 593     }
 594
 595     if (EC_POINT_is_at_infinity(group, b))
 596         return 1;
 597
 598     if (a->Z_is_one && b->Z_is_one) {
 599         return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
 600     }
 601
 602 #ifndef FIPS_MODULE
 603     if (ctx == NULL) {
 604         ctx = new_ctx = BN_CTX_new();
 605         if (ctx == NULL)
 606             return -1;
 607     }
 608 #endif
 609
 610     BN_CTX_start(ctx);
 611     aX = BN_CTX_get(ctx);
 612     aY = BN_CTX_get(ctx);
 613     bX = BN_CTX_get(ctx);
 614     bY = BN_CTX_get(ctx);
 615     if (bY == NULL)
 616         goto err;
 617
 618     if (!EC_POINT_get_affine_coordinates(group, a, aX, aY, ctx))
 619         goto err;
 620     if (!EC_POINT_get_affine_coordinates(group, b, bX, bY, ctx))
 621         goto err;
 622     ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
 623
 624  err:
 625     BN_CTX_end(ctx);
 626 #ifndef FIPS_MODULE
 627     BN_CTX_free(new_ctx);
 628 #endif
 629     return ret;
 630 }
 631
 632 /* Forces the given EC_POINT to internally use affine coordinates. */
 633 int ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
 634                                BN_CTX *ctx)
 635 {
 636     BIGNUM *x, *y;
 637     int ret = 0;
 638 #ifndef FIPS_MODULE
 639     BN_CTX *new_ctx = NULL;
 640 #endif
 641
 642     if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
 643         return 1;
 644
 645 #ifndef FIPS_MODULE
 646     if (ctx == NULL) {
 647         ctx = new_ctx = BN_CTX_new();
 648         if (ctx == NULL)
 649             return 0;
 650     }
 651 #endif
 652
 653     BN_CTX_start(ctx);
 654     x = BN_CTX_get(ctx);
 655     y = BN_CTX_get(ctx);
 656     if (y == NULL)
 657         goto err;
 658
 659     if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
 660         goto err;
 661     if (!BN_copy(point->X, x))
 662         goto err;
 663     if (!BN_copy(point->Y, y))
 664         goto err;
 665     if (!BN_one(point->Z))
 666         goto err;
 667     point->Z_is_one = 1;
 668
 669     ret = 1;
 670
 671  err:
 672     BN_CTX_end(ctx);
 673 #ifndef FIPS_MODULE
 674     BN_CTX_free(new_ctx);
 675 #endif
 676     return ret;
 677 }
 678
 679 /*
 680  * Forces each of the EC_POINTs in the given array to use affine coordinates.
 681  */
 682 int ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num,
 683                                       EC_POINT *points[], BN_CTX *ctx)
 684 {
 685     size_t i;
 686
 687     for (i = 0; i < num; i++) {
 688         if (!group->meth->make_affine(group, points[i], ctx))
 689             return 0;
 690     }
 691
 692     return 1;
 693 }
 694
 695 /* Wrapper to simple binary polynomial field multiplication implementation. */
 696 int ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r,
 697                              const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 698 {
 699     return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
 700 }
 701
 702 /* Wrapper to simple binary polynomial field squaring implementation. */
 703 int ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r,
 704                              const BIGNUM *a, BN_CTX *ctx)
 705 {
 706     return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
 707 }
 708
 709 /* Wrapper to simple binary polynomial field division implementation. */
 710 int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r,
 711                              const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 712 {
 713     return BN_GF2m_mod_div(r, a, b, group->field, ctx);
 714 }
 715
 716 /*-
 717  * Lopez-Dahab ladder, pre step.
 718  * See e.g. "Guide to ECC" Alg 3.40.
 719  * Modified to blind s and r independently.
 720  * s:= p, r := 2p
 721  */
 722 static
 723 int ec_GF2m_simple_ladder_pre(const EC_GROUP *group,
 724                               EC_POINT *r, EC_POINT *s,
 725                               EC_POINT *p, BN_CTX *ctx)
 726 {
 727     /* if p is not affine, something is wrong */
 728     if (p->Z_is_one == 0)
 729         return 0;
 730
 731     /* s blinding: make sure lambda (s->Z here) is not zero */
 732     do {
 733         if (!BN_priv_rand_ex(s->Z, BN_num_bits(group->field) - 1,
 734                              BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, ctx)) {
 735             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
 736             return 0;
 737         }
 738     } while (BN_is_zero(s->Z));
 739
 740     /* if field_encode defined convert between representations */
 741     if ((group->meth->field_encode != NULL
 742          && !group->meth->field_encode(group, s->Z, s->Z, ctx))
 743         || !group->meth->field_mul(group, s->X, p->X, s->Z, ctx))
 744         return 0;
 745
 746     /* r blinding: make sure lambda (r->Y here for storage) is not zero */
 747     do {
 748         if (!BN_priv_rand_ex(r->Y, BN_num_bits(group->field) - 1,
 749                              BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, ctx)) {
 750             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_PRE, ERR_R_BN_LIB);
 751             return 0;
 752         }
 753     } while (BN_is_zero(r->Y));
 754
 755     if ((group->meth->field_encode != NULL
 756          && !group->meth->field_encode(group, r->Y, r->Y, ctx))
 757         || !group->meth->field_sqr(group, r->Z, p->X, ctx)
 758         || !group->meth->field_sqr(group, r->X, r->Z, ctx)
 759         || !BN_GF2m_add(r->X, r->X, group->b)
 760         || !group->meth->field_mul(group, r->Z, r->Z, r->Y, ctx)
 761         || !group->meth->field_mul(group, r->X, r->X, r->Y, ctx))
 762         return 0;
 763
 764     s->Z_is_one = 0;
 765     r->Z_is_one = 0;
 766
 767     return 1;
 768 }
 769
 770 /*-
 771  * Ladder step: differential addition-and-doubling, mixed Lopez-Dahab coords.
 772  * http://www.hyperelliptic.org/EFD/g12o/auto-code/shortw/xz/ladder/mladd-2003-s.op3
 773  * s := r + s, r := 2r
 774  */
 775 static
 776 int ec_GF2m_simple_ladder_step(const EC_GROUP *group,
 777                                EC_POINT *r, EC_POINT *s,
 778                                EC_POINT *p, BN_CTX *ctx)
 779 {
 780     if (!group->meth->field_mul(group, r->Y, r->Z, s->X, ctx)
 781         || !group->meth->field_mul(group, s->X, r->X, s->Z, ctx)
 782         || !group->meth->field_sqr(group, s->Y, r->Z, ctx)
 783         || !group->meth->field_sqr(group, r->Z, r->X, ctx)
 784         || !BN_GF2m_add(s->Z, r->Y, s->X)
 785         || !group->meth->field_sqr(group, s->Z, s->Z, ctx)
 786         || !group->meth->field_mul(group, s->X, r->Y, s->X, ctx)
 787         || !group->meth->field_mul(group, r->Y, s->Z, p->X, ctx)
 788         || !BN_GF2m_add(s->X, s->X, r->Y)
 789         || !group->meth->field_sqr(group, r->Y, r->Z, ctx)
 790         || !group->meth->field_mul(group, r->Z, r->Z, s->Y, ctx)
 791         || !group->meth->field_sqr(group, s->Y, s->Y, ctx)
 792         || !group->meth->field_mul(group, s->Y, s->Y, group->b, ctx)
 793         || !BN_GF2m_add(r->X, r->Y, s->Y))
 794         return 0;
 795
 796     return 1;
 797 }
 798
 799 /*-
 800  * Recover affine (x,y) result from Lopez-Dahab r and s, affine p.
 801  * See e.g. "Fast Multiplication on Elliptic Curves over GF(2**m)
 802  * without Precomputation" (Lopez and Dahab, CHES 1999),
 803  * Appendix Alg Mxy.
 804  */
 805 static
 806 int ec_GF2m_simple_ladder_post(const EC_GROUP *group,
 807                                EC_POINT *r, EC_POINT *s,
 808                                EC_POINT *p, BN_CTX *ctx)
 809 {
 810     int ret = 0;
 811     BIGNUM *t0, *t1, *t2 = NULL;
 812
 813     if (BN_is_zero(r->Z))
 814         return EC_POINT_set_to_infinity(group, r);
 815
 816     if (BN_is_zero(s->Z)) {
 817         if (!EC_POINT_copy(r, p)
 818             || !EC_POINT_invert(group, r, ctx)) {
 819             ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_EC_LIB);
 820             return 0;
 821         }
 822         return 1;
 823     }
 824
 825     BN_CTX_start(ctx);
 826     t0 = BN_CTX_get(ctx);
 827     t1 = BN_CTX_get(ctx);
 828     t2 = BN_CTX_get(ctx);
 829     if (t2 == NULL) {
 830         ECerr(EC_F_EC_GF2M_SIMPLE_LADDER_POST, ERR_R_MALLOC_FAILURE);
 831         goto err;
 832     }
 833
 834     if (!group->meth->field_mul(group, t0, r->Z, s->Z, ctx)
 835         || !group->meth->field_mul(group, t1, p->X, r->Z, ctx)
 836         || !BN_GF2m_add(t1, r->X, t1)
 837         || !group->meth->field_mul(group, t2, p->X, s->Z, ctx)
 838         || !group->meth->field_mul(group, r->Z, r->X, t2, ctx)
 839         || !BN_GF2m_add(t2, t2, s->X)
 840         || !group->meth->field_mul(group, t1, t1, t2, ctx)
 841         || !group->meth->field_sqr(group, t2, p->X, ctx)
 842         || !BN_GF2m_add(t2, p->Y, t2)
 843         || !group->meth->field_mul(group, t2, t2, t0, ctx)
 844         || !BN_GF2m_add(t1, t2, t1)
 845         || !group->meth->field_mul(group, t2, p->X, t0, ctx)
 846         || !group->meth->field_inv(group, t2, t2, ctx)
 847         || !group->meth->field_mul(group, t1, t1, t2, ctx)
 848         || !group->meth->field_mul(group, r->X, r->Z, t2, ctx)
 849         || !BN_GF2m_add(t2, p->X, r->X)
 850         || !group->meth->field_mul(group, t2, t2, t1, ctx)
 851         || !BN_GF2m_add(r->Y, p->Y, t2)
 852         || !BN_one(r->Z))
 853         goto err;
 854
 855     r->Z_is_one = 1;
 856
 857     /* GF(2^m) field elements should always have BIGNUM::neg = 0 */
 858     BN_set_negative(r->X, 0);
 859     BN_set_negative(r->Y, 0);
 860
 861     ret = 1;
 862
 863  err:
 864     BN_CTX_end(ctx);
 865     return ret;
 866 }
 867
 868 static
 869 int ec_GF2m_simple_points_mul(const EC_GROUP *group, EC_POINT *r,
 870                               const BIGNUM *scalar, size_t num,
 871                               const EC_POINT *points[],
 872                               const BIGNUM *scalars[],
 873                               BN_CTX *ctx)
 874 {
 875     int ret = 0;
 876     EC_POINT *t = NULL;
 877
 878     /*-
 879      * We limit use of the ladder only to the following cases:
 880      * - r := scalar * G
 881      *   Fixed point mul: scalar != NULL && num == 0;
 882      * - r := scalars[0] * points[0]
 883      *   Variable point mul: scalar == NULL && num == 1;
 884      * - r := scalar * G + scalars[0] * points[0]
 885      *   used, e.g., in ECDSA verification: scalar != NULL && num == 1
 886      *
 887      * In any other case (num > 1) we use the default wNAF implementation.
 888      *
 889      * We also let the default implementation handle degenerate cases like group
 890      * order or cofactor set to 0.
 891      */
 892     if (num > 1 || BN_is_zero(group->order) || BN_is_zero(group->cofactor))
 893         return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
 894
 895     if (scalar != NULL && num == 0)
 896         /* Fixed point multiplication */
 897         return ec_scalar_mul_ladder(group, r, scalar, NULL, ctx);
 898
 899     if (scalar == NULL && num == 1)
 900         /* Variable point multiplication */
 901         return ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx);
 902
 903     /*-
 904      * Double point multiplication:
 905      *  r := scalar * G + scalars[0] * points[0]
 906      */
 907
 908     if ((t = EC_POINT_new(group)) == NULL) {
 909         ECerr(EC_F_EC_GF2M_SIMPLE_POINTS_MUL, ERR_R_MALLOC_FAILURE);
 910         return 0;
 911     }
 912
 913     if (!ec_scalar_mul_ladder(group, t, scalar, NULL, ctx)
 914         || !ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx)
 915         || !EC_POINT_add(group, r, t, r, ctx))
 916         goto err;
 917
 918     ret = 1;
 919
 920  err:
 921     EC_POINT_free(t);
 922     return ret;
 923 }
 924
 925 /*-
 926  * Computes the multiplicative inverse of a in GF(2^m), storing the result in r.
 927  * If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error.
 928  * SCA hardening is with blinding: BN_GF2m_mod_inv does that.
 929  */
 930 static int ec_GF2m_simple_field_inv(const EC_GROUP *group, BIGNUM *r,
 931                                     const BIGNUM *a, BN_CTX *ctx)
 932 {
 933     int ret;
 934
 935     if (!(ret = BN_GF2m_mod_inv(r, a, group->field, ctx)))
 936         ECerr(EC_F_EC_GF2M_SIMPLE_FIELD_INV, EC_R_CANNOT_INVERT);
 937     return ret;
 938 }
 939
 940 const EC_METHOD *EC_GF2m_simple_method(void)
 941 {
 942     static const EC_METHOD ret = {
 943         EC_FLAGS_DEFAULT_OCT,
 944         NID_X9_62_characteristic_two_field,
 945         ec_GF2m_simple_group_init,
 946         ec_GF2m_simple_group_finish,
 947         ec_GF2m_simple_group_clear_finish,
 948         ec_GF2m_simple_group_copy,
 949         ec_GF2m_simple_group_set_curve,
 950         ec_GF2m_simple_group_get_curve,
 951         ec_GF2m_simple_group_get_degree,
 952         ec_group_simple_order_bits,
 953         ec_GF2m_simple_group_check_discriminant,
 954         ec_GF2m_simple_point_init,
 955         ec_GF2m_simple_point_finish,
 956         ec_GF2m_simple_point_clear_finish,
 957         ec_GF2m_simple_point_copy,
 958         ec_GF2m_simple_point_set_to_infinity,
 959         ec_GF2m_simple_point_set_affine_coordinates,
 960         ec_GF2m_simple_point_get_affine_coordinates,
 961         0, /* point_set_compressed_coordinates */
 962         0, /* point2oct */
 963         0, /* oct2point */
 964         ec_GF2m_simple_add,
 965         ec_GF2m_simple_dbl,
 966         ec_GF2m_simple_invert,
 967         ec_GF2m_simple_is_at_infinity,
 968         ec_GF2m_simple_is_on_curve,
 969         ec_GF2m_simple_cmp,
 970         ec_GF2m_simple_make_affine,
 971         ec_GF2m_simple_points_make_affine,
 972         ec_GF2m_simple_points_mul,
 973         0, /* precompute_mult */
 974         0, /* have_precompute_mult */
 975         ec_GF2m_simple_field_mul,
 976         ec_GF2m_simple_field_sqr,
 977         ec_GF2m_simple_field_div,
 978         ec_GF2m_simple_field_inv,
 979         0, /* field_encode */
 980         0, /* field_decode */
 981         0, /* field_set_to_one */
 982         ec_key_simple_priv2oct,
 983         ec_key_simple_oct2priv,
 984         0, /* set private */
 985         ec_key_simple_generate_key,
 986         ec_key_simple_check_key,
 987         ec_key_simple_generate_public_key,
 988         0, /* keycopy */
 989         0, /* keyfinish */
 990         ecdh_simple_compute_key,
 991         ecdsa_simple_sign_setup,
 992         ecdsa_simple_sign_sig,
 993         ecdsa_simple_verify_sig,
 994         0, /* field_inverse_mod_ord */
 995         0, /* blind_coordinates */
 996         ec_GF2m_simple_ladder_pre,
 997         ec_GF2m_simple_ladder_step,
 998         ec_GF2m_simple_ladder_post
 999     };
1000
1001     return &ret;
1002 }
1003
1004 #endif