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