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