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 #include "../internal.h" 78 79 80 /* Most method functions in this file are designed to work with non-trivial 81 * representations of field elements if necessary (see ecp_mont.c): while 82 * standard modular addition and subtraction are used, the field_mul and 83 * field_sqr methods will be used for multiplication, and field_encode and 84 * field_decode (if defined) will be used for converting between 85 * representations. 86 * 87 * Functions here specifically assume that if a non-trivial representation is 88 * used, it is a Montgomery representation (i.e. 'encoding' means multiplying 89 * 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 BN_init(&group->one); 96 group->a_is_minus3 = 0; 97 return 1; 98 } 99 100 void ec_GFp_simple_group_finish(EC_GROUP *group) { 101 BN_free(&group->field); 102 BN_free(&group->a); 103 BN_free(&group->b); 104 BN_free(&group->one); 105 } 106 107 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) { 108 if (!BN_copy(&dest->field, &src->field) || 109 !BN_copy(&dest->a, &src->a) || 110 !BN_copy(&dest->b, &src->b) || 111 !BN_copy(&dest->one, &src->one)) { 112 return 0; 113 } 114 115 dest->a_is_minus3 = src->a_is_minus3; 116 return 1; 117 } 118 119 int ec_GFp_simple_group_set_curve(EC_GROUP *group, const BIGNUM *p, 120 const BIGNUM *a, const BIGNUM *b, 121 BN_CTX *ctx) { 122 int ret = 0; 123 BN_CTX *new_ctx = NULL; 124 BIGNUM *tmp_a; 125 126 /* p must be a prime > 3 */ 127 if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) { 128 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_FIELD); 129 return 0; 130 } 131 132 if (ctx == NULL) { 133 ctx = new_ctx = BN_CTX_new(); 134 if (ctx == NULL) { 135 return 0; 136 } 137 } 138 139 BN_CTX_start(ctx); 140 tmp_a = BN_CTX_get(ctx); 141 if (tmp_a == NULL) { 142 goto err; 143 } 144 145 /* group->field */ 146 if (!BN_copy(&group->field, p)) { 147 goto err; 148 } 149 BN_set_negative(&group->field, 0); 150 151 /* group->a */ 152 if (!BN_nnmod(tmp_a, a, p, ctx)) { 153 goto err; 154 } 155 if (group->meth->field_encode) { 156 if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) { 157 goto err; 158 } 159 } else if (!BN_copy(&group->a, tmp_a)) { 160 goto err; 161 } 162 163 /* group->b */ 164 if (!BN_nnmod(&group->b, b, p, ctx)) { 165 goto err; 166 } 167 if (group->meth->field_encode && 168 !group->meth->field_encode(group, &group->b, &group->b, ctx)) { 169 goto err; 170 } 171 172 /* group->a_is_minus3 */ 173 if (!BN_add_word(tmp_a, 3)) { 174 goto err; 175 } 176 group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field)); 177 178 if (group->meth->field_encode != NULL) { 179 if (!group->meth->field_encode(group, &group->one, BN_value_one(), ctx)) { 180 goto err; 181 } 182 } else if (!BN_copy(&group->one, BN_value_one())) { 183 goto err; 184 } 185 186 ret = 1; 187 188 err: 189 BN_CTX_end(ctx); 190 BN_CTX_free(new_ctx); 191 return ret; 192 } 193 194 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, 195 BIGNUM *b, BN_CTX *ctx) { 196 int ret = 0; 197 BN_CTX *new_ctx = NULL; 198 199 if (p != NULL && !BN_copy(p, &group->field)) { 200 return 0; 201 } 202 203 if (a != NULL || b != NULL) { 204 if (group->meth->field_decode) { 205 if (ctx == NULL) { 206 ctx = new_ctx = BN_CTX_new(); 207 if (ctx == NULL) { 208 return 0; 209 } 210 } 211 if (a != NULL && !group->meth->field_decode(group, a, &group->a, ctx)) { 212 goto err; 213 } 214 if (b != NULL && !group->meth->field_decode(group, b, &group->b, ctx)) { 215 goto err; 216 } 217 } else { 218 if (a != NULL && !BN_copy(a, &group->a)) { 219 goto err; 220 } 221 if (b != NULL && !BN_copy(b, &group->b)) { 222 goto err; 223 } 224 } 225 } 226 227 ret = 1; 228 229 err: 230 BN_CTX_free(new_ctx); 231 return ret; 232 } 233 234 unsigned ec_GFp_simple_group_get_degree(const EC_GROUP *group) { 235 return BN_num_bits(&group->field); 236 } 237 238 int ec_GFp_simple_point_init(EC_POINT *point) { 239 BN_init(&point->X); 240 BN_init(&point->Y); 241 BN_init(&point->Z); 242 243 return 1; 244 } 245 246 void ec_GFp_simple_point_finish(EC_POINT *point) { 247 BN_free(&point->X); 248 BN_free(&point->Y); 249 BN_free(&point->Z); 250 } 251 252 void ec_GFp_simple_point_clear_finish(EC_POINT *point) { 253 BN_clear_free(&point->X); 254 BN_clear_free(&point->Y); 255 BN_clear_free(&point->Z); 256 } 257 258 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) { 259 if (!BN_copy(&dest->X, &src->X) || 260 !BN_copy(&dest->Y, &src->Y) || 261 !BN_copy(&dest->Z, &src->Z)) { 262 return 0; 263 } 264 265 return 1; 266 } 267 268 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, 269 EC_POINT *point) { 270 BN_zero(&point->Z); 271 return 1; 272 } 273 274 static int set_Jprojective_coordinate_GFp(const EC_GROUP *group, BIGNUM *out, 275 const BIGNUM *in, BN_CTX *ctx) { 276 if (in == NULL) { 277 return 1; 278 } 279 if (BN_is_negative(in) || 280 BN_cmp(in, &group->field) >= 0) { 281 OPENSSL_PUT_ERROR(EC, EC_R_COORDINATES_OUT_OF_RANGE); 282 return 0; 283 } 284 if (group->meth->field_encode) { 285 return group->meth->field_encode(group, out, in, ctx); 286 } 287 return BN_copy(out, in) != NULL; 288 } 289 290 int ec_GFp_simple_set_Jprojective_coordinates_GFp( 291 const EC_GROUP *group, EC_POINT *point, const BIGNUM *x, const BIGNUM *y, 292 const BIGNUM *z, BN_CTX *ctx) { 293 BN_CTX *new_ctx = NULL; 294 int ret = 0; 295 296 if (ctx == NULL) { 297 ctx = new_ctx = BN_CTX_new(); 298 if (ctx == NULL) { 299 return 0; 300 } 301 } 302 303 if (!set_Jprojective_coordinate_GFp(group, &point->X, x, ctx) || 304 !set_Jprojective_coordinate_GFp(group, &point->Y, y, ctx) || 305 !set_Jprojective_coordinate_GFp(group, &point->Z, z, ctx)) { 306 goto err; 307 } 308 309 ret = 1; 310 311 err: 312 BN_CTX_free(new_ctx); 313 return ret; 314 } 315 316 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, 317 const EC_POINT *point, 318 BIGNUM *x, BIGNUM *y, 319 BIGNUM *z, BN_CTX *ctx) { 320 BN_CTX *new_ctx = NULL; 321 int ret = 0; 322 323 if (group->meth->field_decode != 0) { 324 if (ctx == NULL) { 325 ctx = new_ctx = BN_CTX_new(); 326 if (ctx == NULL) { 327 return 0; 328 } 329 } 330 331 if (x != NULL && !group->meth->field_decode(group, x, &point->X, ctx)) { 332 goto err; 333 } 334 if (y != NULL && !group->meth->field_decode(group, y, &point->Y, ctx)) { 335 goto err; 336 } 337 if (z != NULL && !group->meth->field_decode(group, z, &point->Z, ctx)) { 338 goto err; 339 } 340 } else { 341 if (x != NULL && !BN_copy(x, &point->X)) { 342 goto err; 343 } 344 if (y != NULL && !BN_copy(y, &point->Y)) { 345 goto err; 346 } 347 if (z != NULL && !BN_copy(z, &point->Z)) { 348 goto err; 349 } 350 } 351 352 ret = 1; 353 354 err: 355 BN_CTX_free(new_ctx); 356 return ret; 357 } 358 359 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, 360 EC_POINT *point, const BIGNUM *x, 361 const BIGNUM *y, BN_CTX *ctx) { 362 if (x == NULL || y == NULL) { 363 /* unlike for projective coordinates, we do not tolerate this */ 364 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER); 365 return 0; 366 } 367 368 return ec_point_set_Jprojective_coordinates_GFp(group, point, x, y, 369 BN_value_one(), ctx); 370 } 371 372 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 373 const EC_POINT *b, BN_CTX *ctx) { 374 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, 375 BN_CTX *); 376 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 377 const BIGNUM *p; 378 BN_CTX *new_ctx = NULL; 379 BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6; 380 int ret = 0; 381 382 if (a == b) { 383 return EC_POINT_dbl(group, r, a, ctx); 384 } 385 if (EC_POINT_is_at_infinity(group, a)) { 386 return EC_POINT_copy(r, b); 387 } 388 if (EC_POINT_is_at_infinity(group, b)) { 389 return EC_POINT_copy(r, a); 390 } 391 392 field_mul = group->meth->field_mul; 393 field_sqr = group->meth->field_sqr; 394 p = &group->field; 395 396 if (ctx == NULL) { 397 ctx = new_ctx = BN_CTX_new(); 398 if (ctx == NULL) { 399 return 0; 400 } 401 } 402 403 BN_CTX_start(ctx); 404 n0 = BN_CTX_get(ctx); 405 n1 = BN_CTX_get(ctx); 406 n2 = BN_CTX_get(ctx); 407 n3 = BN_CTX_get(ctx); 408 n4 = BN_CTX_get(ctx); 409 n5 = BN_CTX_get(ctx); 410 n6 = BN_CTX_get(ctx); 411 if (n6 == NULL) { 412 goto end; 413 } 414 415 /* Note that in this function we must not read components of 'a' or 'b' 416 * once we have written the corresponding components of 'r'. 417 * ('r' might be one of 'a' or 'b'.) 418 */ 419 420 /* n1, n2 */ 421 int b_Z_is_one = BN_cmp(&b->Z, &group->one) == 0; 422 423 if (b_Z_is_one) { 424 if (!BN_copy(n1, &a->X) || !BN_copy(n2, &a->Y)) { 425 goto end; 426 } 427 /* n1 = X_a */ 428 /* n2 = Y_a */ 429 } else { 430 if (!field_sqr(group, n0, &b->Z, ctx) || 431 !field_mul(group, n1, &a->X, n0, ctx)) { 432 goto end; 433 } 434 /* n1 = X_a * Z_b^2 */ 435 436 if (!field_mul(group, n0, n0, &b->Z, ctx) || 437 !field_mul(group, n2, &a->Y, n0, ctx)) { 438 goto end; 439 } 440 /* n2 = Y_a * Z_b^3 */ 441 } 442 443 /* n3, n4 */ 444 int a_Z_is_one = BN_cmp(&a->Z, &group->one) == 0; 445 if (a_Z_is_one) { 446 if (!BN_copy(n3, &b->X) || !BN_copy(n4, &b->Y)) { 447 goto end; 448 } 449 /* n3 = X_b */ 450 /* n4 = Y_b */ 451 } else { 452 if (!field_sqr(group, n0, &a->Z, ctx) || 453 !field_mul(group, n3, &b->X, n0, ctx)) { 454 goto end; 455 } 456 /* n3 = X_b * Z_a^2 */ 457 458 if (!field_mul(group, n0, n0, &a->Z, ctx) || 459 !field_mul(group, n4, &b->Y, n0, ctx)) { 460 goto end; 461 } 462 /* n4 = Y_b * Z_a^3 */ 463 } 464 465 /* n5, n6 */ 466 if (!BN_mod_sub_quick(n5, n1, n3, p) || 467 !BN_mod_sub_quick(n6, n2, n4, p)) { 468 goto end; 469 } 470 /* n5 = n1 - n3 */ 471 /* n6 = n2 - n4 */ 472 473 if (BN_is_zero(n5)) { 474 if (BN_is_zero(n6)) { 475 /* a is the same point as b */ 476 BN_CTX_end(ctx); 477 ret = EC_POINT_dbl(group, r, a, ctx); 478 ctx = NULL; 479 goto end; 480 } else { 481 /* a is the inverse of b */ 482 BN_zero(&r->Z); 483 ret = 1; 484 goto end; 485 } 486 } 487 488 /* 'n7', 'n8' */ 489 if (!BN_mod_add_quick(n1, n1, n3, p) || 490 !BN_mod_add_quick(n2, n2, n4, p)) { 491 goto end; 492 } 493 /* 'n7' = n1 + n3 */ 494 /* 'n8' = n2 + n4 */ 495 496 /* Z_r */ 497 if (a_Z_is_one && b_Z_is_one) { 498 if (!BN_copy(&r->Z, n5)) { 499 goto end; 500 } 501 } else { 502 if (a_Z_is_one) { 503 if (!BN_copy(n0, &b->Z)) { 504 goto end; 505 } 506 } else if (b_Z_is_one) { 507 if (!BN_copy(n0, &a->Z)) { 508 goto end; 509 } 510 } else if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) { 511 goto end; 512 } 513 if (!field_mul(group, &r->Z, n0, n5, ctx)) { 514 goto end; 515 } 516 } 517 518 /* Z_r = Z_a * Z_b * n5 */ 519 520 /* X_r */ 521 if (!field_sqr(group, n0, n6, ctx) || 522 !field_sqr(group, n4, n5, ctx) || 523 !field_mul(group, n3, n1, n4, ctx) || 524 !BN_mod_sub_quick(&r->X, n0, n3, p)) { 525 goto end; 526 } 527 /* X_r = n6^2 - n5^2 * 'n7' */ 528 529 /* 'n9' */ 530 if (!BN_mod_lshift1_quick(n0, &r->X, p) || 531 !BN_mod_sub_quick(n0, n3, n0, p)) { 532 goto end; 533 } 534 /* n9 = n5^2 * 'n7' - 2 * X_r */ 535 536 /* Y_r */ 537 if (!field_mul(group, n0, n0, n6, ctx) || 538 !field_mul(group, n5, n4, n5, ctx)) { 539 goto end; /* now n5 is n5^3 */ 540 } 541 if (!field_mul(group, n1, n2, n5, ctx) || 542 !BN_mod_sub_quick(n0, n0, n1, p)) { 543 goto end; 544 } 545 if (BN_is_odd(n0) && !BN_add(n0, n0, p)) { 546 goto end; 547 } 548 /* now 0 <= n0 < 2*p, and n0 is even */ 549 if (!BN_rshift1(&r->Y, n0)) { 550 goto end; 551 } 552 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */ 553 554 ret = 1; 555 556 end: 557 if (ctx) { 558 /* otherwise we already called BN_CTX_end */ 559 BN_CTX_end(ctx); 560 } 561 BN_CTX_free(new_ctx); 562 return ret; 563 } 564 565 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 566 BN_CTX *ctx) { 567 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, 568 BN_CTX *); 569 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 570 const BIGNUM *p; 571 BN_CTX *new_ctx = NULL; 572 BIGNUM *n0, *n1, *n2, *n3; 573 int ret = 0; 574 575 if (EC_POINT_is_at_infinity(group, a)) { 576 BN_zero(&r->Z); 577 return 1; 578 } 579 580 field_mul = group->meth->field_mul; 581 field_sqr = group->meth->field_sqr; 582 p = &group->field; 583 584 if (ctx == NULL) { 585 ctx = new_ctx = BN_CTX_new(); 586 if (ctx == NULL) { 587 return 0; 588 } 589 } 590 591 BN_CTX_start(ctx); 592 n0 = BN_CTX_get(ctx); 593 n1 = BN_CTX_get(ctx); 594 n2 = BN_CTX_get(ctx); 595 n3 = BN_CTX_get(ctx); 596 if (n3 == NULL) { 597 goto err; 598 } 599 600 /* Note that in this function we must not read components of 'a' 601 * once we have written the corresponding components of 'r'. 602 * ('r' might the same as 'a'.) 603 */ 604 605 /* n1 */ 606 if (BN_cmp(&a->Z, &group->one) == 0) { 607 if (!field_sqr(group, n0, &a->X, ctx) || 608 !BN_mod_lshift1_quick(n1, n0, p) || 609 !BN_mod_add_quick(n0, n0, n1, p) || 610 !BN_mod_add_quick(n1, n0, &group->a, p)) { 611 goto err; 612 } 613 /* n1 = 3 * X_a^2 + a_curve */ 614 } else if (group->a_is_minus3) { 615 if (!field_sqr(group, n1, &a->Z, ctx) || 616 !BN_mod_add_quick(n0, &a->X, n1, p) || 617 !BN_mod_sub_quick(n2, &a->X, n1, p) || 618 !field_mul(group, n1, n0, n2, ctx) || 619 !BN_mod_lshift1_quick(n0, n1, p) || 620 !BN_mod_add_quick(n1, n0, n1, p)) { 621 goto err; 622 } 623 /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) 624 * = 3 * X_a^2 - 3 * Z_a^4 */ 625 } else { 626 if (!field_sqr(group, n0, &a->X, ctx) || 627 !BN_mod_lshift1_quick(n1, n0, p) || 628 !BN_mod_add_quick(n0, n0, n1, p) || 629 !field_sqr(group, n1, &a->Z, ctx) || 630 !field_sqr(group, n1, n1, ctx) || 631 !field_mul(group, n1, n1, &group->a, ctx) || 632 !BN_mod_add_quick(n1, n1, n0, p)) { 633 goto err; 634 } 635 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */ 636 } 637 638 /* Z_r */ 639 if (BN_cmp(&a->Z, &group->one) == 0) { 640 if (!BN_copy(n0, &a->Y)) { 641 goto err; 642 } 643 } else if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) { 644 goto err; 645 } 646 if (!BN_mod_lshift1_quick(&r->Z, n0, p)) { 647 goto err; 648 } 649 /* Z_r = 2 * Y_a * Z_a */ 650 651 /* n2 */ 652 if (!field_sqr(group, n3, &a->Y, ctx) || 653 !field_mul(group, n2, &a->X, n3, ctx) || 654 !BN_mod_lshift_quick(n2, n2, 2, p)) { 655 goto err; 656 } 657 /* n2 = 4 * X_a * Y_a^2 */ 658 659 /* X_r */ 660 if (!BN_mod_lshift1_quick(n0, n2, p) || 661 !field_sqr(group, &r->X, n1, ctx) || 662 !BN_mod_sub_quick(&r->X, &r->X, n0, p)) { 663 goto err; 664 } 665 /* X_r = n1^2 - 2 * n2 */ 666 667 /* n3 */ 668 if (!field_sqr(group, n0, n3, ctx) || 669 !BN_mod_lshift_quick(n3, n0, 3, p)) { 670 goto err; 671 } 672 /* n3 = 8 * Y_a^4 */ 673 674 /* Y_r */ 675 if (!BN_mod_sub_quick(n0, n2, &r->X, p) || 676 !field_mul(group, n0, n1, n0, ctx) || 677 !BN_mod_sub_quick(&r->Y, n0, n3, p)) { 678 goto err; 679 } 680 /* Y_r = n1 * (n2 - X_r) - n3 */ 681 682 ret = 1; 683 684 err: 685 BN_CTX_end(ctx); 686 BN_CTX_free(new_ctx); 687 return ret; 688 } 689 690 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) { 691 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) { 692 /* point is its own inverse */ 693 return 1; 694 } 695 696 return BN_usub(&point->Y, &group->field, &point->Y); 697 } 698 699 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) { 700 return BN_is_zero(&point->Z); 701 } 702 703 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, 704 BN_CTX *ctx) { 705 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, 706 BN_CTX *); 707 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 708 const BIGNUM *p; 709 BN_CTX *new_ctx = NULL; 710 BIGNUM *rh, *tmp, *Z4, *Z6; 711 int ret = 0; 712 713 if (EC_POINT_is_at_infinity(group, point)) { 714 return 1; 715 } 716 717 field_mul = group->meth->field_mul; 718 field_sqr = group->meth->field_sqr; 719 p = &group->field; 720 721 if (ctx == NULL) { 722 ctx = new_ctx = BN_CTX_new(); 723 if (ctx == NULL) { 724 return 0; 725 } 726 } 727 728 BN_CTX_start(ctx); 729 rh = BN_CTX_get(ctx); 730 tmp = BN_CTX_get(ctx); 731 Z4 = BN_CTX_get(ctx); 732 Z6 = BN_CTX_get(ctx); 733 if (Z6 == NULL) { 734 goto err; 735 } 736 737 /* We have a curve defined by a Weierstrass equation 738 * y^2 = x^3 + a*x + b. 739 * The point to consider is given in Jacobian projective coordinates 740 * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). 741 * Substituting this and multiplying by Z^6 transforms the above equation 742 * into 743 * Y^2 = X^3 + a*X*Z^4 + b*Z^6. 744 * To test this, we add up the right-hand side in 'rh'. 745 */ 746 747 /* rh := X^2 */ 748 if (!field_sqr(group, rh, &point->X, ctx)) { 749 goto err; 750 } 751 752 if (BN_cmp(&point->Z, &group->one) != 0) { 753 if (!field_sqr(group, tmp, &point->Z, ctx) || 754 !field_sqr(group, Z4, tmp, ctx) || 755 !field_mul(group, Z6, Z4, tmp, ctx)) { 756 goto err; 757 } 758 759 /* rh := (rh + a*Z^4)*X */ 760 if (group->a_is_minus3) { 761 if (!BN_mod_lshift1_quick(tmp, Z4, p) || 762 !BN_mod_add_quick(tmp, tmp, Z4, p) || 763 !BN_mod_sub_quick(rh, rh, tmp, p) || 764 !field_mul(group, rh, rh, &point->X, ctx)) { 765 goto err; 766 } 767 } else { 768 if (!field_mul(group, tmp, Z4, &group->a, ctx) || 769 !BN_mod_add_quick(rh, rh, tmp, p) || 770 !field_mul(group, rh, rh, &point->X, ctx)) { 771 goto err; 772 } 773 } 774 775 /* rh := rh + b*Z^6 */ 776 if (!field_mul(group, tmp, &group->b, Z6, ctx) || 777 !BN_mod_add_quick(rh, rh, tmp, p)) { 778 goto err; 779 } 780 } else { 781 /* rh := (rh + a)*X */ 782 if (!BN_mod_add_quick(rh, rh, &group->a, p) || 783 !field_mul(group, rh, rh, &point->X, ctx)) { 784 goto err; 785 } 786 /* rh := rh + b */ 787 if (!BN_mod_add_quick(rh, rh, &group->b, p)) { 788 goto err; 789 } 790 } 791 792 /* 'lh' := Y^2 */ 793 if (!field_sqr(group, tmp, &point->Y, ctx)) { 794 goto err; 795 } 796 797 ret = (0 == BN_ucmp(tmp, rh)); 798 799 err: 800 BN_CTX_end(ctx); 801 BN_CTX_free(new_ctx); 802 return ret; 803 } 804 805 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, 806 const EC_POINT *b, BN_CTX *ctx) { 807 /* return values: 808 * -1 error 809 * 0 equal (in affine coordinates) 810 * 1 not equal 811 */ 812 813 int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, 814 BN_CTX *); 815 int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 816 BN_CTX *new_ctx = NULL; 817 BIGNUM *tmp1, *tmp2, *Za23, *Zb23; 818 const BIGNUM *tmp1_, *tmp2_; 819 int ret = -1; 820 821 if (EC_POINT_is_at_infinity(group, a)) { 822 return EC_POINT_is_at_infinity(group, b) ? 0 : 1; 823 } 824 825 if (EC_POINT_is_at_infinity(group, b)) { 826 return 1; 827 } 828 829 int a_Z_is_one = BN_cmp(&a->Z, &group->one) == 0; 830 int b_Z_is_one = BN_cmp(&b->Z, &group->one) == 0; 831 832 if (a_Z_is_one && b_Z_is_one) { 833 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; 834 } 835 836 field_mul = group->meth->field_mul; 837 field_sqr = group->meth->field_sqr; 838 839 if (ctx == NULL) { 840 ctx = new_ctx = BN_CTX_new(); 841 if (ctx == NULL) { 842 return -1; 843 } 844 } 845 846 BN_CTX_start(ctx); 847 tmp1 = BN_CTX_get(ctx); 848 tmp2 = BN_CTX_get(ctx); 849 Za23 = BN_CTX_get(ctx); 850 Zb23 = BN_CTX_get(ctx); 851 if (Zb23 == NULL) { 852 goto end; 853 } 854 855 /* We have to decide whether 856 * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), 857 * or equivalently, whether 858 * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). 859 */ 860 861 if (!b_Z_is_one) { 862 if (!field_sqr(group, Zb23, &b->Z, ctx) || 863 !field_mul(group, tmp1, &a->X, Zb23, ctx)) { 864 goto end; 865 } 866 tmp1_ = tmp1; 867 } else { 868 tmp1_ = &a->X; 869 } 870 if (!a_Z_is_one) { 871 if (!field_sqr(group, Za23, &a->Z, ctx) || 872 !field_mul(group, tmp2, &b->X, Za23, ctx)) { 873 goto end; 874 } 875 tmp2_ = tmp2; 876 } else { 877 tmp2_ = &b->X; 878 } 879 880 /* compare X_a*Z_b^2 with X_b*Z_a^2 */ 881 if (BN_cmp(tmp1_, tmp2_) != 0) { 882 ret = 1; /* points differ */ 883 goto end; 884 } 885 886 887 if (!b_Z_is_one) { 888 if (!field_mul(group, Zb23, Zb23, &b->Z, ctx) || 889 !field_mul(group, tmp1, &a->Y, Zb23, ctx)) { 890 goto end; 891 } 892 /* tmp1_ = tmp1 */ 893 } else { 894 tmp1_ = &a->Y; 895 } 896 if (!a_Z_is_one) { 897 if (!field_mul(group, Za23, Za23, &a->Z, ctx) || 898 !field_mul(group, tmp2, &b->Y, Za23, ctx)) { 899 goto end; 900 } 901 /* tmp2_ = tmp2 */ 902 } else { 903 tmp2_ = &b->Y; 904 } 905 906 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ 907 if (BN_cmp(tmp1_, tmp2_) != 0) { 908 ret = 1; /* points differ */ 909 goto end; 910 } 911 912 /* points are equal */ 913 ret = 0; 914 915 end: 916 BN_CTX_end(ctx); 917 BN_CTX_free(new_ctx); 918 return ret; 919 } 920 921 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, 922 BN_CTX *ctx) { 923 BN_CTX *new_ctx = NULL; 924 BIGNUM *x, *y; 925 int ret = 0; 926 927 if (BN_cmp(&point->Z, &group->one) == 0 || 928 EC_POINT_is_at_infinity(group, point)) { 929 return 1; 930 } 931 932 if (ctx == NULL) { 933 ctx = new_ctx = BN_CTX_new(); 934 if (ctx == NULL) { 935 return 0; 936 } 937 } 938 939 BN_CTX_start(ctx); 940 x = BN_CTX_get(ctx); 941 y = BN_CTX_get(ctx); 942 if (y == NULL) { 943 goto err; 944 } 945 946 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx) || 947 !EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) { 948 goto err; 949 } 950 if (BN_cmp(&point->Z, &group->one) != 0) { 951 OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR); 952 goto err; 953 } 954 955 ret = 1; 956 957 err: 958 BN_CTX_end(ctx); 959 BN_CTX_free(new_ctx); 960 return ret; 961 } 962 963 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, 964 EC_POINT *points[], BN_CTX *ctx) { 965 BN_CTX *new_ctx = NULL; 966 BIGNUM *tmp, *tmp_Z; 967 BIGNUM **prod_Z = NULL; 968 int ret = 0; 969 970 if (num == 0) { 971 return 1; 972 } 973 974 if (ctx == NULL) { 975 ctx = new_ctx = BN_CTX_new(); 976 if (ctx == NULL) { 977 return 0; 978 } 979 } 980 981 BN_CTX_start(ctx); 982 tmp = BN_CTX_get(ctx); 983 tmp_Z = BN_CTX_get(ctx); 984 if (tmp == NULL || tmp_Z == NULL) { 985 goto err; 986 } 987 988 prod_Z = OPENSSL_malloc(num * sizeof(prod_Z[0])); 989 if (prod_Z == NULL) { 990 goto err; 991 } 992 OPENSSL_memset(prod_Z, 0, num * sizeof(prod_Z[0])); 993 for (size_t i = 0; i < num; i++) { 994 prod_Z[i] = BN_new(); 995 if (prod_Z[i] == NULL) { 996 goto err; 997 } 998 } 999 1000 /* Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z, 1001 * skipping any zero-valued inputs (pretend that they're 1). */ 1002 1003 if (!BN_is_zero(&points[0]->Z)) { 1004 if (!BN_copy(prod_Z[0], &points[0]->Z)) { 1005 goto err; 1006 } 1007 } else { 1008 if (BN_copy(prod_Z[0], &group->one) == NULL) { 1009 goto err; 1010 } 1011 } 1012 1013 for (size_t i = 1; i < num; i++) { 1014 if (!BN_is_zero(&points[i]->Z)) { 1015 if (!group->meth->field_mul(group, prod_Z[i], prod_Z[i - 1], 1016 &points[i]->Z, ctx)) { 1017 goto err; 1018 } 1019 } else { 1020 if (!BN_copy(prod_Z[i], prod_Z[i - 1])) { 1021 goto err; 1022 } 1023 } 1024 } 1025 1026 /* Now use a single explicit inversion to replace every non-zero points[i]->Z 1027 * by its inverse. We use |BN_mod_inverse_odd| instead of doing a constant- 1028 * time inversion using Fermat's Little Theorem because this function is 1029 * usually only used for converting multiples of a public key point to 1030 * affine, and a public key point isn't secret. If we were to use Fermat's 1031 * Little Theorem then the cost of the inversion would usually be so high 1032 * that converting the multiples to affine would be counterproductive. */ 1033 int no_inverse; 1034 if (!BN_mod_inverse_odd(tmp, &no_inverse, prod_Z[num - 1], &group->field, 1035 ctx)) { 1036 OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); 1037 goto err; 1038 } 1039 1040 if (group->meth->field_encode != NULL) { 1041 /* In the Montgomery case, we just turned R*H (representing H) 1042 * into 1/(R*H), but we need R*(1/H) (representing 1/H); 1043 * i.e. we need to multiply by the Montgomery factor twice. */ 1044 if (!group->meth->field_encode(group, tmp, tmp, ctx) || 1045 !group->meth->field_encode(group, tmp, tmp, ctx)) { 1046 goto err; 1047 } 1048 } 1049 1050 for (size_t i = num - 1; i > 0; --i) { 1051 /* Loop invariant: tmp is the product of the inverses of 1052 * points[0]->Z .. points[i]->Z (zero-valued inputs skipped). */ 1053 if (BN_is_zero(&points[i]->Z)) { 1054 continue; 1055 } 1056 1057 /* Set tmp_Z to the inverse of points[i]->Z (as product 1058 * of Z inverses 0 .. i, Z values 0 .. i - 1). */ 1059 if (!group->meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx) || 1060 /* Update tmp to satisfy the loop invariant for i - 1. */ 1061 !group->meth->field_mul(group, tmp, tmp, &points[i]->Z, ctx) || 1062 /* Replace points[i]->Z by its inverse. */ 1063 !BN_copy(&points[i]->Z, tmp_Z)) { 1064 goto err; 1065 } 1066 } 1067 1068 /* Replace points[0]->Z by its inverse. */ 1069 if (!BN_is_zero(&points[0]->Z) && !BN_copy(&points[0]->Z, tmp)) { 1070 goto err; 1071 } 1072 1073 /* Finally, fix up the X and Y coordinates for all points. */ 1074 for (size_t i = 0; i < num; i++) { 1075 EC_POINT *p = points[i]; 1076 1077 if (!BN_is_zero(&p->Z)) { 1078 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1). */ 1079 if (!group->meth->field_sqr(group, tmp, &p->Z, ctx) || 1080 !group->meth->field_mul(group, &p->X, &p->X, tmp, ctx) || 1081 !group->meth->field_mul(group, tmp, tmp, &p->Z, ctx) || 1082 !group->meth->field_mul(group, &p->Y, &p->Y, tmp, ctx)) { 1083 goto err; 1084 } 1085 1086 if (BN_copy(&p->Z, &group->one) == NULL) { 1087 goto err; 1088 } 1089 } 1090 } 1091 1092 ret = 1; 1093 1094 err: 1095 BN_CTX_end(ctx); 1096 BN_CTX_free(new_ctx); 1097 if (prod_Z != NULL) { 1098 for (size_t i = 0; i < num; i++) { 1099 if (prod_Z[i] == NULL) { 1100 break; 1101 } 1102 BN_clear_free(prod_Z[i]); 1103 } 1104 OPENSSL_free(prod_Z); 1105 } 1106 1107 return ret; 1108 } 1109 1110 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1111 const BIGNUM *b, BN_CTX *ctx) { 1112 return BN_mod_mul(r, a, b, &group->field, ctx); 1113 } 1114 1115 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1116 BN_CTX *ctx) { 1117 return BN_mod_sqr(r, a, &group->field, ctx); 1118 } 1119
