crypto/ec/ec2_smpl.c

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