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