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