1 /* $OpenBSD: ecp_methods.c,v 1.36 2025/01/11 21:20:39 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 <stdlib.h> 66 67 #include <openssl/bn.h> 68 #include <openssl/ec.h> 69 #include <openssl/err.h> 70 #include <openssl/objects.h> 71 72 #include "bn_local.h" 73 #include "ec_local.h" 74 75 /* 76 * Most method functions in this file are designed to work with non-trivial 77 * representations of field elements if necessary: while standard modular 78 * addition and subtraction are used, the field_mul and field_sqr methods will 79 * be used for multiplication, and field_encode and field_decode (if defined) 80 * will be used for converting between representations. 81 * 82 * The functions ec_points_make_affine() and ec_point_get_affine_coordinates() 83 * assume that if a non-trivial representation is used, it is a Montgomery 84 * representation (i.e. 'encoding' means multiplying by some factor R). 85 */ 86 87 static int 88 ec_decode_scalar(const EC_GROUP *group, BIGNUM *bn, const BIGNUM *x, BN_CTX *ctx) 89 { 90 if (bn == NULL) 91 return 1; 92 93 if (group->meth->field_decode != NULL) 94 return group->meth->field_decode(group, bn, x, ctx); 95 96 return bn_copy(bn, x); 97 } 98 99 static int 100 ec_encode_scalar(const EC_GROUP *group, BIGNUM *bn, const BIGNUM *x, BN_CTX *ctx) 101 { 102 if (!BN_nnmod(bn, x, group->p, ctx)) 103 return 0; 104 105 if (group->meth->field_encode != NULL) 106 return group->meth->field_encode(group, bn, bn, ctx); 107 108 return 1; 109 } 110 111 static int 112 ec_group_set_curve(EC_GROUP *group, 113 const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 114 { 115 BIGNUM *a_plus_3; 116 int ret = 0; 117 118 /* p must be a prime > 3 */ 119 if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) { 120 ECerror(EC_R_INVALID_FIELD); 121 return 0; 122 } 123 124 BN_CTX_start(ctx); 125 126 if ((a_plus_3 = BN_CTX_get(ctx)) == NULL) 127 goto err; 128 129 if (!bn_copy(group->p, p)) 130 goto err; 131 BN_set_negative(group->p, 0); 132 133 if (!ec_encode_scalar(group, group->a, a, ctx)) 134 goto err; 135 if (!ec_encode_scalar(group, group->b, b, ctx)) 136 goto err; 137 138 if (!BN_set_word(a_plus_3, 3)) 139 goto err; 140 if (!BN_mod_add(a_plus_3, a_plus_3, a, group->p, ctx)) 141 goto err; 142 143 group->a_is_minus3 = BN_is_zero(a_plus_3); 144 145 ret = 1; 146 147 err: 148 BN_CTX_end(ctx); 149 150 return ret; 151 } 152 153 static int 154 ec_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, 155 BN_CTX *ctx) 156 { 157 if (p != NULL) { 158 if (!bn_copy(p, group->p)) 159 return 0; 160 } 161 if (!ec_decode_scalar(group, a, group->a, ctx)) 162 return 0; 163 if (!ec_decode_scalar(group, b, group->b, ctx)) 164 return 0; 165 166 return 1; 167 } 168 169 static int 170 ec_point_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx) 171 { 172 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 173 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 174 const BIGNUM *p; 175 BIGNUM *rh, *tmp, *Z4, *Z6; 176 int ret = -1; 177 178 if (EC_POINT_is_at_infinity(group, point)) 179 return 1; 180 181 field_mul = group->meth->field_mul; 182 field_sqr = group->meth->field_sqr; 183 p = group->p; 184 185 BN_CTX_start(ctx); 186 187 if ((rh = BN_CTX_get(ctx)) == NULL) 188 goto err; 189 if ((tmp = BN_CTX_get(ctx)) == NULL) 190 goto err; 191 if ((Z4 = BN_CTX_get(ctx)) == NULL) 192 goto err; 193 if ((Z6 = BN_CTX_get(ctx)) == NULL) 194 goto err; 195 196 /* 197 * The curve is defined by a Weierstrass equation y^2 = x^3 + a*x + b. 198 * The point is given in Jacobian projective coordinates where (X, Y, Z) 199 * represents (x, y) = (X/Z^2, Y/Z^3). Substituting this and multiplying 200 * by Z^6 transforms the above into Y^2 = X^3 + a*X*Z^4 + b*Z^6. 201 */ 202 203 /* rh := X^2 */ 204 if (!field_sqr(group, rh, point->X, ctx)) 205 goto err; 206 207 if (!point->Z_is_one) { 208 if (!field_sqr(group, tmp, point->Z, ctx)) 209 goto err; 210 if (!field_sqr(group, Z4, tmp, ctx)) 211 goto err; 212 if (!field_mul(group, Z6, Z4, tmp, ctx)) 213 goto err; 214 215 /* rh := (rh + a*Z^4)*X */ 216 if (group->a_is_minus3) { 217 if (!BN_mod_lshift1_quick(tmp, Z4, p)) 218 goto err; 219 if (!BN_mod_add_quick(tmp, tmp, Z4, p)) 220 goto err; 221 if (!BN_mod_sub_quick(rh, rh, tmp, p)) 222 goto err; 223 if (!field_mul(group, rh, rh, point->X, ctx)) 224 goto err; 225 } else { 226 if (!field_mul(group, tmp, Z4, group->a, ctx)) 227 goto err; 228 if (!BN_mod_add_quick(rh, rh, tmp, p)) 229 goto err; 230 if (!field_mul(group, rh, rh, point->X, ctx)) 231 goto err; 232 } 233 234 /* rh := rh + b*Z^6 */ 235 if (!field_mul(group, tmp, group->b, Z6, ctx)) 236 goto err; 237 if (!BN_mod_add_quick(rh, rh, tmp, p)) 238 goto err; 239 } else { 240 /* point->Z_is_one */ 241 242 /* rh := (rh + a)*X */ 243 if (!BN_mod_add_quick(rh, rh, group->a, p)) 244 goto err; 245 if (!field_mul(group, rh, rh, point->X, ctx)) 246 goto err; 247 /* rh := rh + b */ 248 if (!BN_mod_add_quick(rh, rh, group->b, p)) 249 goto err; 250 } 251 252 /* 'lh' := Y^2 */ 253 if (!field_sqr(group, tmp, point->Y, ctx)) 254 goto err; 255 256 ret = (0 == BN_ucmp(tmp, rh)); 257 258 err: 259 BN_CTX_end(ctx); 260 261 return ret; 262 } 263 264 /* 265 * Returns -1 on error, 0 if the points are equal, 1 if the points are distinct. 266 */ 267 268 static int 269 ec_point_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, 270 BN_CTX *ctx) 271 { 272 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 273 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 274 BIGNUM *tmp1, *tmp2, *Za23, *Zb23; 275 const BIGNUM *tmp1_, *tmp2_; 276 int ret = -1; 277 278 if (EC_POINT_is_at_infinity(group, a) && EC_POINT_is_at_infinity(group, b)) 279 return 0; 280 if (EC_POINT_is_at_infinity(group, a) || EC_POINT_is_at_infinity(group, b)) 281 return 1; 282 283 if (a->Z_is_one && b->Z_is_one) 284 return BN_cmp(a->X, b->X) != 0 || BN_cmp(a->Y, b->Y) != 0; 285 286 field_mul = group->meth->field_mul; 287 field_sqr = group->meth->field_sqr; 288 289 BN_CTX_start(ctx); 290 291 if ((tmp1 = BN_CTX_get(ctx)) == NULL) 292 goto end; 293 if ((tmp2 = BN_CTX_get(ctx)) == NULL) 294 goto end; 295 if ((Za23 = BN_CTX_get(ctx)) == NULL) 296 goto end; 297 if ((Zb23 = BN_CTX_get(ctx)) == NULL) 298 goto end; 299 300 /* 301 * Decide whether (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), or 302 * equivalently, (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). 303 */ 304 305 if (!b->Z_is_one) { 306 if (!field_sqr(group, Zb23, b->Z, ctx)) 307 goto end; 308 if (!field_mul(group, tmp1, a->X, Zb23, ctx)) 309 goto end; 310 tmp1_ = tmp1; 311 } else 312 tmp1_ = a->X; 313 if (!a->Z_is_one) { 314 if (!field_sqr(group, Za23, a->Z, ctx)) 315 goto end; 316 if (!field_mul(group, tmp2, b->X, Za23, ctx)) 317 goto end; 318 tmp2_ = tmp2; 319 } else 320 tmp2_ = b->X; 321 322 /* compare X_a*Z_b^2 with X_b*Z_a^2 */ 323 if (BN_cmp(tmp1_, tmp2_) != 0) { 324 ret = 1; /* points differ */ 325 goto end; 326 } 327 if (!b->Z_is_one) { 328 if (!field_mul(group, Zb23, Zb23, b->Z, ctx)) 329 goto end; 330 if (!field_mul(group, tmp1, a->Y, Zb23, ctx)) 331 goto end; 332 /* tmp1_ = tmp1 */ 333 } else 334 tmp1_ = a->Y; 335 if (!a->Z_is_one) { 336 if (!field_mul(group, Za23, Za23, a->Z, ctx)) 337 goto end; 338 if (!field_mul(group, tmp2, b->Y, Za23, ctx)) 339 goto end; 340 /* tmp2_ = tmp2 */ 341 } else 342 tmp2_ = b->Y; 343 344 /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ 345 if (BN_cmp(tmp1_, tmp2_) != 0) { 346 ret = 1; /* points differ */ 347 goto end; 348 } 349 /* points are equal */ 350 ret = 0; 351 352 end: 353 BN_CTX_end(ctx); 354 355 return ret; 356 } 357 358 static int 359 ec_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point, 360 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) 361 { 362 int ret = 0; 363 364 if (x == NULL || y == NULL) { 365 ECerror(ERR_R_PASSED_NULL_PARAMETER); 366 goto err; 367 } 368 369 if (!ec_encode_scalar(group, point->X, x, ctx)) 370 goto err; 371 if (!ec_encode_scalar(group, point->Y, y, ctx)) 372 goto err; 373 if (!ec_encode_scalar(group, point->Z, BN_value_one(), ctx)) 374 goto err; 375 point->Z_is_one = 1; 376 377 ret = 1; 378 379 err: 380 return ret; 381 } 382 383 static int 384 ec_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point, 385 BIGNUM *x, BIGNUM *y, BN_CTX *ctx) 386 { 387 BIGNUM *z, *Z, *Z_1, *Z_2, *Z_3; 388 int ret = 0; 389 390 BN_CTX_start(ctx); 391 392 if ((z = BN_CTX_get(ctx)) == NULL) 393 goto err; 394 if ((Z = BN_CTX_get(ctx)) == NULL) 395 goto err; 396 if ((Z_1 = BN_CTX_get(ctx)) == NULL) 397 goto err; 398 if ((Z_2 = BN_CTX_get(ctx)) == NULL) 399 goto err; 400 if ((Z_3 = BN_CTX_get(ctx)) == NULL) 401 goto err; 402 403 /* 404 * Convert from Jacobian projective coordinates (X, Y, Z) into 405 * (X/Z^2, Y/Z^3). 406 */ 407 408 if (!ec_decode_scalar(group, z, point->Z, ctx)) 409 goto err; 410 411 if (BN_is_one(z)) { 412 if (!ec_decode_scalar(group, x, point->X, ctx)) 413 goto err; 414 if (!ec_decode_scalar(group, y, point->Y, ctx)) 415 goto err; 416 goto done; 417 } 418 419 if (BN_mod_inverse_ct(Z_1, z, group->p, ctx) == NULL) { 420 ECerror(ERR_R_BN_LIB); 421 goto err; 422 } 423 if (group->meth->field_encode == NULL) { 424 /* field_sqr works on standard representation */ 425 if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) 426 goto err; 427 } else { 428 if (!BN_mod_sqr(Z_2, Z_1, group->p, ctx)) 429 goto err; 430 } 431 432 if (x != NULL) { 433 /* 434 * in the Montgomery case, field_mul will cancel out 435 * Montgomery factor in X: 436 */ 437 if (!group->meth->field_mul(group, x, point->X, Z_2, ctx)) 438 goto err; 439 } 440 if (y != NULL) { 441 if (group->meth->field_encode == NULL) { 442 /* field_mul works on standard representation */ 443 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) 444 goto err; 445 } else { 446 if (!BN_mod_mul(Z_3, Z_2, Z_1, group->p, ctx)) 447 goto err; 448 } 449 450 /* 451 * in the Montgomery case, field_mul will cancel out 452 * Montgomery factor in Y: 453 */ 454 if (!group->meth->field_mul(group, y, point->Y, Z_3, ctx)) 455 goto err; 456 } 457 458 done: 459 ret = 1; 460 461 err: 462 BN_CTX_end(ctx); 463 464 return ret; 465 } 466 467 static int 468 ec_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT **points, 469 BN_CTX *ctx) 470 { 471 BIGNUM **prod_Z = NULL; 472 BIGNUM *one, *tmp, *tmp_Z; 473 size_t i; 474 int ret = 0; 475 476 if (num == 0) 477 return 1; 478 479 BN_CTX_start(ctx); 480 481 if ((one = BN_CTX_get(ctx)) == NULL) 482 goto err; 483 if ((tmp = BN_CTX_get(ctx)) == NULL) 484 goto err; 485 if ((tmp_Z = BN_CTX_get(ctx)) == NULL) 486 goto err; 487 488 if (!ec_encode_scalar(group, one, BN_value_one(), ctx)) 489 goto err; 490 491 if ((prod_Z = calloc(num, sizeof *prod_Z)) == NULL) 492 goto err; 493 for (i = 0; i < num; i++) { 494 if ((prod_Z[i] = BN_CTX_get(ctx)) == NULL) 495 goto err; 496 } 497 498 /* 499 * Set prod_Z[i] to the product of points[0]->Z, ..., points[i]->Z, 500 * skipping any zero-valued inputs (pretend that they're 1). 501 */ 502 503 if (!BN_is_zero(points[0]->Z)) { 504 if (!bn_copy(prod_Z[0], points[0]->Z)) 505 goto err; 506 } else { 507 if (!bn_copy(prod_Z[0], one)) 508 goto err; 509 } 510 511 for (i = 1; i < num; i++) { 512 if (!BN_is_zero(points[i]->Z)) { 513 if (!group->meth->field_mul(group, prod_Z[i], 514 prod_Z[i - 1], points[i]->Z, ctx)) 515 goto err; 516 } else { 517 if (!bn_copy(prod_Z[i], prod_Z[i - 1])) 518 goto err; 519 } 520 } 521 522 /* 523 * Now use a single explicit inversion to replace every non-zero 524 * points[i]->Z by its inverse. 525 */ 526 if (!BN_mod_inverse_nonct(tmp, prod_Z[num - 1], group->p, ctx)) { 527 ECerror(ERR_R_BN_LIB); 528 goto err; 529 } 530 531 if (group->meth->field_encode != NULL) { 532 /* 533 * In the Montgomery case we just turned R*H (representing H) 534 * into 1/(R*H), but we need R*(1/H) (representing 1/H); i.e., 535 * we need to multiply by the Montgomery factor twice. 536 */ 537 if (!group->meth->field_encode(group, tmp, tmp, ctx)) 538 goto err; 539 if (!group->meth->field_encode(group, tmp, tmp, ctx)) 540 goto err; 541 } 542 543 for (i = num - 1; i > 0; i--) { 544 /* 545 * Loop invariant: tmp is the product of the inverses of 546 * points[0]->Z, ..., points[i]->Z (zero-valued inputs skipped). 547 */ 548 if (BN_is_zero(points[i]->Z)) 549 continue; 550 551 /* Set tmp_Z to the inverse of points[i]->Z. */ 552 if (!group->meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx)) 553 goto err; 554 /* Adjust tmp to satisfy loop invariant. */ 555 if (!group->meth->field_mul(group, tmp, tmp, points[i]->Z, ctx)) 556 goto err; 557 /* Replace points[i]->Z by its inverse. */ 558 if (!bn_copy(points[i]->Z, tmp_Z)) 559 goto err; 560 } 561 562 if (!BN_is_zero(points[0]->Z)) { 563 /* Replace points[0]->Z by its inverse. */ 564 if (!bn_copy(points[0]->Z, tmp)) 565 goto err; 566 } 567 568 /* Finally, fix up the X and Y coordinates for all points. */ 569 for (i = 0; i < num; i++) { 570 EC_POINT *p = points[i]; 571 572 if (BN_is_zero(p->Z)) 573 continue; 574 575 /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */ 576 577 if (!group->meth->field_sqr(group, tmp, p->Z, ctx)) 578 goto err; 579 if (!group->meth->field_mul(group, p->X, p->X, tmp, ctx)) 580 goto err; 581 582 if (!group->meth->field_mul(group, tmp, tmp, p->Z, ctx)) 583 goto err; 584 if (!group->meth->field_mul(group, p->Y, p->Y, tmp, ctx)) 585 goto err; 586 587 if (!bn_copy(p->Z, one)) 588 goto err; 589 p->Z_is_one = 1; 590 } 591 592 ret = 1; 593 594 err: 595 BN_CTX_end(ctx); 596 free(prod_Z); 597 598 return ret; 599 } 600 601 static int 602 ec_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, 603 BN_CTX *ctx) 604 { 605 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 606 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 607 BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6; 608 const BIGNUM *p; 609 int ret = 0; 610 611 if (a == b) 612 return EC_POINT_dbl(group, r, a, ctx); 613 if (EC_POINT_is_at_infinity(group, a)) 614 return EC_POINT_copy(r, b); 615 if (EC_POINT_is_at_infinity(group, b)) 616 return EC_POINT_copy(r, a); 617 618 field_mul = group->meth->field_mul; 619 field_sqr = group->meth->field_sqr; 620 p = group->p; 621 622 BN_CTX_start(ctx); 623 624 if ((n0 = BN_CTX_get(ctx)) == NULL) 625 goto end; 626 if ((n1 = BN_CTX_get(ctx)) == NULL) 627 goto end; 628 if ((n2 = BN_CTX_get(ctx)) == NULL) 629 goto end; 630 if ((n3 = BN_CTX_get(ctx)) == NULL) 631 goto end; 632 if ((n4 = BN_CTX_get(ctx)) == NULL) 633 goto end; 634 if ((n5 = BN_CTX_get(ctx)) == NULL) 635 goto end; 636 if ((n6 = BN_CTX_get(ctx)) == NULL) 637 goto end; 638 639 /* 640 * Note that in this function we must not read components of 'a' or 641 * 'b' once we have written the corresponding components of 'r'. ('r' 642 * might be one of 'a' or 'b'.) 643 */ 644 645 /* n1, n2 */ 646 if (b->Z_is_one) { 647 if (!bn_copy(n1, a->X)) 648 goto end; 649 if (!bn_copy(n2, a->Y)) 650 goto end; 651 /* n1 = X_a */ 652 /* n2 = Y_a */ 653 } else { 654 if (!field_sqr(group, n0, b->Z, ctx)) 655 goto end; 656 if (!field_mul(group, n1, a->X, n0, ctx)) 657 goto end; 658 /* n1 = X_a * Z_b^2 */ 659 660 if (!field_mul(group, n0, n0, b->Z, ctx)) 661 goto end; 662 if (!field_mul(group, n2, a->Y, n0, ctx)) 663 goto end; 664 /* n2 = Y_a * Z_b^3 */ 665 } 666 667 /* n3, n4 */ 668 if (a->Z_is_one) { 669 if (!bn_copy(n3, b->X)) 670 goto end; 671 if (!bn_copy(n4, b->Y)) 672 goto end; 673 /* n3 = X_b */ 674 /* n4 = Y_b */ 675 } else { 676 if (!field_sqr(group, n0, a->Z, ctx)) 677 goto end; 678 if (!field_mul(group, n3, b->X, n0, ctx)) 679 goto end; 680 /* n3 = X_b * Z_a^2 */ 681 682 if (!field_mul(group, n0, n0, a->Z, ctx)) 683 goto end; 684 if (!field_mul(group, n4, b->Y, n0, ctx)) 685 goto end; 686 /* n4 = Y_b * Z_a^3 */ 687 } 688 689 /* n5, n6 */ 690 if (!BN_mod_sub_quick(n5, n1, n3, p)) 691 goto end; 692 if (!BN_mod_sub_quick(n6, n2, n4, p)) 693 goto end; 694 /* n5 = n1 - n3 */ 695 /* n6 = n2 - n4 */ 696 697 if (BN_is_zero(n5)) { 698 if (BN_is_zero(n6)) { 699 /* a is the same point as b */ 700 BN_CTX_end(ctx); 701 ret = EC_POINT_dbl(group, r, a, ctx); 702 ctx = NULL; 703 goto end; 704 } else { 705 /* a is the inverse of b */ 706 BN_zero(r->Z); 707 r->Z_is_one = 0; 708 ret = 1; 709 goto end; 710 } 711 } 712 /* 'n7', 'n8' */ 713 if (!BN_mod_add_quick(n1, n1, n3, p)) 714 goto end; 715 if (!BN_mod_add_quick(n2, n2, n4, p)) 716 goto end; 717 /* 'n7' = n1 + n3 */ 718 /* 'n8' = n2 + n4 */ 719 720 /* Z_r */ 721 if (a->Z_is_one && b->Z_is_one) { 722 if (!bn_copy(r->Z, n5)) 723 goto end; 724 } else { 725 if (a->Z_is_one) { 726 if (!bn_copy(n0, b->Z)) 727 goto end; 728 } else if (b->Z_is_one) { 729 if (!bn_copy(n0, a->Z)) 730 goto end; 731 } else { 732 if (!field_mul(group, n0, a->Z, b->Z, ctx)) 733 goto end; 734 } 735 if (!field_mul(group, r->Z, n0, n5, ctx)) 736 goto end; 737 } 738 r->Z_is_one = 0; 739 /* Z_r = Z_a * Z_b * n5 */ 740 741 /* X_r */ 742 if (!field_sqr(group, n0, n6, ctx)) 743 goto end; 744 if (!field_sqr(group, n4, n5, ctx)) 745 goto end; 746 if (!field_mul(group, n3, n1, n4, ctx)) 747 goto end; 748 if (!BN_mod_sub_quick(r->X, n0, n3, p)) 749 goto end; 750 /* X_r = n6^2 - n5^2 * 'n7' */ 751 752 /* 'n9' */ 753 if (!BN_mod_lshift1_quick(n0, r->X, p)) 754 goto end; 755 if (!BN_mod_sub_quick(n0, n3, n0, p)) 756 goto end; 757 /* n9 = n5^2 * 'n7' - 2 * X_r */ 758 759 /* Y_r */ 760 if (!field_mul(group, n0, n0, n6, ctx)) 761 goto end; 762 if (!field_mul(group, n5, n4, n5, ctx)) 763 goto end; /* now n5 is n5^3 */ 764 if (!field_mul(group, n1, n2, n5, ctx)) 765 goto end; 766 if (!BN_mod_sub_quick(n0, n0, n1, p)) 767 goto end; 768 if (BN_is_odd(n0)) 769 if (!BN_add(n0, n0, p)) 770 goto end; 771 /* now 0 <= n0 < 2*p, and n0 is even */ 772 if (!BN_rshift1(r->Y, n0)) 773 goto end; 774 /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */ 775 776 ret = 1; 777 778 end: 779 BN_CTX_end(ctx); 780 781 return ret; 782 } 783 784 static int 785 ec_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx) 786 { 787 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 788 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 789 const BIGNUM *p; 790 BIGNUM *n0, *n1, *n2, *n3; 791 int ret = 0; 792 793 if (EC_POINT_is_at_infinity(group, a)) 794 return EC_POINT_set_to_infinity(group, r); 795 796 field_mul = group->meth->field_mul; 797 field_sqr = group->meth->field_sqr; 798 p = group->p; 799 800 BN_CTX_start(ctx); 801 802 if ((n0 = BN_CTX_get(ctx)) == NULL) 803 goto err; 804 if ((n1 = BN_CTX_get(ctx)) == NULL) 805 goto err; 806 if ((n2 = BN_CTX_get(ctx)) == NULL) 807 goto err; 808 if ((n3 = BN_CTX_get(ctx)) == NULL) 809 goto err; 810 811 /* 812 * Note that in this function we must not read components of 'a' once 813 * we have written the corresponding components of 'r'. ('r' might 814 * the same as 'a'.) 815 */ 816 817 /* n1 */ 818 if (a->Z_is_one) { 819 if (!field_sqr(group, n0, a->X, ctx)) 820 goto err; 821 if (!BN_mod_lshift1_quick(n1, n0, p)) 822 goto err; 823 if (!BN_mod_add_quick(n0, n0, n1, p)) 824 goto err; 825 if (!BN_mod_add_quick(n1, n0, group->a, p)) 826 goto err; 827 /* n1 = 3 * X_a^2 + a_curve */ 828 } else if (group->a_is_minus3) { 829 if (!field_sqr(group, n1, a->Z, ctx)) 830 goto err; 831 if (!BN_mod_add_quick(n0, a->X, n1, p)) 832 goto err; 833 if (!BN_mod_sub_quick(n2, a->X, n1, p)) 834 goto err; 835 if (!field_mul(group, n1, n0, n2, ctx)) 836 goto err; 837 if (!BN_mod_lshift1_quick(n0, n1, p)) 838 goto err; 839 if (!BN_mod_add_quick(n1, n0, n1, p)) 840 goto err; 841 /* 842 * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) = 3 * X_a^2 - 3 * 843 * Z_a^4 844 */ 845 } else { 846 if (!field_sqr(group, n0, a->X, ctx)) 847 goto err; 848 if (!BN_mod_lshift1_quick(n1, n0, p)) 849 goto err; 850 if (!BN_mod_add_quick(n0, n0, n1, p)) 851 goto err; 852 if (!field_sqr(group, n1, a->Z, ctx)) 853 goto err; 854 if (!field_sqr(group, n1, n1, ctx)) 855 goto err; 856 if (!field_mul(group, n1, n1, group->a, ctx)) 857 goto err; 858 if (!BN_mod_add_quick(n1, n1, n0, p)) 859 goto err; 860 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */ 861 } 862 863 /* Z_r */ 864 if (a->Z_is_one) { 865 if (!bn_copy(n0, a->Y)) 866 goto err; 867 } else { 868 if (!field_mul(group, n0, a->Y, a->Z, ctx)) 869 goto err; 870 } 871 if (!BN_mod_lshift1_quick(r->Z, n0, p)) 872 goto err; 873 r->Z_is_one = 0; 874 /* Z_r = 2 * Y_a * Z_a */ 875 876 /* n2 */ 877 if (!field_sqr(group, n3, a->Y, ctx)) 878 goto err; 879 if (!field_mul(group, n2, a->X, n3, ctx)) 880 goto err; 881 if (!BN_mod_lshift_quick(n2, n2, 2, p)) 882 goto err; 883 /* n2 = 4 * X_a * Y_a^2 */ 884 885 /* X_r */ 886 if (!BN_mod_lshift1_quick(n0, n2, p)) 887 goto err; 888 if (!field_sqr(group, r->X, n1, ctx)) 889 goto err; 890 if (!BN_mod_sub_quick(r->X, r->X, n0, p)) 891 goto err; 892 /* X_r = n1^2 - 2 * n2 */ 893 894 /* n3 */ 895 if (!field_sqr(group, n0, n3, ctx)) 896 goto err; 897 if (!BN_mod_lshift_quick(n3, n0, 3, p)) 898 goto err; 899 /* n3 = 8 * Y_a^4 */ 900 901 /* Y_r */ 902 if (!BN_mod_sub_quick(n0, n2, r->X, p)) 903 goto err; 904 if (!field_mul(group, n0, n1, n0, ctx)) 905 goto err; 906 if (!BN_mod_sub_quick(r->Y, n0, n3, p)) 907 goto err; 908 /* Y_r = n1 * (n2 - X_r) - n3 */ 909 910 ret = 1; 911 912 err: 913 BN_CTX_end(ctx); 914 915 return ret; 916 } 917 918 static int 919 ec_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 920 { 921 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(point->Y)) 922 /* point is its own inverse */ 923 return 1; 924 925 return BN_usub(point->Y, group->p, point->Y); 926 } 927 928 static int 929 ec_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 930 BN_CTX *ctx) 931 { 932 return BN_mod_mul(r, a, b, group->p, ctx); 933 } 934 935 static int 936 ec_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) 937 { 938 return BN_mod_sqr(r, a, group->p, ctx); 939 } 940 941 /* 942 * Apply randomization of EC point Jacobian projective coordinates: 943 * 944 * (X, Y, Z) = (lambda^2 * X, lambda^3 * Y, lambda * Z) 945 * 946 * where lambda is in the interval [1, p). 947 */ 948 static int 949 ec_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx) 950 { 951 BIGNUM *lambda = NULL; 952 BIGNUM *tmp = NULL; 953 int ret = 0; 954 955 BN_CTX_start(ctx); 956 if ((lambda = BN_CTX_get(ctx)) == NULL) 957 goto err; 958 if ((tmp = BN_CTX_get(ctx)) == NULL) 959 goto err; 960 961 /* Generate lambda in [1, p). */ 962 if (!bn_rand_interval(lambda, 1, group->p)) 963 goto err; 964 965 if (group->meth->field_encode != NULL && 966 !group->meth->field_encode(group, lambda, lambda, ctx)) 967 goto err; 968 969 /* Z = lambda * Z */ 970 if (!group->meth->field_mul(group, p->Z, lambda, p->Z, ctx)) 971 goto err; 972 973 /* tmp = lambda^2 */ 974 if (!group->meth->field_sqr(group, tmp, lambda, ctx)) 975 goto err; 976 977 /* X = lambda^2 * X */ 978 if (!group->meth->field_mul(group, p->X, tmp, p->X, ctx)) 979 goto err; 980 981 /* tmp = lambda^3 */ 982 if (!group->meth->field_mul(group, tmp, tmp, lambda, ctx)) 983 goto err; 984 985 /* Y = lambda^3 * Y */ 986 if (!group->meth->field_mul(group, p->Y, tmp, p->Y, ctx)) 987 goto err; 988 989 /* Disable optimized arithmetics after replacing Z by lambda * Z. */ 990 p->Z_is_one = 0; 991 992 ret = 1; 993 994 err: 995 BN_CTX_end(ctx); 996 return ret; 997 } 998 999 #define EC_POINT_BN_set_flags(P, flags) do { \ 1000 BN_set_flags((P)->X, (flags)); \ 1001 BN_set_flags((P)->Y, (flags)); \ 1002 BN_set_flags((P)->Z, (flags)); \ 1003 } while(0) 1004 1005 #define EC_POINT_CSWAP(c, a, b, w, t) do { \ 1006 if (!BN_swap_ct(c, (a)->X, (b)->X, w) || \ 1007 !BN_swap_ct(c, (a)->Y, (b)->Y, w) || \ 1008 !BN_swap_ct(c, (a)->Z, (b)->Z, w)) \ 1009 goto err; \ 1010 t = ((a)->Z_is_one ^ (b)->Z_is_one) & (c); \ 1011 (a)->Z_is_one ^= (t); \ 1012 (b)->Z_is_one ^= (t); \ 1013 } while(0) 1014 1015 /* 1016 * This function computes (in constant time) a point multiplication over the 1017 * EC group. 1018 * 1019 * At a high level, it is Montgomery ladder with conditional swaps. 1020 * 1021 * It performs either a fixed point multiplication 1022 * (scalar * generator) 1023 * when point is NULL, or a variable point multiplication 1024 * (scalar * point) 1025 * when point is not NULL. 1026 * 1027 * scalar should be in the range [0,n) otherwise all constant time bets are off. 1028 * 1029 * NB: This says nothing about EC_POINT_add and EC_POINT_dbl, 1030 * which of course are not constant time themselves. 1031 * 1032 * The product is stored in r. 1033 * 1034 * Returns 1 on success, 0 otherwise. 1035 */ 1036 static int 1037 ec_mul_ct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 1038 const EC_POINT *point, BN_CTX *ctx) 1039 { 1040 int i, cardinality_bits, group_top, kbit, pbit, Z_is_one; 1041 EC_POINT *s = NULL; 1042 BIGNUM *k = NULL; 1043 BIGNUM *lambda = NULL; 1044 BIGNUM *cardinality = NULL; 1045 int ret = 0; 1046 1047 BN_CTX_start(ctx); 1048 1049 if ((s = EC_POINT_new(group)) == NULL) 1050 goto err; 1051 1052 if (point == NULL) { 1053 if (!EC_POINT_copy(s, group->generator)) 1054 goto err; 1055 } else { 1056 if (!EC_POINT_copy(s, point)) 1057 goto err; 1058 } 1059 1060 EC_POINT_BN_set_flags(s, BN_FLG_CONSTTIME); 1061 1062 if ((cardinality = BN_CTX_get(ctx)) == NULL) 1063 goto err; 1064 if ((lambda = BN_CTX_get(ctx)) == NULL) 1065 goto err; 1066 if ((k = BN_CTX_get(ctx)) == NULL) 1067 goto err; 1068 if (!BN_mul(cardinality, group->order, group->cofactor, ctx)) 1069 goto err; 1070 1071 /* 1072 * Group cardinalities are often on a word boundary. 1073 * So when we pad the scalar, some timing diff might 1074 * pop if it needs to be expanded due to carries. 1075 * So expand ahead of time. 1076 */ 1077 cardinality_bits = BN_num_bits(cardinality); 1078 group_top = cardinality->top; 1079 if (!bn_wexpand(k, group_top + 2) || 1080 !bn_wexpand(lambda, group_top + 2)) 1081 goto err; 1082 1083 if (!bn_copy(k, scalar)) 1084 goto err; 1085 1086 BN_set_flags(k, BN_FLG_CONSTTIME); 1087 1088 if (BN_num_bits(k) > cardinality_bits || BN_is_negative(k)) { 1089 /* 1090 * This is an unusual input, and we don't guarantee 1091 * constant-timeness 1092 */ 1093 if (!BN_nnmod(k, k, cardinality, ctx)) 1094 goto err; 1095 } 1096 1097 if (!BN_add(lambda, k, cardinality)) 1098 goto err; 1099 BN_set_flags(lambda, BN_FLG_CONSTTIME); 1100 if (!BN_add(k, lambda, cardinality)) 1101 goto err; 1102 /* 1103 * lambda := scalar + cardinality 1104 * k := scalar + 2*cardinality 1105 */ 1106 kbit = BN_is_bit_set(lambda, cardinality_bits); 1107 if (!BN_swap_ct(kbit, k, lambda, group_top + 2)) 1108 goto err; 1109 1110 group_top = group->p->top; 1111 if (!bn_wexpand(s->X, group_top) || 1112 !bn_wexpand(s->Y, group_top) || 1113 !bn_wexpand(s->Z, group_top) || 1114 !bn_wexpand(r->X, group_top) || 1115 !bn_wexpand(r->Y, group_top) || 1116 !bn_wexpand(r->Z, group_top)) 1117 goto err; 1118 1119 /* 1120 * Apply coordinate blinding for EC_POINT if the underlying EC_METHOD 1121 * implements it. 1122 */ 1123 if (!ec_blind_coordinates(group, s, ctx)) 1124 goto err; 1125 1126 /* top bit is a 1, in a fixed pos */ 1127 if (!EC_POINT_copy(r, s)) 1128 goto err; 1129 1130 EC_POINT_BN_set_flags(r, BN_FLG_CONSTTIME); 1131 1132 if (!EC_POINT_dbl(group, s, s, ctx)) 1133 goto err; 1134 1135 pbit = 0; 1136 1137 /* 1138 * The ladder step, with branches, is 1139 * 1140 * k[i] == 0: S = add(R, S), R = dbl(R) 1141 * k[i] == 1: R = add(S, R), S = dbl(S) 1142 * 1143 * Swapping R, S conditionally on k[i] leaves you with state 1144 * 1145 * k[i] == 0: T, U = R, S 1146 * k[i] == 1: T, U = S, R 1147 * 1148 * Then perform the ECC ops. 1149 * 1150 * U = add(T, U) 1151 * T = dbl(T) 1152 * 1153 * Which leaves you with state 1154 * 1155 * k[i] == 0: U = add(R, S), T = dbl(R) 1156 * k[i] == 1: U = add(S, R), T = dbl(S) 1157 * 1158 * Swapping T, U conditionally on k[i] leaves you with state 1159 * 1160 * k[i] == 0: R, S = T, U 1161 * k[i] == 1: R, S = U, T 1162 * 1163 * Which leaves you with state 1164 * 1165 * k[i] == 0: S = add(R, S), R = dbl(R) 1166 * k[i] == 1: R = add(S, R), S = dbl(S) 1167 * 1168 * So we get the same logic, but instead of a branch it's a 1169 * conditional swap, followed by ECC ops, then another conditional swap. 1170 * 1171 * Optimization: The end of iteration i and start of i-1 looks like 1172 * 1173 * ... 1174 * CSWAP(k[i], R, S) 1175 * ECC 1176 * CSWAP(k[i], R, S) 1177 * (next iteration) 1178 * CSWAP(k[i-1], R, S) 1179 * ECC 1180 * CSWAP(k[i-1], R, S) 1181 * ... 1182 * 1183 * So instead of two contiguous swaps, you can merge the condition 1184 * bits and do a single swap. 1185 * 1186 * k[i] k[i-1] Outcome 1187 * 0 0 No Swap 1188 * 0 1 Swap 1189 * 1 0 Swap 1190 * 1 1 No Swap 1191 * 1192 * This is XOR. pbit tracks the previous bit of k. 1193 */ 1194 1195 for (i = cardinality_bits - 1; i >= 0; i--) { 1196 kbit = BN_is_bit_set(k, i) ^ pbit; 1197 EC_POINT_CSWAP(kbit, r, s, group_top, Z_is_one); 1198 if (!EC_POINT_add(group, s, r, s, ctx)) 1199 goto err; 1200 if (!EC_POINT_dbl(group, r, r, ctx)) 1201 goto err; 1202 /* 1203 * pbit logic merges this cswap with that of the 1204 * next iteration 1205 */ 1206 pbit ^= kbit; 1207 } 1208 /* one final cswap to move the right value into r */ 1209 EC_POINT_CSWAP(pbit, r, s, group_top, Z_is_one); 1210 1211 ret = 1; 1212 1213 err: 1214 EC_POINT_free(s); 1215 BN_CTX_end(ctx); 1216 1217 return ret; 1218 } 1219 1220 #undef EC_POINT_BN_set_flags 1221 #undef EC_POINT_CSWAP 1222 1223 static int 1224 ec_mul_generator_ct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 1225 BN_CTX *ctx) 1226 { 1227 return ec_mul_ct(group, r, scalar, NULL, ctx); 1228 } 1229 1230 static int 1231 ec_mul_single_ct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 1232 const EC_POINT *point, BN_CTX *ctx) 1233 { 1234 return ec_mul_ct(group, r, scalar, point, ctx); 1235 } 1236 1237 static int 1238 ec_mul_double_nonct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar, 1239 const BIGNUM *p_scalar, const EC_POINT *point, BN_CTX *ctx) 1240 { 1241 return ec_wnaf_mul(group, r, g_scalar, point, p_scalar, ctx); 1242 } 1243 1244 static int 1245 ec_mont_group_set_curve(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, 1246 const BIGNUM *b, BN_CTX *ctx) 1247 { 1248 BN_MONT_CTX *mont = NULL; 1249 int ret = 0; 1250 1251 BN_MONT_CTX_free(group->mont_ctx); 1252 group->mont_ctx = NULL; 1253 1254 if ((mont = BN_MONT_CTX_new()) == NULL) 1255 goto err; 1256 if (!BN_MONT_CTX_set(mont, p, ctx)) { 1257 ECerror(ERR_R_BN_LIB); 1258 goto err; 1259 } 1260 group->mont_ctx = mont; 1261 mont = NULL; 1262 1263 if (!ec_group_set_curve(group, p, a, b, ctx)) { 1264 BN_MONT_CTX_free(group->mont_ctx); 1265 group->mont_ctx = NULL; 1266 goto err; 1267 } 1268 1269 ret = 1; 1270 1271 err: 1272 BN_MONT_CTX_free(mont); 1273 1274 return ret; 1275 } 1276 1277 static int 1278 ec_mont_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1279 const BIGNUM *b, BN_CTX *ctx) 1280 { 1281 if (group->mont_ctx == NULL) { 1282 ECerror(EC_R_NOT_INITIALIZED); 1283 return 0; 1284 } 1285 return BN_mod_mul_montgomery(r, a, b, group->mont_ctx, ctx); 1286 } 1287 1288 static int 1289 ec_mont_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1290 BN_CTX *ctx) 1291 { 1292 if (group->mont_ctx == NULL) { 1293 ECerror(EC_R_NOT_INITIALIZED); 1294 return 0; 1295 } 1296 return BN_mod_mul_montgomery(r, a, a, group->mont_ctx, ctx); 1297 } 1298 1299 static int 1300 ec_mont_field_encode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1301 BN_CTX *ctx) 1302 { 1303 if (group->mont_ctx == NULL) { 1304 ECerror(EC_R_NOT_INITIALIZED); 1305 return 0; 1306 } 1307 return BN_to_montgomery(r, a, group->mont_ctx, ctx); 1308 } 1309 1310 static int 1311 ec_mont_field_decode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1312 BN_CTX *ctx) 1313 { 1314 if (group->mont_ctx == NULL) { 1315 ECerror(EC_R_NOT_INITIALIZED); 1316 return 0; 1317 } 1318 return BN_from_montgomery(r, a, group->mont_ctx, ctx); 1319 } 1320 1321 static const EC_METHOD ec_GFp_simple_method = { 1322 .field_type = NID_X9_62_prime_field, 1323 .group_set_curve = ec_group_set_curve, 1324 .group_get_curve = ec_group_get_curve, 1325 .point_is_on_curve = ec_point_is_on_curve, 1326 .point_cmp = ec_point_cmp, 1327 .point_set_affine_coordinates = ec_point_set_affine_coordinates, 1328 .point_get_affine_coordinates = ec_point_get_affine_coordinates, 1329 .points_make_affine = ec_points_make_affine, 1330 .add = ec_add, 1331 .dbl = ec_dbl, 1332 .invert = ec_invert, 1333 .mul_generator_ct = ec_mul_generator_ct, 1334 .mul_single_ct = ec_mul_single_ct, 1335 .mul_double_nonct = ec_mul_double_nonct, 1336 .field_mul = ec_field_mul, 1337 .field_sqr = ec_field_sqr, 1338 }; 1339 1340 const EC_METHOD * 1341 EC_GFp_simple_method(void) 1342 { 1343 return &ec_GFp_simple_method; 1344 } 1345 LCRYPTO_ALIAS(EC_GFp_simple_method); 1346 1347 static const EC_METHOD ec_GFp_mont_method = { 1348 .field_type = NID_X9_62_prime_field, 1349 .group_set_curve = ec_mont_group_set_curve, 1350 .group_get_curve = ec_group_get_curve, 1351 .point_is_on_curve = ec_point_is_on_curve, 1352 .point_cmp = ec_point_cmp, 1353 .point_set_affine_coordinates = ec_point_set_affine_coordinates, 1354 .point_get_affine_coordinates = ec_point_get_affine_coordinates, 1355 .points_make_affine = ec_points_make_affine, 1356 .add = ec_add, 1357 .dbl = ec_dbl, 1358 .invert = ec_invert, 1359 .mul_generator_ct = ec_mul_generator_ct, 1360 .mul_single_ct = ec_mul_single_ct, 1361 .mul_double_nonct = ec_mul_double_nonct, 1362 .field_mul = ec_mont_field_mul, 1363 .field_sqr = ec_mont_field_sqr, 1364 .field_encode = ec_mont_field_encode, 1365 .field_decode = ec_mont_field_decode, 1366 }; 1367 1368 const EC_METHOD * 1369 EC_GFp_mont_method(void) 1370 { 1371 return &ec_GFp_mont_method; 1372 } 1373 LCRYPTO_ALIAS(EC_GFp_mont_method); 1374