1 /* $OpenBSD: ec_lib.c,v 1.57 2023/05/04 13:51:59 tb Exp $ */ 2 /* 3 * Originally written by Bodo Moeller for the OpenSSL project. 4 */ 5 /* ==================================================================== 6 * Copyright (c) 1998-2003 The OpenSSL Project. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in 17 * the documentation and/or other materials provided with the 18 * distribution. 19 * 20 * 3. All advertising materials mentioning features or use of this 21 * software must display the following acknowledgment: 22 * "This product includes software developed by the OpenSSL Project 23 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 24 * 25 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 26 * endorse or promote products derived from this software without 27 * prior written permission. For written permission, please contact 28 * openssl-core@openssl.org. 29 * 30 * 5. Products derived from this software may not be called "OpenSSL" 31 * nor may "OpenSSL" appear in their names without prior written 32 * permission of the OpenSSL Project. 33 * 34 * 6. Redistributions of any form whatsoever must retain the following 35 * acknowledgment: 36 * "This product includes software developed by the OpenSSL Project 37 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 38 * 39 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 40 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 41 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 42 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 43 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 45 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 46 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 48 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 49 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 50 * OF THE POSSIBILITY OF SUCH DAMAGE. 51 * ==================================================================== 52 * 53 * This product includes cryptographic software written by Eric Young 54 * (eay@cryptsoft.com). This product includes software written by Tim 55 * Hudson (tjh@cryptsoft.com). 56 * 57 */ 58 /* ==================================================================== 59 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 60 * Binary polynomial ECC support in OpenSSL originally developed by 61 * SUN MICROSYSTEMS, INC., and contributed to the OpenSSL project. 62 */ 63 64 #include <string.h> 65 66 #include <openssl/opensslconf.h> 67 68 #include <openssl/err.h> 69 #include <openssl/opensslv.h> 70 71 #include "bn_local.h" 72 #include "ec_local.h" 73 74 /* functions for EC_GROUP objects */ 75 76 EC_GROUP * 77 EC_GROUP_new(const EC_METHOD *meth) 78 { 79 EC_GROUP *ret; 80 81 if (meth == NULL) { 82 ECerror(EC_R_SLOT_FULL); 83 return NULL; 84 } 85 if (meth->group_init == NULL) { 86 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 87 return NULL; 88 } 89 ret = malloc(sizeof *ret); 90 if (ret == NULL) { 91 ECerror(ERR_R_MALLOC_FAILURE); 92 return NULL; 93 } 94 ret->meth = meth; 95 96 ret->extra_data = NULL; 97 98 ret->generator = NULL; 99 BN_init(&ret->order); 100 BN_init(&ret->cofactor); 101 102 ret->curve_name = 0; 103 ret->asn1_flag = OPENSSL_EC_NAMED_CURVE; 104 ret->asn1_form = POINT_CONVERSION_UNCOMPRESSED; 105 106 ret->seed = NULL; 107 ret->seed_len = 0; 108 109 if (!meth->group_init(ret)) { 110 free(ret); 111 return NULL; 112 } 113 return ret; 114 } 115 116 117 void 118 EC_GROUP_free(EC_GROUP *group) 119 { 120 if (group == NULL) 121 return; 122 123 if (group->meth->group_finish != NULL) 124 group->meth->group_finish(group); 125 126 EC_EX_DATA_clear_free_all_data(&group->extra_data); 127 128 EC_POINT_free(group->generator); 129 BN_free(&group->order); 130 BN_free(&group->cofactor); 131 132 freezero(group->seed, group->seed_len); 133 freezero(group, sizeof *group); 134 } 135 136 void 137 EC_GROUP_clear_free(EC_GROUP *group) 138 { 139 EC_GROUP_free(group); 140 } 141 142 int 143 EC_GROUP_copy(EC_GROUP *dest, const EC_GROUP *src) 144 { 145 EC_EXTRA_DATA *d; 146 147 if (dest->meth->group_copy == NULL) { 148 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 149 return 0; 150 } 151 if (dest->meth != src->meth) { 152 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 153 return 0; 154 } 155 if (dest == src) 156 return 1; 157 158 EC_EX_DATA_free_all_data(&dest->extra_data); 159 160 for (d = src->extra_data; d != NULL; d = d->next) { 161 void *t = d->dup_func(d->data); 162 163 if (t == NULL) 164 return 0; 165 if (!EC_EX_DATA_set_data(&dest->extra_data, t, d->dup_func, 166 d->free_func, d->clear_free_func)) 167 return 0; 168 } 169 170 if (src->generator != NULL) { 171 if (dest->generator == NULL) { 172 dest->generator = EC_POINT_new(dest); 173 if (dest->generator == NULL) 174 return 0; 175 } 176 if (!EC_POINT_copy(dest->generator, src->generator)) 177 return 0; 178 } else { 179 /* src->generator == NULL */ 180 EC_POINT_free(dest->generator); 181 dest->generator = NULL; 182 } 183 184 if (!bn_copy(&dest->order, &src->order)) 185 return 0; 186 if (!bn_copy(&dest->cofactor, &src->cofactor)) 187 return 0; 188 189 dest->curve_name = src->curve_name; 190 dest->asn1_flag = src->asn1_flag; 191 dest->asn1_form = src->asn1_form; 192 193 if (src->seed) { 194 free(dest->seed); 195 dest->seed = malloc(src->seed_len); 196 if (dest->seed == NULL) 197 return 0; 198 memcpy(dest->seed, src->seed, src->seed_len); 199 dest->seed_len = src->seed_len; 200 } else { 201 free(dest->seed); 202 dest->seed = NULL; 203 dest->seed_len = 0; 204 } 205 206 207 return dest->meth->group_copy(dest, src); 208 } 209 210 211 EC_GROUP * 212 EC_GROUP_dup(const EC_GROUP *a) 213 { 214 EC_GROUP *t = NULL; 215 216 if ((a != NULL) && ((t = EC_GROUP_new(a->meth)) != NULL) && 217 (!EC_GROUP_copy(t, a))) { 218 EC_GROUP_free(t); 219 t = NULL; 220 } 221 return t; 222 } 223 224 225 const EC_METHOD * 226 EC_GROUP_method_of(const EC_GROUP *group) 227 { 228 return group->meth; 229 } 230 231 232 int 233 EC_METHOD_get_field_type(const EC_METHOD *meth) 234 { 235 return meth->field_type; 236 } 237 238 /* 239 * Try computing the cofactor from generator order n and field cardinality q. 240 * This works for all curves of cryptographic interest. 241 * 242 * Hasse's theorem: | h * n - (q + 1) | <= 2 * sqrt(q) 243 * 244 * So: h_min = (q + 1 - 2*sqrt(q)) / n and h_max = (q + 1 + 2*sqrt(q)) / n and 245 * therefore h_max - h_min = 4*sqrt(q) / n. So if n > 4*sqrt(q) holds, there is 246 * only one possible value for h: 247 * 248 * h = \lfloor (h_min + h_max)/2 \rceil = \lfloor (q + 1)/n \rceil 249 * 250 * Otherwise, zero cofactor and return success. 251 */ 252 static int 253 ec_guess_cofactor(EC_GROUP *group) 254 { 255 BN_CTX *ctx = NULL; 256 BIGNUM *q = NULL; 257 int ret = 0; 258 259 /* 260 * If the cofactor is too large, we cannot guess it and default to zero. 261 * The RHS of below is a strict overestimate of log(4 * sqrt(q)). 262 */ 263 if (BN_num_bits(&group->order) <= 264 (BN_num_bits(&group->field) + 1) / 2 + 3) { 265 BN_zero(&group->cofactor); 266 return 1; 267 } 268 269 if ((ctx = BN_CTX_new()) == NULL) 270 goto err; 271 272 BN_CTX_start(ctx); 273 if ((q = BN_CTX_get(ctx)) == NULL) 274 goto err; 275 276 /* Set q = 2**m for binary fields; q = p otherwise. */ 277 if (group->meth->field_type == NID_X9_62_characteristic_two_field) { 278 BN_zero(q); 279 if (!BN_set_bit(q, BN_num_bits(&group->field) - 1)) 280 goto err; 281 } else { 282 if (!bn_copy(q, &group->field)) 283 goto err; 284 } 285 286 /* 287 * Compute 288 * h = \lfloor (q + 1)/n \rceil = \lfloor (q + 1 + n/2) / n \rfloor. 289 */ 290 291 /* h = n/2 */ 292 if (!BN_rshift1(&group->cofactor, &group->order)) 293 goto err; 294 /* h = 1 + n/2 */ 295 if (!BN_add(&group->cofactor, &group->cofactor, BN_value_one())) 296 goto err; 297 /* h = q + 1 + n/2 */ 298 if (!BN_add(&group->cofactor, &group->cofactor, q)) 299 goto err; 300 /* h = (q + 1 + n/2) / n */ 301 if (!BN_div_ct(&group->cofactor, NULL, &group->cofactor, &group->order, 302 ctx)) 303 goto err; 304 305 ret = 1; 306 307 err: 308 BN_CTX_end(ctx); 309 BN_CTX_free(ctx); 310 311 if (ret != 1) 312 BN_zero(&group->cofactor); 313 314 return ret; 315 } 316 317 int 318 EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, 319 const BIGNUM *order, const BIGNUM *cofactor) 320 { 321 if (generator == NULL) { 322 ECerror(ERR_R_PASSED_NULL_PARAMETER); 323 return 0; 324 } 325 326 /* Require group->field >= 1. */ 327 if (BN_is_zero(&group->field) || BN_is_negative(&group->field)) { 328 ECerror(EC_R_INVALID_FIELD); 329 return 0; 330 } 331 332 /* 333 * Require order > 1 and enforce an upper bound of at most one bit more 334 * than the field cardinality due to Hasse's theorem. 335 */ 336 if (order == NULL || BN_cmp(order, BN_value_one()) <= 0 || 337 BN_num_bits(order) > BN_num_bits(&group->field) + 1) { 338 ECerror(EC_R_INVALID_GROUP_ORDER); 339 return 0; 340 } 341 342 /* 343 * Unfortunately, the cofactor is an optional field in many standards. 344 * Internally, the library uses a 0 cofactor as a marker for "unknown 345 * cofactor". So accept cofactor == NULL or cofactor >= 0. 346 */ 347 if (cofactor != NULL && BN_is_negative(cofactor)) { 348 ECerror(EC_R_UNKNOWN_COFACTOR); 349 return 0; 350 } 351 352 if (group->generator == NULL) { 353 group->generator = EC_POINT_new(group); 354 if (group->generator == NULL) 355 return 0; 356 } 357 if (!EC_POINT_copy(group->generator, generator)) 358 return 0; 359 360 if (!bn_copy(&group->order, order)) 361 return 0; 362 363 /* Either take the provided positive cofactor, or try to compute it. */ 364 if (cofactor != NULL && !BN_is_zero(cofactor)) { 365 if (!bn_copy(&group->cofactor, cofactor)) 366 return 0; 367 } else if (!ec_guess_cofactor(group)) 368 return 0; 369 370 /* Use Hasse's theorem to bound the cofactor. */ 371 if (BN_num_bits(&group->cofactor) > BN_num_bits(&group->field) + 1) { 372 ECerror(EC_R_INVALID_GROUP_ORDER); 373 return 0; 374 } 375 376 return 1; 377 } 378 379 380 const EC_POINT * 381 EC_GROUP_get0_generator(const EC_GROUP *group) 382 { 383 return group->generator; 384 } 385 386 387 int 388 EC_GROUP_get_order(const EC_GROUP *group, BIGNUM *order, BN_CTX *ctx) 389 { 390 if (!bn_copy(order, &group->order)) 391 return 0; 392 393 return !BN_is_zero(order); 394 } 395 396 int 397 EC_GROUP_order_bits(const EC_GROUP *group) 398 { 399 return group->meth->group_order_bits(group); 400 } 401 402 int 403 EC_GROUP_get_cofactor(const EC_GROUP *group, BIGNUM *cofactor, BN_CTX *ctx) 404 { 405 if (!bn_copy(cofactor, &group->cofactor)) 406 return 0; 407 408 return !BN_is_zero(&group->cofactor); 409 } 410 411 412 void 413 EC_GROUP_set_curve_name(EC_GROUP *group, int nid) 414 { 415 group->curve_name = nid; 416 } 417 418 419 int 420 EC_GROUP_get_curve_name(const EC_GROUP *group) 421 { 422 return group->curve_name; 423 } 424 425 426 void 427 EC_GROUP_set_asn1_flag(EC_GROUP *group, int flag) 428 { 429 group->asn1_flag = flag; 430 } 431 432 433 int 434 EC_GROUP_get_asn1_flag(const EC_GROUP *group) 435 { 436 return group->asn1_flag; 437 } 438 439 440 void 441 EC_GROUP_set_point_conversion_form(EC_GROUP *group, 442 point_conversion_form_t form) 443 { 444 group->asn1_form = form; 445 } 446 447 448 point_conversion_form_t 449 EC_GROUP_get_point_conversion_form(const EC_GROUP *group) 450 { 451 return group->asn1_form; 452 } 453 454 455 size_t 456 EC_GROUP_set_seed(EC_GROUP *group, const unsigned char *p, size_t len) 457 { 458 if (group->seed) { 459 free(group->seed); 460 group->seed = NULL; 461 group->seed_len = 0; 462 } 463 if (!len || !p) 464 return 1; 465 466 if ((group->seed = malloc(len)) == NULL) 467 return 0; 468 memcpy(group->seed, p, len); 469 group->seed_len = len; 470 471 return len; 472 } 473 474 475 unsigned char * 476 EC_GROUP_get0_seed(const EC_GROUP *group) 477 { 478 return group->seed; 479 } 480 481 482 size_t 483 EC_GROUP_get_seed_len(const EC_GROUP *group) 484 { 485 return group->seed_len; 486 } 487 488 int 489 EC_GROUP_set_curve(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, 490 const BIGNUM *b, BN_CTX *ctx_in) 491 { 492 BN_CTX *ctx; 493 int ret = 0; 494 495 if ((ctx = ctx_in) == NULL) 496 ctx = BN_CTX_new(); 497 if (ctx == NULL) 498 goto err; 499 500 if (group->meth->group_set_curve == NULL) { 501 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 502 goto err; 503 } 504 ret = group->meth->group_set_curve(group, p, a, b, ctx); 505 506 err: 507 if (ctx != ctx_in) 508 BN_CTX_free(ctx); 509 510 return ret; 511 } 512 513 int 514 EC_GROUP_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, 515 BN_CTX *ctx_in) 516 { 517 BN_CTX *ctx; 518 int ret = 0; 519 520 if ((ctx = ctx_in) == NULL) 521 ctx = BN_CTX_new(); 522 if (ctx == NULL) 523 goto err; 524 525 if (group->meth->group_get_curve == NULL) { 526 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 527 goto err; 528 } 529 ret = group->meth->group_get_curve(group, p, a, b, ctx); 530 531 err: 532 if (ctx != ctx_in) 533 BN_CTX_free(ctx); 534 535 return ret; 536 } 537 538 int 539 EC_GROUP_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, 540 const BIGNUM *b, BN_CTX *ctx) 541 { 542 return EC_GROUP_set_curve(group, p, a, b, ctx); 543 } 544 545 int 546 EC_GROUP_get_curve_GFp(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, 547 BN_CTX *ctx) 548 { 549 return EC_GROUP_get_curve(group, p, a, b, ctx); 550 } 551 552 int 553 EC_GROUP_get_degree(const EC_GROUP *group) 554 { 555 if (group->meth->group_get_degree == NULL) { 556 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 557 return 0; 558 } 559 return group->meth->group_get_degree(group); 560 } 561 562 563 int 564 EC_GROUP_check_discriminant(const EC_GROUP *group, BN_CTX *ctx_in) 565 { 566 BN_CTX *ctx; 567 int ret = 0; 568 569 if ((ctx = ctx_in) == NULL) 570 ctx = BN_CTX_new(); 571 if (ctx == NULL) 572 goto err; 573 574 if (group->meth->group_check_discriminant == NULL) { 575 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 576 goto err; 577 } 578 ret = group->meth->group_check_discriminant(group, ctx); 579 580 err: 581 if (ctx != ctx_in) 582 BN_CTX_free(ctx); 583 584 return ret; 585 } 586 587 588 int 589 EC_GROUP_cmp(const EC_GROUP *a, const EC_GROUP *b, BN_CTX *ctx) 590 { 591 int r = 0; 592 BIGNUM *a1, *a2, *a3, *b1, *b2, *b3; 593 BN_CTX *ctx_new = NULL; 594 595 /* compare the field types */ 596 if (EC_METHOD_get_field_type(EC_GROUP_method_of(a)) != 597 EC_METHOD_get_field_type(EC_GROUP_method_of(b))) 598 return 1; 599 /* compare the curve name (if present in both) */ 600 if (EC_GROUP_get_curve_name(a) && EC_GROUP_get_curve_name(b) && 601 EC_GROUP_get_curve_name(a) != EC_GROUP_get_curve_name(b)) 602 return 1; 603 604 if (!ctx) 605 ctx_new = ctx = BN_CTX_new(); 606 if (!ctx) 607 return -1; 608 609 BN_CTX_start(ctx); 610 if ((a1 = BN_CTX_get(ctx)) == NULL) 611 goto err; 612 if ((a2 = BN_CTX_get(ctx)) == NULL) 613 goto err; 614 if ((a3 = BN_CTX_get(ctx)) == NULL) 615 goto err; 616 if ((b1 = BN_CTX_get(ctx)) == NULL) 617 goto err; 618 if ((b2 = BN_CTX_get(ctx)) == NULL) 619 goto err; 620 if ((b3 = BN_CTX_get(ctx)) == NULL) 621 goto err; 622 623 /* 624 * XXX This approach assumes that the external representation of 625 * curves over the same field type is the same. 626 */ 627 if (!a->meth->group_get_curve(a, a1, a2, a3, ctx) || 628 !b->meth->group_get_curve(b, b1, b2, b3, ctx)) 629 r = 1; 630 631 if (r || BN_cmp(a1, b1) || BN_cmp(a2, b2) || BN_cmp(a3, b3)) 632 r = 1; 633 634 /* XXX EC_POINT_cmp() assumes that the methods are equal */ 635 if (r || EC_POINT_cmp(a, EC_GROUP_get0_generator(a), 636 EC_GROUP_get0_generator(b), ctx)) 637 r = 1; 638 639 if (!r) { 640 /* compare the order and cofactor */ 641 if (!EC_GROUP_get_order(a, a1, ctx) || 642 !EC_GROUP_get_order(b, b1, ctx) || 643 !EC_GROUP_get_cofactor(a, a2, ctx) || 644 !EC_GROUP_get_cofactor(b, b2, ctx)) 645 goto err; 646 if (BN_cmp(a1, b1) || BN_cmp(a2, b2)) 647 r = 1; 648 } 649 BN_CTX_end(ctx); 650 if (ctx_new) 651 BN_CTX_free(ctx); 652 653 return r; 654 655 err: 656 BN_CTX_end(ctx); 657 if (ctx_new) 658 BN_CTX_free(ctx); 659 return -1; 660 } 661 662 /* 663 * Coordinate blinding for EC_POINT. 664 * 665 * The underlying EC_METHOD can optionally implement this function: 666 * underlying implementations should return 0 on errors, or 1 on success. 667 * 668 * This wrapper returns 1 in case the underlying EC_METHOD does not support 669 * coordinate blinding. 670 */ 671 int 672 ec_point_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx) 673 { 674 if (group->meth->blind_coordinates == NULL) 675 return 1; 676 677 return group->meth->blind_coordinates(group, p, ctx); 678 } 679 680 /* this has 'package' visibility */ 681 int 682 EC_EX_DATA_set_data(EC_EXTRA_DATA ** ex_data, void *data, 683 void *(*dup_func) (void *), 684 void (*free_func) (void *), 685 void (*clear_free_func) (void *)) 686 { 687 EC_EXTRA_DATA *d; 688 689 if (ex_data == NULL) 690 return 0; 691 692 for (d = *ex_data; d != NULL; d = d->next) { 693 if (d->dup_func == dup_func && d->free_func == free_func && 694 d->clear_free_func == clear_free_func) { 695 ECerror(EC_R_SLOT_FULL); 696 return 0; 697 } 698 } 699 700 if (data == NULL) 701 /* no explicit entry needed */ 702 return 1; 703 704 d = malloc(sizeof *d); 705 if (d == NULL) 706 return 0; 707 708 d->data = data; 709 d->dup_func = dup_func; 710 d->free_func = free_func; 711 d->clear_free_func = clear_free_func; 712 713 d->next = *ex_data; 714 *ex_data = d; 715 716 return 1; 717 } 718 719 /* this has 'package' visibility */ 720 void * 721 EC_EX_DATA_get_data(const EC_EXTRA_DATA *ex_data, 722 void *(*dup_func) (void *), 723 void (*free_func) (void *), 724 void (*clear_free_func) (void *)) 725 { 726 const EC_EXTRA_DATA *d; 727 728 for (d = ex_data; d != NULL; d = d->next) { 729 if (d->dup_func == dup_func && d->free_func == free_func && d->clear_free_func == clear_free_func) 730 return d->data; 731 } 732 733 return NULL; 734 } 735 736 /* this has 'package' visibility */ 737 void 738 EC_EX_DATA_free_data(EC_EXTRA_DATA ** ex_data, 739 void *(*dup_func) (void *), 740 void (*free_func) (void *), 741 void (*clear_free_func) (void *)) 742 { 743 EC_EXTRA_DATA **p; 744 745 if (ex_data == NULL) 746 return; 747 748 for (p = ex_data; *p != NULL; p = &((*p)->next)) { 749 if ((*p)->dup_func == dup_func && 750 (*p)->free_func == free_func && 751 (*p)->clear_free_func == clear_free_func) { 752 EC_EXTRA_DATA *next = (*p)->next; 753 754 (*p)->free_func((*p)->data); 755 free(*p); 756 757 *p = next; 758 return; 759 } 760 } 761 } 762 763 /* this has 'package' visibility */ 764 void 765 EC_EX_DATA_clear_free_data(EC_EXTRA_DATA ** ex_data, 766 void *(*dup_func) (void *), 767 void (*free_func) (void *), 768 void (*clear_free_func) (void *)) 769 { 770 EC_EXTRA_DATA **p; 771 772 if (ex_data == NULL) 773 return; 774 775 for (p = ex_data; *p != NULL; p = &((*p)->next)) { 776 if ((*p)->dup_func == dup_func && 777 (*p)->free_func == free_func && 778 (*p)->clear_free_func == clear_free_func) { 779 EC_EXTRA_DATA *next = (*p)->next; 780 781 (*p)->clear_free_func((*p)->data); 782 free(*p); 783 784 *p = next; 785 return; 786 } 787 } 788 } 789 790 /* this has 'package' visibility */ 791 void 792 EC_EX_DATA_free_all_data(EC_EXTRA_DATA ** ex_data) 793 { 794 EC_EXTRA_DATA *d; 795 796 if (ex_data == NULL) 797 return; 798 799 d = *ex_data; 800 while (d) { 801 EC_EXTRA_DATA *next = d->next; 802 803 d->free_func(d->data); 804 free(d); 805 806 d = next; 807 } 808 *ex_data = NULL; 809 } 810 811 /* this has 'package' visibility */ 812 void 813 EC_EX_DATA_clear_free_all_data(EC_EXTRA_DATA ** ex_data) 814 { 815 EC_EXTRA_DATA *d; 816 817 if (ex_data == NULL) 818 return; 819 820 d = *ex_data; 821 while (d) { 822 EC_EXTRA_DATA *next = d->next; 823 824 d->clear_free_func(d->data); 825 free(d); 826 827 d = next; 828 } 829 *ex_data = NULL; 830 } 831 832 EC_POINT * 833 EC_POINT_new(const EC_GROUP *group) 834 { 835 EC_POINT *ret; 836 837 if (group == NULL) { 838 ECerror(ERR_R_PASSED_NULL_PARAMETER); 839 return NULL; 840 } 841 if (group->meth->point_init == NULL) { 842 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 843 return NULL; 844 } 845 ret = malloc(sizeof *ret); 846 if (ret == NULL) { 847 ECerror(ERR_R_MALLOC_FAILURE); 848 return NULL; 849 } 850 ret->meth = group->meth; 851 852 if (!ret->meth->point_init(ret)) { 853 free(ret); 854 return NULL; 855 } 856 return ret; 857 } 858 859 void 860 EC_POINT_free(EC_POINT *point) 861 { 862 if (point == NULL) 863 return; 864 865 if (point->meth->point_finish != NULL) 866 point->meth->point_finish(point); 867 868 freezero(point, sizeof *point); 869 } 870 871 void 872 EC_POINT_clear_free(EC_POINT *point) 873 { 874 EC_POINT_free(point); 875 } 876 877 int 878 EC_POINT_copy(EC_POINT *dest, const EC_POINT *src) 879 { 880 if (dest->meth->point_copy == NULL) { 881 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 882 return 0; 883 } 884 if (dest->meth != src->meth) { 885 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 886 return 0; 887 } 888 if (dest == src) 889 return 1; 890 return dest->meth->point_copy(dest, src); 891 } 892 893 EC_POINT * 894 EC_POINT_dup(const EC_POINT *a, const EC_GROUP *group) 895 { 896 EC_POINT *t; 897 int r; 898 899 if (a == NULL) 900 return NULL; 901 902 t = EC_POINT_new(group); 903 if (t == NULL) 904 return (NULL); 905 r = EC_POINT_copy(t, a); 906 if (!r) { 907 EC_POINT_free(t); 908 return NULL; 909 } else 910 return t; 911 } 912 913 const EC_METHOD * 914 EC_POINT_method_of(const EC_POINT *point) 915 { 916 return point->meth; 917 } 918 919 int 920 EC_POINT_set_to_infinity(const EC_GROUP *group, EC_POINT *point) 921 { 922 if (group->meth->point_set_to_infinity == NULL) { 923 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 924 return 0; 925 } 926 if (group->meth != point->meth) { 927 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 928 return 0; 929 } 930 return group->meth->point_set_to_infinity(group, point); 931 } 932 933 int 934 EC_POINT_set_Jprojective_coordinates(const EC_GROUP *group, EC_POINT *point, 935 const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx_in) 936 { 937 BN_CTX *ctx; 938 int ret = 0; 939 940 if ((ctx = ctx_in) == NULL) 941 ctx = BN_CTX_new(); 942 if (ctx == NULL) 943 goto err; 944 945 if (group->meth->point_set_Jprojective_coordinates == NULL) { 946 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 947 goto err; 948 } 949 if (group->meth != point->meth) { 950 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 951 goto err; 952 } 953 if (!group->meth->point_set_Jprojective_coordinates(group, point, 954 x, y, z, ctx)) 955 goto err; 956 957 if (EC_POINT_is_on_curve(group, point, ctx) <= 0) { 958 ECerror(EC_R_POINT_IS_NOT_ON_CURVE); 959 goto err; 960 } 961 962 ret = 1; 963 964 err: 965 if (ctx != ctx_in) 966 BN_CTX_free(ctx); 967 968 return ret; 969 } 970 971 int 972 EC_POINT_get_Jprojective_coordinates(const EC_GROUP *group, 973 const EC_POINT *point, BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx_in) 974 { 975 BN_CTX *ctx; 976 int ret = 0; 977 978 if ((ctx = ctx_in) == NULL) 979 ctx = BN_CTX_new(); 980 if (ctx == NULL) 981 goto err; 982 983 if (group->meth->point_get_Jprojective_coordinates == NULL) { 984 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 985 goto err; 986 } 987 if (group->meth != point->meth) { 988 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 989 goto err; 990 } 991 ret = group->meth->point_get_Jprojective_coordinates(group, point, 992 x, y, z, ctx); 993 994 err: 995 if (ctx != ctx_in) 996 BN_CTX_free(ctx); 997 998 return ret; 999 } 1000 1001 int 1002 EC_POINT_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, 1003 const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx) 1004 { 1005 return EC_POINT_set_Jprojective_coordinates(group, point, x, y, z, ctx); 1006 } 1007 1008 int 1009 EC_POINT_get_Jprojective_coordinates_GFp(const EC_GROUP *group, 1010 const EC_POINT *point, BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx) 1011 { 1012 return EC_POINT_get_Jprojective_coordinates(group, point, x, y, z, ctx); 1013 } 1014 1015 int 1016 EC_POINT_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point, 1017 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx_in) 1018 { 1019 BN_CTX *ctx; 1020 int ret = 0; 1021 1022 if ((ctx = ctx_in) == NULL) 1023 ctx = BN_CTX_new(); 1024 if (ctx == NULL) 1025 goto err; 1026 1027 if (group->meth->point_set_affine_coordinates == NULL) { 1028 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1029 goto err; 1030 } 1031 if (group->meth != point->meth) { 1032 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1033 goto err; 1034 } 1035 if (!group->meth->point_set_affine_coordinates(group, point, x, y, ctx)) 1036 goto err; 1037 1038 if (EC_POINT_is_on_curve(group, point, ctx) <= 0) { 1039 ECerror(EC_R_POINT_IS_NOT_ON_CURVE); 1040 goto err; 1041 } 1042 1043 ret = 1; 1044 1045 err: 1046 if (ctx != ctx_in) 1047 BN_CTX_free(ctx); 1048 1049 return ret; 1050 } 1051 1052 int 1053 EC_POINT_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, 1054 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) 1055 { 1056 return EC_POINT_set_affine_coordinates(group, point, x, y, ctx); 1057 } 1058 1059 int 1060 EC_POINT_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point, 1061 BIGNUM *x, BIGNUM *y, BN_CTX *ctx_in) 1062 { 1063 BN_CTX *ctx; 1064 int ret = 0; 1065 1066 if ((ctx = ctx_in) == NULL) 1067 ctx = BN_CTX_new(); 1068 if (ctx == NULL) 1069 goto err; 1070 1071 if (group->meth->point_get_affine_coordinates == NULL) { 1072 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1073 goto err; 1074 } 1075 if (group->meth != point->meth) { 1076 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1077 goto err; 1078 } 1079 ret = group->meth->point_get_affine_coordinates(group, point, x, y, ctx); 1080 1081 err: 1082 if (ctx != ctx_in) 1083 BN_CTX_free(ctx); 1084 1085 return ret; 1086 } 1087 1088 int 1089 EC_POINT_get_affine_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point, 1090 BIGNUM *x, BIGNUM *y, BN_CTX *ctx) 1091 { 1092 return EC_POINT_get_affine_coordinates(group, point, x, y, ctx); 1093 } 1094 1095 int 1096 EC_POINT_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 1097 const EC_POINT *b, BN_CTX *ctx_in) 1098 { 1099 BN_CTX *ctx; 1100 int ret = 0; 1101 1102 if ((ctx = ctx_in) == NULL) 1103 ctx = BN_CTX_new(); 1104 if (ctx == NULL) 1105 goto err; 1106 1107 if (group->meth->add == NULL) { 1108 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1109 goto err; 1110 } 1111 if (group->meth != r->meth || group->meth != a->meth || 1112 group->meth != b->meth) { 1113 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1114 goto err; 1115 } 1116 ret = group->meth->add(group, r, a, b, ctx); 1117 1118 err: 1119 if (ctx != ctx_in) 1120 BN_CTX_free(ctx); 1121 1122 return ret; 1123 } 1124 1125 int 1126 EC_POINT_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 1127 BN_CTX *ctx_in) 1128 { 1129 BN_CTX *ctx; 1130 int ret = 0; 1131 1132 if ((ctx = ctx_in) == NULL) 1133 ctx = BN_CTX_new(); 1134 if (ctx == NULL) 1135 goto err; 1136 1137 if (group->meth->dbl == NULL) { 1138 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1139 goto err; 1140 } 1141 if (group->meth != r->meth || r->meth != a->meth) { 1142 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1143 goto err; 1144 } 1145 ret = group->meth->dbl(group, r, a, ctx); 1146 1147 err: 1148 if (ctx != ctx_in) 1149 BN_CTX_free(ctx); 1150 1151 return ret; 1152 } 1153 1154 int 1155 EC_POINT_invert(const EC_GROUP *group, EC_POINT *a, BN_CTX *ctx_in) 1156 { 1157 BN_CTX *ctx; 1158 int ret = 0; 1159 1160 if ((ctx = ctx_in) == NULL) 1161 ctx = BN_CTX_new(); 1162 if (ctx == NULL) 1163 goto err; 1164 1165 if (group->meth->invert == NULL) { 1166 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1167 goto err; 1168 } 1169 if (group->meth != a->meth) { 1170 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1171 goto err; 1172 } 1173 ret = group->meth->invert(group, a, ctx); 1174 1175 err: 1176 if (ctx != ctx_in) 1177 BN_CTX_free(ctx); 1178 1179 return ret; 1180 } 1181 1182 int 1183 EC_POINT_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) 1184 { 1185 if (group->meth->is_at_infinity == NULL) { 1186 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1187 return 0; 1188 } 1189 if (group->meth != point->meth) { 1190 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1191 return 0; 1192 } 1193 return group->meth->is_at_infinity(group, point); 1194 } 1195 1196 int 1197 EC_POINT_is_on_curve(const EC_GROUP *group, const EC_POINT *point, 1198 BN_CTX *ctx_in) 1199 { 1200 BN_CTX *ctx; 1201 int ret = 0; 1202 1203 if ((ctx = ctx_in) == NULL) 1204 ctx = BN_CTX_new(); 1205 if (ctx == NULL) 1206 goto err; 1207 1208 if (group->meth->is_on_curve == NULL) { 1209 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1210 goto err; 1211 } 1212 if (group->meth != point->meth) { 1213 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1214 goto err; 1215 } 1216 ret = group->meth->is_on_curve(group, point, ctx); 1217 1218 err: 1219 if (ctx != ctx_in) 1220 BN_CTX_free(ctx); 1221 1222 return ret; 1223 } 1224 1225 int 1226 EC_POINT_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, 1227 BN_CTX *ctx_in) 1228 { 1229 BN_CTX *ctx; 1230 int ret = -1; 1231 1232 if ((ctx = ctx_in) == NULL) 1233 ctx = BN_CTX_new(); 1234 if (ctx == NULL) 1235 goto err; 1236 1237 if (group->meth->point_cmp == NULL) { 1238 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1239 goto err; 1240 } 1241 if (group->meth != a->meth || a->meth != b->meth) { 1242 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1243 goto err; 1244 } 1245 ret = group->meth->point_cmp(group, a, b, ctx); 1246 1247 err: 1248 if (ctx != ctx_in) 1249 BN_CTX_free(ctx); 1250 1251 return ret; 1252 } 1253 1254 int 1255 EC_POINT_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx_in) 1256 { 1257 BN_CTX *ctx; 1258 int ret = 0; 1259 1260 if ((ctx = ctx_in) == NULL) 1261 ctx = BN_CTX_new(); 1262 if (ctx == NULL) 1263 goto err; 1264 1265 if (group->meth->make_affine == NULL) { 1266 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1267 goto err; 1268 } 1269 if (group->meth != point->meth) { 1270 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1271 goto err; 1272 } 1273 ret = group->meth->make_affine(group, point, ctx); 1274 1275 err: 1276 if (ctx != ctx_in) 1277 BN_CTX_free(ctx); 1278 1279 return ret; 1280 } 1281 1282 int 1283 EC_POINTs_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], 1284 BN_CTX *ctx_in) 1285 { 1286 BN_CTX *ctx; 1287 size_t i; 1288 int ret = 0; 1289 1290 if ((ctx = ctx_in) == NULL) 1291 ctx = BN_CTX_new(); 1292 if (ctx == NULL) 1293 goto err; 1294 1295 if (group->meth->points_make_affine == NULL) { 1296 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1297 goto err; 1298 } 1299 for (i = 0; i < num; i++) { 1300 if (group->meth != points[i]->meth) { 1301 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1302 goto err; 1303 } 1304 } 1305 ret = group->meth->points_make_affine(group, num, points, ctx); 1306 1307 err: 1308 if (ctx != ctx_in) 1309 BN_CTX_free(ctx); 1310 1311 return ret; 1312 } 1313 1314 int 1315 EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 1316 size_t num, const EC_POINT *points[], const BIGNUM *scalars[], 1317 BN_CTX *ctx_in) 1318 { 1319 BN_CTX *ctx; 1320 int ret = 0; 1321 1322 if ((ctx = ctx_in) == NULL) 1323 ctx = BN_CTX_new(); 1324 if (ctx == NULL) 1325 goto err; 1326 1327 /* Only num == 0 and num == 1 is supported. */ 1328 if (group->meth->mul_generator_ct == NULL || 1329 group->meth->mul_single_ct == NULL || 1330 group->meth->mul_double_nonct == NULL || 1331 num > 1) { 1332 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1333 goto err; 1334 } 1335 1336 if (num == 1 && points != NULL && scalars != NULL) { 1337 /* Either bP or aG + bP, this is sane. */ 1338 ret = EC_POINT_mul(group, r, scalar, points[0], scalars[0], ctx); 1339 } else if (scalar != NULL && points == NULL && scalars == NULL) { 1340 /* aG, this is sane */ 1341 ret = EC_POINT_mul(group, r, scalar, NULL, NULL, ctx); 1342 } else { 1343 /* anything else is an error */ 1344 ECerror(ERR_R_EC_LIB); 1345 goto err; 1346 } 1347 1348 err: 1349 if (ctx != ctx_in) 1350 BN_CTX_free(ctx); 1351 1352 return ret; 1353 } 1354 1355 int 1356 EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar, 1357 const EC_POINT *point, const BIGNUM *p_scalar, BN_CTX *ctx_in) 1358 { 1359 BN_CTX *ctx; 1360 int ret = 0; 1361 1362 if ((ctx = ctx_in) == NULL) 1363 ctx = BN_CTX_new(); 1364 if (ctx == NULL) 1365 goto err; 1366 1367 if (group->meth->mul_generator_ct == NULL || 1368 group->meth->mul_single_ct == NULL || 1369 group->meth->mul_double_nonct == NULL) { 1370 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1371 goto err; 1372 } 1373 1374 if (g_scalar != NULL && point == NULL && p_scalar == NULL) { 1375 /* 1376 * In this case we want to compute g_scalar * GeneratorPoint: 1377 * this codepath is reached most prominently by (ephemeral) key 1378 * generation of EC cryptosystems (i.e. ECDSA keygen and sign 1379 * setup, ECDH keygen/first half), where the scalar is always 1380 * secret. This is why we ignore if BN_FLG_CONSTTIME is actually 1381 * set and we always call the constant time version. 1382 */ 1383 ret = group->meth->mul_generator_ct(group, r, g_scalar, ctx); 1384 } else if (g_scalar == NULL && point != NULL && p_scalar != NULL) { 1385 /* 1386 * In this case we want to compute p_scalar * GenericPoint: 1387 * this codepath is reached most prominently by the second half 1388 * of ECDH, where the secret scalar is multiplied by the peer's 1389 * public point. To protect the secret scalar, we ignore if 1390 * BN_FLG_CONSTTIME is actually set and we always call the 1391 * constant time version. 1392 */ 1393 ret = group->meth->mul_single_ct(group, r, p_scalar, point, ctx); 1394 } else if (g_scalar != NULL && point != NULL && p_scalar != NULL) { 1395 /* 1396 * In this case we want to compute 1397 * g_scalar * GeneratorPoint + p_scalar * GenericPoint: 1398 * this codepath is reached most prominently by ECDSA signature 1399 * verification. So we call the non-ct version. 1400 */ 1401 ret = group->meth->mul_double_nonct(group, r, g_scalar, 1402 p_scalar, point, ctx); 1403 } else { 1404 /* Anything else is an error. */ 1405 ECerror(ERR_R_EC_LIB); 1406 goto err; 1407 } 1408 1409 err: 1410 if (ctx != ctx_in) 1411 BN_CTX_free(ctx); 1412 1413 return ret; 1414 } 1415 1416 int 1417 EC_GROUP_precompute_mult(EC_GROUP *group, BN_CTX *ctx_in) 1418 { 1419 BN_CTX *ctx; 1420 int ret = 0; 1421 1422 if (group->meth->precompute_mult == NULL) 1423 return 1; 1424 1425 if ((ctx = ctx_in) == NULL) 1426 ctx = BN_CTX_new(); 1427 if (ctx == NULL) 1428 goto err; 1429 1430 ret = group->meth->precompute_mult(group, ctx); 1431 1432 err: 1433 if (ctx != ctx_in) 1434 BN_CTX_free(ctx); 1435 1436 return ret; 1437 } 1438 1439 int 1440 EC_GROUP_have_precompute_mult(const EC_GROUP *group) 1441 { 1442 if (group->meth->have_precompute_mult == NULL) 1443 return 0; 1444 1445 return group->meth->have_precompute_mult(group); 1446 } 1447 1448 int 1449 ec_group_simple_order_bits(const EC_GROUP *group) 1450 { 1451 /* XXX change group->order to a pointer? */ 1452 #if 0 1453 if (group->order == NULL) 1454 return 0; 1455 #endif 1456 return BN_num_bits(&group->order); 1457 } 1458 1459 EC_KEY * 1460 ECParameters_dup(EC_KEY *key) 1461 { 1462 const unsigned char *p; 1463 unsigned char *der = NULL; 1464 EC_KEY *dup = NULL; 1465 int len; 1466 1467 if (key == NULL) 1468 return NULL; 1469 1470 if ((len = i2d_ECParameters(key, &der)) <= 0) 1471 return NULL; 1472 1473 p = der; 1474 dup = d2i_ECParameters(NULL, &p, len); 1475 freezero(der, len); 1476 1477 return dup; 1478 } 1479