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