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