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_MALLOC_FAILURE); 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_MALLOC_FAILURE); 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_MALLOC_FAILURE); 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 a 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 1004