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