crypto/ec/ec2_smpl.c

   1 /*
   2  * Copyright 2002-2021 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 ossl_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 ossl_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 ossl_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 ossl_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 ossl_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         ERR_raise(ERR_LIB_EC, 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 ossl_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 ossl_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 ossl_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             ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
 192             goto err;
 193         }
 194     }
 195 #endif
 196     BN_CTX_start(ctx);
 197     b = BN_CTX_get(ctx);
 198     if (b == NULL)
 199         goto err;
 200
 201     if (!BN_GF2m_mod_arr(b, group->b, group->poly))
 202         goto err;
 203
 204     /*
 205      * check the discriminant: y^2 + x*y = x^3 + a*x^2 + b is an elliptic
 206      * curve <=> b != 0 (mod p)
 207      */
 208     if (BN_is_zero(b))
 209         goto err;
 210
 211     ret = 1;
 212
 213  err:
 214     BN_CTX_end(ctx);
 215 #ifndef FIPS_MODULE
 216     BN_CTX_free(new_ctx);
 217 #endif
 218     return ret;
 219 }
 220
 221 /* Initializes an EC_POINT. */
 222 int ossl_ec_GF2m_simple_point_init(EC_POINT *point)
 223 {
 224     point->X = BN_new();
 225     point->Y = BN_new();
 226     point->Z = BN_new();
 227
 228     if (point->X == NULL || point->Y == NULL || point->Z == NULL) {
 229         BN_free(point->X);
 230         BN_free(point->Y);
 231         BN_free(point->Z);
 232         return 0;
 233     }
 234     return 1;
 235 }
 236
 237 /* Frees an EC_POINT. */
 238 void ossl_ec_GF2m_simple_point_finish(EC_POINT *point)
 239 {
 240     BN_free(point->X);
 241     BN_free(point->Y);
 242     BN_free(point->Z);
 243 }
 244
 245 /* Clears and frees an EC_POINT. */
 246 void ossl_ec_GF2m_simple_point_clear_finish(EC_POINT *point)
 247 {
 248     BN_clear_free(point->X);
 249     BN_clear_free(point->Y);
 250     BN_clear_free(point->Z);
 251     point->Z_is_one = 0;
 252 }
 253
 254 /*
 255  * Copy the contents of one EC_POINT into another.  Assumes dest is
 256  * initialized.
 257  */
 258 int ossl_ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
 259 {
 260     if (!BN_copy(dest->X, src->X))
 261         return 0;
 262     if (!BN_copy(dest->Y, src->Y))
 263         return 0;
 264     if (!BN_copy(dest->Z, src->Z))
 265         return 0;
 266     dest->Z_is_one = src->Z_is_one;
 267     dest->curve_name = src->curve_name;
 268
 269     return 1;
 270 }
 271
 272 /*
 273  * Set an EC_POINT to the point at infinity. A point at infinity is
 274  * represented by having Z=0.
 275  */
 276 int ossl_ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group,
 277                                               EC_POINT *point)
 278 {
 279     point->Z_is_one = 0;
 280     BN_zero(point->Z);
 281     return 1;
 282 }
 283
 284 /*
 285  * Set the coordinates of an EC_POINT using affine coordinates. Note that
 286  * the simple implementation only uses affine coordinates.
 287  */
 288 int ossl_ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group,
 289                                                      EC_POINT *point,
 290                                                      const BIGNUM *x,
 291                                                      const BIGNUM *y,
 292                                                      BN_CTX *ctx)
 293 {
 294     int ret = 0;
 295     if (x == NULL || y == NULL) {
 296         ERR_raise(ERR_LIB_EC, ERR_R_PASSED_NULL_PARAMETER);
 297         return 0;
 298     }
 299
 300     if (!BN_copy(point->X, x))
 301         goto err;
 302     BN_set_negative(point->X, 0);
 303     if (!BN_copy(point->Y, y))
 304         goto err;
 305     BN_set_negative(point->Y, 0);
 306     if (!BN_copy(point->Z, BN_value_one()))
 307         goto err;
 308     BN_set_negative(point->Z, 0);
 309     point->Z_is_one = 1;
 310     ret = 1;
 311
 312  err:
 313     return ret;
 314 }
 315
 316 /*
 317  * Gets the affine coordinates of an EC_POINT. Note that the simple
 318  * implementation only uses affine coordinates.
 319  */
 320 int ossl_ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group,
 321                                                      const EC_POINT *point,
 322                                                      BIGNUM *x, BIGNUM *y,
 323                                                      BN_CTX *ctx)
 324 {
 325     int ret = 0;
 326
 327     if (EC_POINT_is_at_infinity(group, point)) {
 328         ERR_raise(ERR_LIB_EC, EC_R_POINT_AT_INFINITY);
 329         return 0;
 330     }
 331
 332     if (BN_cmp(point->Z, BN_value_one())) {
 333         ERR_raise(ERR_LIB_EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
 334         return 0;
 335     }
 336     if (x != NULL) {
 337         if (!BN_copy(x, point->X))
 338             goto err;
 339         BN_set_negative(x, 0);
 340     }
 341     if (y != NULL) {
 342         if (!BN_copy(y, point->Y))
 343             goto err;
 344         BN_set_negative(y, 0);
 345     }
 346     ret = 1;
 347
 348  err:
 349     return ret;
 350 }
 351
 352 /*
 353  * Computes a + b and stores the result in r.  r could be a or b, a could be
 354  * b. Uses algorithm A.10.2 of IEEE P1363.
 355  */
 356 int ossl_ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r,
 357                             const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
 358 {
 359     BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t;
 360     int ret = 0;
 361 #ifndef FIPS_MODULE
 362     BN_CTX *new_ctx = NULL;
 363 #endif
 364
 365     if (EC_POINT_is_at_infinity(group, a)) {
 366         if (!EC_POINT_copy(r, b))
 367             return 0;
 368         return 1;
 369     }
 370
 371     if (EC_POINT_is_at_infinity(group, b)) {
 372         if (!EC_POINT_copy(r, a))
 373             return 0;
 374         return 1;
 375     }
 376
 377 #ifndef FIPS_MODULE
 378     if (ctx == NULL) {
 379         ctx = new_ctx = BN_CTX_new();
 380         if (ctx == NULL)
 381             return 0;
 382     }
 383 #endif
 384
 385     BN_CTX_start(ctx);
 386     x0 = BN_CTX_get(ctx);
 387     y0 = BN_CTX_get(ctx);
 388     x1 = BN_CTX_get(ctx);
 389     y1 = BN_CTX_get(ctx);
 390     x2 = BN_CTX_get(ctx);
 391     y2 = BN_CTX_get(ctx);
 392     s = BN_CTX_get(ctx);
 393     t = BN_CTX_get(ctx);
 394     if (t == NULL)
 395         goto err;
 396
 397     if (a->Z_is_one) {
 398         if (!BN_copy(x0, a->X))
 399             goto err;
 400         if (!BN_copy(y0, a->Y))
 401             goto err;
 402     } else {
 403         if (!EC_POINT_get_affine_coordinates(group, a, x0, y0, ctx))
 404             goto err;
 405     }
 406     if (b->Z_is_one) {
 407         if (!BN_copy(x1, b->X))
 408             goto err;
 409         if (!BN_copy(y1, b->Y))
 410             goto err;
 411     } else {
 412         if (!EC_POINT_get_affine_coordinates(group, b, x1, y1, ctx))
 413             goto err;
 414     }
 415
 416     if (BN_GF2m_cmp(x0, x1)) {
 417         if (!BN_GF2m_add(t, x0, x1))
 418             goto err;
 419         if (!BN_GF2m_add(s, y0, y1))
 420             goto err;
 421         if (!group->meth->field_div(group, s, s, t, ctx))
 422             goto err;
 423         if (!group->meth->field_sqr(group, x2, s, ctx))
 424             goto err;
 425         if (!BN_GF2m_add(x2, x2, group->a))
 426             goto err;
 427         if (!BN_GF2m_add(x2, x2, s))
 428             goto err;
 429         if (!BN_GF2m_add(x2, x2, t))
 430             goto err;
 431     } else {
 432         if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) {
 433             if (!EC_POINT_set_to_infinity(group, r))
 434                 goto err;
 435             ret = 1;
 436             goto err;
 437         }
 438         if (!group->meth->field_div(group, s, y1, x1, ctx))
 439             goto err;
 440         if (!BN_GF2m_add(s, s, x1))
 441             goto err;
 442
 443         if (!group->meth->field_sqr(group, x2, s, ctx))
 444             goto err;
 445         if (!BN_GF2m_add(x2, x2, s))
 446             goto err;
 447         if (!BN_GF2m_add(x2, x2, group->a))
 448             goto err;
 449     }
 450
 451     if (!BN_GF2m_add(y2, x1, x2))
 452         goto err;
 453     if (!group->meth->field_mul(group, y2, y2, s, ctx))
 454         goto err;
 455     if (!BN_GF2m_add(y2, y2, x2))
 456         goto err;
 457     if (!BN_GF2m_add(y2, y2, y1))
 458         goto err;
 459
 460     if (!EC_POINT_set_affine_coordinates(group, r, x2, y2, ctx))
 461         goto err;
 462
 463     ret = 1;
 464
 465  err:
 466     BN_CTX_end(ctx);
 467 #ifndef FIPS_MODULE
 468     BN_CTX_free(new_ctx);
 469 #endif
 470     return ret;
 471 }
 472
 473 /*
 474  * Computes 2 * a and stores the result in r.  r could be a. Uses algorithm
 475  * A.10.2 of IEEE P1363.
 476  */
 477 int ossl_ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r,
 478                             const EC_POINT *a, BN_CTX *ctx)
 479 {
 480     return ossl_ec_GF2m_simple_add(group, r, a, a, ctx);
 481 }
 482
 483 int ossl_ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point,
 484                                BN_CTX *ctx)
 485 {
 486     if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y))
 487         /* point is its own inverse */
 488         return 1;
 489
 490     if (group->meth->make_affine == NULL
 491         || !group->meth->make_affine(group, point, ctx))
 492         return 0;
 493     return BN_GF2m_add(point->Y, point->X, point->Y);
 494 }
 495
 496 /* Indicates whether the given point is the point at infinity. */
 497 int ossl_ec_GF2m_simple_is_at_infinity(const EC_GROUP *group,
 498                                        const EC_POINT *point)
 499 {
 500     return BN_is_zero(point->Z);
 501 }
 502
 503 /*-
 504  * Determines whether the given EC_POINT is an actual point on the curve defined
 505  * in the EC_GROUP.  A point is valid if it satisfies the Weierstrass equation:
 506  *      y^2 + x*y = x^3 + a*x^2 + b.
 507  */
 508 int ossl_ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point,
 509                                     BN_CTX *ctx)
 510 {
 511     int ret = -1;
 512     BIGNUM *lh, *y2;
 513     int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *,
 514                       const BIGNUM *, BN_CTX *);
 515     int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
 516 #ifndef FIPS_MODULE
 517     BN_CTX *new_ctx = NULL;
 518 #endif
 519
 520     if (EC_POINT_is_at_infinity(group, point))
 521         return 1;
 522
 523     field_mul = group->meth->field_mul;
 524     field_sqr = group->meth->field_sqr;
 525
 526     /* only support affine coordinates */
 527     if (!point->Z_is_one)
 528         return -1;
 529
 530 #ifndef FIPS_MODULE
 531     if (ctx == NULL) {
 532         ctx = new_ctx = BN_CTX_new();
 533         if (ctx == NULL)
 534             return -1;
 535     }
 536 #endif
 537
 538     BN_CTX_start(ctx);
 539     y2 = BN_CTX_get(ctx);
 540     lh = BN_CTX_get(ctx);
 541     if (lh == NULL)
 542         goto err;
 543
 544     /*-
 545      * We have a curve defined by a Weierstrass equation
 546      *      y^2 + x*y = x^3 + a*x^2 + b.
 547      *  <=> x^3 + a*x^2 + x*y + b + y^2 = 0
 548      *  <=> ((x + a) * x + y) * x + b + y^2 = 0
 549      */
 550     if (!BN_GF2m_add(lh, point->X, group->a))
 551         goto err;
 552     if (!field_mul(group, lh, lh, point->X, ctx))
 553         goto err;
 554     if (!BN_GF2m_add(lh, lh, point->Y))
 555         goto err;
 556     if (!field_mul(group, lh, lh, point->X, ctx))
 557         goto err;
 558     if (!BN_GF2m_add(lh, lh, group->b))
 559         goto err;
 560     if (!field_sqr(group, y2, point->Y, ctx))
 561         goto err;
 562     if (!BN_GF2m_add(lh, lh, y2))
 563         goto err;
 564     ret = BN_is_zero(lh);
 565
 566  err:
 567     BN_CTX_end(ctx);
 568 #ifndef FIPS_MODULE
 569     BN_CTX_free(new_ctx);
 570 #endif
 571     return ret;
 572 }
 573
 574 /*-
 575  * Indicates whether two points are equal.
 576  * Return values:
 577  *  -1   error
 578  *   0   equal (in affine coordinates)
 579  *   1   not equal
 580  */
 581 int ossl_ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a,
 582                             const EC_POINT *b, BN_CTX *ctx)
 583 {
 584     BIGNUM *aX, *aY, *bX, *bY;
 585     int ret = -1;
 586 #ifndef FIPS_MODULE
 587     BN_CTX *new_ctx = NULL;
 588 #endif
 589
 590     if (EC_POINT_is_at_infinity(group, a)) {
 591         return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
 592     }
 593
 594     if (EC_POINT_is_at_infinity(group, b))
 595         return 1;
 596
 597     if (a->Z_is_one && b->Z_is_one) {
 598         return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1;
 599     }
 600
 601 #ifndef FIPS_MODULE
 602     if (ctx == NULL) {
 603         ctx = new_ctx = BN_CTX_new();
 604         if (ctx == NULL)
 605             return -1;
 606     }
 607 #endif
 608
 609     BN_CTX_start(ctx);
 610     aX = BN_CTX_get(ctx);
 611     aY = BN_CTX_get(ctx);
 612     bX = BN_CTX_get(ctx);
 613     bY = BN_CTX_get(ctx);
 614     if (bY == NULL)
 615         goto err;
 616
 617     if (!EC_POINT_get_affine_coordinates(group, a, aX, aY, ctx))
 618         goto err;
 619     if (!EC_POINT_get_affine_coordinates(group, b, bX, bY, ctx))
 620         goto err;
 621     ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
 622
 623  err:
 624     BN_CTX_end(ctx);
 625 #ifndef FIPS_MODULE
 626     BN_CTX_free(new_ctx);
 627 #endif
 628     return ret;
 629 }
 630
 631 /* Forces the given EC_POINT to internally use affine coordinates. */
 632 int ossl_ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point,
 633                                     BN_CTX *ctx)
 634 {
 635     BIGNUM *x, *y;
 636     int ret = 0;
 637 #ifndef FIPS_MODULE
 638     BN_CTX *new_ctx = NULL;
 639 #endif
 640
 641     if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
 642         return 1;
 643
 644 #ifndef FIPS_MODULE
 645     if (ctx == NULL) {
 646         ctx = new_ctx = BN_CTX_new();
 647         if (ctx == NULL)
 648             return 0;
 649     }
 650 #endif
 651
 652     BN_CTX_start(ctx);
 653     x = BN_CTX_get(ctx);
 654     y = BN_CTX_get(ctx);
 655     if (y == NULL)
 656         goto err;
 657
 658     if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
 659         goto err;
 660     if (!BN_copy(point->X, x))
 661         goto err;
 662     if (!BN_copy(point->Y, y))
 663         goto err;
 664     if (!BN_one(point->Z))
 665         goto err;
 666     point->Z_is_one = 1;
 667
 668     ret = 1;
 669
 670  err:
 671     BN_CTX_end(ctx);
 672 #ifndef FIPS_MODULE
 673     BN_CTX_free(new_ctx);
 674 #endif
 675     return ret;
 676 }
 677
 678 /*
 679  * Forces each of the EC_POINTs in the given array to use affine coordinates.
 680  */
 681 int ossl_ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num,
 682                                            EC_POINT *points[], BN_CTX *ctx)
 683 {
 684     size_t i;
 685
 686     for (i = 0; i < num; i++) {
 687         if (!group->meth->make_affine(group, points[i], ctx))
 688             return 0;
 689     }
 690
 691     return 1;
 692 }
 693
 694 /* Wrapper to simple binary polynomial field multiplication implementation. */
 695 int ossl_ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r,
 696                                   const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 697 {
 698     return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
 699 }
 700
 701 /* Wrapper to simple binary polynomial field squaring implementation. */
 702 int ossl_ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r,
 703                                   const BIGNUM *a, BN_CTX *ctx)
 704 {
 705     return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
 706 }
 707
 708 /* Wrapper to simple binary polynomial field division implementation. */
 709 int ossl_ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r,
 710                                   const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 711 {
 712     return BN_GF2m_mod_div(r, a, b, group->field, ctx);
 713 }
 714
 715 /*-
 716  * Lopez-Dahab ladder, pre step.
 717  * See e.g. "Guide to ECC" Alg 3.40.
 718  * Modified to blind s and r independently.
 719  * s:= p, r := 2p
 720  */
 721 static
 722 int ec_GF2m_simple_ladder_pre(const EC_GROUP *group,
 723                               EC_POINT *r, EC_POINT *s,
 724                               EC_POINT *p, BN_CTX *ctx)
 725 {
 726     /* if p is not affine, something is wrong */
 727     if (p->Z_is_one == 0)
 728         return 0;
 729
 730     /* s blinding: make sure lambda (s->Z here) is not zero */
 731     do {
 732         if (!BN_priv_rand_ex(s->Z, BN_num_bits(group->field) - 1,
 733                              BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, 0, ctx)) {
 734             ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
 735             return 0;
 736         }
 737     } while (BN_is_zero(s->Z));
 738
 739     /* if field_encode defined convert between representations */
 740     if ((group->meth->field_encode != NULL
 741          && !group->meth->field_encode(group, s->Z, s->Z, ctx))
 742         || !group->meth->field_mul(group, s->X, p->X, s->Z, ctx))
 743         return 0;
 744
 745     /* r blinding: make sure lambda (r->Y here for storage) is not zero */
 746     do {
 747         if (!BN_priv_rand_ex(r->Y, BN_num_bits(group->field) - 1,
 748                              BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, 0, ctx)) {
 749             ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
 750             return 0;
 751         }
 752     } while (BN_is_zero(r->Y));
 753
 754     if ((group->meth->field_encode != NULL
 755          && !group->meth->field_encode(group, r->Y, r->Y, ctx))
 756         || !group->meth->field_sqr(group, r->Z, p->X, ctx)
 757         || !group->meth->field_sqr(group, r->X, r->Z, ctx)
 758         || !BN_GF2m_add(r->X, r->X, group->b)
 759         || !group->meth->field_mul(group, r->Z, r->Z, r->Y, ctx)
 760         || !group->meth->field_mul(group, r->X, r->X, r->Y, ctx))
 761         return 0;
 762
 763     s->Z_is_one = 0;
 764     r->Z_is_one = 0;
 765
 766     return 1;
 767 }
 768
 769 /*-
 770  * Ladder step: differential addition-and-doubling, mixed Lopez-Dahab coords.
 771  * http://www.hyperelliptic.org/EFD/g12o/auto-code/shortw/xz/ladder/mladd-2003-s.op3
 772  * s := r + s, r := 2r
 773  */
 774 static
 775 int ec_GF2m_simple_ladder_step(const EC_GROUP *group,
 776                                EC_POINT *r, EC_POINT *s,
 777                                EC_POINT *p, BN_CTX *ctx)
 778 {
 779     if (!group->meth->field_mul(group, r->Y, r->Z, s->X, ctx)
 780         || !group->meth->field_mul(group, s->X, r->X, s->Z, ctx)
 781         || !group->meth->field_sqr(group, s->Y, r->Z, ctx)
 782         || !group->meth->field_sqr(group, r->Z, r->X, ctx)
 783         || !BN_GF2m_add(s->Z, r->Y, s->X)
 784         || !group->meth->field_sqr(group, s->Z, s->Z, ctx)
 785         || !group->meth->field_mul(group, s->X, r->Y, s->X, ctx)
 786         || !group->meth->field_mul(group, r->Y, s->Z, p->X, ctx)
 787         || !BN_GF2m_add(s->X, s->X, r->Y)
 788         || !group->meth->field_sqr(group, r->Y, r->Z, ctx)
 789         || !group->meth->field_mul(group, r->Z, r->Z, s->Y, ctx)
 790         || !group->meth->field_sqr(group, s->Y, s->Y, ctx)
 791         || !group->meth->field_mul(group, s->Y, s->Y, group->b, ctx)
 792         || !BN_GF2m_add(r->X, r->Y, s->Y))
 793         return 0;
 794
 795     return 1;
 796 }
 797
 798 /*-
 799  * Recover affine (x,y) result from Lopez-Dahab r and s, affine p.
 800  * See e.g. "Fast Multiplication on Elliptic Curves over GF(2**m)
 801  * without Precomputation" (Lopez and Dahab, CHES 1999),
 802  * Appendix Alg Mxy.
 803  */
 804 static
 805 int ec_GF2m_simple_ladder_post(const EC_GROUP *group,
 806                                EC_POINT *r, EC_POINT *s,
 807                                EC_POINT *p, BN_CTX *ctx)
 808 {
 809     int ret = 0;
 810     BIGNUM *t0, *t1, *t2 = NULL;
 811
 812     if (BN_is_zero(r->Z))
 813         return EC_POINT_set_to_infinity(group, r);
 814
 815     if (BN_is_zero(s->Z)) {
 816         if (!EC_POINT_copy(r, p)
 817             || !EC_POINT_invert(group, r, ctx)) {
 818             ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
 819             return 0;
 820         }
 821         return 1;
 822     }
 823
 824     BN_CTX_start(ctx);
 825     t0 = BN_CTX_get(ctx);
 826     t1 = BN_CTX_get(ctx);
 827     t2 = BN_CTX_get(ctx);
 828     if (t2 == NULL) {
 829         ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB);
 830         goto err;
 831     }
 832
 833     if (!group->meth->field_mul(group, t0, r->Z, s->Z, ctx)
 834         || !group->meth->field_mul(group, t1, p->X, r->Z, ctx)
 835         || !BN_GF2m_add(t1, r->X, t1)
 836         || !group->meth->field_mul(group, t2, p->X, s->Z, ctx)
 837         || !group->meth->field_mul(group, r->Z, r->X, t2, ctx)
 838         || !BN_GF2m_add(t2, t2, s->X)
 839         || !group->meth->field_mul(group, t1, t1, t2, ctx)
 840         || !group->meth->field_sqr(group, t2, p->X, ctx)
 841         || !BN_GF2m_add(t2, p->Y, t2)
 842         || !group->meth->field_mul(group, t2, t2, t0, ctx)
 843         || !BN_GF2m_add(t1, t2, t1)
 844         || !group->meth->field_mul(group, t2, p->X, t0, ctx)
 845         || !group->meth->field_inv(group, t2, t2, ctx)
 846         || !group->meth->field_mul(group, t1, t1, t2, ctx)
 847         || !group->meth->field_mul(group, r->X, r->Z, t2, ctx)
 848         || !BN_GF2m_add(t2, p->X, r->X)
 849         || !group->meth->field_mul(group, t2, t2, t1, ctx)
 850         || !BN_GF2m_add(r->Y, p->Y, t2)
 851         || !BN_one(r->Z))
 852         goto err;
 853
 854     r->Z_is_one = 1;
 855
 856     /* GF(2^m) field elements should always have BIGNUM::neg = 0 */
 857     BN_set_negative(r->X, 0);
 858     BN_set_negative(r->Y, 0);
 859
 860     ret = 1;
 861
 862  err:
 863     BN_CTX_end(ctx);
 864     return ret;
 865 }
 866
 867 static
 868 int ec_GF2m_simple_points_mul(const EC_GROUP *group, EC_POINT *r,
 869                               const BIGNUM *scalar, size_t num,
 870                               const EC_POINT *points[],
 871                               const BIGNUM *scalars[],
 872                               BN_CTX *ctx)
 873 {
 874     int ret = 0;
 875     EC_POINT *t = NULL;
 876
 877     /*-
 878      * We limit use of the ladder only to the following cases:
 879      * - r := scalar * G
 880      *   Fixed point mul: scalar != NULL && num == 0;
 881      * - r := scalars[0] * points[0]
 882      *   Variable point mul: scalar == NULL && num == 1;
 883      * - r := scalar * G + scalars[0] * points[0]
 884      *   used, e.g., in ECDSA verification: scalar != NULL && num == 1
 885      *
 886      * In any other case (num > 1) we use the default wNAF implementation.
 887      *
 888      * We also let the default implementation handle degenerate cases like group
 889      * order or cofactor set to 0.
 890      */
 891     if (num > 1 || BN_is_zero(group->order) || BN_is_zero(group->cofactor))
 892         return ossl_ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
 893
 894     if (scalar != NULL && num == 0)
 895         /* Fixed point multiplication */
 896         return ossl_ec_scalar_mul_ladder(group, r, scalar, NULL, ctx);
 897
 898     if (scalar == NULL && num == 1)
 899         /* Variable point multiplication */
 900         return ossl_ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx);
 901
 902     /*-
 903      * Double point multiplication:
 904      *  r := scalar * G + scalars[0] * points[0]
 905      */
 906
 907     if ((t = EC_POINT_new(group)) == NULL) {
 908         ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB);
 909         return 0;
 910     }
 911
 912     if (!ossl_ec_scalar_mul_ladder(group, t, scalar, NULL, ctx)
 913         || !ossl_ec_scalar_mul_ladder(group, r, scalars[0], points[0], ctx)
 914         || !EC_POINT_add(group, r, t, r, ctx))
 915         goto err;
 916
 917     ret = 1;
 918
 919  err:
 920     EC_POINT_free(t);
 921     return ret;
 922 }
 923
 924 /*-
 925  * Computes the multiplicative inverse of a in GF(2^m), storing the result in r.
 926  * If a is zero (or equivalent), you'll get an EC_R_CANNOT_INVERT error.
 927  * SCA hardening is with blinding: BN_GF2m_mod_inv does that.
 928  */
 929 static int ec_GF2m_simple_field_inv(const EC_GROUP *group, BIGNUM *r,
 930                                     const BIGNUM *a, BN_CTX *ctx)
 931 {
 932     int ret;
 933
 934     if (!(ret = BN_GF2m_mod_inv(r, a, group->field, ctx)))
 935         ERR_raise(ERR_LIB_EC, EC_R_CANNOT_INVERT);
 936     return ret;
 937 }
 938
 939 const EC_METHOD *EC_GF2m_simple_method(void)
 940 {
 941     static const EC_METHOD ret = {
 942         EC_FLAGS_DEFAULT_OCT,
 943         NID_X9_62_characteristic_two_field,
 944         ossl_ec_GF2m_simple_group_init,
 945         ossl_ec_GF2m_simple_group_finish,
 946         ossl_ec_GF2m_simple_group_clear_finish,
 947         ossl_ec_GF2m_simple_group_copy,
 948         ossl_ec_GF2m_simple_group_set_curve,
 949         ossl_ec_GF2m_simple_group_get_curve,
 950         ossl_ec_GF2m_simple_group_get_degree,
 951         ossl_ec_group_simple_order_bits,
 952         ossl_ec_GF2m_simple_group_check_discriminant,
 953         ossl_ec_GF2m_simple_point_init,
 954         ossl_ec_GF2m_simple_point_finish,
 955         ossl_ec_GF2m_simple_point_clear_finish,
 956         ossl_ec_GF2m_simple_point_copy,
 957         ossl_ec_GF2m_simple_point_set_to_infinity,
 958         ossl_ec_GF2m_simple_point_set_affine_coordinates,
 959         ossl_ec_GF2m_simple_point_get_affine_coordinates,
 960         0, /* point_set_compressed_coordinates */
 961         0, /* point2oct */
 962         0, /* oct2point */
 963         ossl_ec_GF2m_simple_add,
 964         ossl_ec_GF2m_simple_dbl,
 965         ossl_ec_GF2m_simple_invert,
 966         ossl_ec_GF2m_simple_is_at_infinity,
 967         ossl_ec_GF2m_simple_is_on_curve,
 968         ossl_ec_GF2m_simple_cmp,
 969         ossl_ec_GF2m_simple_make_affine,
 970         ossl_ec_GF2m_simple_points_make_affine,
 971         ec_GF2m_simple_points_mul,
 972         0, /* precompute_mult */
 973         0, /* have_precompute_mult */
 974         ossl_ec_GF2m_simple_field_mul,
 975         ossl_ec_GF2m_simple_field_sqr,
 976         ossl_ec_GF2m_simple_field_div,
 977         ec_GF2m_simple_field_inv,
 978         0, /* field_encode */
 979         0, /* field_decode */
 980         0, /* field_set_to_one */
 981         ossl_ec_key_simple_priv2oct,
 982         ossl_ec_key_simple_oct2priv,
 983         0, /* set private */
 984         ossl_ec_key_simple_generate_key,
 985         ossl_ec_key_simple_check_key,
 986         ossl_ec_key_simple_generate_public_key,
 987         0, /* keycopy */
 988         0, /* keyfinish */
 989         ossl_ecdh_simple_compute_key,
 990         ossl_ecdsa_simple_sign_setup,
 991         ossl_ecdsa_simple_sign_sig,
 992         ossl_ecdsa_simple_verify_sig,
 993         0, /* field_inverse_mod_ord */
 994         0, /* blind_coordinates */
 995         ec_GF2m_simple_ladder_pre,
 996         ec_GF2m_simple_ladder_step,
 997         ec_GF2m_simple_ladder_post
 998     };
 999
1000     return &ret;
1001 }
1002
1003 #endif