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