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