1 /* 2 * Copyright 2001-2020 The OpenSSL Project Authors. All Rights Reserved. 3 * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved 4 * 5 * Licensed under the OpenSSL license (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 #include <openssl/symhacks.h> 13 14 #include "ec_local.h" 15 16 const EC_METHOD *EC_GFp_simple_method(void) 17 { 18 static const EC_METHOD ret = { 19 EC_FLAGS_DEFAULT_OCT, 20 NID_X9_62_prime_field, 21 ec_GFp_simple_group_init, 22 ec_GFp_simple_group_finish, 23 ec_GFp_simple_group_clear_finish, 24 ec_GFp_simple_group_copy, 25 ec_GFp_simple_group_set_curve, 26 ec_GFp_simple_group_get_curve, 27 ec_GFp_simple_group_get_degree, 28 ec_group_simple_order_bits, 29 ec_GFp_simple_group_check_discriminant, 30 ec_GFp_simple_point_init, 31 ec_GFp_simple_point_finish, 32 ec_GFp_simple_point_clear_finish, 33 ec_GFp_simple_point_copy, 34 ec_GFp_simple_point_set_to_infinity, 35 ec_GFp_simple_set_Jprojective_coordinates_GFp, 36 ec_GFp_simple_get_Jprojective_coordinates_GFp, 37 ec_GFp_simple_point_set_affine_coordinates, 38 ec_GFp_simple_point_get_affine_coordinates, 39 0, 0, 0, 40 ec_GFp_simple_add, 41 ec_GFp_simple_dbl, 42 ec_GFp_simple_invert, 43 ec_GFp_simple_is_at_infinity, 44 ec_GFp_simple_is_on_curve, 45 ec_GFp_simple_cmp, 46 ec_GFp_simple_make_affine, 47 ec_GFp_simple_points_make_affine, 48 0 /* mul */ , 49 0 /* precompute_mult */ , 50 0 /* have_precompute_mult */ , 51 ec_GFp_simple_field_mul, 52 ec_GFp_simple_field_sqr, 53 0 /* field_div */ , 54 ec_GFp_simple_field_inv, 55 0 /* field_encode */ , 56 0 /* field_decode */ , 57 0, /* field_set_to_one */ 58 ec_key_simple_priv2oct, 59 ec_key_simple_oct2priv, 60 0, /* set private */ 61 ec_key_simple_generate_key, 62 ec_key_simple_check_key, 63 ec_key_simple_generate_public_key, 64 0, /* keycopy */ 65 0, /* keyfinish */ 66 ecdh_simple_compute_key, 67 0, /* field_inverse_mod_ord */ 68 ec_GFp_simple_blind_coordinates, 69 ec_GFp_simple_ladder_pre, 70 ec_GFp_simple_ladder_step, 71 ec_GFp_simple_ladder_post 72 }; 73 74 return &ret; 75 } 76 77 /* 78 * Most method functions in this file are designed to work with 79 * non-trivial representations of field elements if necessary 80 * (see ecp_mont.c): while standard modular addition and subtraction 81 * are used, the field_mul and field_sqr methods will be used for 82 * multiplication, and field_encode and field_decode (if defined) 83 * will be used for converting between representations. 84 * 85 * Functions ec_GFp_simple_points_make_affine() and 86 * ec_GFp_simple_point_get_affine_coordinates() specifically assume 87 * that if a non-trivial representation is used, it is a Montgomery 88 * representation (i.e. 'encoding' means multiplying by some factor R). 89 */ 90 91 int ec_GFp_simple_group_init(EC_GROUP *group) 92 { 93 group->field = BN_new(); 94 group->a = BN_new(); 95 group->b = BN_new(); 96 if (group->field == NULL || group->a == NULL || group->b == NULL) { 97 BN_free(group->field); 98 BN_free(group->a); 99 BN_free(group->b); 100 return 0; 101 } 102 group->a_is_minus3 = 0; 103 return 1; 104 } 105 106 void ec_GFp_simple_group_finish(EC_GROUP *group) 107 { 108 BN_free(group->field); 109 BN_free(group->a); 110 BN_free(group->b); 111 } 112 113 void ec_GFp_simple_group_clear_finish(EC_GROUP *group) 114 { 115 BN_clear_free(group->field); 116 BN_clear_free(group->a); 117 BN_clear_free(group->b); 118 } 119 120 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) 121 { 122 if (!BN_copy(dest->field, src->field)) 123 return 0; 124 if (!BN_copy(dest->a, src->a)) 125 return 0; 126 if (!BN_copy(dest->b, src->b)) 127 return 0; 128 129 dest->a_is_minus3 = src->a_is_minus3; 130 131 return 1; 132 } 133 134 int ec_GFp_simple_group_set_curve(EC_GROUP *group, 135 const BIGNUM *p, const BIGNUM *a, 136 const BIGNUM *b, BN_CTX *ctx) 137 { 138 int ret = 0; 139 BN_CTX *new_ctx = NULL; 140 BIGNUM *tmp_a; 141 142 /* p must be a prime > 3 */ 143 if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) { 144 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD); 145 return 0; 146 } 147 148 if (ctx == NULL) { 149 ctx = new_ctx = BN_CTX_new(); 150 if (ctx == NULL) 151 return 0; 152 } 153 154 BN_CTX_start(ctx); 155 tmp_a = BN_CTX_get(ctx); 156 if (tmp_a == NULL) 157 goto err; 158 159 /* group->field */ 160 if (!BN_copy(group->field, p)) 161 goto err; 162 BN_set_negative(group->field, 0); 163 164 /* group->a */ 165 if (!BN_nnmod(tmp_a, a, p, ctx)) 166 goto err; 167 if (group->meth->field_encode) { 168 if (!group->meth->field_encode(group, group->a, tmp_a, ctx)) 169 goto err; 170 } else if (!BN_copy(group->a, tmp_a)) 171 goto err; 172 173 /* group->b */ 174 if (!BN_nnmod(group->b, b, p, ctx)) 175 goto err; 176 if (group->meth->field_encode) 177 if (!group->meth->field_encode(group, group->b, group->b, ctx)) 178 goto err; 179 180 /* group->a_is_minus3 */ 181 if (!BN_add_word(tmp_a, 3)) 182 goto err; 183 group->a_is_minus3 = (0 == BN_cmp(tmp_a, group->field)); 184 185 ret = 1; 186 187 err: 188 BN_CTX_end(ctx); 189 BN_CTX_free(new_ctx); 190 return ret; 191 } 192 193 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, 194 BIGNUM *b, BN_CTX *ctx) 195 { 196 int ret = 0; 197 BN_CTX *new_ctx = NULL; 198 199 if (p != NULL) { 200 if (!BN_copy(p, group->field)) 201 return 0; 202 } 203 204 if (a != NULL || b != NULL) { 205 if (group->meth->field_decode) { 206 if (ctx == NULL) { 207 ctx = new_ctx = BN_CTX_new(); 208 if (ctx == NULL) 209 return 0; 210 } 211 if (a != NULL) { 212 if (!group->meth->field_decode(group, a, group->a, ctx)) 213 goto err; 214 } 215 if (b != NULL) { 216 if (!group->meth->field_decode(group, b, group->b, ctx)) 217 goto err; 218 } 219 } else { 220 if (a != NULL) { 221 if (!BN_copy(a, group->a)) 222 goto err; 223 } 224 if (b != NULL) { 225 if (!BN_copy(b, group->b)) 226 goto err; 227 } 228 } 229 } 230 231 ret = 1; 232 233 err: 234 BN_CTX_free(new_ctx); 235 return ret; 236 } 237 238 int ec_GFp_simple_group_get_degree(const EC_GROUP *group) 239 { 240 return BN_num_bits(group->field); 241 } 242 243 int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx) 244 { 245 int ret = 0; 246 BIGNUM *a, *b, *order, *tmp_1, *tmp_2; 247 const BIGNUM *p = group->field; 248 BN_CTX *new_ctx = NULL; 249 250 if (ctx == NULL) { 251 ctx = new_ctx = BN_CTX_new(); 252 if (ctx == NULL) { 253 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, 254 ERR_R_MALLOC_FAILURE); 255 goto err; 256 } 257 } 258 BN_CTX_start(ctx); 259 a = BN_CTX_get(ctx); 260 b = BN_CTX_get(ctx); 261 tmp_1 = BN_CTX_get(ctx); 262 tmp_2 = BN_CTX_get(ctx); 263 order = BN_CTX_get(ctx); 264 if (order == NULL) 265 goto err; 266 267 if (group->meth->field_decode) { 268 if (!group->meth->field_decode(group, a, group->a, ctx)) 269 goto err; 270 if (!group->meth->field_decode(group, b, group->b, ctx)) 271 goto err; 272 } else { 273 if (!BN_copy(a, group->a)) 274 goto err; 275 if (!BN_copy(b, group->b)) 276 goto err; 277 } 278 279 /*- 280 * check the discriminant: 281 * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p) 282 * 0 =< a, b < p 283 */ 284 if (BN_is_zero(a)) { 285 if (BN_is_zero(b)) 286 goto err; 287 } else if (!BN_is_zero(b)) { 288 if (!BN_mod_sqr(tmp_1, a, p, ctx)) 289 goto err; 290 if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) 291 goto err; 292 if (!BN_lshift(tmp_1, tmp_2, 2)) 293 goto err; 294 /* tmp_1 = 4*a^3 */ 295 296 if (!BN_mod_sqr(tmp_2, b, p, ctx)) 297 goto err; 298 if (!BN_mul_word(tmp_2, 27)) 299 goto err; 300 /* tmp_2 = 27*b^2 */ 301 302 if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) 303 goto err; 304 if (BN_is_zero(a)) 305 goto err; 306 } 307 ret = 1; 308 309 err: 310 BN_CTX_end(ctx); 311 BN_CTX_free(new_ctx); 312 return ret; 313 } 314 315 int ec_GFp_simple_point_init(EC_POINT *point) 316 { 317 point->X = BN_new(); 318 point->Y = BN_new(); 319 point->Z = BN_new(); 320 point->Z_is_one = 0; 321 322 if (point->X == NULL || point->Y == NULL || point->Z == NULL) { 323 BN_free(point->X); 324 BN_free(point->Y); 325 BN_free(point->Z); 326 return 0; 327 } 328 return 1; 329 } 330 331 void ec_GFp_simple_point_finish(EC_POINT *point) 332 { 333 BN_free(point->X); 334 BN_free(point->Y); 335 BN_free(point->Z); 336 } 337 338 void ec_GFp_simple_point_clear_finish(EC_POINT *point) 339 { 340 BN_clear_free(point->X); 341 BN_clear_free(point->Y); 342 BN_clear_free(point->Z); 343 point->Z_is_one = 0; 344 } 345 346 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) 347 { 348 if (!BN_copy(dest->X, src->X)) 349 return 0; 350 if (!BN_copy(dest->Y, src->Y)) 351 return 0; 352 if (!BN_copy(dest->Z, src->Z)) 353 return 0; 354 dest->Z_is_one = src->Z_is_one; 355 dest->curve_name = src->curve_name; 356 357 return 1; 358 } 359 360 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, 361 EC_POINT *point) 362 { 363 point->Z_is_one = 0; 364 BN_zero(point->Z); 365 return 1; 366 } 367 368 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, 369 EC_POINT *point, 370 const BIGNUM *x, 371 const BIGNUM *y, 372 const BIGNUM *z, 373 BN_CTX *ctx) 374 { 375 BN_CTX *new_ctx = NULL; 376 int ret = 0; 377 378 if (ctx == NULL) { 379 ctx = new_ctx = BN_CTX_new(); 380 if (ctx == NULL) 381 return 0; 382 } 383 384 if (x != NULL) { 385 if (!BN_nnmod(point->X, x, group->field, ctx)) 386 goto err; 387 if (group->meth->field_encode) { 388 if (!group->meth->field_encode(group, point->X, point->X, ctx)) 389 goto err; 390 } 391 } 392 393 if (y != NULL) { 394 if (!BN_nnmod(point->Y, y, group->field, ctx)) 395 goto err; 396 if (group->meth->field_encode) { 397 if (!group->meth->field_encode(group, point->Y, point->Y, ctx)) 398 goto err; 399 } 400 } 401 402 if (z != NULL) { 403 int Z_is_one; 404 405 if (!BN_nnmod(point->Z, z, group->field, ctx)) 406 goto err; 407 Z_is_one = BN_is_one(point->Z); 408 if (group->meth->field_encode) { 409 if (Z_is_one && (group->meth->field_set_to_one != 0)) { 410 if (!group->meth->field_set_to_one(group, point->Z, ctx)) 411 goto err; 412 } else { 413 if (!group-> 414 meth->field_encode(group, point->Z, point->Z, ctx)) 415 goto err; 416 } 417 } 418 point->Z_is_one = Z_is_one; 419 } 420 421 ret = 1; 422 423 err: 424 BN_CTX_free(new_ctx); 425 return ret; 426 } 427 428 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, 429 const EC_POINT *point, 430 BIGNUM *x, BIGNUM *y, 431 BIGNUM *z, BN_CTX *ctx) 432 { 433 BN_CTX *new_ctx = NULL; 434 int ret = 0; 435 436 if (group->meth->field_decode != 0) { 437 if (ctx == NULL) { 438 ctx = new_ctx = BN_CTX_new(); 439 if (ctx == NULL) 440 return 0; 441 } 442 443 if (x != NULL) { 444 if (!group->meth->field_decode(group, x, point->X, ctx)) 445 goto err; 446 } 447 if (y != NULL) { 448 if (!group->meth->field_decode(group, y, point->Y, ctx)) 449 goto err; 450 } 451 if (z != NULL) { 452 if (!group->meth->field_decode(group, z, point->Z, ctx)) 453 goto err; 454 } 455 } else { 456 if (x != NULL) { 457 if (!BN_copy(x, point->X)) 458 goto err; 459 } 460 if (y != NULL) { 461 if (!BN_copy(y, point->Y)) 462 goto err; 463 } 464 if (z != NULL) { 465 if (!BN_copy(z, point->Z)) 466 goto err; 467 } 468 } 469 470 ret = 1; 471 472 err: 473 BN_CTX_free(new_ctx); 474 return ret; 475 } 476 477 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, 478 EC_POINT *point, 479 const BIGNUM *x, 480 const BIGNUM *y, BN_CTX *ctx) 481 { 482 if (x == NULL || y == NULL) { 483 /* 484 * unlike for projective coordinates, we do not tolerate this 485 */ 486 ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, 487 ERR_R_PASSED_NULL_PARAMETER); 488 return 0; 489 } 490 491 return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, 492 BN_value_one(), ctx); 493 } 494 495 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, 496 const EC_POINT *point, 497 BIGNUM *x, BIGNUM *y, 498 BN_CTX *ctx) 499 { 500 BN_CTX *new_ctx = NULL; 501 BIGNUM *Z, *Z_1, *Z_2, *Z_3; 502 const BIGNUM *Z_; 503 int ret = 0; 504 505 if (EC_POINT_is_at_infinity(group, point)) { 506 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, 507 EC_R_POINT_AT_INFINITY); 508 return 0; 509 } 510 511 if (ctx == NULL) { 512 ctx = new_ctx = BN_CTX_new(); 513 if (ctx == NULL) 514 return 0; 515 } 516 517 BN_CTX_start(ctx); 518 Z = BN_CTX_get(ctx); 519 Z_1 = BN_CTX_get(ctx); 520 Z_2 = BN_CTX_get(ctx); 521 Z_3 = BN_CTX_get(ctx); 522 if (Z_3 == NULL) 523 goto err; 524 525 /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */ 526 527 if (group->meth->field_decode) { 528 if (!group->meth->field_decode(group, Z, point->Z, ctx)) 529 goto err; 530 Z_ = Z; 531 } else { 532 Z_ = point->Z; 533 } 534 535 if (BN_is_one(Z_)) { 536 if (group->meth->field_decode) { 537 if (x != NULL) { 538 if (!group->meth->field_decode(group, x, point->X, ctx)) 539 goto err; 540 } 541 if (y != NULL) { 542 if (!group->meth->field_decode(group, y, point->Y, ctx)) 543 goto err; 544 } 545 } else { 546 if (x != NULL) { 547 if (!BN_copy(x, point->X)) 548 goto err; 549 } 550 if (y != NULL) { 551 if (!BN_copy(y, point->Y)) 552 goto err; 553 } 554 } 555 } else { 556 if (!group->meth->field_inv(group, Z_1, Z_, ctx)) { 557 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, 558 ERR_R_BN_LIB); 559 goto err; 560 } 561 562 if (group->meth->field_encode == 0) { 563 /* field_sqr works on standard representation */ 564 if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) 565 goto err; 566 } else { 567 if (!BN_mod_sqr(Z_2, Z_1, group->field, ctx)) 568 goto err; 569 } 570 571 if (x != NULL) { 572 /* 573 * in the Montgomery case, field_mul will cancel out Montgomery 574 * factor in X: 575 */ 576 if (!group->meth->field_mul(group, x, point->X, Z_2, ctx)) 577 goto err; 578 } 579 580 if (y != NULL) { 581 if (group->meth->field_encode == 0) { 582 /* 583 * field_mul works on standard representation 584 */ 585 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) 586 goto err; 587 } else { 588 if (!BN_mod_mul(Z_3, Z_2, Z_1, group->field, ctx)) 589 goto err; 590 } 591 592 /* 593 * in the Montgomery case, field_mul will cancel out Montgomery 594 * factor in Y: 595 */ 596 if (!group->meth->field_mul(group, y, point->Y, Z_3, ctx)) 597 goto err; 598 } 599 } 600 601 ret = 1; 602 603 err: 604 BN_CTX_end(ctx); 605 BN_CTX_free(new_ctx); 606 return ret; 607 } 608 609 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 610 const EC_POINT *b, BN_CTX *ctx) 611 { 612 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 613 const BIGNUM *, BN_CTX *); 614 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 615 const BIGNUM *p; 616 BN_CTX *new_ctx = NULL; 617 BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6; 618 int ret = 0; 619 620 if (a == b) 621 return EC_POINT_dbl(group, r, a, ctx); 622 if (EC_POINT_is_at_infinity(group, a)) 623 return EC_POINT_copy(r, b); 624 if (EC_POINT_is_at_infinity(group, b)) 625 return EC_POINT_copy(r, a); 626 627 field_mul = group->meth->field_mul; 628 field_sqr = group->meth->field_sqr; 629 p = group->field; 630 631 if (ctx == NULL) { 632 ctx = new_ctx = BN_CTX_new(); 633 if (ctx == NULL) 634 return 0; 635 } 636 637 BN_CTX_start(ctx); 638 n0 = BN_CTX_get(ctx); 639 n1 = BN_CTX_get(ctx); 640 n2 = BN_CTX_get(ctx); 641 n3 = BN_CTX_get(ctx); 642 n4 = BN_CTX_get(ctx); 643 n5 = BN_CTX_get(ctx); 644 n6 = BN_CTX_get(ctx); 645 if (n6 == NULL) 646 goto end; 647 648 /* 649 * Note that in this function we must not read components of 'a' or 'b' 650 * once we have written the corresponding components of 'r'. ('r' might 651 * be one of 'a' or 'b'.) 652 */ 653 654 /* n1, n2 */ 655 if (b->Z_is_one) { 656 if (!BN_copy(n1, a->X)) 657 goto end; 658 if (!BN_copy(n2, a->Y)) 659 goto end; 660 /* n1 = X_a */ 661 /* n2 = Y_a */ 662 } else { 663 if (!field_sqr(group, n0, b->Z, ctx)) 664 goto end; 665 if (!field_mul(group, n1, a->X, n0, ctx)) 666 goto end; 667 /* n1 = X_a * Z_b^2 */ 668 669 if (!field_mul(group, n0, n0, b->Z, ctx)) 670 goto end; 671 if (!field_mul(group, n2, a->Y, n0, ctx)) 672 goto end; 673 /* n2 = Y_a * Z_b^3 */ 674 } 675 676 /* n3, n4 */ 677 if (a->Z_is_one) { 678 if (!BN_copy(n3, b->X)) 679 goto end; 680 if (!BN_copy(n4, b->Y)) 681 goto end; 682 /* n3 = X_b */ 683 /* n4 = Y_b */ 684 } else { 685 if (!field_sqr(group, n0, a->Z, ctx)) 686 goto end; 687 if (!field_mul(group, n3, b->X, n0, ctx)) 688 goto end; 689 /* n3 = X_b * Z_a^2 */ 690 691 if (!field_mul(group, n0, n0, a->Z, ctx)) 692 goto end; 693 if (!field_mul(group, n4, b->Y, n0, ctx)) 694 goto end; 695 /* n4 = Y_b * Z_a^3 */ 696 } 697 698 /* n5, n6 */ 699 if (!BN_mod_sub_quick(n5, n1, n3, p)) 700 goto end; 701 if (!BN_mod_sub_quick(n6, n2, n4, p)) 702 goto end; 703 /* n5 = n1 - n3 */ 704 /* n6 = n2 - n4 */ 705 706 if (BN_is_zero(n5)) { 707 if (BN_is_zero(n6)) { 708 /* a is the same point as b */ 709 BN_CTX_end(ctx); 710 ret = EC_POINT_dbl(group, r, a, ctx); 711 ctx = NULL; 712 goto end; 713 } else { 714 /* a is the inverse of b */ 715 BN_zero(r->Z); 716 r->Z_is_one = 0; 717 ret = 1; 718 goto end; 719 } 720 } 721 722 /* 'n7', 'n8' */ 723 if (!BN_mod_add_quick(n1, n1, n3, p)) 724 goto end; 725 if (!BN_mod_add_quick(n2, n2, n4, p)) 726 goto end; 727 /* 'n7' = n1 + n3 */ 728 /* 'n8' = n2 + n4 */ 729 730 /* Z_r */ 731 if (a->Z_is_one && b->Z_is_one) { 732 if (!BN_copy(r->Z, n5)) 733 goto end; 734 } else { 735 if (a->Z_is_one) { 736 if (!BN_copy(n0, b->Z)) 737 goto end; 738 } else if (b->Z_is_one) { 739 if (!BN_copy(n0, a->Z)) 740 goto end; 741 } else { 742 if (!field_mul(group, n0, a->Z, b->Z, ctx)) 743 goto end; 744 } 745 if (!field_mul(group, r->Z, n0, n5, ctx)) 746 goto end; 747 } 748 r->Z_is_one = 0; 749 /* Z_r = Z_a * Z_b * n5 */ 750 751 /* X_r */ 752 if (!field_sqr(group, n0, n6, ctx)) 753 goto end; 754 if (!field_sqr(group, n4, n5, ctx)) 755 goto end; 756 if (!field_mul(group, n3, n1, n4, ctx)) 757 goto end; 758 if (!BN_mod_sub_quick(r->X, n0, n3, p)) 759 goto end; 760 /* X_r = n6^2 - n5^2 * 'n7' */ 761 762 /* 'n9' */ 763 if (!BN_mod_lshift1_quick(n0, r->X, p)) 764 goto end; 765 if (!BN_mod_sub_quick(n0, n3, n0, p)) 766 goto end; 767 /* n9 = n5^2 * 'n7' - 2 * X_r */ 768 769 /* Y_r */ 770 if (!field_mul(group, n0, n0, n6, ctx)) 771 goto end; 772 if (!field_mul(group, n5, n4, n5, ctx)) 773 goto end; /* now n5 is n5^3 */ 774 if (!field_mul(group, n1, n2, n5, ctx)) 775 goto end; 776 if (!BN_mod_sub_quick(n0, n0, n1, p)) 777 goto end; 778 if (BN_is_odd(n0)) 779 if (!BN_add(n0, n0, p)) 780 goto end; 781 /* now 0 <= n0 < 2*p, and n0 is even */ 782 if (!BN_rshift1(r->Y, n0)) 783 goto end; 784 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */ 785 786 ret = 1; 787 788 end: 789 BN_CTX_end(ctx); 790 BN_CTX_free(new_ctx); 791 return ret; 792 } 793 794 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 795 BN_CTX *ctx) 796 { 797 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 798 const BIGNUM *, BN_CTX *); 799 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 800 const BIGNUM *p; 801 BN_CTX *new_ctx = NULL; 802 BIGNUM *n0, *n1, *n2, *n3; 803 int ret = 0; 804 805 if (EC_POINT_is_at_infinity(group, a)) { 806 BN_zero(r->Z); 807 r->Z_is_one = 0; 808 return 1; 809 } 810 811 field_mul = group->meth->field_mul; 812 field_sqr = group->meth->field_sqr; 813 p = group->field; 814 815 if (ctx == NULL) { 816 ctx = new_ctx = BN_CTX_new(); 817 if (ctx == NULL) 818 return 0; 819 } 820 821 BN_CTX_start(ctx); 822 n0 = BN_CTX_get(ctx); 823 n1 = BN_CTX_get(ctx); 824 n2 = BN_CTX_get(ctx); 825 n3 = BN_CTX_get(ctx); 826 if (n3 == NULL) 827 goto err; 828 829 /* 830 * Note that in this function we must not read components of 'a' once we 831 * have written the corresponding components of 'r'. ('r' might the same 832 * as 'a'.) 833 */ 834 835 /* n1 */ 836 if (a->Z_is_one) { 837 if (!field_sqr(group, n0, a->X, ctx)) 838 goto err; 839 if (!BN_mod_lshift1_quick(n1, n0, p)) 840 goto err; 841 if (!BN_mod_add_quick(n0, n0, n1, p)) 842 goto err; 843 if (!BN_mod_add_quick(n1, n0, group->a, p)) 844 goto err; 845 /* n1 = 3 * X_a^2 + a_curve */ 846 } else if (group->a_is_minus3) { 847 if (!field_sqr(group, n1, a->Z, ctx)) 848 goto err; 849 if (!BN_mod_add_quick(n0, a->X, n1, p)) 850 goto err; 851 if (!BN_mod_sub_quick(n2, a->X, n1, p)) 852 goto err; 853 if (!field_mul(group, n1, n0, n2, ctx)) 854 goto err; 855 if (!BN_mod_lshift1_quick(n0, n1, p)) 856 goto err; 857 if (!BN_mod_add_quick(n1, n0, n1, p)) 858 goto err; 859 /*- 860 * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) 861 * = 3 * X_a^2 - 3 * Z_a^4 862 */ 863 } else { 864 if (!field_sqr(group, n0, a->X, ctx)) 865 goto err; 866 if (!BN_mod_lshift1_quick(n1, n0, p)) 867 goto err; 868 if (!BN_mod_add_quick(n0, n0, n1, p)) 869 goto err; 870 if (!field_sqr(group, n1, a->Z, ctx)) 871 goto err; 872 if (!field_sqr(group, n1, n1, ctx)) 873 goto err; 874 if (!field_mul(group, n1, n1, group->a, ctx)) 875 goto err; 876 if (!BN_mod_add_quick(n1, n1, n0, p)) 877 goto err; 878 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */ 879 } 880 881 /* Z_r */ 882 if (a->Z_is_one) { 883 if (!BN_copy(n0, a->Y)) 884 goto err; 885 } else { 886 if (!field_mul(group, n0, a->Y, a->Z, ctx)) 887 goto err; 888 } 889 if (!BN_mod_lshift1_quick(r->Z, n0, p)) 890 goto err; 891 r->Z_is_one = 0; 892 /* Z_r = 2 * Y_a * Z_a */ 893 894 /* n2 */ 895 if (!field_sqr(group, n3, a->Y, ctx)) 896 goto err; 897 if (!field_mul(group, n2, a->X, n3, ctx)) 898 goto err; 899 if (!BN_mod_lshift_quick(n2, n2, 2, p)) 900 goto err; 901 /* n2 = 4 * X_a * Y_a^2 */ 902 903 /* X_r */ 904 if (!BN_mod_lshift1_quick(n0, n2, p)) 905 goto err; 906 if (!field_sqr(group, r->X, n1, ctx)) 907 goto err; 908 if (!BN_mod_sub_quick(r->X, r->X, n0, p)) 909 goto err; 910 /* X_r = n1^2 - 2 * n2 */ 911 912 /* n3 */ 913 if (!field_sqr(group, n0, n3, ctx)) 914 goto err; 915 if (!BN_mod_lshift_quick(n3, n0, 3, p)) 916 goto err; 917 /* n3 = 8 * Y_a^4 */ 918 919 /* Y_r */ 920 if (!BN_mod_sub_quick(n0, n2, r->X, p)) 921 goto err; 922 if (!field_mul(group, n0, n1, n0, ctx)) 923 goto err; 924 if (!BN_mod_sub_quick(r->Y, n0, n3, p)) 925 goto err; 926 /* Y_r = n1 * (n2 - X_r) - n3 */ 927 928 ret = 1; 929 930 err: 931 BN_CTX_end(ctx); 932 BN_CTX_free(new_ctx); 933 return ret; 934 } 935 936 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 937 { 938 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y)) 939 /* point is its own inverse */ 940 return 1; 941 942 return BN_usub(point->Y, group->field, point->Y); 943 } 944 945 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) 946 { 947 return BN_is_zero(point->Z); 948 } 949 950 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, 951 BN_CTX *ctx) 952 { 953 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 954 const BIGNUM *, BN_CTX *); 955 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 956 const BIGNUM *p; 957 BN_CTX *new_ctx = NULL; 958 BIGNUM *rh, *tmp, *Z4, *Z6; 959 int ret = -1; 960 961 if (EC_POINT_is_at_infinity(group, point)) 962 return 1; 963 964 field_mul = group->meth->field_mul; 965 field_sqr = group->meth->field_sqr; 966 p = group->field; 967 968 if (ctx == NULL) { 969 ctx = new_ctx = BN_CTX_new(); 970 if (ctx == NULL) 971 return -1; 972 } 973 974 BN_CTX_start(ctx); 975 rh = BN_CTX_get(ctx); 976 tmp = BN_CTX_get(ctx); 977 Z4 = BN_CTX_get(ctx); 978 Z6 = BN_CTX_get(ctx); 979 if (Z6 == NULL) 980 goto err; 981 982 /*- 983 * We have a curve defined by a Weierstrass equation 984 * y^2 = x^3 + a*x + b. 985 * The point to consider is given in Jacobian projective coordinates 986 * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). 987 * Substituting this and multiplying by Z^6 transforms the above equation into 988 * Y^2 = X^3 + a*X*Z^4 + b*Z^6. 989 * To test this, we add up the right-hand side in 'rh'. 990 */ 991 992 /* rh := X^2 */ 993 if (!field_sqr(group, rh, point->X, ctx)) 994 goto err; 995 996 if (!point->Z_is_one) { 997 if (!field_sqr(group, tmp, point->Z, ctx)) 998 goto err; 999 if (!field_sqr(group, Z4, tmp, ctx)) 1000 goto err; 1001 if (!field_mul(group, Z6, Z4, tmp, ctx)) 1002 goto err; 1003 1004 /* rh := (rh + a*Z^4)*X */ 1005 if (group->a_is_minus3) { 1006 if (!BN_mod_lshift1_quick(tmp, Z4, p)) 1007 goto err; 1008 if (!BN_mod_add_quick(tmp, tmp, Z4, p)) 1009 goto err; 1010 if (!BN_mod_sub_quick(rh, rh, tmp, p)) 1011 goto err; 1012 if (!field_mul(group, rh, rh, point->X, ctx)) 1013 goto err; 1014 } else { 1015 if (!field_mul(group, tmp, Z4, group->a, ctx)) 1016 goto err; 1017 if (!BN_mod_add_quick(rh, rh, tmp, p)) 1018 goto err; 1019 if (!field_mul(group, rh, rh, point->X, ctx)) 1020 goto err; 1021 } 1022 1023 /* rh := rh + b*Z^6 */ 1024 if (!field_mul(group, tmp, group->b, Z6, ctx)) 1025 goto err; 1026 if (!BN_mod_add_quick(rh, rh, tmp, p)) 1027 goto err; 1028 } else { 1029 /* point->Z_is_one */ 1030 1031 /* rh := (rh + a)*X */ 1032 if (!BN_mod_add_quick(rh, rh, group->a, p)) 1033 goto err; 1034 if (!field_mul(group, rh, rh, point->X, ctx)) 1035 goto err; 1036 /* rh := rh + b */ 1037 if (!BN_mod_add_quick(rh, rh, group->b, p)) 1038 goto err; 1039 } 1040 1041 /* 'lh' := Y^2 */ 1042 if (!field_sqr(group, tmp, point->Y, ctx)) 1043 goto err; 1044 1045 ret = (0 == BN_ucmp(tmp, rh)); 1046 1047 err: 1048 BN_CTX_end(ctx); 1049 BN_CTX_free(new_ctx); 1050 return ret; 1051 } 1052 1053 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, 1054 const EC_POINT *b, BN_CTX *ctx) 1055 { 1056 /*- 1057 * return values: 1058 * -1 error 1059 * 0 equal (in affine coordinates) 1060 * 1 not equal 1061 */ 1062 1063 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 1064 const BIGNUM *, BN_CTX *); 1065 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1066 BN_CTX *new_ctx = NULL; 1067 BIGNUM *tmp1, *tmp2, *Za23, *Zb23; 1068 const BIGNUM *tmp1_, *tmp2_; 1069 int ret = -1; 1070 1071 if (EC_POINT_is_at_infinity(group, a)) { 1072 return EC_POINT_is_at_infinity(group, b) ? 0 : 1; 1073 } 1074 1075 if (EC_POINT_is_at_infinity(group, b)) 1076 return 1; 1077 1078 if (a->Z_is_one && b->Z_is_one) { 1079 return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1; 1080 } 1081 1082 field_mul = group->meth->field_mul; 1083 field_sqr = group->meth->field_sqr; 1084 1085 if (ctx == NULL) { 1086 ctx = new_ctx = BN_CTX_new(); 1087 if (ctx == NULL) 1088 return -1; 1089 } 1090 1091 BN_CTX_start(ctx); 1092 tmp1 = BN_CTX_get(ctx); 1093 tmp2 = BN_CTX_get(ctx); 1094 Za23 = BN_CTX_get(ctx); 1095 Zb23 = BN_CTX_get(ctx); 1096 if (Zb23 == NULL) 1097 goto end; 1098 1099 /*- 1100 * We have to decide whether 1101 * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), 1102 * or equivalently, whether 1103 * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). 1104 */ 1105 1106 if (!b->Z_is_one) { 1107 if (!field_sqr(group, Zb23, b->Z, ctx)) 1108 goto end; 1109 if (!field_mul(group, tmp1, a->X, Zb23, ctx)) 1110 goto end; 1111 tmp1_ = tmp1; 1112 } else 1113 tmp1_ = a->X; 1114 if (!a->Z_is_one) { 1115 if (!field_sqr(group, Za23, a->Z, ctx)) 1116 goto end; 1117 if (!field_mul(group, tmp2, b->X, Za23, ctx)) 1118 goto end; 1119 tmp2_ = tmp2; 1120 } else 1121 tmp2_ = b->X; 1122 1123 /* compare X_a*Z_b^2 with X_b*Z_a^2 */ 1124 if (BN_cmp(tmp1_, tmp2_) != 0) { 1125 ret = 1; /* points differ */ 1126 goto end; 1127 } 1128 1129 if (!b->Z_is_one) { 1130 if (!field_mul(group, Zb23, Zb23, b->Z, ctx)) 1131 goto end; 1132 if (!field_mul(group, tmp1, a->Y, Zb23, ctx)) 1133 goto end; 1134 /* tmp1_ = tmp1 */ 1135 } else 1136 tmp1_ = a->Y; 1137 if (!a->Z_is_one) { 1138 if (!field_mul(group, Za23, Za23, a->Z, ctx)) 1139 goto end; 1140 if (!field_mul(group, tmp2, b->Y, Za23, ctx)) 1141 goto end; 1142 /* tmp2_ = tmp2 */ 1143 } else 1144 tmp2_ = b->Y; 1145 1146 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ 1147 if (BN_cmp(tmp1_, tmp2_) != 0) { 1148 ret = 1; /* points differ */ 1149 goto end; 1150 } 1151 1152 /* points are equal */ 1153 ret = 0; 1154 1155 end: 1156 BN_CTX_end(ctx); 1157 BN_CTX_free(new_ctx); 1158 return ret; 1159 } 1160 1161 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, 1162 BN_CTX *ctx) 1163 { 1164 BN_CTX *new_ctx = NULL; 1165 BIGNUM *x, *y; 1166 int ret = 0; 1167 1168 if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) 1169 return 1; 1170 1171 if (ctx == NULL) { 1172 ctx = new_ctx = BN_CTX_new(); 1173 if (ctx == NULL) 1174 return 0; 1175 } 1176 1177 BN_CTX_start(ctx); 1178 x = BN_CTX_get(ctx); 1179 y = BN_CTX_get(ctx); 1180 if (y == NULL) 1181 goto err; 1182 1183 if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx)) 1184 goto err; 1185 if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx)) 1186 goto err; 1187 if (!point->Z_is_one) { 1188 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR); 1189 goto err; 1190 } 1191 1192 ret = 1; 1193 1194 err: 1195 BN_CTX_end(ctx); 1196 BN_CTX_free(new_ctx); 1197 return ret; 1198 } 1199 1200 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, 1201 EC_POINT *points[], BN_CTX *ctx) 1202 { 1203 BN_CTX *new_ctx = NULL; 1204 BIGNUM *tmp, *tmp_Z; 1205 BIGNUM **prod_Z = NULL; 1206 size_t i; 1207 int ret = 0; 1208 1209 if (num == 0) 1210 return 1; 1211 1212 if (ctx == NULL) { 1213 ctx = new_ctx = BN_CTX_new(); 1214 if (ctx == NULL) 1215 return 0; 1216 } 1217 1218 BN_CTX_start(ctx); 1219 tmp = BN_CTX_get(ctx); 1220 tmp_Z = BN_CTX_get(ctx); 1221 if (tmp_Z == NULL) 1222 goto err; 1223 1224 prod_Z = OPENSSL_malloc(num * sizeof(prod_Z[0])); 1225 if (prod_Z == NULL) 1226 goto err; 1227 for (i = 0; i < num; i++) { 1228 prod_Z[i] = BN_new(); 1229 if (prod_Z[i] == NULL) 1230 goto err; 1231 } 1232 1233 /* 1234 * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z, 1235 * skipping any zero-valued inputs (pretend that they're 1). 1236 */ 1237 1238 if (!BN_is_zero(points[0]->Z)) { 1239 if (!BN_copy(prod_Z[0], points[0]->Z)) 1240 goto err; 1241 } else { 1242 if (group->meth->field_set_to_one != 0) { 1243 if (!group->meth->field_set_to_one(group, prod_Z[0], ctx)) 1244 goto err; 1245 } else { 1246 if (!BN_one(prod_Z[0])) 1247 goto err; 1248 } 1249 } 1250 1251 for (i = 1; i < num; i++) { 1252 if (!BN_is_zero(points[i]->Z)) { 1253 if (!group-> 1254 meth->field_mul(group, prod_Z[i], prod_Z[i - 1], points[i]->Z, 1255 ctx)) 1256 goto err; 1257 } else { 1258 if (!BN_copy(prod_Z[i], prod_Z[i - 1])) 1259 goto err; 1260 } 1261 } 1262 1263 /* 1264 * Now use a single explicit inversion to replace every non-zero 1265 * points[i]->Z by its inverse. 1266 */ 1267 1268 if (!group->meth->field_inv(group, tmp, prod_Z[num - 1], ctx)) { 1269 ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB); 1270 goto err; 1271 } 1272 if (group->meth->field_encode != 0) { 1273 /* 1274 * In the Montgomery case, we just turned R*H (representing H) into 1275 * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to 1276 * multiply by the Montgomery factor twice. 1277 */ 1278 if (!group->meth->field_encode(group, tmp, tmp, ctx)) 1279 goto err; 1280 if (!group->meth->field_encode(group, tmp, tmp, ctx)) 1281 goto err; 1282 } 1283 1284 for (i = num - 1; i > 0; --i) { 1285 /* 1286 * Loop invariant: tmp is the product of the inverses of points[0]->Z 1287 * .. points[i]->Z (zero-valued inputs skipped). 1288 */ 1289 if (!BN_is_zero(points[i]->Z)) { 1290 /* 1291 * Set tmp_Z to the inverse of points[i]->Z (as product of Z 1292 * inverses 0 .. i, Z values 0 .. i - 1). 1293 */ 1294 if (!group-> 1295 meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx)) 1296 goto err; 1297 /* 1298 * Update tmp to satisfy the loop invariant for i - 1. 1299 */ 1300 if (!group->meth->field_mul(group, tmp, tmp, points[i]->Z, ctx)) 1301 goto err; 1302 /* Replace points[i]->Z by its inverse. */ 1303 if (!BN_copy(points[i]->Z, tmp_Z)) 1304 goto err; 1305 } 1306 } 1307 1308 if (!BN_is_zero(points[0]->Z)) { 1309 /* Replace points[0]->Z by its inverse. */ 1310 if (!BN_copy(points[0]->Z, tmp)) 1311 goto err; 1312 } 1313 1314 /* Finally, fix up the X and Y coordinates for all points. */ 1315 1316 for (i = 0; i < num; i++) { 1317 EC_POINT *p = points[i]; 1318 1319 if (!BN_is_zero(p->Z)) { 1320 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */ 1321 1322 if (!group->meth->field_sqr(group, tmp, p->Z, ctx)) 1323 goto err; 1324 if (!group->meth->field_mul(group, p->X, p->X, tmp, ctx)) 1325 goto err; 1326 1327 if (!group->meth->field_mul(group, tmp, tmp, p->Z, ctx)) 1328 goto err; 1329 if (!group->meth->field_mul(group, p->Y, p->Y, tmp, ctx)) 1330 goto err; 1331 1332 if (group->meth->field_set_to_one != 0) { 1333 if (!group->meth->field_set_to_one(group, p->Z, ctx)) 1334 goto err; 1335 } else { 1336 if (!BN_one(p->Z)) 1337 goto err; 1338 } 1339 p->Z_is_one = 1; 1340 } 1341 } 1342 1343 ret = 1; 1344 1345 err: 1346 BN_CTX_end(ctx); 1347 BN_CTX_free(new_ctx); 1348 if (prod_Z != NULL) { 1349 for (i = 0; i < num; i++) { 1350 if (prod_Z[i] == NULL) 1351 break; 1352 BN_clear_free(prod_Z[i]); 1353 } 1354 OPENSSL_free(prod_Z); 1355 } 1356 return ret; 1357 } 1358 1359 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1360 const BIGNUM *b, BN_CTX *ctx) 1361 { 1362 return BN_mod_mul(r, a, b, group->field, ctx); 1363 } 1364 1365 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1366 BN_CTX *ctx) 1367 { 1368 return BN_mod_sqr(r, a, group->field, ctx); 1369 } 1370 1371 /*- 1372 * Computes the multiplicative inverse of a in GF(p), storing the result in r. 1373 * If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error. 1374 * Since we don't have a Mont structure here, SCA hardening is with blinding. 1375 * NB: "a" must be in _decoded_ form. (i.e. field_decode must precede.) 1376 */ 1377 int ec_GFp_simple_field_inv(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1378 BN_CTX *ctx) 1379 { 1380 BIGNUM *e = NULL; 1381 BN_CTX *new_ctx = NULL; 1382 int ret = 0; 1383 1384 if (ctx == NULL && (ctx = new_ctx = BN_CTX_secure_new()) == NULL) 1385 return 0; 1386 1387 BN_CTX_start(ctx); 1388 if ((e = BN_CTX_get(ctx)) == NULL) 1389 goto err; 1390 1391 do { 1392 if (!BN_priv_rand_range(e, group->field)) 1393 goto err; 1394 } while (BN_is_zero(e)); 1395 1396 /* r := a * e */ 1397 if (!group->meth->field_mul(group, r, a, e, ctx)) 1398 goto err; 1399 /* r := 1/(a * e) */ 1400 if (!BN_mod_inverse(r, r, group->field, ctx)) { 1401 ECerr(EC_F_EC_GFP_SIMPLE_FIELD_INV, EC_R_CANNOT_INVERT); 1402 goto err; 1403 } 1404 /* r := e/(a * e) = 1/a */ 1405 if (!group->meth->field_mul(group, r, r, e, ctx)) 1406 goto err; 1407 1408 ret = 1; 1409 1410 err: 1411 BN_CTX_end(ctx); 1412 BN_CTX_free(new_ctx); 1413 return ret; 1414 } 1415 1416 /*- 1417 * Apply randomization of EC point projective coordinates: 1418 * 1419 * (X, Y ,Z ) = (lambda^2*X, lambda^3*Y, lambda*Z) 1420 * lambda = [1,group->field) 1421 * 1422 */ 1423 int ec_GFp_simple_blind_coordinates(const EC_GROUP *group, EC_POINT *p, 1424 BN_CTX *ctx) 1425 { 1426 int ret = 0; 1427 BIGNUM *lambda = NULL; 1428 BIGNUM *temp = NULL; 1429 1430 BN_CTX_start(ctx); 1431 lambda = BN_CTX_get(ctx); 1432 temp = BN_CTX_get(ctx); 1433 if (temp == NULL) { 1434 ECerr(EC_F_EC_GFP_SIMPLE_BLIND_COORDINATES, ERR_R_MALLOC_FAILURE); 1435 goto end; 1436 } 1437 1438 /*- 1439 * Make sure lambda is not zero. 1440 * If the RNG fails, we cannot blind but nevertheless want 1441 * code to continue smoothly and not clobber the error stack. 1442 */ 1443 do { 1444 ERR_set_mark(); 1445 ret = BN_priv_rand_range(lambda, group->field); 1446 ERR_pop_to_mark(); 1447 if (ret == 0) { 1448 ret = 1; 1449 goto end; 1450 } 1451 } while (BN_is_zero(lambda)); 1452 1453 /* if field_encode defined convert between representations */ 1454 if ((group->meth->field_encode != NULL 1455 && !group->meth->field_encode(group, lambda, lambda, ctx)) 1456 || !group->meth->field_mul(group, p->Z, p->Z, lambda, ctx) 1457 || !group->meth->field_sqr(group, temp, lambda, ctx) 1458 || !group->meth->field_mul(group, p->X, p->X, temp, ctx) 1459 || !group->meth->field_mul(group, temp, temp, lambda, ctx) 1460 || !group->meth->field_mul(group, p->Y, p->Y, temp, ctx)) 1461 goto end; 1462 1463 p->Z_is_one = 0; 1464 ret = 1; 1465 1466 end: 1467 BN_CTX_end(ctx); 1468 return ret; 1469 } 1470 1471 /*- 1472 * Input: 1473 * - p: affine coordinates 1474 * 1475 * Output: 1476 * - s := p, r := 2p: blinded projective (homogeneous) coordinates 1477 * 1478 * For doubling we use Formula 3 from Izu-Takagi "A fast parallel elliptic curve 1479 * multiplication resistant against side channel attacks" appendix, described at 1480 * https://hyperelliptic.org/EFD/g1p/auto-shortw-xz.html#doubling-dbl-2002-it-2 1481 * simplified for Z1=1. 1482 * 1483 * Blinding uses the equivalence relation (\lambda X, \lambda Y, \lambda Z) 1484 * for any non-zero \lambda that holds for projective (homogeneous) coords. 1485 */ 1486 int ec_GFp_simple_ladder_pre(const EC_GROUP *group, 1487 EC_POINT *r, EC_POINT *s, 1488 EC_POINT *p, BN_CTX *ctx) 1489 { 1490 BIGNUM *t1, *t2, *t3, *t4, *t5 = NULL; 1491 1492 t1 = s->Z; 1493 t2 = r->Z; 1494 t3 = s->X; 1495 t4 = r->X; 1496 t5 = s->Y; 1497 1498 if (!p->Z_is_one /* r := 2p */ 1499 || !group->meth->field_sqr(group, t3, p->X, ctx) 1500 || !BN_mod_sub_quick(t4, t3, group->a, group->field) 1501 || !group->meth->field_sqr(group, t4, t4, ctx) 1502 || !group->meth->field_mul(group, t5, p->X, group->b, ctx) 1503 || !BN_mod_lshift_quick(t5, t5, 3, group->field) 1504 /* r->X coord output */ 1505 || !BN_mod_sub_quick(r->X, t4, t5, group->field) 1506 || !BN_mod_add_quick(t1, t3, group->a, group->field) 1507 || !group->meth->field_mul(group, t2, p->X, t1, ctx) 1508 || !BN_mod_add_quick(t2, group->b, t2, group->field) 1509 /* r->Z coord output */ 1510 || !BN_mod_lshift_quick(r->Z, t2, 2, group->field)) 1511 return 0; 1512 1513 /* make sure lambda (r->Y here for storage) is not zero */ 1514 do { 1515 if (!BN_priv_rand_range(r->Y, group->field)) 1516 return 0; 1517 } while (BN_is_zero(r->Y)); 1518 1519 /* make sure lambda (s->Z here for storage) is not zero */ 1520 do { 1521 if (!BN_priv_rand_range(s->Z, group->field)) 1522 return 0; 1523 } while (BN_is_zero(s->Z)); 1524 1525 /* if field_encode defined convert between representations */ 1526 if (group->meth->field_encode != NULL 1527 && (!group->meth->field_encode(group, r->Y, r->Y, ctx) 1528 || !group->meth->field_encode(group, s->Z, s->Z, ctx))) 1529 return 0; 1530 1531 /* blind r and s independently */ 1532 if (!group->meth->field_mul(group, r->Z, r->Z, r->Y, ctx) 1533 || !group->meth->field_mul(group, r->X, r->X, r->Y, ctx) 1534 || !group->meth->field_mul(group, s->X, p->X, s->Z, ctx)) /* s := p */ 1535 return 0; 1536 1537 r->Z_is_one = 0; 1538 s->Z_is_one = 0; 1539 1540 return 1; 1541 } 1542 1543 /*- 1544 * Input: 1545 * - s, r: projective (homogeneous) coordinates 1546 * - p: affine coordinates 1547 * 1548 * Output: 1549 * - s := r + s, r := 2r: projective (homogeneous) coordinates 1550 * 1551 * Differential addition-and-doubling using Eq. (9) and (10) from Izu-Takagi 1552 * "A fast parallel elliptic curve multiplication resistant against side channel 1553 * attacks", as described at 1554 * https://hyperelliptic.org/EFD/g1p/auto-shortw-xz.html#ladder-mladd-2002-it-4 1555 */ 1556 int ec_GFp_simple_ladder_step(const EC_GROUP *group, 1557 EC_POINT *r, EC_POINT *s, 1558 EC_POINT *p, BN_CTX *ctx) 1559 { 1560 int ret = 0; 1561 BIGNUM *t0, *t1, *t2, *t3, *t4, *t5, *t6 = NULL; 1562 1563 BN_CTX_start(ctx); 1564 t0 = BN_CTX_get(ctx); 1565 t1 = BN_CTX_get(ctx); 1566 t2 = BN_CTX_get(ctx); 1567 t3 = BN_CTX_get(ctx); 1568 t4 = BN_CTX_get(ctx); 1569 t5 = BN_CTX_get(ctx); 1570 t6 = BN_CTX_get(ctx); 1571 1572 if (t6 == NULL 1573 || !group->meth->field_mul(group, t6, r->X, s->X, ctx) 1574 || !group->meth->field_mul(group, t0, r->Z, s->Z, ctx) 1575 || !group->meth->field_mul(group, t4, r->X, s->Z, ctx) 1576 || !group->meth->field_mul(group, t3, r->Z, s->X, ctx) 1577 || !group->meth->field_mul(group, t5, group->a, t0, ctx) 1578 || !BN_mod_add_quick(t5, t6, t5, group->field) 1579 || !BN_mod_add_quick(t6, t3, t4, group->field) 1580 || !group->meth->field_mul(group, t5, t6, t5, ctx) 1581 || !group->meth->field_sqr(group, t0, t0, ctx) 1582 || !BN_mod_lshift_quick(t2, group->b, 2, group->field) 1583 || !group->meth->field_mul(group, t0, t2, t0, ctx) 1584 || !BN_mod_lshift1_quick(t5, t5, group->field) 1585 || !BN_mod_sub_quick(t3, t4, t3, group->field) 1586 /* s->Z coord output */ 1587 || !group->meth->field_sqr(group, s->Z, t3, ctx) 1588 || !group->meth->field_mul(group, t4, s->Z, p->X, ctx) 1589 || !BN_mod_add_quick(t0, t0, t5, group->field) 1590 /* s->X coord output */ 1591 || !BN_mod_sub_quick(s->X, t0, t4, group->field) 1592 || !group->meth->field_sqr(group, t4, r->X, ctx) 1593 || !group->meth->field_sqr(group, t5, r->Z, ctx) 1594 || !group->meth->field_mul(group, t6, t5, group->a, ctx) 1595 || !BN_mod_add_quick(t1, r->X, r->Z, group->field) 1596 || !group->meth->field_sqr(group, t1, t1, ctx) 1597 || !BN_mod_sub_quick(t1, t1, t4, group->field) 1598 || !BN_mod_sub_quick(t1, t1, t5, group->field) 1599 || !BN_mod_sub_quick(t3, t4, t6, group->field) 1600 || !group->meth->field_sqr(group, t3, t3, ctx) 1601 || !group->meth->field_mul(group, t0, t5, t1, ctx) 1602 || !group->meth->field_mul(group, t0, t2, t0, ctx) 1603 /* r->X coord output */ 1604 || !BN_mod_sub_quick(r->X, t3, t0, group->field) 1605 || !BN_mod_add_quick(t3, t4, t6, group->field) 1606 || !group->meth->field_sqr(group, t4, t5, ctx) 1607 || !group->meth->field_mul(group, t4, t4, t2, ctx) 1608 || !group->meth->field_mul(group, t1, t1, t3, ctx) 1609 || !BN_mod_lshift1_quick(t1, t1, group->field) 1610 /* r->Z coord output */ 1611 || !BN_mod_add_quick(r->Z, t4, t1, group->field)) 1612 goto err; 1613 1614 ret = 1; 1615 1616 err: 1617 BN_CTX_end(ctx); 1618 return ret; 1619 } 1620 1621 /*- 1622 * Input: 1623 * - s, r: projective (homogeneous) coordinates 1624 * - p: affine coordinates 1625 * 1626 * Output: 1627 * - r := (x,y): affine coordinates 1628 * 1629 * Recovers the y-coordinate of r using Eq. (8) from Brier-Joye, "Weierstrass 1630 * Elliptic Curves and Side-Channel Attacks", modified to work in mixed 1631 * projective coords, i.e. p is affine and (r,s) in projective (homogeneous) 1632 * coords, and return r in affine coordinates. 1633 * 1634 * X4 = two*Y1*X2*Z3*Z2; 1635 * Y4 = two*b*Z3*SQR(Z2) + Z3*(a*Z2+X1*X2)*(X1*Z2+X2) - X3*SQR(X1*Z2-X2); 1636 * Z4 = two*Y1*Z3*SQR(Z2); 1637 * 1638 * Z4 != 0 because: 1639 * - Z2==0 implies r is at infinity (handled by the BN_is_zero(r->Z) branch); 1640 * - Z3==0 implies s is at infinity (handled by the BN_is_zero(s->Z) branch); 1641 * - Y1==0 implies p has order 2, so either r or s are infinity and handled by 1642 * one of the BN_is_zero(...) branches. 1643 */ 1644 int ec_GFp_simple_ladder_post(const EC_GROUP *group, 1645 EC_POINT *r, EC_POINT *s, 1646 EC_POINT *p, BN_CTX *ctx) 1647 { 1648 int ret = 0; 1649 BIGNUM *t0, *t1, *t2, *t3, *t4, *t5, *t6 = NULL; 1650 1651 if (BN_is_zero(r->Z)) 1652 return EC_POINT_set_to_infinity(group, r); 1653 1654 if (BN_is_zero(s->Z)) { 1655 if (!EC_POINT_copy(r, p) 1656 || !EC_POINT_invert(group, r, ctx)) 1657 return 0; 1658 return 1; 1659 } 1660 1661 BN_CTX_start(ctx); 1662 t0 = BN_CTX_get(ctx); 1663 t1 = BN_CTX_get(ctx); 1664 t2 = BN_CTX_get(ctx); 1665 t3 = BN_CTX_get(ctx); 1666 t4 = BN_CTX_get(ctx); 1667 t5 = BN_CTX_get(ctx); 1668 t6 = BN_CTX_get(ctx); 1669 1670 if (t6 == NULL 1671 || !BN_mod_lshift1_quick(t4, p->Y, group->field) 1672 || !group->meth->field_mul(group, t6, r->X, t4, ctx) 1673 || !group->meth->field_mul(group, t6, s->Z, t6, ctx) 1674 || !group->meth->field_mul(group, t5, r->Z, t6, ctx) 1675 || !BN_mod_lshift1_quick(t1, group->b, group->field) 1676 || !group->meth->field_mul(group, t1, s->Z, t1, ctx) 1677 || !group->meth->field_sqr(group, t3, r->Z, ctx) 1678 || !group->meth->field_mul(group, t2, t3, t1, ctx) 1679 || !group->meth->field_mul(group, t6, r->Z, group->a, ctx) 1680 || !group->meth->field_mul(group, t1, p->X, r->X, ctx) 1681 || !BN_mod_add_quick(t1, t1, t6, group->field) 1682 || !group->meth->field_mul(group, t1, s->Z, t1, ctx) 1683 || !group->meth->field_mul(group, t0, p->X, r->Z, ctx) 1684 || !BN_mod_add_quick(t6, r->X, t0, group->field) 1685 || !group->meth->field_mul(group, t6, t6, t1, ctx) 1686 || !BN_mod_add_quick(t6, t6, t2, group->field) 1687 || !BN_mod_sub_quick(t0, t0, r->X, group->field) 1688 || !group->meth->field_sqr(group, t0, t0, ctx) 1689 || !group->meth->field_mul(group, t0, t0, s->X, ctx) 1690 || !BN_mod_sub_quick(t0, t6, t0, group->field) 1691 || !group->meth->field_mul(group, t1, s->Z, t4, ctx) 1692 || !group->meth->field_mul(group, t1, t3, t1, ctx) 1693 || (group->meth->field_decode != NULL 1694 && !group->meth->field_decode(group, t1, t1, ctx)) 1695 || !group->meth->field_inv(group, t1, t1, ctx) 1696 || (group->meth->field_encode != NULL 1697 && !group->meth->field_encode(group, t1, t1, ctx)) 1698 || !group->meth->field_mul(group, r->X, t5, t1, ctx) 1699 || !group->meth->field_mul(group, r->Y, t0, t1, ctx)) 1700 goto err; 1701 1702 if (group->meth->field_set_to_one != NULL) { 1703 if (!group->meth->field_set_to_one(group, r->Z, ctx)) 1704 goto err; 1705 } else { 1706 if (!BN_one(r->Z)) 1707 goto err; 1708 } 1709 1710 r->Z_is_one = 1; 1711 ret = 1; 1712 1713 err: 1714 BN_CTX_end(ctx); 1715 return ret; 1716 } 1717