1 /* $OpenBSD: ec_lib.c,v 1.39 2021/04/20 17:29:21 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_lcl.h" 72 #include "ec_lcl.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 == 0) { 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 = 0; 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) 121 return; 122 123 if (group->meth->group_finish != 0) 124 group->meth->group_finish(group); 125 126 EC_EX_DATA_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 free(group->seed); 133 134 free(group); 135 } 136 137 138 void 139 EC_GROUP_clear_free(EC_GROUP * group) 140 { 141 if (!group) 142 return; 143 144 if (group->meth->group_clear_finish != 0) 145 group->meth->group_clear_finish(group); 146 else if (group->meth->group_finish != 0) 147 group->meth->group_finish(group); 148 149 EC_EX_DATA_clear_free_all_data(&group->extra_data); 150 151 EC_POINT_clear_free(group->generator); 152 BN_clear_free(&group->order); 153 BN_clear_free(&group->cofactor); 154 155 freezero(group->seed, group->seed_len); 156 freezero(group, sizeof *group); 157 } 158 159 160 int 161 EC_GROUP_copy(EC_GROUP * dest, const EC_GROUP * src) 162 { 163 EC_EXTRA_DATA *d; 164 165 if (dest->meth->group_copy == 0) { 166 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 167 return 0; 168 } 169 if (dest->meth != src->meth) { 170 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 171 return 0; 172 } 173 if (dest == src) 174 return 1; 175 176 EC_EX_DATA_free_all_data(&dest->extra_data); 177 178 for (d = src->extra_data; d != NULL; d = d->next) { 179 void *t = d->dup_func(d->data); 180 181 if (t == NULL) 182 return 0; 183 if (!EC_EX_DATA_set_data(&dest->extra_data, t, d->dup_func, 184 d->free_func, d->clear_free_func)) 185 return 0; 186 } 187 188 if (src->generator != NULL) { 189 if (dest->generator == NULL) { 190 dest->generator = EC_POINT_new(dest); 191 if (dest->generator == NULL) 192 return 0; 193 } 194 if (!EC_POINT_copy(dest->generator, src->generator)) 195 return 0; 196 } else { 197 /* src->generator == NULL */ 198 EC_POINT_clear_free(dest->generator); 199 dest->generator = NULL; 200 } 201 202 if (!BN_copy(&dest->order, &src->order)) 203 return 0; 204 if (!BN_copy(&dest->cofactor, &src->cofactor)) 205 return 0; 206 207 dest->curve_name = src->curve_name; 208 dest->asn1_flag = src->asn1_flag; 209 dest->asn1_form = src->asn1_form; 210 211 if (src->seed) { 212 free(dest->seed); 213 dest->seed = malloc(src->seed_len); 214 if (dest->seed == NULL) 215 return 0; 216 memcpy(dest->seed, src->seed, src->seed_len); 217 dest->seed_len = src->seed_len; 218 } else { 219 free(dest->seed); 220 dest->seed = NULL; 221 dest->seed_len = 0; 222 } 223 224 225 return dest->meth->group_copy(dest, src); 226 } 227 228 229 EC_GROUP * 230 EC_GROUP_dup(const EC_GROUP * a) 231 { 232 EC_GROUP *t = NULL; 233 234 if ((a != NULL) && ((t = EC_GROUP_new(a->meth)) != NULL) && 235 (!EC_GROUP_copy(t, a))) { 236 EC_GROUP_free(t); 237 t = NULL; 238 } 239 return t; 240 } 241 242 243 const EC_METHOD * 244 EC_GROUP_method_of(const EC_GROUP *group) 245 { 246 return group->meth; 247 } 248 249 250 int 251 EC_METHOD_get_field_type(const EC_METHOD *meth) 252 { 253 return meth->field_type; 254 } 255 256 /* 257 * Try computing the cofactor from generator order n and field cardinality q. 258 * This works for all curves of cryptographic interest. 259 * 260 * Hasse's theorem: | h * n - (q + 1) | <= 2 * sqrt(q) 261 * 262 * So: h_min = (q + 1 - 2*sqrt(q)) / n and h_max = (q + 1 + 2*sqrt(q)) / n and 263 * therefore h_max - h_min = 4*sqrt(q) / n. So if n > 4*sqrt(q) holds, there is 264 * only one possible value for h: 265 * 266 * h = \lfloor (h_min + h_max)/2 \rceil = \lfloor (q + 1)/n \rceil 267 * 268 * Otherwise, zero cofactor and return success. 269 */ 270 static int 271 ec_guess_cofactor(EC_GROUP *group) 272 { 273 BN_CTX *ctx = NULL; 274 BIGNUM *q = NULL; 275 int ret = 0; 276 277 /* 278 * If the cofactor is too large, we cannot guess it and default to zero. 279 * The RHS of below is a strict overestimate of log(4 * sqrt(q)). 280 */ 281 if (BN_num_bits(&group->order) <= 282 (BN_num_bits(&group->field) + 1) / 2 + 3) { 283 BN_zero(&group->cofactor); 284 return 1; 285 } 286 287 if ((ctx = BN_CTX_new()) == NULL) 288 goto err; 289 290 BN_CTX_start(ctx); 291 if ((q = BN_CTX_get(ctx)) == NULL) 292 goto err; 293 294 /* Set q = 2**m for binary fields; q = p otherwise. */ 295 if (group->meth->field_type == NID_X9_62_characteristic_two_field) { 296 BN_zero(q); 297 if (!BN_set_bit(q, BN_num_bits(&group->field) - 1)) 298 goto err; 299 } else { 300 if (!BN_copy(q, &group->field)) 301 goto err; 302 } 303 304 /* 305 * Compute 306 * h = \lfloor (q + 1)/n \rceil = \lfloor (q + 1 + n/2) / n \rfloor. 307 */ 308 309 /* h = n/2 */ 310 if (!BN_rshift1(&group->cofactor, &group->order)) 311 goto err; 312 /* h = 1 + n/2 */ 313 if (!BN_add(&group->cofactor, &group->cofactor, BN_value_one())) 314 goto err; 315 /* h = q + 1 + n/2 */ 316 if (!BN_add(&group->cofactor, &group->cofactor, q)) 317 goto err; 318 /* h = (q + 1 + n/2) / n */ 319 if (!BN_div_ct(&group->cofactor, NULL, &group->cofactor, &group->order, 320 ctx)) 321 goto err; 322 323 ret = 1; 324 err: 325 BN_CTX_end(ctx); 326 BN_CTX_free(ctx); 327 BN_zero(&group->cofactor); 328 return ret; 329 } 330 331 int 332 EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, 333 const BIGNUM *order, const BIGNUM *cofactor) 334 { 335 if (generator == NULL) { 336 ECerror(ERR_R_PASSED_NULL_PARAMETER); 337 return 0; 338 } 339 340 /* Require group->field >= 1. */ 341 if (BN_is_zero(&group->field) || BN_is_negative(&group->field)) { 342 ECerror(EC_R_INVALID_FIELD); 343 return 0; 344 } 345 346 /* 347 * Require order >= 1 and enforce an upper bound of at most one bit more 348 * than the field cardinality due to Hasse's theorem. 349 */ 350 if (order == NULL || BN_is_zero(order) || BN_is_negative(order) || 351 BN_num_bits(order) > BN_num_bits(&group->field) + 1) { 352 ECerror(EC_R_INVALID_GROUP_ORDER); 353 return 0; 354 } 355 356 /* 357 * Unfortunately, the cofactor is an optional field in many standards. 358 * Internally, the library uses a 0 cofactor as a marker for "unknown 359 * cofactor". So accept cofactor == NULL or cofactor >= 0. 360 */ 361 if (cofactor != NULL && BN_is_negative(cofactor)) { 362 ECerror(EC_R_UNKNOWN_COFACTOR); 363 return 0; 364 } 365 366 if (group->generator == NULL) { 367 group->generator = EC_POINT_new(group); 368 if (group->generator == NULL) 369 return 0; 370 } 371 if (!EC_POINT_copy(group->generator, generator)) 372 return 0; 373 374 if (!BN_copy(&group->order, order)) 375 return 0; 376 377 /* Either take the provided positive cofactor, or try to compute it. */ 378 if (cofactor != NULL && !BN_is_zero(cofactor)) { 379 if (!BN_copy(&group->cofactor, cofactor)) 380 return 0; 381 } else if (!ec_guess_cofactor(group)) 382 return 0; 383 384 return 1; 385 } 386 387 388 const EC_POINT * 389 EC_GROUP_get0_generator(const EC_GROUP *group) 390 { 391 return group->generator; 392 } 393 394 395 int 396 EC_GROUP_get_order(const EC_GROUP *group, BIGNUM *order, BN_CTX *ctx) 397 { 398 if (!BN_copy(order, &group->order)) 399 return 0; 400 401 return !BN_is_zero(order); 402 } 403 404 405 int 406 EC_GROUP_get_cofactor(const EC_GROUP *group, BIGNUM *cofactor, BN_CTX *ctx) 407 { 408 if (!BN_copy(cofactor, &group->cofactor)) 409 return 0; 410 411 return !BN_is_zero(&group->cofactor); 412 } 413 414 415 void 416 EC_GROUP_set_curve_name(EC_GROUP * group, int nid) 417 { 418 group->curve_name = nid; 419 } 420 421 422 int 423 EC_GROUP_get_curve_name(const EC_GROUP * group) 424 { 425 return group->curve_name; 426 } 427 428 429 void 430 EC_GROUP_set_asn1_flag(EC_GROUP * group, int flag) 431 { 432 group->asn1_flag = flag; 433 } 434 435 436 int 437 EC_GROUP_get_asn1_flag(const EC_GROUP * group) 438 { 439 return group->asn1_flag; 440 } 441 442 443 void 444 EC_GROUP_set_point_conversion_form(EC_GROUP * group, 445 point_conversion_form_t form) 446 { 447 group->asn1_form = form; 448 } 449 450 451 point_conversion_form_t 452 EC_GROUP_get_point_conversion_form(const EC_GROUP * group) 453 { 454 return group->asn1_form; 455 } 456 457 458 size_t 459 EC_GROUP_set_seed(EC_GROUP * group, const unsigned char *p, size_t len) 460 { 461 if (group->seed) { 462 free(group->seed); 463 group->seed = NULL; 464 group->seed_len = 0; 465 } 466 if (!len || !p) 467 return 1; 468 469 if ((group->seed = malloc(len)) == NULL) 470 return 0; 471 memcpy(group->seed, p, len); 472 group->seed_len = len; 473 474 return len; 475 } 476 477 478 unsigned char * 479 EC_GROUP_get0_seed(const EC_GROUP * group) 480 { 481 return group->seed; 482 } 483 484 485 size_t 486 EC_GROUP_get_seed_len(const EC_GROUP * group) 487 { 488 return group->seed_len; 489 } 490 491 int 492 EC_GROUP_set_curve(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, 493 const BIGNUM *b, BN_CTX *ctx) 494 { 495 if (group->meth->group_set_curve == NULL) { 496 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 497 return 0; 498 } 499 return group->meth->group_set_curve(group, p, a, b, ctx); 500 } 501 502 int 503 EC_GROUP_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, 504 BN_CTX *ctx) 505 { 506 if (group->meth->group_get_curve == NULL) { 507 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 508 return 0; 509 } 510 return group->meth->group_get_curve(group, p, a, b, ctx); 511 } 512 513 int 514 EC_GROUP_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, 515 const BIGNUM *b, BN_CTX *ctx) 516 { 517 return EC_GROUP_set_curve(group, p, a, b, ctx); 518 } 519 520 int 521 EC_GROUP_get_curve_GFp(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, 522 BN_CTX *ctx) 523 { 524 return EC_GROUP_get_curve(group, p, a, b, ctx); 525 } 526 527 #ifndef OPENSSL_NO_EC2M 528 int 529 EC_GROUP_set_curve_GF2m(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, 530 const BIGNUM *b, BN_CTX *ctx) 531 { 532 return EC_GROUP_set_curve(group, p, a, b, ctx); 533 } 534 535 int 536 EC_GROUP_get_curve_GF2m(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, 537 BIGNUM *b, BN_CTX *ctx) 538 { 539 return EC_GROUP_get_curve(group, p, a, b, ctx); 540 } 541 #endif 542 543 int 544 EC_GROUP_get_degree(const EC_GROUP * group) 545 { 546 if (group->meth->group_get_degree == 0) { 547 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 548 return 0; 549 } 550 return group->meth->group_get_degree(group); 551 } 552 553 554 int 555 EC_GROUP_check_discriminant(const EC_GROUP * group, BN_CTX * ctx) 556 { 557 if (group->meth->group_check_discriminant == 0) { 558 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 559 return 0; 560 } 561 return group->meth->group_check_discriminant(group, ctx); 562 } 563 564 565 int 566 EC_GROUP_cmp(const EC_GROUP * a, const EC_GROUP * b, BN_CTX * ctx) 567 { 568 int r = 0; 569 BIGNUM *a1, *a2, *a3, *b1, *b2, *b3; 570 BN_CTX *ctx_new = NULL; 571 572 /* compare the field types */ 573 if (EC_METHOD_get_field_type(EC_GROUP_method_of(a)) != 574 EC_METHOD_get_field_type(EC_GROUP_method_of(b))) 575 return 1; 576 /* compare the curve name (if present in both) */ 577 if (EC_GROUP_get_curve_name(a) && EC_GROUP_get_curve_name(b) && 578 EC_GROUP_get_curve_name(a) != EC_GROUP_get_curve_name(b)) 579 return 1; 580 581 if (!ctx) 582 ctx_new = ctx = BN_CTX_new(); 583 if (!ctx) 584 return -1; 585 586 BN_CTX_start(ctx); 587 if ((a1 = BN_CTX_get(ctx)) == NULL) 588 goto err; 589 if ((a2 = BN_CTX_get(ctx)) == NULL) 590 goto err; 591 if ((a3 = BN_CTX_get(ctx)) == NULL) 592 goto err; 593 if ((b1 = BN_CTX_get(ctx)) == NULL) 594 goto err; 595 if ((b2 = BN_CTX_get(ctx)) == NULL) 596 goto err; 597 if ((b3 = BN_CTX_get(ctx)) == NULL) 598 goto err; 599 600 /* 601 * XXX This approach assumes that the external representation of 602 * curves over the same field type is the same. 603 */ 604 if (!a->meth->group_get_curve(a, a1, a2, a3, ctx) || 605 !b->meth->group_get_curve(b, b1, b2, b3, ctx)) 606 r = 1; 607 608 if (r || BN_cmp(a1, b1) || BN_cmp(a2, b2) || BN_cmp(a3, b3)) 609 r = 1; 610 611 /* XXX EC_POINT_cmp() assumes that the methods are equal */ 612 if (r || EC_POINT_cmp(a, EC_GROUP_get0_generator(a), 613 EC_GROUP_get0_generator(b), ctx)) 614 r = 1; 615 616 if (!r) { 617 /* compare the order and cofactor */ 618 if (!EC_GROUP_get_order(a, a1, ctx) || 619 !EC_GROUP_get_order(b, b1, ctx) || 620 !EC_GROUP_get_cofactor(a, a2, ctx) || 621 !EC_GROUP_get_cofactor(b, b2, ctx)) 622 goto err; 623 if (BN_cmp(a1, b1) || BN_cmp(a2, b2)) 624 r = 1; 625 } 626 BN_CTX_end(ctx); 627 if (ctx_new) 628 BN_CTX_free(ctx); 629 630 return r; 631 632 err: 633 BN_CTX_end(ctx); 634 if (ctx_new) 635 BN_CTX_free(ctx); 636 return -1; 637 } 638 639 /* 640 * Coordinate blinding for EC_POINT. 641 * 642 * The underlying EC_METHOD can optionally implement this function: 643 * underlying implementations should return 0 on errors, or 1 on success. 644 * 645 * This wrapper returns 1 in case the underlying EC_METHOD does not support 646 * coordinate blinding. 647 */ 648 int 649 ec_point_blind_coordinates(const EC_GROUP *group, EC_POINT *p, BN_CTX *ctx) 650 { 651 if (group->meth->blind_coordinates == NULL) 652 return 1; 653 654 return group->meth->blind_coordinates(group, p, ctx); 655 } 656 657 /* this has 'package' visibility */ 658 int 659 EC_EX_DATA_set_data(EC_EXTRA_DATA ** ex_data, void *data, 660 void *(*dup_func) (void *), 661 void (*free_func) (void *), 662 void (*clear_free_func) (void *)) 663 { 664 EC_EXTRA_DATA *d; 665 666 if (ex_data == NULL) 667 return 0; 668 669 for (d = *ex_data; d != NULL; d = d->next) { 670 if (d->dup_func == dup_func && d->free_func == free_func && 671 d->clear_free_func == clear_free_func) { 672 ECerror(EC_R_SLOT_FULL); 673 return 0; 674 } 675 } 676 677 if (data == NULL) 678 /* no explicit entry needed */ 679 return 1; 680 681 d = malloc(sizeof *d); 682 if (d == NULL) 683 return 0; 684 685 d->data = data; 686 d->dup_func = dup_func; 687 d->free_func = free_func; 688 d->clear_free_func = clear_free_func; 689 690 d->next = *ex_data; 691 *ex_data = d; 692 693 return 1; 694 } 695 696 /* this has 'package' visibility */ 697 void * 698 EC_EX_DATA_get_data(const EC_EXTRA_DATA * ex_data, 699 void *(*dup_func) (void *), 700 void (*free_func) (void *), 701 void (*clear_free_func) (void *)) 702 { 703 const EC_EXTRA_DATA *d; 704 705 for (d = ex_data; d != NULL; d = d->next) { 706 if (d->dup_func == dup_func && d->free_func == free_func && d->clear_free_func == clear_free_func) 707 return d->data; 708 } 709 710 return NULL; 711 } 712 713 /* this has 'package' visibility */ 714 void 715 EC_EX_DATA_free_data(EC_EXTRA_DATA ** ex_data, 716 void *(*dup_func) (void *), 717 void (*free_func) (void *), 718 void (*clear_free_func) (void *)) 719 { 720 EC_EXTRA_DATA **p; 721 722 if (ex_data == NULL) 723 return; 724 725 for (p = ex_data; *p != NULL; p = &((*p)->next)) { 726 if ((*p)->dup_func == dup_func && 727 (*p)->free_func == free_func && 728 (*p)->clear_free_func == clear_free_func) { 729 EC_EXTRA_DATA *next = (*p)->next; 730 731 (*p)->free_func((*p)->data); 732 free(*p); 733 734 *p = next; 735 return; 736 } 737 } 738 } 739 740 /* this has 'package' visibility */ 741 void 742 EC_EX_DATA_clear_free_data(EC_EXTRA_DATA ** ex_data, 743 void *(*dup_func) (void *), 744 void (*free_func) (void *), 745 void (*clear_free_func) (void *)) 746 { 747 EC_EXTRA_DATA **p; 748 749 if (ex_data == NULL) 750 return; 751 752 for (p = ex_data; *p != NULL; p = &((*p)->next)) { 753 if ((*p)->dup_func == dup_func && 754 (*p)->free_func == free_func && 755 (*p)->clear_free_func == clear_free_func) { 756 EC_EXTRA_DATA *next = (*p)->next; 757 758 (*p)->clear_free_func((*p)->data); 759 free(*p); 760 761 *p = next; 762 return; 763 } 764 } 765 } 766 767 /* this has 'package' visibility */ 768 void 769 EC_EX_DATA_free_all_data(EC_EXTRA_DATA ** ex_data) 770 { 771 EC_EXTRA_DATA *d; 772 773 if (ex_data == NULL) 774 return; 775 776 d = *ex_data; 777 while (d) { 778 EC_EXTRA_DATA *next = d->next; 779 780 d->free_func(d->data); 781 free(d); 782 783 d = next; 784 } 785 *ex_data = NULL; 786 } 787 788 /* this has 'package' visibility */ 789 void 790 EC_EX_DATA_clear_free_all_data(EC_EXTRA_DATA ** ex_data) 791 { 792 EC_EXTRA_DATA *d; 793 794 if (ex_data == NULL) 795 return; 796 797 d = *ex_data; 798 while (d) { 799 EC_EXTRA_DATA *next = d->next; 800 801 d->clear_free_func(d->data); 802 free(d); 803 804 d = next; 805 } 806 *ex_data = NULL; 807 } 808 809 810 /* functions for EC_POINT objects */ 811 812 EC_POINT * 813 EC_POINT_new(const EC_GROUP * group) 814 { 815 EC_POINT *ret; 816 817 if (group == NULL) { 818 ECerror(ERR_R_PASSED_NULL_PARAMETER); 819 return NULL; 820 } 821 if (group->meth->point_init == 0) { 822 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 823 return NULL; 824 } 825 ret = malloc(sizeof *ret); 826 if (ret == NULL) { 827 ECerror(ERR_R_MALLOC_FAILURE); 828 return NULL; 829 } 830 ret->meth = group->meth; 831 832 if (!ret->meth->point_init(ret)) { 833 free(ret); 834 return NULL; 835 } 836 return ret; 837 } 838 839 840 void 841 EC_POINT_free(EC_POINT * point) 842 { 843 if (!point) 844 return; 845 846 if (point->meth->point_finish != 0) 847 point->meth->point_finish(point); 848 free(point); 849 } 850 851 852 void 853 EC_POINT_clear_free(EC_POINT * point) 854 { 855 if (!point) 856 return; 857 858 if (point->meth->point_clear_finish != 0) 859 point->meth->point_clear_finish(point); 860 else if (point->meth->point_finish != 0) 861 point->meth->point_finish(point); 862 freezero(point, sizeof *point); 863 } 864 865 866 int 867 EC_POINT_copy(EC_POINT * dest, const EC_POINT * src) 868 { 869 if (dest->meth->point_copy == 0) { 870 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 871 return 0; 872 } 873 if (dest->meth != src->meth) { 874 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 875 return 0; 876 } 877 if (dest == src) 878 return 1; 879 return dest->meth->point_copy(dest, src); 880 } 881 882 883 EC_POINT * 884 EC_POINT_dup(const EC_POINT * a, const EC_GROUP * group) 885 { 886 EC_POINT *t; 887 int r; 888 889 if (a == NULL) 890 return NULL; 891 892 t = EC_POINT_new(group); 893 if (t == NULL) 894 return (NULL); 895 r = EC_POINT_copy(t, a); 896 if (!r) { 897 EC_POINT_free(t); 898 return NULL; 899 } else 900 return t; 901 } 902 903 904 const EC_METHOD * 905 EC_POINT_method_of(const EC_POINT * point) 906 { 907 return point->meth; 908 } 909 910 911 int 912 EC_POINT_set_to_infinity(const EC_GROUP * group, EC_POINT * point) 913 { 914 if (group->meth->point_set_to_infinity == 0) { 915 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 916 return 0; 917 } 918 if (group->meth != point->meth) { 919 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 920 return 0; 921 } 922 return group->meth->point_set_to_infinity(group, point); 923 } 924 925 int 926 EC_POINT_set_Jprojective_coordinates(const EC_GROUP *group, EC_POINT *point, 927 const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx) 928 { 929 if (group->meth->point_set_Jprojective_coordinates == NULL) { 930 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 931 return 0; 932 } 933 if (group->meth != point->meth) { 934 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 935 return 0; 936 } 937 return group->meth->point_set_Jprojective_coordinates(group, point, 938 x, y, z, ctx); 939 } 940 941 int 942 EC_POINT_get_Jprojective_coordinates(const EC_GROUP *group, 943 const EC_POINT *point, BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx) 944 { 945 if (group->meth->point_get_Jprojective_coordinates == NULL) { 946 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 947 return 0; 948 } 949 if (group->meth != point->meth) { 950 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 951 return 0; 952 } 953 return group->meth->point_get_Jprojective_coordinates(group, point, 954 x, y, z, ctx); 955 } 956 957 int 958 EC_POINT_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, 959 const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx) 960 { 961 return EC_POINT_set_Jprojective_coordinates(group, point, x, y, z, ctx); 962 } 963 964 int 965 EC_POINT_get_Jprojective_coordinates_GFp(const EC_GROUP *group, 966 const EC_POINT *point, BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx) 967 { 968 return EC_POINT_get_Jprojective_coordinates(group, point, x, y, z, ctx); 969 } 970 971 int 972 EC_POINT_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point, 973 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) 974 { 975 if (group->meth->point_set_affine_coordinates == NULL) { 976 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 977 return 0; 978 } 979 if (group->meth != point->meth) { 980 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 981 return 0; 982 } 983 if (!group->meth->point_set_affine_coordinates(group, point, x, y, ctx)) 984 return 0; 985 if (EC_POINT_is_on_curve(group, point, ctx) <= 0) { 986 ECerror(EC_R_POINT_IS_NOT_ON_CURVE); 987 return 0; 988 } 989 return 1; 990 } 991 992 int 993 EC_POINT_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, 994 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) 995 { 996 return EC_POINT_set_affine_coordinates(group, point, x, y, ctx); 997 } 998 999 #ifndef OPENSSL_NO_EC2M 1000 int 1001 EC_POINT_set_affine_coordinates_GF2m(const EC_GROUP *group, EC_POINT *point, 1002 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) 1003 { 1004 return EC_POINT_set_affine_coordinates(group, point, x, y, ctx); 1005 } 1006 #endif 1007 1008 int 1009 EC_POINT_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point, 1010 BIGNUM *x, BIGNUM *y, BN_CTX *ctx) 1011 { 1012 if (group->meth->point_get_affine_coordinates == NULL) { 1013 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1014 return 0; 1015 } 1016 if (group->meth != point->meth) { 1017 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1018 return 0; 1019 } 1020 return group->meth->point_get_affine_coordinates(group, point, x, y, ctx); 1021 } 1022 1023 int 1024 EC_POINT_get_affine_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point, 1025 BIGNUM *x, BIGNUM *y, BN_CTX *ctx) 1026 { 1027 return EC_POINT_get_affine_coordinates(group, point, x, y, ctx); 1028 } 1029 1030 #ifndef OPENSSL_NO_EC2M 1031 int 1032 EC_POINT_get_affine_coordinates_GF2m(const EC_GROUP *group, const EC_POINT *point, 1033 BIGNUM *x, BIGNUM *y, BN_CTX *ctx) 1034 { 1035 return EC_POINT_get_affine_coordinates(group, point, x, y, ctx); 1036 } 1037 #endif 1038 1039 int 1040 EC_POINT_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 1041 const EC_POINT *b, BN_CTX *ctx) 1042 { 1043 if (group->meth->add == 0) { 1044 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1045 return 0; 1046 } 1047 if ((group->meth != r->meth) || (r->meth != a->meth) || (a->meth != b->meth)) { 1048 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1049 return 0; 1050 } 1051 return group->meth->add(group, r, a, b, ctx); 1052 } 1053 1054 1055 int 1056 EC_POINT_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx) 1057 { 1058 if (group->meth->dbl == 0) { 1059 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1060 return 0; 1061 } 1062 if ((group->meth != r->meth) || (r->meth != a->meth)) { 1063 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1064 return 0; 1065 } 1066 return group->meth->dbl(group, r, a, ctx); 1067 } 1068 1069 1070 int 1071 EC_POINT_invert(const EC_GROUP *group, EC_POINT *a, BN_CTX *ctx) 1072 { 1073 if (group->meth->invert == 0) { 1074 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1075 return 0; 1076 } 1077 if (group->meth != a->meth) { 1078 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1079 return 0; 1080 } 1081 return group->meth->invert(group, a, ctx); 1082 } 1083 1084 1085 int 1086 EC_POINT_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) 1087 { 1088 if (group->meth->is_at_infinity == 0) { 1089 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1090 return 0; 1091 } 1092 if (group->meth != point->meth) { 1093 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1094 return 0; 1095 } 1096 return group->meth->is_at_infinity(group, point); 1097 } 1098 1099 1100 int 1101 EC_POINT_is_on_curve(const EC_GROUP * group, const EC_POINT * point, BN_CTX * ctx) 1102 { 1103 if (group->meth->is_on_curve == 0) { 1104 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1105 return 0; 1106 } 1107 if (group->meth != point->meth) { 1108 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1109 return 0; 1110 } 1111 return group->meth->is_on_curve(group, point, ctx); 1112 } 1113 1114 1115 int 1116 EC_POINT_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, 1117 BN_CTX * ctx) 1118 { 1119 if (group->meth->point_cmp == 0) { 1120 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1121 return -1; 1122 } 1123 if ((group->meth != a->meth) || (a->meth != b->meth)) { 1124 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1125 return -1; 1126 } 1127 return group->meth->point_cmp(group, a, b, ctx); 1128 } 1129 1130 1131 int 1132 EC_POINT_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 1133 { 1134 if (group->meth->make_affine == 0) { 1135 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1136 return 0; 1137 } 1138 if (group->meth != point->meth) { 1139 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1140 return 0; 1141 } 1142 return group->meth->make_affine(group, point, ctx); 1143 } 1144 1145 1146 int 1147 EC_POINTs_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], 1148 BN_CTX *ctx) 1149 { 1150 size_t i; 1151 1152 if (group->meth->points_make_affine == 0) { 1153 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1154 return 0; 1155 } 1156 for (i = 0; i < num; i++) { 1157 if (group->meth != points[i]->meth) { 1158 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 1159 return 0; 1160 } 1161 } 1162 return group->meth->points_make_affine(group, num, points, ctx); 1163 } 1164 1165 1166 /* Functions for point multiplication */ 1167 int 1168 EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 1169 size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx) 1170 { 1171 /* 1172 * The function pointers must be set, and only support num == 0 and 1173 * num == 1. 1174 */ 1175 if (group->meth->mul_generator_ct == NULL || 1176 group->meth->mul_single_ct == NULL || 1177 group->meth->mul_double_nonct == NULL || 1178 num > 1) { 1179 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1180 return 0; 1181 } 1182 1183 /* Either bP or aG + bP, this is sane. */ 1184 if (num == 1 && points != NULL && scalars != NULL) 1185 return EC_POINT_mul(group, r, scalar, points[0], scalars[0], 1186 ctx); 1187 1188 /* aG, this is sane */ 1189 if (scalar != NULL && points == NULL && scalars == NULL) 1190 return EC_POINT_mul(group, r, scalar, NULL, NULL, ctx); 1191 1192 /* anything else is an error */ 1193 ECerror(ERR_R_EC_LIB); 1194 return 0; 1195 } 1196 1197 int 1198 EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar, 1199 const EC_POINT *point, const BIGNUM *p_scalar, BN_CTX *ctx) 1200 { 1201 if (group->meth->mul_generator_ct == NULL || 1202 group->meth->mul_single_ct == NULL || 1203 group->meth->mul_double_nonct == NULL) { 1204 ECerror(ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 1205 return 0; 1206 } 1207 if (g_scalar != NULL && point == NULL && p_scalar == NULL) { 1208 /* 1209 * In this case we want to compute g_scalar * GeneratorPoint: 1210 * this codepath is reached most prominently by (ephemeral) key 1211 * generation of EC cryptosystems (i.e. ECDSA keygen and sign 1212 * setup, ECDH keygen/first half), where the scalar is always 1213 * secret. This is why we ignore if BN_FLG_CONSTTIME is actually 1214 * set and we always call the constant time version. 1215 */ 1216 return group->meth->mul_generator_ct(group, r, g_scalar, ctx); 1217 } 1218 if (g_scalar == NULL && point != NULL && p_scalar != NULL) { 1219 /* In this case we want to compute p_scalar * GenericPoint: 1220 * this codepath is reached most prominently by the second half 1221 * of ECDH, where the secret scalar is multiplied by the peer's 1222 * public point. To protect the secret scalar, we ignore if 1223 * BN_FLG_CONSTTIME is actually set and we always call the 1224 * constant time version. 1225 */ 1226 return group->meth->mul_single_ct(group, r, p_scalar, point, 1227 ctx); 1228 } 1229 if (g_scalar != NULL && point != NULL && p_scalar != NULL) { 1230 /* 1231 * In this case we want to compute 1232 * g_scalar * GeneratorPoint + p_scalar * GenericPoint: 1233 * this codepath is reached most prominently by ECDSA signature 1234 * verification. So we call the non-ct version. 1235 */ 1236 return group->meth->mul_double_nonct(group, r, g_scalar, 1237 p_scalar, point, ctx); 1238 } 1239 1240 /* Anything else is an error. */ 1241 ECerror(ERR_R_EC_LIB); 1242 return 0; 1243 } 1244 1245 int 1246 EC_GROUP_precompute_mult(EC_GROUP * group, BN_CTX * ctx) 1247 { 1248 if (group->meth->precompute_mult != 0) 1249 return group->meth->precompute_mult(group, ctx); 1250 else 1251 return 1; /* nothing to do, so report success */ 1252 } 1253 1254 int 1255 EC_GROUP_have_precompute_mult(const EC_GROUP * group) 1256 { 1257 if (group->meth->have_precompute_mult != 0) 1258 return group->meth->have_precompute_mult(group); 1259 else 1260 return 0; /* cannot tell whether precomputation has 1261 * been performed */ 1262 } 1263 1264 EC_KEY * 1265 ECParameters_dup(EC_KEY *key) 1266 { 1267 unsigned char *p = NULL; 1268 EC_KEY *k = NULL; 1269 int len; 1270 1271 if (key == NULL) 1272 return (NULL); 1273 1274 if ((len = i2d_ECParameters(key, &p)) > 0) 1275 k = d2i_ECParameters(NULL, (const unsigned char **)&p, len); 1276 1277 return (k); 1278 } 1279