ecp_smpl.c revision 331638
1/* crypto/ec/ecp_smpl.c */ 2/* 3 * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> 4 * for the OpenSSL project. Includes code written by Bodo Moeller for the 5 * OpenSSL project. 6 */ 7/* ==================================================================== 8 * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in 19 * the documentation and/or other materials provided with the 20 * distribution. 21 * 22 * 3. All advertising materials mentioning features or use of this 23 * software must display the following acknowledgment: 24 * "This product includes software developed by the OpenSSL Project 25 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 26 * 27 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 28 * endorse or promote products derived from this software without 29 * prior written permission. For written permission, please contact 30 * openssl-core@openssl.org. 31 * 32 * 5. Products derived from this software may not be called "OpenSSL" 33 * nor may "OpenSSL" appear in their names without prior written 34 * permission of the OpenSSL Project. 35 * 36 * 6. Redistributions of any form whatsoever must retain the following 37 * acknowledgment: 38 * "This product includes software developed by the OpenSSL Project 39 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 40 * 41 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 42 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 44 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 45 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 46 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 47 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 48 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 49 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 50 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 51 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 52 * OF THE POSSIBILITY OF SUCH DAMAGE. 53 * ==================================================================== 54 * 55 * This product includes cryptographic software written by Eric Young 56 * (eay@cryptsoft.com). This product includes software written by Tim 57 * Hudson (tjh@cryptsoft.com). 58 * 59 */ 60/* ==================================================================== 61 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 62 * Portions of this software developed by SUN MICROSYSTEMS, INC., 63 * and contributed to the OpenSSL project. 64 */ 65 66#include <openssl/err.h> 67#include <openssl/symhacks.h> 68 69#ifdef OPENSSL_FIPS 70# include <openssl/fips.h> 71#endif 72 73#include "ec_lcl.h" 74 75const EC_METHOD *EC_GFp_simple_method(void) 76{ 77 static const EC_METHOD ret = { 78 EC_FLAGS_DEFAULT_OCT, 79 NID_X9_62_prime_field, 80 ec_GFp_simple_group_init, 81 ec_GFp_simple_group_finish, 82 ec_GFp_simple_group_clear_finish, 83 ec_GFp_simple_group_copy, 84 ec_GFp_simple_group_set_curve, 85 ec_GFp_simple_group_get_curve, 86 ec_GFp_simple_group_get_degree, 87 ec_GFp_simple_group_check_discriminant, 88 ec_GFp_simple_point_init, 89 ec_GFp_simple_point_finish, 90 ec_GFp_simple_point_clear_finish, 91 ec_GFp_simple_point_copy, 92 ec_GFp_simple_point_set_to_infinity, 93 ec_GFp_simple_set_Jprojective_coordinates_GFp, 94 ec_GFp_simple_get_Jprojective_coordinates_GFp, 95 ec_GFp_simple_point_set_affine_coordinates, 96 ec_GFp_simple_point_get_affine_coordinates, 97 0, 0, 0, 98 ec_GFp_simple_add, 99 ec_GFp_simple_dbl, 100 ec_GFp_simple_invert, 101 ec_GFp_simple_is_at_infinity, 102 ec_GFp_simple_is_on_curve, 103 ec_GFp_simple_cmp, 104 ec_GFp_simple_make_affine, 105 ec_GFp_simple_points_make_affine, 106 0 /* mul */ , 107 0 /* precompute_mult */ , 108 0 /* have_precompute_mult */ , 109 ec_GFp_simple_field_mul, 110 ec_GFp_simple_field_sqr, 111 0 /* field_div */ , 112 0 /* field_encode */ , 113 0 /* field_decode */ , 114 0 /* field_set_to_one */ 115 }; 116 117#ifdef OPENSSL_FIPS 118 if (FIPS_mode()) 119 return fips_ec_gfp_simple_method(); 120#endif 121 122 return &ret; 123} 124 125/* 126 * Most method functions in this file are designed to work with 127 * non-trivial representations of field elements if necessary 128 * (see ecp_mont.c): while standard modular addition and subtraction 129 * are used, the field_mul and field_sqr methods will be used for 130 * multiplication, and field_encode and field_decode (if defined) 131 * will be used for converting between representations. 132 * 133 * Functions ec_GFp_simple_points_make_affine() and 134 * ec_GFp_simple_point_get_affine_coordinates() specifically assume 135 * that if a non-trivial representation is used, it is a Montgomery 136 * representation (i.e. 'encoding' means multiplying by some factor R). 137 */ 138 139int ec_GFp_simple_group_init(EC_GROUP *group) 140{ 141 BN_init(&group->field); 142 BN_init(&group->a); 143 BN_init(&group->b); 144 group->a_is_minus3 = 0; 145 return 1; 146} 147 148void ec_GFp_simple_group_finish(EC_GROUP *group) 149{ 150 BN_free(&group->field); 151 BN_free(&group->a); 152 BN_free(&group->b); 153} 154 155void ec_GFp_simple_group_clear_finish(EC_GROUP *group) 156{ 157 BN_clear_free(&group->field); 158 BN_clear_free(&group->a); 159 BN_clear_free(&group->b); 160} 161 162int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) 163{ 164 if (!BN_copy(&dest->field, &src->field)) 165 return 0; 166 if (!BN_copy(&dest->a, &src->a)) 167 return 0; 168 if (!BN_copy(&dest->b, &src->b)) 169 return 0; 170 171 dest->a_is_minus3 = src->a_is_minus3; 172 173 return 1; 174} 175 176int ec_GFp_simple_group_set_curve(EC_GROUP *group, 177 const BIGNUM *p, const BIGNUM *a, 178 const BIGNUM *b, BN_CTX *ctx) 179{ 180 int ret = 0; 181 BN_CTX *new_ctx = NULL; 182 BIGNUM *tmp_a; 183 184 /* p must be a prime > 3 */ 185 if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) { 186 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD); 187 return 0; 188 } 189 190 if (ctx == NULL) { 191 ctx = new_ctx = BN_CTX_new(); 192 if (ctx == NULL) 193 return 0; 194 } 195 196 BN_CTX_start(ctx); 197 tmp_a = BN_CTX_get(ctx); 198 if (tmp_a == NULL) 199 goto err; 200 201 /* group->field */ 202 if (!BN_copy(&group->field, p)) 203 goto err; 204 BN_set_negative(&group->field, 0); 205 206 /* group->a */ 207 if (!BN_nnmod(tmp_a, a, p, ctx)) 208 goto err; 209 if (group->meth->field_encode) { 210 if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) 211 goto err; 212 } else if (!BN_copy(&group->a, tmp_a)) 213 goto err; 214 215 /* group->b */ 216 if (!BN_nnmod(&group->b, b, p, ctx)) 217 goto err; 218 if (group->meth->field_encode) 219 if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) 220 goto err; 221 222 /* group->a_is_minus3 */ 223 if (!BN_add_word(tmp_a, 3)) 224 goto err; 225 group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field)); 226 227 ret = 1; 228 229 err: 230 BN_CTX_end(ctx); 231 if (new_ctx != NULL) 232 BN_CTX_free(new_ctx); 233 return ret; 234} 235 236int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, 237 BIGNUM *b, BN_CTX *ctx) 238{ 239 int ret = 0; 240 BN_CTX *new_ctx = NULL; 241 242 if (p != NULL) { 243 if (!BN_copy(p, &group->field)) 244 return 0; 245 } 246 247 if (a != NULL || b != NULL) { 248 if (group->meth->field_decode) { 249 if (ctx == NULL) { 250 ctx = new_ctx = BN_CTX_new(); 251 if (ctx == NULL) 252 return 0; 253 } 254 if (a != NULL) { 255 if (!group->meth->field_decode(group, a, &group->a, ctx)) 256 goto err; 257 } 258 if (b != NULL) { 259 if (!group->meth->field_decode(group, b, &group->b, ctx)) 260 goto err; 261 } 262 } else { 263 if (a != NULL) { 264 if (!BN_copy(a, &group->a)) 265 goto err; 266 } 267 if (b != NULL) { 268 if (!BN_copy(b, &group->b)) 269 goto err; 270 } 271 } 272 } 273 274 ret = 1; 275 276 err: 277 if (new_ctx) 278 BN_CTX_free(new_ctx); 279 return ret; 280} 281 282int ec_GFp_simple_group_get_degree(const EC_GROUP *group) 283{ 284 return BN_num_bits(&group->field); 285} 286 287int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx) 288{ 289 int ret = 0; 290 BIGNUM *a, *b, *order, *tmp_1, *tmp_2; 291 const BIGNUM *p = &group->field; 292 BN_CTX *new_ctx = NULL; 293 294 if (ctx == NULL) { 295 ctx = new_ctx = BN_CTX_new(); 296 if (ctx == NULL) { 297 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, 298 ERR_R_MALLOC_FAILURE); 299 goto err; 300 } 301 } 302 BN_CTX_start(ctx); 303 a = BN_CTX_get(ctx); 304 b = BN_CTX_get(ctx); 305 tmp_1 = BN_CTX_get(ctx); 306 tmp_2 = BN_CTX_get(ctx); 307 order = BN_CTX_get(ctx); 308 if (order == NULL) 309 goto err; 310 311 if (group->meth->field_decode) { 312 if (!group->meth->field_decode(group, a, &group->a, ctx)) 313 goto err; 314 if (!group->meth->field_decode(group, b, &group->b, ctx)) 315 goto err; 316 } else { 317 if (!BN_copy(a, &group->a)) 318 goto err; 319 if (!BN_copy(b, &group->b)) 320 goto err; 321 } 322 323 /*- 324 * check the discriminant: 325 * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p) 326 * 0 =< a, b < p 327 */ 328 if (BN_is_zero(a)) { 329 if (BN_is_zero(b)) 330 goto err; 331 } else if (!BN_is_zero(b)) { 332 if (!BN_mod_sqr(tmp_1, a, p, ctx)) 333 goto err; 334 if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) 335 goto err; 336 if (!BN_lshift(tmp_1, tmp_2, 2)) 337 goto err; 338 /* tmp_1 = 4*a^3 */ 339 340 if (!BN_mod_sqr(tmp_2, b, p, ctx)) 341 goto err; 342 if (!BN_mul_word(tmp_2, 27)) 343 goto err; 344 /* tmp_2 = 27*b^2 */ 345 346 if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) 347 goto err; 348 if (BN_is_zero(a)) 349 goto err; 350 } 351 ret = 1; 352 353 err: 354 if (ctx != NULL) 355 BN_CTX_end(ctx); 356 if (new_ctx != NULL) 357 BN_CTX_free(new_ctx); 358 return ret; 359} 360 361int ec_GFp_simple_point_init(EC_POINT *point) 362{ 363 BN_init(&point->X); 364 BN_init(&point->Y); 365 BN_init(&point->Z); 366 point->Z_is_one = 0; 367 368 return 1; 369} 370 371void ec_GFp_simple_point_finish(EC_POINT *point) 372{ 373 BN_free(&point->X); 374 BN_free(&point->Y); 375 BN_free(&point->Z); 376} 377 378void ec_GFp_simple_point_clear_finish(EC_POINT *point) 379{ 380 BN_clear_free(&point->X); 381 BN_clear_free(&point->Y); 382 BN_clear_free(&point->Z); 383 point->Z_is_one = 0; 384} 385 386int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) 387{ 388 if (!BN_copy(&dest->X, &src->X)) 389 return 0; 390 if (!BN_copy(&dest->Y, &src->Y)) 391 return 0; 392 if (!BN_copy(&dest->Z, &src->Z)) 393 return 0; 394 dest->Z_is_one = src->Z_is_one; 395 396 return 1; 397} 398 399int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, 400 EC_POINT *point) 401{ 402 point->Z_is_one = 0; 403 BN_zero(&point->Z); 404 return 1; 405} 406 407int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, 408 EC_POINT *point, 409 const BIGNUM *x, 410 const BIGNUM *y, 411 const BIGNUM *z, 412 BN_CTX *ctx) 413{ 414 BN_CTX *new_ctx = NULL; 415 int ret = 0; 416 417 if (ctx == NULL) { 418 ctx = new_ctx = BN_CTX_new(); 419 if (ctx == NULL) 420 return 0; 421 } 422 423 if (x != NULL) { 424 if (!BN_nnmod(&point->X, x, &group->field, ctx)) 425 goto err; 426 if (group->meth->field_encode) { 427 if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) 428 goto err; 429 } 430 } 431 432 if (y != NULL) { 433 if (!BN_nnmod(&point->Y, y, &group->field, ctx)) 434 goto err; 435 if (group->meth->field_encode) { 436 if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) 437 goto err; 438 } 439 } 440 441 if (z != NULL) { 442 int Z_is_one; 443 444 if (!BN_nnmod(&point->Z, z, &group->field, ctx)) 445 goto err; 446 Z_is_one = BN_is_one(&point->Z); 447 if (group->meth->field_encode) { 448 if (Z_is_one && (group->meth->field_set_to_one != 0)) { 449 if (!group->meth->field_set_to_one(group, &point->Z, ctx)) 450 goto err; 451 } else { 452 if (!group-> 453 meth->field_encode(group, &point->Z, &point->Z, ctx)) 454 goto err; 455 } 456 } 457 point->Z_is_one = Z_is_one; 458 } 459 460 ret = 1; 461 462 err: 463 if (new_ctx != NULL) 464 BN_CTX_free(new_ctx); 465 return ret; 466} 467 468int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, 469 const EC_POINT *point, 470 BIGNUM *x, BIGNUM *y, 471 BIGNUM *z, BN_CTX *ctx) 472{ 473 BN_CTX *new_ctx = NULL; 474 int ret = 0; 475 476 if (group->meth->field_decode != 0) { 477 if (ctx == NULL) { 478 ctx = new_ctx = BN_CTX_new(); 479 if (ctx == NULL) 480 return 0; 481 } 482 483 if (x != NULL) { 484 if (!group->meth->field_decode(group, x, &point->X, ctx)) 485 goto err; 486 } 487 if (y != NULL) { 488 if (!group->meth->field_decode(group, y, &point->Y, ctx)) 489 goto err; 490 } 491 if (z != NULL) { 492 if (!group->meth->field_decode(group, z, &point->Z, ctx)) 493 goto err; 494 } 495 } else { 496 if (x != NULL) { 497 if (!BN_copy(x, &point->X)) 498 goto err; 499 } 500 if (y != NULL) { 501 if (!BN_copy(y, &point->Y)) 502 goto err; 503 } 504 if (z != NULL) { 505 if (!BN_copy(z, &point->Z)) 506 goto err; 507 } 508 } 509 510 ret = 1; 511 512 err: 513 if (new_ctx != NULL) 514 BN_CTX_free(new_ctx); 515 return ret; 516} 517 518int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, 519 EC_POINT *point, 520 const BIGNUM *x, 521 const BIGNUM *y, BN_CTX *ctx) 522{ 523 if (x == NULL || y == NULL) { 524 /* 525 * unlike for projective coordinates, we do not tolerate this 526 */ 527 ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, 528 ERR_R_PASSED_NULL_PARAMETER); 529 return 0; 530 } 531 532 return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, 533 BN_value_one(), ctx); 534} 535 536int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, 537 const EC_POINT *point, 538 BIGNUM *x, BIGNUM *y, 539 BN_CTX *ctx) 540{ 541 BN_CTX *new_ctx = NULL; 542 BIGNUM *Z, *Z_1, *Z_2, *Z_3; 543 const BIGNUM *Z_; 544 int ret = 0; 545 546 if (EC_POINT_is_at_infinity(group, point)) { 547 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, 548 EC_R_POINT_AT_INFINITY); 549 return 0; 550 } 551 552 if (ctx == NULL) { 553 ctx = new_ctx = BN_CTX_new(); 554 if (ctx == NULL) 555 return 0; 556 } 557 558 BN_CTX_start(ctx); 559 Z = BN_CTX_get(ctx); 560 Z_1 = BN_CTX_get(ctx); 561 Z_2 = BN_CTX_get(ctx); 562 Z_3 = BN_CTX_get(ctx); 563 if (Z_3 == NULL) 564 goto err; 565 566 /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */ 567 568 if (group->meth->field_decode) { 569 if (!group->meth->field_decode(group, Z, &point->Z, ctx)) 570 goto err; 571 Z_ = Z; 572 } else { 573 Z_ = &point->Z; 574 } 575 576 if (BN_is_one(Z_)) { 577 if (group->meth->field_decode) { 578 if (x != NULL) { 579 if (!group->meth->field_decode(group, x, &point->X, ctx)) 580 goto err; 581 } 582 if (y != NULL) { 583 if (!group->meth->field_decode(group, y, &point->Y, ctx)) 584 goto err; 585 } 586 } else { 587 if (x != NULL) { 588 if (!BN_copy(x, &point->X)) 589 goto err; 590 } 591 if (y != NULL) { 592 if (!BN_copy(y, &point->Y)) 593 goto err; 594 } 595 } 596 } else { 597 if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx)) { 598 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, 599 ERR_R_BN_LIB); 600 goto err; 601 } 602 603 if (group->meth->field_encode == 0) { 604 /* field_sqr works on standard representation */ 605 if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) 606 goto err; 607 } else { 608 if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) 609 goto err; 610 } 611 612 if (x != NULL) { 613 /* 614 * in the Montgomery case, field_mul will cancel out Montgomery 615 * factor in X: 616 */ 617 if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) 618 goto err; 619 } 620 621 if (y != NULL) { 622 if (group->meth->field_encode == 0) { 623 /* 624 * field_mul works on standard representation 625 */ 626 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) 627 goto err; 628 } else { 629 if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) 630 goto err; 631 } 632 633 /* 634 * in the Montgomery case, field_mul will cancel out Montgomery 635 * factor in Y: 636 */ 637 if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) 638 goto err; 639 } 640 } 641 642 ret = 1; 643 644 err: 645 BN_CTX_end(ctx); 646 if (new_ctx != NULL) 647 BN_CTX_free(new_ctx); 648 return ret; 649} 650 651int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 652 const EC_POINT *b, BN_CTX *ctx) 653{ 654 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 655 const BIGNUM *, BN_CTX *); 656 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 657 const BIGNUM *p; 658 BN_CTX *new_ctx = NULL; 659 BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6; 660 int ret = 0; 661 662 if (a == b) 663 return EC_POINT_dbl(group, r, a, ctx); 664 if (EC_POINT_is_at_infinity(group, a)) 665 return EC_POINT_copy(r, b); 666 if (EC_POINT_is_at_infinity(group, b)) 667 return EC_POINT_copy(r, a); 668 669 field_mul = group->meth->field_mul; 670 field_sqr = group->meth->field_sqr; 671 p = &group->field; 672 673 if (ctx == NULL) { 674 ctx = new_ctx = BN_CTX_new(); 675 if (ctx == NULL) 676 return 0; 677 } 678 679 BN_CTX_start(ctx); 680 n0 = BN_CTX_get(ctx); 681 n1 = BN_CTX_get(ctx); 682 n2 = BN_CTX_get(ctx); 683 n3 = BN_CTX_get(ctx); 684 n4 = BN_CTX_get(ctx); 685 n5 = BN_CTX_get(ctx); 686 n6 = BN_CTX_get(ctx); 687 if (n6 == NULL) 688 goto end; 689 690 /* 691 * Note that in this function we must not read components of 'a' or 'b' 692 * once we have written the corresponding components of 'r'. ('r' might 693 * be one of 'a' or 'b'.) 694 */ 695 696 /* n1, n2 */ 697 if (b->Z_is_one) { 698 if (!BN_copy(n1, &a->X)) 699 goto end; 700 if (!BN_copy(n2, &a->Y)) 701 goto end; 702 /* n1 = X_a */ 703 /* n2 = Y_a */ 704 } else { 705 if (!field_sqr(group, n0, &b->Z, ctx)) 706 goto end; 707 if (!field_mul(group, n1, &a->X, n0, ctx)) 708 goto end; 709 /* n1 = X_a * Z_b^2 */ 710 711 if (!field_mul(group, n0, n0, &b->Z, ctx)) 712 goto end; 713 if (!field_mul(group, n2, &a->Y, n0, ctx)) 714 goto end; 715 /* n2 = Y_a * Z_b^3 */ 716 } 717 718 /* n3, n4 */ 719 if (a->Z_is_one) { 720 if (!BN_copy(n3, &b->X)) 721 goto end; 722 if (!BN_copy(n4, &b->Y)) 723 goto end; 724 /* n3 = X_b */ 725 /* n4 = Y_b */ 726 } else { 727 if (!field_sqr(group, n0, &a->Z, ctx)) 728 goto end; 729 if (!field_mul(group, n3, &b->X, n0, ctx)) 730 goto end; 731 /* n3 = X_b * Z_a^2 */ 732 733 if (!field_mul(group, n0, n0, &a->Z, ctx)) 734 goto end; 735 if (!field_mul(group, n4, &b->Y, n0, ctx)) 736 goto end; 737 /* n4 = Y_b * Z_a^3 */ 738 } 739 740 /* n5, n6 */ 741 if (!BN_mod_sub_quick(n5, n1, n3, p)) 742 goto end; 743 if (!BN_mod_sub_quick(n6, n2, n4, p)) 744 goto end; 745 /* n5 = n1 - n3 */ 746 /* n6 = n2 - n4 */ 747 748 if (BN_is_zero(n5)) { 749 if (BN_is_zero(n6)) { 750 /* a is the same point as b */ 751 BN_CTX_end(ctx); 752 ret = EC_POINT_dbl(group, r, a, ctx); 753 ctx = NULL; 754 goto end; 755 } else { 756 /* a is the inverse of b */ 757 BN_zero(&r->Z); 758 r->Z_is_one = 0; 759 ret = 1; 760 goto end; 761 } 762 } 763 764 /* 'n7', 'n8' */ 765 if (!BN_mod_add_quick(n1, n1, n3, p)) 766 goto end; 767 if (!BN_mod_add_quick(n2, n2, n4, p)) 768 goto end; 769 /* 'n7' = n1 + n3 */ 770 /* 'n8' = n2 + n4 */ 771 772 /* Z_r */ 773 if (a->Z_is_one && b->Z_is_one) { 774 if (!BN_copy(&r->Z, n5)) 775 goto end; 776 } else { 777 if (a->Z_is_one) { 778 if (!BN_copy(n0, &b->Z)) 779 goto end; 780 } else if (b->Z_is_one) { 781 if (!BN_copy(n0, &a->Z)) 782 goto end; 783 } else { 784 if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) 785 goto end; 786 } 787 if (!field_mul(group, &r->Z, n0, n5, ctx)) 788 goto end; 789 } 790 r->Z_is_one = 0; 791 /* Z_r = Z_a * Z_b * n5 */ 792 793 /* X_r */ 794 if (!field_sqr(group, n0, n6, ctx)) 795 goto end; 796 if (!field_sqr(group, n4, n5, ctx)) 797 goto end; 798 if (!field_mul(group, n3, n1, n4, ctx)) 799 goto end; 800 if (!BN_mod_sub_quick(&r->X, n0, n3, p)) 801 goto end; 802 /* X_r = n6^2 - n5^2 * 'n7' */ 803 804 /* 'n9' */ 805 if (!BN_mod_lshift1_quick(n0, &r->X, p)) 806 goto end; 807 if (!BN_mod_sub_quick(n0, n3, n0, p)) 808 goto end; 809 /* n9 = n5^2 * 'n7' - 2 * X_r */ 810 811 /* Y_r */ 812 if (!field_mul(group, n0, n0, n6, ctx)) 813 goto end; 814 if (!field_mul(group, n5, n4, n5, ctx)) 815 goto end; /* now n5 is n5^3 */ 816 if (!field_mul(group, n1, n2, n5, ctx)) 817 goto end; 818 if (!BN_mod_sub_quick(n0, n0, n1, p)) 819 goto end; 820 if (BN_is_odd(n0)) 821 if (!BN_add(n0, n0, p)) 822 goto end; 823 /* now 0 <= n0 < 2*p, and n0 is even */ 824 if (!BN_rshift1(&r->Y, n0)) 825 goto end; 826 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */ 827 828 ret = 1; 829 830 end: 831 if (ctx) /* otherwise we already called BN_CTX_end */ 832 BN_CTX_end(ctx); 833 if (new_ctx != NULL) 834 BN_CTX_free(new_ctx); 835 return ret; 836} 837 838int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 839 BN_CTX *ctx) 840{ 841 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 842 const BIGNUM *, BN_CTX *); 843 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 844 const BIGNUM *p; 845 BN_CTX *new_ctx = NULL; 846 BIGNUM *n0, *n1, *n2, *n3; 847 int ret = 0; 848 849 if (EC_POINT_is_at_infinity(group, a)) { 850 BN_zero(&r->Z); 851 r->Z_is_one = 0; 852 return 1; 853 } 854 855 field_mul = group->meth->field_mul; 856 field_sqr = group->meth->field_sqr; 857 p = &group->field; 858 859 if (ctx == NULL) { 860 ctx = new_ctx = BN_CTX_new(); 861 if (ctx == NULL) 862 return 0; 863 } 864 865 BN_CTX_start(ctx); 866 n0 = BN_CTX_get(ctx); 867 n1 = BN_CTX_get(ctx); 868 n2 = BN_CTX_get(ctx); 869 n3 = BN_CTX_get(ctx); 870 if (n3 == NULL) 871 goto err; 872 873 /* 874 * Note that in this function we must not read components of 'a' once we 875 * have written the corresponding components of 'r'. ('r' might the same 876 * as 'a'.) 877 */ 878 879 /* n1 */ 880 if (a->Z_is_one) { 881 if (!field_sqr(group, n0, &a->X, ctx)) 882 goto err; 883 if (!BN_mod_lshift1_quick(n1, n0, p)) 884 goto err; 885 if (!BN_mod_add_quick(n0, n0, n1, p)) 886 goto err; 887 if (!BN_mod_add_quick(n1, n0, &group->a, p)) 888 goto err; 889 /* n1 = 3 * X_a^2 + a_curve */ 890 } else if (group->a_is_minus3) { 891 if (!field_sqr(group, n1, &a->Z, ctx)) 892 goto err; 893 if (!BN_mod_add_quick(n0, &a->X, n1, p)) 894 goto err; 895 if (!BN_mod_sub_quick(n2, &a->X, n1, p)) 896 goto err; 897 if (!field_mul(group, n1, n0, n2, ctx)) 898 goto err; 899 if (!BN_mod_lshift1_quick(n0, n1, p)) 900 goto err; 901 if (!BN_mod_add_quick(n1, n0, n1, p)) 902 goto err; 903 /*- 904 * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) 905 * = 3 * X_a^2 - 3 * Z_a^4 906 */ 907 } else { 908 if (!field_sqr(group, n0, &a->X, ctx)) 909 goto err; 910 if (!BN_mod_lshift1_quick(n1, n0, p)) 911 goto err; 912 if (!BN_mod_add_quick(n0, n0, n1, p)) 913 goto err; 914 if (!field_sqr(group, n1, &a->Z, ctx)) 915 goto err; 916 if (!field_sqr(group, n1, n1, ctx)) 917 goto err; 918 if (!field_mul(group, n1, n1, &group->a, ctx)) 919 goto err; 920 if (!BN_mod_add_quick(n1, n1, n0, p)) 921 goto err; 922 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */ 923 } 924 925 /* Z_r */ 926 if (a->Z_is_one) { 927 if (!BN_copy(n0, &a->Y)) 928 goto err; 929 } else { 930 if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) 931 goto err; 932 } 933 if (!BN_mod_lshift1_quick(&r->Z, n0, p)) 934 goto err; 935 r->Z_is_one = 0; 936 /* Z_r = 2 * Y_a * Z_a */ 937 938 /* n2 */ 939 if (!field_sqr(group, n3, &a->Y, ctx)) 940 goto err; 941 if (!field_mul(group, n2, &a->X, n3, ctx)) 942 goto err; 943 if (!BN_mod_lshift_quick(n2, n2, 2, p)) 944 goto err; 945 /* n2 = 4 * X_a * Y_a^2 */ 946 947 /* X_r */ 948 if (!BN_mod_lshift1_quick(n0, n2, p)) 949 goto err; 950 if (!field_sqr(group, &r->X, n1, ctx)) 951 goto err; 952 if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) 953 goto err; 954 /* X_r = n1^2 - 2 * n2 */ 955 956 /* n3 */ 957 if (!field_sqr(group, n0, n3, ctx)) 958 goto err; 959 if (!BN_mod_lshift_quick(n3, n0, 3, p)) 960 goto err; 961 /* n3 = 8 * Y_a^4 */ 962 963 /* Y_r */ 964 if (!BN_mod_sub_quick(n0, n2, &r->X, p)) 965 goto err; 966 if (!field_mul(group, n0, n1, n0, ctx)) 967 goto err; 968 if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) 969 goto err; 970 /* Y_r = n1 * (n2 - X_r) - n3 */ 971 972 ret = 1; 973 974 err: 975 BN_CTX_end(ctx); 976 if (new_ctx != NULL) 977 BN_CTX_free(new_ctx); 978 return ret; 979} 980 981int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 982{ 983 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) 984 /* point is its own inverse */ 985 return 1; 986 987 return BN_usub(&point->Y, &group->field, &point->Y); 988} 989 990int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) 991{ 992 return BN_is_zero(&point->Z); 993} 994 995int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, 996 BN_CTX *ctx) 997{ 998 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 999 const BIGNUM *, BN_CTX *); 1000 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1001 const BIGNUM *p; 1002 BN_CTX *new_ctx = NULL; 1003 BIGNUM *rh, *tmp, *Z4, *Z6; 1004 int ret = -1; 1005 1006 if (EC_POINT_is_at_infinity(group, point)) 1007 return 1; 1008 1009 field_mul = group->meth->field_mul; 1010 field_sqr = group->meth->field_sqr; 1011 p = &group->field; 1012 1013 if (ctx == NULL) { 1014 ctx = new_ctx = BN_CTX_new(); 1015 if (ctx == NULL) 1016 return -1; 1017 } 1018 1019 BN_CTX_start(ctx); 1020 rh = BN_CTX_get(ctx); 1021 tmp = BN_CTX_get(ctx); 1022 Z4 = BN_CTX_get(ctx); 1023 Z6 = BN_CTX_get(ctx); 1024 if (Z6 == NULL) 1025 goto err; 1026 1027 /*- 1028 * We have a curve defined by a Weierstrass equation 1029 * y^2 = x^3 + a*x + b. 1030 * The point to consider is given in Jacobian projective coordinates 1031 * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). 1032 * Substituting this and multiplying by Z^6 transforms the above equation into 1033 * Y^2 = X^3 + a*X*Z^4 + b*Z^6. 1034 * To test this, we add up the right-hand side in 'rh'. 1035 */ 1036 1037 /* rh := X^2 */ 1038 if (!field_sqr(group, rh, &point->X, ctx)) 1039 goto err; 1040 1041 if (!point->Z_is_one) { 1042 if (!field_sqr(group, tmp, &point->Z, ctx)) 1043 goto err; 1044 if (!field_sqr(group, Z4, tmp, ctx)) 1045 goto err; 1046 if (!field_mul(group, Z6, Z4, tmp, ctx)) 1047 goto err; 1048 1049 /* rh := (rh + a*Z^4)*X */ 1050 if (group->a_is_minus3) { 1051 if (!BN_mod_lshift1_quick(tmp, Z4, p)) 1052 goto err; 1053 if (!BN_mod_add_quick(tmp, tmp, Z4, p)) 1054 goto err; 1055 if (!BN_mod_sub_quick(rh, rh, tmp, p)) 1056 goto err; 1057 if (!field_mul(group, rh, rh, &point->X, ctx)) 1058 goto err; 1059 } else { 1060 if (!field_mul(group, tmp, Z4, &group->a, ctx)) 1061 goto err; 1062 if (!BN_mod_add_quick(rh, rh, tmp, p)) 1063 goto err; 1064 if (!field_mul(group, rh, rh, &point->X, ctx)) 1065 goto err; 1066 } 1067 1068 /* rh := rh + b*Z^6 */ 1069 if (!field_mul(group, tmp, &group->b, Z6, ctx)) 1070 goto err; 1071 if (!BN_mod_add_quick(rh, rh, tmp, p)) 1072 goto err; 1073 } else { 1074 /* point->Z_is_one */ 1075 1076 /* rh := (rh + a)*X */ 1077 if (!BN_mod_add_quick(rh, rh, &group->a, p)) 1078 goto err; 1079 if (!field_mul(group, rh, rh, &point->X, ctx)) 1080 goto err; 1081 /* rh := rh + b */ 1082 if (!BN_mod_add_quick(rh, rh, &group->b, p)) 1083 goto err; 1084 } 1085 1086 /* 'lh' := Y^2 */ 1087 if (!field_sqr(group, tmp, &point->Y, ctx)) 1088 goto err; 1089 1090 ret = (0 == BN_ucmp(tmp, rh)); 1091 1092 err: 1093 BN_CTX_end(ctx); 1094 if (new_ctx != NULL) 1095 BN_CTX_free(new_ctx); 1096 return ret; 1097} 1098 1099int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, 1100 const EC_POINT *b, BN_CTX *ctx) 1101{ 1102 /*- 1103 * return values: 1104 * -1 error 1105 * 0 equal (in affine coordinates) 1106 * 1 not equal 1107 */ 1108 1109 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 1110 const BIGNUM *, BN_CTX *); 1111 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1112 BN_CTX *new_ctx = NULL; 1113 BIGNUM *tmp1, *tmp2, *Za23, *Zb23; 1114 const BIGNUM *tmp1_, *tmp2_; 1115 int ret = -1; 1116 1117 if (EC_POINT_is_at_infinity(group, a)) { 1118 return EC_POINT_is_at_infinity(group, b) ? 0 : 1; 1119 } 1120 1121 if (EC_POINT_is_at_infinity(group, b)) 1122 return 1; 1123 1124 if (a->Z_is_one && b->Z_is_one) { 1125 return ((BN_cmp(&a->X, &b->X) == 0) 1126 && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; 1127 } 1128 1129 field_mul = group->meth->field_mul; 1130 field_sqr = group->meth->field_sqr; 1131 1132 if (ctx == NULL) { 1133 ctx = new_ctx = BN_CTX_new(); 1134 if (ctx == NULL) 1135 return -1; 1136 } 1137 1138 BN_CTX_start(ctx); 1139 tmp1 = BN_CTX_get(ctx); 1140 tmp2 = BN_CTX_get(ctx); 1141 Za23 = BN_CTX_get(ctx); 1142 Zb23 = BN_CTX_get(ctx); 1143 if (Zb23 == NULL) 1144 goto end; 1145 1146 /*- 1147 * We have to decide whether 1148 * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), 1149 * or equivalently, whether 1150 * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). 1151 */ 1152 1153 if (!b->Z_is_one) { 1154 if (!field_sqr(group, Zb23, &b->Z, ctx)) 1155 goto end; 1156 if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) 1157 goto end; 1158 tmp1_ = tmp1; 1159 } else 1160 tmp1_ = &a->X; 1161 if (!a->Z_is_one) { 1162 if (!field_sqr(group, Za23, &a->Z, ctx)) 1163 goto end; 1164 if (!field_mul(group, tmp2, &b->X, Za23, ctx)) 1165 goto end; 1166 tmp2_ = tmp2; 1167 } else 1168 tmp2_ = &b->X; 1169 1170 /* compare X_a*Z_b^2 with X_b*Z_a^2 */ 1171 if (BN_cmp(tmp1_, tmp2_) != 0) { 1172 ret = 1; /* points differ */ 1173 goto end; 1174 } 1175 1176 if (!b->Z_is_one) { 1177 if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) 1178 goto end; 1179 if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) 1180 goto end; 1181 /* tmp1_ = tmp1 */ 1182 } else 1183 tmp1_ = &a->Y; 1184 if (!a->Z_is_one) { 1185 if (!field_mul(group, Za23, Za23, &a->Z, ctx)) 1186 goto end; 1187 if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) 1188 goto end; 1189 /* tmp2_ = tmp2 */ 1190 } else 1191 tmp2_ = &b->Y; 1192 1193 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ 1194 if (BN_cmp(tmp1_, tmp2_) != 0) { 1195 ret = 1; /* points differ */ 1196 goto end; 1197 } 1198 1199 /* points are equal */ 1200 ret = 0; 1201 1202 end: 1203 BN_CTX_end(ctx); 1204 if (new_ctx != NULL) 1205 BN_CTX_free(new_ctx); 1206 return ret; 1207} 1208 1209int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, 1210 BN_CTX *ctx) 1211{ 1212 BN_CTX *new_ctx = NULL; 1213 BIGNUM *x, *y; 1214 int ret = 0; 1215 1216 if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) 1217 return 1; 1218 1219 if (ctx == NULL) { 1220 ctx = new_ctx = BN_CTX_new(); 1221 if (ctx == NULL) 1222 return 0; 1223 } 1224 1225 BN_CTX_start(ctx); 1226 x = BN_CTX_get(ctx); 1227 y = BN_CTX_get(ctx); 1228 if (y == NULL) 1229 goto err; 1230 1231 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) 1232 goto err; 1233 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) 1234 goto err; 1235 if (!point->Z_is_one) { 1236 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR); 1237 goto err; 1238 } 1239 1240 ret = 1; 1241 1242 err: 1243 BN_CTX_end(ctx); 1244 if (new_ctx != NULL) 1245 BN_CTX_free(new_ctx); 1246 return ret; 1247} 1248 1249int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, 1250 EC_POINT *points[], BN_CTX *ctx) 1251{ 1252 BN_CTX *new_ctx = NULL; 1253 BIGNUM *tmp, *tmp_Z; 1254 BIGNUM **prod_Z = NULL; 1255 size_t i; 1256 int ret = 0; 1257 1258 if (num == 0) 1259 return 1; 1260 1261 if (ctx == NULL) { 1262 ctx = new_ctx = BN_CTX_new(); 1263 if (ctx == NULL) 1264 return 0; 1265 } 1266 1267 BN_CTX_start(ctx); 1268 tmp = BN_CTX_get(ctx); 1269 tmp_Z = BN_CTX_get(ctx); 1270 if (tmp == NULL || tmp_Z == NULL) 1271 goto err; 1272 1273 prod_Z = OPENSSL_malloc(num * sizeof(prod_Z[0])); 1274 if (prod_Z == NULL) 1275 goto err; 1276 for (i = 0; i < num; i++) { 1277 prod_Z[i] = BN_new(); 1278 if (prod_Z[i] == NULL) 1279 goto err; 1280 } 1281 1282 /* 1283 * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z, 1284 * skipping any zero-valued inputs (pretend that they're 1). 1285 */ 1286 1287 if (!BN_is_zero(&points[0]->Z)) { 1288 if (!BN_copy(prod_Z[0], &points[0]->Z)) 1289 goto err; 1290 } else { 1291 if (group->meth->field_set_to_one != 0) { 1292 if (!group->meth->field_set_to_one(group, prod_Z[0], ctx)) 1293 goto err; 1294 } else { 1295 if (!BN_one(prod_Z[0])) 1296 goto err; 1297 } 1298 } 1299 1300 for (i = 1; i < num; i++) { 1301 if (!BN_is_zero(&points[i]->Z)) { 1302 if (!group->meth->field_mul(group, prod_Z[i], prod_Z[i - 1], 1303 &points[i]->Z, ctx)) 1304 goto err; 1305 } else { 1306 if (!BN_copy(prod_Z[i], prod_Z[i - 1])) 1307 goto err; 1308 } 1309 } 1310 1311 /* 1312 * Now use a single explicit inversion to replace every non-zero 1313 * points[i]->Z by its inverse. 1314 */ 1315 1316 if (!BN_mod_inverse(tmp, prod_Z[num - 1], &group->field, ctx)) { 1317 ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB); 1318 goto err; 1319 } 1320 if (group->meth->field_encode != 0) { 1321 /* 1322 * In the Montgomery case, we just turned R*H (representing H) into 1323 * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to 1324 * multiply by the Montgomery factor twice. 1325 */ 1326 if (!group->meth->field_encode(group, tmp, tmp, ctx)) 1327 goto err; 1328 if (!group->meth->field_encode(group, tmp, tmp, ctx)) 1329 goto err; 1330 } 1331 1332 for (i = num - 1; i > 0; --i) { 1333 /* 1334 * Loop invariant: tmp is the product of the inverses of points[0]->Z 1335 * .. points[i]->Z (zero-valued inputs skipped). 1336 */ 1337 if (!BN_is_zero(&points[i]->Z)) { 1338 /* 1339 * Set tmp_Z to the inverse of points[i]->Z (as product of Z 1340 * inverses 0 .. i, Z values 0 .. i - 1). 1341 */ 1342 if (!group-> 1343 meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx)) 1344 goto err; 1345 /* 1346 * Update tmp to satisfy the loop invariant for i - 1. 1347 */ 1348 if (!group->meth->field_mul(group, tmp, tmp, &points[i]->Z, ctx)) 1349 goto err; 1350 /* Replace points[i]->Z by its inverse. */ 1351 if (!BN_copy(&points[i]->Z, tmp_Z)) 1352 goto err; 1353 } 1354 } 1355 1356 if (!BN_is_zero(&points[0]->Z)) { 1357 /* Replace points[0]->Z by its inverse. */ 1358 if (!BN_copy(&points[0]->Z, tmp)) 1359 goto err; 1360 } 1361 1362 /* Finally, fix up the X and Y coordinates for all points. */ 1363 1364 for (i = 0; i < num; i++) { 1365 EC_POINT *p = points[i]; 1366 1367 if (!BN_is_zero(&p->Z)) { 1368 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */ 1369 1370 if (!group->meth->field_sqr(group, tmp, &p->Z, ctx)) 1371 goto err; 1372 if (!group->meth->field_mul(group, &p->X, &p->X, tmp, ctx)) 1373 goto err; 1374 1375 if (!group->meth->field_mul(group, tmp, tmp, &p->Z, ctx)) 1376 goto err; 1377 if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp, ctx)) 1378 goto err; 1379 1380 if (group->meth->field_set_to_one != 0) { 1381 if (!group->meth->field_set_to_one(group, &p->Z, ctx)) 1382 goto err; 1383 } else { 1384 if (!BN_one(&p->Z)) 1385 goto err; 1386 } 1387 p->Z_is_one = 1; 1388 } 1389 } 1390 1391 ret = 1; 1392 1393 err: 1394 BN_CTX_end(ctx); 1395 if (new_ctx != NULL) 1396 BN_CTX_free(new_ctx); 1397 if (prod_Z != NULL) { 1398 for (i = 0; i < num; i++) { 1399 if (prod_Z[i] == NULL) 1400 break; 1401 BN_clear_free(prod_Z[i]); 1402 } 1403 OPENSSL_free(prod_Z); 1404 } 1405 return ret; 1406} 1407 1408int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1409 const BIGNUM *b, BN_CTX *ctx) 1410{ 1411 return BN_mod_mul(r, a, b, &group->field, ctx); 1412} 1413 1414int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1415 BN_CTX *ctx) 1416{ 1417 return BN_mod_sqr(r, a, &group->field, ctx); 1418} 1419