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