1 /* 2 * Copyright 2001-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 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_lcl.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 0 /* field_encode */ , 55 0 /* field_decode */ , 56 0, /* field_set_to_one */ 57 ec_key_simple_priv2oct, 58 ec_key_simple_oct2priv, 59 0, /* set private */ 60 ec_key_simple_generate_key, 61 ec_key_simple_check_key, 62 ec_key_simple_generate_public_key, 63 0, /* keycopy */ 64 0, /* keyfinish */ 65 ecdh_simple_compute_key, 66 0, /* field_inverse_mod_ord */ 67 ec_GFp_simple_blind_coordinates, 68 ec_GFp_simple_ladder_pre, 69 ec_GFp_simple_ladder_step, 70 ec_GFp_simple_ladder_post 71 }; 72 73 return &ret; 74 } 75 76 /* 77 * Most method functions in this file are designed to work with 78 * non-trivial representations of field elements if necessary 79 * (see ecp_mont.c): while standard modular addition and subtraction 80 * are used, the field_mul and field_sqr methods will be used for 81 * multiplication, and field_encode and field_decode (if defined) 82 * will be used for converting between representations. 83 * 84 * Functions ec_GFp_simple_points_make_affine() and 85 * ec_GFp_simple_point_get_affine_coordinates() specifically assume 86 * that if a non-trivial representation is used, it is a Montgomery 87 * representation (i.e. 'encoding' means multiplying by some factor R). 88 */ 89 90 int ec_GFp_simple_group_init(EC_GROUP *group) 91 { 92 group->field = BN_new(); 93 group->a = BN_new(); 94 group->b = BN_new(); 95 if (group->field == NULL || group->a == NULL || group->b == NULL) { 96 BN_free(group->field); 97 BN_free(group->a); 98 BN_free(group->b); 99 return 0; 100 } 101 group->a_is_minus3 = 0; 102 return 1; 103 } 104 105 void ec_GFp_simple_group_finish(EC_GROUP *group) 106 { 107 BN_free(group->field); 108 BN_free(group->a); 109 BN_free(group->b); 110 } 111 112 void ec_GFp_simple_group_clear_finish(EC_GROUP *group) 113 { 114 BN_clear_free(group->field); 115 BN_clear_free(group->a); 116 BN_clear_free(group->b); 117 } 118 119 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) 120 { 121 if (!BN_copy(dest->field, src->field)) 122 return 0; 123 if (!BN_copy(dest->a, src->a)) 124 return 0; 125 if (!BN_copy(dest->b, src->b)) 126 return 0; 127 128 dest->a_is_minus3 = src->a_is_minus3; 129 130 return 1; 131 } 132 133 int ec_GFp_simple_group_set_curve(EC_GROUP *group, 134 const BIGNUM *p, const BIGNUM *a, 135 const BIGNUM *b, BN_CTX *ctx) 136 { 137 int ret = 0; 138 BN_CTX *new_ctx = NULL; 139 BIGNUM *tmp_a; 140 141 /* p must be a prime > 3 */ 142 if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) { 143 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD); 144 return 0; 145 } 146 147 if (ctx == NULL) { 148 ctx = new_ctx = BN_CTX_new(); 149 if (ctx == NULL) 150 return 0; 151 } 152 153 BN_CTX_start(ctx); 154 tmp_a = BN_CTX_get(ctx); 155 if (tmp_a == NULL) 156 goto err; 157 158 /* group->field */ 159 if (!BN_copy(group->field, p)) 160 goto err; 161 BN_set_negative(group->field, 0); 162 163 /* group->a */ 164 if (!BN_nnmod(tmp_a, a, p, ctx)) 165 goto err; 166 if (group->meth->field_encode) { 167 if (!group->meth->field_encode(group, group->a, tmp_a, ctx)) 168 goto err; 169 } else if (!BN_copy(group->a, tmp_a)) 170 goto err; 171 172 /* group->b */ 173 if (!BN_nnmod(group->b, b, p, ctx)) 174 goto err; 175 if (group->meth->field_encode) 176 if (!group->meth->field_encode(group, group->b, group->b, ctx)) 177 goto err; 178 179 /* group->a_is_minus3 */ 180 if (!BN_add_word(tmp_a, 3)) 181 goto err; 182 group->a_is_minus3 = (0 == BN_cmp(tmp_a, group->field)); 183 184 ret = 1; 185 186 err: 187 BN_CTX_end(ctx); 188 BN_CTX_free(new_ctx); 189 return ret; 190 } 191 192 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, 193 BIGNUM *b, BN_CTX *ctx) 194 { 195 int ret = 0; 196 BN_CTX *new_ctx = NULL; 197 198 if (p != NULL) { 199 if (!BN_copy(p, group->field)) 200 return 0; 201 } 202 203 if (a != NULL || b != NULL) { 204 if (group->meth->field_decode) { 205 if (ctx == NULL) { 206 ctx = new_ctx = BN_CTX_new(); 207 if (ctx == NULL) 208 return 0; 209 } 210 if (a != NULL) { 211 if (!group->meth->field_decode(group, a, group->a, ctx)) 212 goto err; 213 } 214 if (b != NULL) { 215 if (!group->meth->field_decode(group, b, group->b, ctx)) 216 goto err; 217 } 218 } else { 219 if (a != NULL) { 220 if (!BN_copy(a, group->a)) 221 goto err; 222 } 223 if (b != NULL) { 224 if (!BN_copy(b, group->b)) 225 goto err; 226 } 227 } 228 } 229 230 ret = 1; 231 232 err: 233 BN_CTX_free(new_ctx); 234 return ret; 235 } 236 237 int ec_GFp_simple_group_get_degree(const EC_GROUP *group) 238 { 239 return BN_num_bits(group->field); 240 } 241 242 int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx) 243 { 244 int ret = 0; 245 BIGNUM *a, *b, *order, *tmp_1, *tmp_2; 246 const BIGNUM *p = group->field; 247 BN_CTX *new_ctx = NULL; 248 249 if (ctx == NULL) { 250 ctx = new_ctx = BN_CTX_new(); 251 if (ctx == NULL) { 252 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, 253 ERR_R_MALLOC_FAILURE); 254 goto err; 255 } 256 } 257 BN_CTX_start(ctx); 258 a = BN_CTX_get(ctx); 259 b = BN_CTX_get(ctx); 260 tmp_1 = BN_CTX_get(ctx); 261 tmp_2 = BN_CTX_get(ctx); 262 order = BN_CTX_get(ctx); 263 if (order == NULL) 264 goto err; 265 266 if (group->meth->field_decode) { 267 if (!group->meth->field_decode(group, a, group->a, ctx)) 268 goto err; 269 if (!group->meth->field_decode(group, b, group->b, ctx)) 270 goto err; 271 } else { 272 if (!BN_copy(a, group->a)) 273 goto err; 274 if (!BN_copy(b, group->b)) 275 goto err; 276 } 277 278 /*- 279 * check the discriminant: 280 * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p) 281 * 0 =< a, b < p 282 */ 283 if (BN_is_zero(a)) { 284 if (BN_is_zero(b)) 285 goto err; 286 } else if (!BN_is_zero(b)) { 287 if (!BN_mod_sqr(tmp_1, a, p, ctx)) 288 goto err; 289 if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) 290 goto err; 291 if (!BN_lshift(tmp_1, tmp_2, 2)) 292 goto err; 293 /* tmp_1 = 4*a^3 */ 294 295 if (!BN_mod_sqr(tmp_2, b, p, ctx)) 296 goto err; 297 if (!BN_mul_word(tmp_2, 27)) 298 goto err; 299 /* tmp_2 = 27*b^2 */ 300 301 if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) 302 goto err; 303 if (BN_is_zero(a)) 304 goto err; 305 } 306 ret = 1; 307 308 err: 309 if (ctx != NULL) 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 (!BN_mod_inverse(Z_1, Z_, group->field, 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 if (ctx) /* otherwise we already called BN_CTX_end */ 790 BN_CTX_end(ctx); 791 BN_CTX_free(new_ctx); 792 return ret; 793 } 794 795 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 796 BN_CTX *ctx) 797 { 798 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 799 const BIGNUM *, BN_CTX *); 800 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 801 const BIGNUM *p; 802 BN_CTX *new_ctx = NULL; 803 BIGNUM *n0, *n1, *n2, *n3; 804 int ret = 0; 805 806 if (EC_POINT_is_at_infinity(group, a)) { 807 BN_zero(r->Z); 808 r->Z_is_one = 0; 809 return 1; 810 } 811 812 field_mul = group->meth->field_mul; 813 field_sqr = group->meth->field_sqr; 814 p = group->field; 815 816 if (ctx == NULL) { 817 ctx = new_ctx = BN_CTX_new(); 818 if (ctx == NULL) 819 return 0; 820 } 821 822 BN_CTX_start(ctx); 823 n0 = BN_CTX_get(ctx); 824 n1 = BN_CTX_get(ctx); 825 n2 = BN_CTX_get(ctx); 826 n3 = BN_CTX_get(ctx); 827 if (n3 == NULL) 828 goto err; 829 830 /* 831 * Note that in this function we must not read components of 'a' once we 832 * have written the corresponding components of 'r'. ('r' might the same 833 * as 'a'.) 834 */ 835 836 /* n1 */ 837 if (a->Z_is_one) { 838 if (!field_sqr(group, n0, a->X, ctx)) 839 goto err; 840 if (!BN_mod_lshift1_quick(n1, n0, p)) 841 goto err; 842 if (!BN_mod_add_quick(n0, n0, n1, p)) 843 goto err; 844 if (!BN_mod_add_quick(n1, n0, group->a, p)) 845 goto err; 846 /* n1 = 3 * X_a^2 + a_curve */ 847 } else if (group->a_is_minus3) { 848 if (!field_sqr(group, n1, a->Z, ctx)) 849 goto err; 850 if (!BN_mod_add_quick(n0, a->X, n1, p)) 851 goto err; 852 if (!BN_mod_sub_quick(n2, a->X, n1, p)) 853 goto err; 854 if (!field_mul(group, n1, n0, n2, ctx)) 855 goto err; 856 if (!BN_mod_lshift1_quick(n0, n1, p)) 857 goto err; 858 if (!BN_mod_add_quick(n1, n0, n1, p)) 859 goto err; 860 /*- 861 * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) 862 * = 3 * X_a^2 - 3 * Z_a^4 863 */ 864 } else { 865 if (!field_sqr(group, n0, a->X, ctx)) 866 goto err; 867 if (!BN_mod_lshift1_quick(n1, n0, p)) 868 goto err; 869 if (!BN_mod_add_quick(n0, n0, n1, p)) 870 goto err; 871 if (!field_sqr(group, n1, a->Z, ctx)) 872 goto err; 873 if (!field_sqr(group, n1, n1, ctx)) 874 goto err; 875 if (!field_mul(group, n1, n1, group->a, ctx)) 876 goto err; 877 if (!BN_mod_add_quick(n1, n1, n0, p)) 878 goto err; 879 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */ 880 } 881 882 /* Z_r */ 883 if (a->Z_is_one) { 884 if (!BN_copy(n0, a->Y)) 885 goto err; 886 } else { 887 if (!field_mul(group, n0, a->Y, a->Z, ctx)) 888 goto err; 889 } 890 if (!BN_mod_lshift1_quick(r->Z, n0, p)) 891 goto err; 892 r->Z_is_one = 0; 893 /* Z_r = 2 * Y_a * Z_a */ 894 895 /* n2 */ 896 if (!field_sqr(group, n3, a->Y, ctx)) 897 goto err; 898 if (!field_mul(group, n2, a->X, n3, ctx)) 899 goto err; 900 if (!BN_mod_lshift_quick(n2, n2, 2, p)) 901 goto err; 902 /* n2 = 4 * X_a * Y_a^2 */ 903 904 /* X_r */ 905 if (!BN_mod_lshift1_quick(n0, n2, p)) 906 goto err; 907 if (!field_sqr(group, r->X, n1, ctx)) 908 goto err; 909 if (!BN_mod_sub_quick(r->X, r->X, n0, p)) 910 goto err; 911 /* X_r = n1^2 - 2 * n2 */ 912 913 /* n3 */ 914 if (!field_sqr(group, n0, n3, ctx)) 915 goto err; 916 if (!BN_mod_lshift_quick(n3, n0, 3, p)) 917 goto err; 918 /* n3 = 8 * Y_a^4 */ 919 920 /* Y_r */ 921 if (!BN_mod_sub_quick(n0, n2, r->X, p)) 922 goto err; 923 if (!field_mul(group, n0, n1, n0, ctx)) 924 goto err; 925 if (!BN_mod_sub_quick(r->Y, n0, n3, p)) 926 goto err; 927 /* Y_r = n1 * (n2 - X_r) - n3 */ 928 929 ret = 1; 930 931 err: 932 BN_CTX_end(ctx); 933 BN_CTX_free(new_ctx); 934 return ret; 935 } 936 937 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 938 { 939 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y)) 940 /* point is its own inverse */ 941 return 1; 942 943 return BN_usub(point->Y, group->field, point->Y); 944 } 945 946 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) 947 { 948 return BN_is_zero(point->Z); 949 } 950 951 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, 952 BN_CTX *ctx) 953 { 954 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 955 const BIGNUM *, BN_CTX *); 956 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 957 const BIGNUM *p; 958 BN_CTX *new_ctx = NULL; 959 BIGNUM *rh, *tmp, *Z4, *Z6; 960 int ret = -1; 961 962 if (EC_POINT_is_at_infinity(group, point)) 963 return 1; 964 965 field_mul = group->meth->field_mul; 966 field_sqr = group->meth->field_sqr; 967 p = group->field; 968 969 if (ctx == NULL) { 970 ctx = new_ctx = BN_CTX_new(); 971 if (ctx == NULL) 972 return -1; 973 } 974 975 BN_CTX_start(ctx); 976 rh = BN_CTX_get(ctx); 977 tmp = BN_CTX_get(ctx); 978 Z4 = BN_CTX_get(ctx); 979 Z6 = BN_CTX_get(ctx); 980 if (Z6 == NULL) 981 goto err; 982 983 /*- 984 * We have a curve defined by a Weierstrass equation 985 * y^2 = x^3 + a*x + b. 986 * The point to consider is given in Jacobian projective coordinates 987 * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). 988 * Substituting this and multiplying by Z^6 transforms the above equation into 989 * Y^2 = X^3 + a*X*Z^4 + b*Z^6. 990 * To test this, we add up the right-hand side in 'rh'. 991 */ 992 993 /* rh := X^2 */ 994 if (!field_sqr(group, rh, point->X, ctx)) 995 goto err; 996 997 if (!point->Z_is_one) { 998 if (!field_sqr(group, tmp, point->Z, ctx)) 999 goto err; 1000 if (!field_sqr(group, Z4, tmp, ctx)) 1001 goto err; 1002 if (!field_mul(group, Z6, Z4, tmp, ctx)) 1003 goto err; 1004 1005 /* rh := (rh + a*Z^4)*X */ 1006 if (group->a_is_minus3) { 1007 if (!BN_mod_lshift1_quick(tmp, Z4, p)) 1008 goto err; 1009 if (!BN_mod_add_quick(tmp, tmp, Z4, p)) 1010 goto err; 1011 if (!BN_mod_sub_quick(rh, rh, tmp, p)) 1012 goto err; 1013 if (!field_mul(group, rh, rh, point->X, ctx)) 1014 goto err; 1015 } else { 1016 if (!field_mul(group, tmp, Z4, group->a, ctx)) 1017 goto err; 1018 if (!BN_mod_add_quick(rh, rh, tmp, p)) 1019 goto err; 1020 if (!field_mul(group, rh, rh, point->X, ctx)) 1021 goto err; 1022 } 1023 1024 /* rh := rh + b*Z^6 */ 1025 if (!field_mul(group, tmp, group->b, Z6, ctx)) 1026 goto err; 1027 if (!BN_mod_add_quick(rh, rh, tmp, p)) 1028 goto err; 1029 } else { 1030 /* point->Z_is_one */ 1031 1032 /* rh := (rh + a)*X */ 1033 if (!BN_mod_add_quick(rh, rh, group->a, p)) 1034 goto err; 1035 if (!field_mul(group, rh, rh, point->X, ctx)) 1036 goto err; 1037 /* rh := rh + b */ 1038 if (!BN_mod_add_quick(rh, rh, group->b, p)) 1039 goto err; 1040 } 1041 1042 /* 'lh' := Y^2 */ 1043 if (!field_sqr(group, tmp, point->Y, ctx)) 1044 goto err; 1045 1046 ret = (0 == BN_ucmp(tmp, rh)); 1047 1048 err: 1049 BN_CTX_end(ctx); 1050 BN_CTX_free(new_ctx); 1051 return ret; 1052 } 1053 1054 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, 1055 const EC_POINT *b, BN_CTX *ctx) 1056 { 1057 /*- 1058 * return values: 1059 * -1 error 1060 * 0 equal (in affine coordinates) 1061 * 1 not equal 1062 */ 1063 1064 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 1065 const BIGNUM *, BN_CTX *); 1066 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1067 BN_CTX *new_ctx = NULL; 1068 BIGNUM *tmp1, *tmp2, *Za23, *Zb23; 1069 const BIGNUM *tmp1_, *tmp2_; 1070 int ret = -1; 1071 1072 if (EC_POINT_is_at_infinity(group, a)) { 1073 return EC_POINT_is_at_infinity(group, b) ? 0 : 1; 1074 } 1075 1076 if (EC_POINT_is_at_infinity(group, b)) 1077 return 1; 1078 1079 if (a->Z_is_one && b->Z_is_one) { 1080 return ((BN_cmp(a->X, b->X) == 0) && BN_cmp(a->Y, b->Y) == 0) ? 0 : 1; 1081 } 1082 1083 field_mul = group->meth->field_mul; 1084 field_sqr = group->meth->field_sqr; 1085 1086 if (ctx == NULL) { 1087 ctx = new_ctx = BN_CTX_new(); 1088 if (ctx == NULL) 1089 return -1; 1090 } 1091 1092 BN_CTX_start(ctx); 1093 tmp1 = BN_CTX_get(ctx); 1094 tmp2 = BN_CTX_get(ctx); 1095 Za23 = BN_CTX_get(ctx); 1096 Zb23 = BN_CTX_get(ctx); 1097 if (Zb23 == NULL) 1098 goto end; 1099 1100 /*- 1101 * We have to decide whether 1102 * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), 1103 * or equivalently, whether 1104 * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). 1105 */ 1106 1107 if (!b->Z_is_one) { 1108 if (!field_sqr(group, Zb23, b->Z, ctx)) 1109 goto end; 1110 if (!field_mul(group, tmp1, a->X, Zb23, ctx)) 1111 goto end; 1112 tmp1_ = tmp1; 1113 } else 1114 tmp1_ = a->X; 1115 if (!a->Z_is_one) { 1116 if (!field_sqr(group, Za23, a->Z, ctx)) 1117 goto end; 1118 if (!field_mul(group, tmp2, b->X, Za23, ctx)) 1119 goto end; 1120 tmp2_ = tmp2; 1121 } else 1122 tmp2_ = b->X; 1123 1124 /* compare X_a*Z_b^2 with X_b*Z_a^2 */ 1125 if (BN_cmp(tmp1_, tmp2_) != 0) { 1126 ret = 1; /* points differ */ 1127 goto end; 1128 } 1129 1130 if (!b->Z_is_one) { 1131 if (!field_mul(group, Zb23, Zb23, b->Z, ctx)) 1132 goto end; 1133 if (!field_mul(group, tmp1, a->Y, Zb23, ctx)) 1134 goto end; 1135 /* tmp1_ = tmp1 */ 1136 } else 1137 tmp1_ = a->Y; 1138 if (!a->Z_is_one) { 1139 if (!field_mul(group, Za23, Za23, a->Z, ctx)) 1140 goto end; 1141 if (!field_mul(group, tmp2, b->Y, Za23, ctx)) 1142 goto end; 1143 /* tmp2_ = tmp2 */ 1144 } else 1145 tmp2_ = b->Y; 1146 1147 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ 1148 if (BN_cmp(tmp1_, tmp2_) != 0) { 1149 ret = 1; /* points differ */ 1150 goto end; 1151 } 1152 1153 /* points are equal */ 1154 ret = 0; 1155 1156 end: 1157 BN_CTX_end(ctx); 1158 BN_CTX_free(new_ctx); 1159 return ret; 1160 } 1161 1162 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, 1163 BN_CTX *ctx) 1164 { 1165 BN_CTX *new_ctx = NULL; 1166 BIGNUM *x, *y; 1167 int ret = 0; 1168 1169 if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) 1170 return 1; 1171 1172 if (ctx == NULL) { 1173 ctx = new_ctx = BN_CTX_new(); 1174 if (ctx == NULL) 1175 return 0; 1176 } 1177 1178 BN_CTX_start(ctx); 1179 x = BN_CTX_get(ctx); 1180 y = BN_CTX_get(ctx); 1181 if (y == NULL) 1182 goto err; 1183 1184 if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx)) 1185 goto err; 1186 if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx)) 1187 goto err; 1188 if (!point->Z_is_one) { 1189 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR); 1190 goto err; 1191 } 1192 1193 ret = 1; 1194 1195 err: 1196 BN_CTX_end(ctx); 1197 BN_CTX_free(new_ctx); 1198 return ret; 1199 } 1200 1201 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, 1202 EC_POINT *points[], BN_CTX *ctx) 1203 { 1204 BN_CTX *new_ctx = NULL; 1205 BIGNUM *tmp, *tmp_Z; 1206 BIGNUM **prod_Z = NULL; 1207 size_t i; 1208 int ret = 0; 1209 1210 if (num == 0) 1211 return 1; 1212 1213 if (ctx == NULL) { 1214 ctx = new_ctx = BN_CTX_new(); 1215 if (ctx == NULL) 1216 return 0; 1217 } 1218 1219 BN_CTX_start(ctx); 1220 tmp = BN_CTX_get(ctx); 1221 tmp_Z = BN_CTX_get(ctx); 1222 if (tmp_Z == NULL) 1223 goto err; 1224 1225 prod_Z = OPENSSL_malloc(num * sizeof(prod_Z[0])); 1226 if (prod_Z == NULL) 1227 goto err; 1228 for (i = 0; i < num; i++) { 1229 prod_Z[i] = BN_new(); 1230 if (prod_Z[i] == NULL) 1231 goto err; 1232 } 1233 1234 /* 1235 * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z, 1236 * skipping any zero-valued inputs (pretend that they're 1). 1237 */ 1238 1239 if (!BN_is_zero(points[0]->Z)) { 1240 if (!BN_copy(prod_Z[0], points[0]->Z)) 1241 goto err; 1242 } else { 1243 if (group->meth->field_set_to_one != 0) { 1244 if (!group->meth->field_set_to_one(group, prod_Z[0], ctx)) 1245 goto err; 1246 } else { 1247 if (!BN_one(prod_Z[0])) 1248 goto err; 1249 } 1250 } 1251 1252 for (i = 1; i < num; i++) { 1253 if (!BN_is_zero(points[i]->Z)) { 1254 if (!group-> 1255 meth->field_mul(group, prod_Z[i], prod_Z[i - 1], points[i]->Z, 1256 ctx)) 1257 goto err; 1258 } else { 1259 if (!BN_copy(prod_Z[i], prod_Z[i - 1])) 1260 goto err; 1261 } 1262 } 1263 1264 /* 1265 * Now use a single explicit inversion to replace every non-zero 1266 * points[i]->Z by its inverse. 1267 */ 1268 1269 if (!BN_mod_inverse(tmp, prod_Z[num - 1], group->field, ctx)) { 1270 ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB); 1271 goto err; 1272 } 1273 if (group->meth->field_encode != 0) { 1274 /* 1275 * In the Montgomery case, we just turned R*H (representing H) into 1276 * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to 1277 * multiply by the Montgomery factor twice. 1278 */ 1279 if (!group->meth->field_encode(group, tmp, tmp, ctx)) 1280 goto err; 1281 if (!group->meth->field_encode(group, tmp, tmp, ctx)) 1282 goto err; 1283 } 1284 1285 for (i = num - 1; i > 0; --i) { 1286 /* 1287 * Loop invariant: tmp is the product of the inverses of points[0]->Z 1288 * .. points[i]->Z (zero-valued inputs skipped). 1289 */ 1290 if (!BN_is_zero(points[i]->Z)) { 1291 /* 1292 * Set tmp_Z to the inverse of points[i]->Z (as product of Z 1293 * inverses 0 .. i, Z values 0 .. i - 1). 1294 */ 1295 if (!group-> 1296 meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx)) 1297 goto err; 1298 /* 1299 * Update tmp to satisfy the loop invariant for i - 1. 1300 */ 1301 if (!group->meth->field_mul(group, tmp, tmp, points[i]->Z, ctx)) 1302 goto err; 1303 /* Replace points[i]->Z by its inverse. */ 1304 if (!BN_copy(points[i]->Z, tmp_Z)) 1305 goto err; 1306 } 1307 } 1308 1309 if (!BN_is_zero(points[0]->Z)) { 1310 /* Replace points[0]->Z by its inverse. */ 1311 if (!BN_copy(points[0]->Z, tmp)) 1312 goto err; 1313 } 1314 1315 /* Finally, fix up the X and Y coordinates for all points. */ 1316 1317 for (i = 0; i < num; i++) { 1318 EC_POINT *p = points[i]; 1319 1320 if (!BN_is_zero(p->Z)) { 1321 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */ 1322 1323 if (!group->meth->field_sqr(group, tmp, p->Z, ctx)) 1324 goto err; 1325 if (!group->meth->field_mul(group, p->X, p->X, tmp, ctx)) 1326 goto err; 1327 1328 if (!group->meth->field_mul(group, tmp, tmp, p->Z, ctx)) 1329 goto err; 1330 if (!group->meth->field_mul(group, p->Y, p->Y, tmp, ctx)) 1331 goto err; 1332 1333 if (group->meth->field_set_to_one != 0) { 1334 if (!group->meth->field_set_to_one(group, p->Z, ctx)) 1335 goto err; 1336 } else { 1337 if (!BN_one(p->Z)) 1338 goto err; 1339 } 1340 p->Z_is_one = 1; 1341 } 1342 } 1343 1344 ret = 1; 1345 1346 err: 1347 BN_CTX_end(ctx); 1348 BN_CTX_free(new_ctx); 1349 if (prod_Z != NULL) { 1350 for (i = 0; i < num; i++) { 1351 if (prod_Z[i] == NULL) 1352 break; 1353 BN_clear_free(prod_Z[i]); 1354 } 1355 OPENSSL_free(prod_Z); 1356 } 1357 return ret; 1358 } 1359 1360 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1361 const BIGNUM *b, BN_CTX *ctx) 1362 { 1363 return BN_mod_mul(r, a, b, group->field, ctx); 1364 } 1365 1366 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1367 BN_CTX *ctx) 1368 { 1369 return BN_mod_sqr(r, a, group->field, ctx); 1370 } 1371 1372 /*- 1373 * Apply randomization of EC point projective coordinates: 1374 * 1375 * (X, Y ,Z ) = (lambda^2*X, lambda^3*Y, lambda*Z) 1376 * lambda = [1,group->field) 1377 * 1378 */ 1379 int ec_GFp_simple_blind_coordinates(const EC_GROUP *group, EC_POINT *p, 1380 BN_CTX *ctx) 1381 { 1382 int ret = 0; 1383 BIGNUM *lambda = NULL; 1384 BIGNUM *temp = NULL; 1385 1386 BN_CTX_start(ctx); 1387 lambda = BN_CTX_get(ctx); 1388 temp = BN_CTX_get(ctx); 1389 if (temp == NULL) { 1390 ECerr(EC_F_EC_GFP_SIMPLE_BLIND_COORDINATES, ERR_R_MALLOC_FAILURE); 1391 goto err; 1392 } 1393 1394 /* make sure lambda is not zero */ 1395 do { 1396 if (!BN_priv_rand_range(lambda, group->field)) { 1397 ECerr(EC_F_EC_GFP_SIMPLE_BLIND_COORDINATES, ERR_R_BN_LIB); 1398 goto err; 1399 } 1400 } while (BN_is_zero(lambda)); 1401 1402 /* if field_encode defined convert between representations */ 1403 if (group->meth->field_encode != NULL 1404 && !group->meth->field_encode(group, lambda, lambda, ctx)) 1405 goto err; 1406 if (!group->meth->field_mul(group, p->Z, p->Z, lambda, ctx)) 1407 goto err; 1408 if (!group->meth->field_sqr(group, temp, lambda, ctx)) 1409 goto err; 1410 if (!group->meth->field_mul(group, p->X, p->X, temp, ctx)) 1411 goto err; 1412 if (!group->meth->field_mul(group, temp, temp, lambda, ctx)) 1413 goto err; 1414 if (!group->meth->field_mul(group, p->Y, p->Y, temp, ctx)) 1415 goto err; 1416 p->Z_is_one = 0; 1417 1418 ret = 1; 1419 1420 err: 1421 BN_CTX_end(ctx); 1422 return ret; 1423 } 1424 1425 /*- 1426 * Set s := p, r := 2p. 1427 * 1428 * For doubling we use Formula 3 from Izu-Takagi "A fast parallel elliptic curve 1429 * multiplication resistant against side channel attacks" appendix, as described 1430 * at 1431 * https://hyperelliptic.org/EFD/g1p/auto-shortw-xz.html#doubling-dbl-2002-it-2 1432 * 1433 * The input point p will be in randomized Jacobian projective coords: 1434 * x = X/Z**2, y=Y/Z**3 1435 * 1436 * The output points p, s, and r are converted to standard (homogeneous) 1437 * projective coords: 1438 * x = X/Z, y=Y/Z 1439 */ 1440 int ec_GFp_simple_ladder_pre(const EC_GROUP *group, 1441 EC_POINT *r, EC_POINT *s, 1442 EC_POINT *p, BN_CTX *ctx) 1443 { 1444 BIGNUM *t1, *t2, *t3, *t4, *t5, *t6 = NULL; 1445 1446 t1 = r->Z; 1447 t2 = r->Y; 1448 t3 = s->X; 1449 t4 = r->X; 1450 t5 = s->Y; 1451 t6 = s->Z; 1452 1453 /* convert p: (X,Y,Z) -> (XZ,Y,Z**3) */ 1454 if (!group->meth->field_mul(group, p->X, p->X, p->Z, ctx) 1455 || !group->meth->field_sqr(group, t1, p->Z, ctx) 1456 || !group->meth->field_mul(group, p->Z, p->Z, t1, ctx) 1457 /* r := 2p */ 1458 || !group->meth->field_sqr(group, t2, p->X, ctx) 1459 || !group->meth->field_sqr(group, t3, p->Z, ctx) 1460 || !group->meth->field_mul(group, t4, t3, group->a, ctx) 1461 || !BN_mod_sub_quick(t5, t2, t4, group->field) 1462 || !BN_mod_add_quick(t2, t2, t4, group->field) 1463 || !group->meth->field_sqr(group, t5, t5, ctx) 1464 || !group->meth->field_mul(group, t6, t3, group->b, ctx) 1465 || !group->meth->field_mul(group, t1, p->X, p->Z, ctx) 1466 || !group->meth->field_mul(group, t4, t1, t6, ctx) 1467 || !BN_mod_lshift_quick(t4, t4, 3, group->field) 1468 /* r->X coord output */ 1469 || !BN_mod_sub_quick(r->X, t5, t4, group->field) 1470 || !group->meth->field_mul(group, t1, t1, t2, ctx) 1471 || !group->meth->field_mul(group, t2, t3, t6, ctx) 1472 || !BN_mod_add_quick(t1, t1, t2, group->field) 1473 /* r->Z coord output */ 1474 || !BN_mod_lshift_quick(r->Z, t1, 2, group->field) 1475 || !EC_POINT_copy(s, p)) 1476 return 0; 1477 1478 r->Z_is_one = 0; 1479 s->Z_is_one = 0; 1480 p->Z_is_one = 0; 1481 1482 return 1; 1483 } 1484 1485 /*- 1486 * Differential addition-and-doubling using Eq. (9) and (10) from Izu-Takagi 1487 * "A fast parallel elliptic curve multiplication resistant against side channel 1488 * attacks", as described at 1489 * https://hyperelliptic.org/EFD/g1p/auto-shortw-xz.html#ladder-ladd-2002-it-4 1490 */ 1491 int ec_GFp_simple_ladder_step(const EC_GROUP *group, 1492 EC_POINT *r, EC_POINT *s, 1493 EC_POINT *p, BN_CTX *ctx) 1494 { 1495 int ret = 0; 1496 BIGNUM *t0, *t1, *t2, *t3, *t4, *t5, *t6, *t7 = NULL; 1497 1498 BN_CTX_start(ctx); 1499 t0 = BN_CTX_get(ctx); 1500 t1 = BN_CTX_get(ctx); 1501 t2 = BN_CTX_get(ctx); 1502 t3 = BN_CTX_get(ctx); 1503 t4 = BN_CTX_get(ctx); 1504 t5 = BN_CTX_get(ctx); 1505 t6 = BN_CTX_get(ctx); 1506 t7 = BN_CTX_get(ctx); 1507 1508 if (t7 == NULL 1509 || !group->meth->field_mul(group, t0, r->X, s->X, ctx) 1510 || !group->meth->field_mul(group, t1, r->Z, s->Z, ctx) 1511 || !group->meth->field_mul(group, t2, r->X, s->Z, ctx) 1512 || !group->meth->field_mul(group, t3, r->Z, s->X, ctx) 1513 || !group->meth->field_mul(group, t4, group->a, t1, ctx) 1514 || !BN_mod_add_quick(t0, t0, t4, group->field) 1515 || !BN_mod_add_quick(t4, t3, t2, group->field) 1516 || !group->meth->field_mul(group, t0, t4, t0, ctx) 1517 || !group->meth->field_sqr(group, t1, t1, ctx) 1518 || !BN_mod_lshift_quick(t7, group->b, 2, group->field) 1519 || !group->meth->field_mul(group, t1, t7, t1, ctx) 1520 || !BN_mod_lshift1_quick(t0, t0, group->field) 1521 || !BN_mod_add_quick(t0, t1, t0, group->field) 1522 || !BN_mod_sub_quick(t1, t2, t3, group->field) 1523 || !group->meth->field_sqr(group, t1, t1, ctx) 1524 || !group->meth->field_mul(group, t3, t1, p->X, ctx) 1525 || !group->meth->field_mul(group, t0, p->Z, t0, ctx) 1526 /* s->X coord output */ 1527 || !BN_mod_sub_quick(s->X, t0, t3, group->field) 1528 /* s->Z coord output */ 1529 || !group->meth->field_mul(group, s->Z, p->Z, t1, ctx) 1530 || !group->meth->field_sqr(group, t3, r->X, ctx) 1531 || !group->meth->field_sqr(group, t2, r->Z, ctx) 1532 || !group->meth->field_mul(group, t4, t2, group->a, ctx) 1533 || !BN_mod_add_quick(t5, r->X, r->Z, group->field) 1534 || !group->meth->field_sqr(group, t5, t5, ctx) 1535 || !BN_mod_sub_quick(t5, t5, t3, group->field) 1536 || !BN_mod_sub_quick(t5, t5, t2, group->field) 1537 || !BN_mod_sub_quick(t6, t3, t4, group->field) 1538 || !group->meth->field_sqr(group, t6, t6, ctx) 1539 || !group->meth->field_mul(group, t0, t2, t5, ctx) 1540 || !group->meth->field_mul(group, t0, t7, t0, ctx) 1541 /* r->X coord output */ 1542 || !BN_mod_sub_quick(r->X, t6, t0, group->field) 1543 || !BN_mod_add_quick(t6, t3, t4, group->field) 1544 || !group->meth->field_sqr(group, t3, t2, ctx) 1545 || !group->meth->field_mul(group, t7, t3, t7, ctx) 1546 || !group->meth->field_mul(group, t5, t5, t6, ctx) 1547 || !BN_mod_lshift1_quick(t5, t5, group->field) 1548 /* r->Z coord output */ 1549 || !BN_mod_add_quick(r->Z, t7, t5, group->field)) 1550 goto err; 1551 1552 ret = 1; 1553 1554 err: 1555 BN_CTX_end(ctx); 1556 return ret; 1557 } 1558 1559 /*- 1560 * Recovers the y-coordinate of r using Eq. (8) from Brier-Joye, "Weierstrass 1561 * Elliptic Curves and Side-Channel Attacks", modified to work in projective 1562 * coordinates and return r in Jacobian projective coordinates. 1563 * 1564 * X4 = two*Y1*X2*Z3*Z2*Z1; 1565 * Y4 = two*b*Z3*SQR(Z2*Z1) + Z3*(a*Z2*Z1+X1*X2)*(X1*Z2+X2*Z1) - X3*SQR(X1*Z2-X2*Z1); 1566 * Z4 = two*Y1*Z3*SQR(Z2)*Z1; 1567 * 1568 * Z4 != 0 because: 1569 * - Z1==0 implies p is at infinity, which would have caused an early exit in 1570 * the caller; 1571 * - Z2==0 implies r is at infinity (handled by the BN_is_zero(r->Z) branch); 1572 * - Z3==0 implies s is at infinity (handled by the BN_is_zero(s->Z) branch); 1573 * - Y1==0 implies p has order 2, so either r or s are infinity and handled by 1574 * one of the BN_is_zero(...) branches. 1575 */ 1576 int ec_GFp_simple_ladder_post(const EC_GROUP *group, 1577 EC_POINT *r, EC_POINT *s, 1578 EC_POINT *p, BN_CTX *ctx) 1579 { 1580 int ret = 0; 1581 BIGNUM *t0, *t1, *t2, *t3, *t4, *t5, *t6 = NULL; 1582 1583 if (BN_is_zero(r->Z)) 1584 return EC_POINT_set_to_infinity(group, r); 1585 1586 if (BN_is_zero(s->Z)) { 1587 /* (X,Y,Z) -> (XZ,YZ**2,Z) */ 1588 if (!group->meth->field_mul(group, r->X, p->X, p->Z, ctx) 1589 || !group->meth->field_sqr(group, r->Z, p->Z, ctx) 1590 || !group->meth->field_mul(group, r->Y, p->Y, r->Z, ctx) 1591 || !BN_copy(r->Z, p->Z) 1592 || !EC_POINT_invert(group, r, ctx)) 1593 return 0; 1594 return 1; 1595 } 1596 1597 BN_CTX_start(ctx); 1598 t0 = BN_CTX_get(ctx); 1599 t1 = BN_CTX_get(ctx); 1600 t2 = BN_CTX_get(ctx); 1601 t3 = BN_CTX_get(ctx); 1602 t4 = BN_CTX_get(ctx); 1603 t5 = BN_CTX_get(ctx); 1604 t6 = BN_CTX_get(ctx); 1605 1606 if (t6 == NULL 1607 || !BN_mod_lshift1_quick(t0, p->Y, group->field) 1608 || !group->meth->field_mul(group, t1, r->X, p->Z, ctx) 1609 || !group->meth->field_mul(group, t2, r->Z, s->Z, ctx) 1610 || !group->meth->field_mul(group, t2, t1, t2, ctx) 1611 || !group->meth->field_mul(group, t3, t2, t0, ctx) 1612 || !group->meth->field_mul(group, t2, r->Z, p->Z, ctx) 1613 || !group->meth->field_sqr(group, t4, t2, ctx) 1614 || !BN_mod_lshift1_quick(t5, group->b, group->field) 1615 || !group->meth->field_mul(group, t4, t4, t5, ctx) 1616 || !group->meth->field_mul(group, t6, t2, group->a, ctx) 1617 || !group->meth->field_mul(group, t5, r->X, p->X, ctx) 1618 || !BN_mod_add_quick(t5, t6, t5, group->field) 1619 || !group->meth->field_mul(group, t6, r->Z, p->X, ctx) 1620 || !BN_mod_add_quick(t2, t6, t1, group->field) 1621 || !group->meth->field_mul(group, t5, t5, t2, ctx) 1622 || !BN_mod_sub_quick(t6, t6, t1, group->field) 1623 || !group->meth->field_sqr(group, t6, t6, ctx) 1624 || !group->meth->field_mul(group, t6, t6, s->X, ctx) 1625 || !BN_mod_add_quick(t4, t5, t4, group->field) 1626 || !group->meth->field_mul(group, t4, t4, s->Z, ctx) 1627 || !BN_mod_sub_quick(t4, t4, t6, group->field) 1628 || !group->meth->field_sqr(group, t5, r->Z, ctx) 1629 || !group->meth->field_mul(group, r->Z, p->Z, s->Z, ctx) 1630 || !group->meth->field_mul(group, r->Z, t5, r->Z, ctx) 1631 || !group->meth->field_mul(group, r->Z, r->Z, t0, ctx) 1632 /* t3 := X, t4 := Y */ 1633 /* (X,Y,Z) -> (XZ,YZ**2,Z) */ 1634 || !group->meth->field_mul(group, r->X, t3, r->Z, ctx) 1635 || !group->meth->field_sqr(group, t3, r->Z, ctx) 1636 || !group->meth->field_mul(group, r->Y, t4, t3, ctx)) 1637 goto err; 1638 1639 ret = 1; 1640 1641 err: 1642 BN_CTX_end(ctx); 1643 return ret; 1644 } 1645