ec2_smpl.c revision 296465
1/* crypto/ec/ec2_smpl.c */ 2/* ==================================================================== 3 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 4 * 5 * The Elliptic Curve Public-Key Crypto Library (ECC Code) included 6 * herein is developed by SUN MICROSYSTEMS, INC., and is contributed 7 * to the OpenSSL project. 8 * 9 * The ECC Code is licensed pursuant to the OpenSSL open source 10 * license provided below. 11 * 12 * The software is originally written by Sheueling Chang Shantz and 13 * Douglas Stebila of Sun Microsystems Laboratories. 14 * 15 */ 16/* ==================================================================== 17 * Copyright (c) 1998-2003 The OpenSSL Project. All rights reserved. 18 * 19 * Redistribution and use in source and binary forms, with or without 20 * modification, are permitted provided that the following conditions 21 * are met: 22 * 23 * 1. Redistributions of source code must retain the above copyright 24 * notice, this list of conditions and the following disclaimer. 25 * 26 * 2. Redistributions in binary form must reproduce the above copyright 27 * notice, this list of conditions and the following disclaimer in 28 * the documentation and/or other materials provided with the 29 * distribution. 30 * 31 * 3. All advertising materials mentioning features or use of this 32 * software must display the following acknowledgment: 33 * "This product includes software developed by the OpenSSL Project 34 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 35 * 36 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 37 * endorse or promote products derived from this software without 38 * prior written permission. For written permission, please contact 39 * openssl-core@openssl.org. 40 * 41 * 5. Products derived from this software may not be called "OpenSSL" 42 * nor may "OpenSSL" appear in their names without prior written 43 * permission of the OpenSSL Project. 44 * 45 * 6. Redistributions of any form whatsoever must retain the following 46 * acknowledgment: 47 * "This product includes software developed by the OpenSSL Project 48 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 49 * 50 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 51 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 52 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 53 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 54 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 55 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 56 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 57 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 58 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 59 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 60 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 61 * OF THE POSSIBILITY OF SUCH DAMAGE. 62 * ==================================================================== 63 * 64 * This product includes cryptographic software written by Eric Young 65 * (eay@cryptsoft.com). This product includes software written by Tim 66 * Hudson (tjh@cryptsoft.com). 67 * 68 */ 69 70#include <openssl/err.h> 71 72#include "ec_lcl.h" 73 74const EC_METHOD *EC_GF2m_simple_method(void) 75{ 76 static const EC_METHOD ret = { 77 NID_X9_62_characteristic_two_field, 78 ec_GF2m_simple_group_init, 79 ec_GF2m_simple_group_finish, 80 ec_GF2m_simple_group_clear_finish, 81 ec_GF2m_simple_group_copy, 82 ec_GF2m_simple_group_set_curve, 83 ec_GF2m_simple_group_get_curve, 84 ec_GF2m_simple_group_get_degree, 85 ec_GF2m_simple_group_check_discriminant, 86 ec_GF2m_simple_point_init, 87 ec_GF2m_simple_point_finish, 88 ec_GF2m_simple_point_clear_finish, 89 ec_GF2m_simple_point_copy, 90 ec_GF2m_simple_point_set_to_infinity, 91 0 /* set_Jprojective_coordinates_GFp */ , 92 0 /* get_Jprojective_coordinates_GFp */ , 93 ec_GF2m_simple_point_set_affine_coordinates, 94 ec_GF2m_simple_point_get_affine_coordinates, 95 ec_GF2m_simple_set_compressed_coordinates, 96 ec_GF2m_simple_point2oct, 97 ec_GF2m_simple_oct2point, 98 ec_GF2m_simple_add, 99 ec_GF2m_simple_dbl, 100 ec_GF2m_simple_invert, 101 ec_GF2m_simple_is_at_infinity, 102 ec_GF2m_simple_is_on_curve, 103 ec_GF2m_simple_cmp, 104 ec_GF2m_simple_make_affine, 105 ec_GF2m_simple_points_make_affine, 106 107 /* 108 * the following three method functions are defined in ec2_mult.c 109 */ 110 ec_GF2m_simple_mul, 111 ec_GF2m_precompute_mult, 112 ec_GF2m_have_precompute_mult, 113 114 ec_GF2m_simple_field_mul, 115 ec_GF2m_simple_field_sqr, 116 ec_GF2m_simple_field_div, 117 0 /* field_encode */ , 118 0 /* field_decode */ , 119 0 /* field_set_to_one */ 120 }; 121 122 return &ret; 123} 124 125/* 126 * Initialize a GF(2^m)-based EC_GROUP structure. Note that all other members 127 * are handled by EC_GROUP_new. 128 */ 129int ec_GF2m_simple_group_init(EC_GROUP *group) 130{ 131 BN_init(&group->field); 132 BN_init(&group->a); 133 BN_init(&group->b); 134 return 1; 135} 136 137/* 138 * Free a GF(2^m)-based EC_GROUP structure. Note that all other members are 139 * handled by EC_GROUP_free. 140 */ 141void ec_GF2m_simple_group_finish(EC_GROUP *group) 142{ 143 BN_free(&group->field); 144 BN_free(&group->a); 145 BN_free(&group->b); 146} 147 148/* 149 * Clear and free a GF(2^m)-based EC_GROUP structure. Note that all other 150 * members are handled by EC_GROUP_clear_free. 151 */ 152void ec_GF2m_simple_group_clear_finish(EC_GROUP *group) 153{ 154 BN_clear_free(&group->field); 155 BN_clear_free(&group->a); 156 BN_clear_free(&group->b); 157 group->poly[0] = 0; 158 group->poly[1] = 0; 159 group->poly[2] = 0; 160 group->poly[3] = 0; 161 group->poly[4] = 0; 162} 163 164/* 165 * Copy a GF(2^m)-based EC_GROUP structure. Note that all other members are 166 * handled by EC_GROUP_copy. 167 */ 168int ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) 169{ 170 int i; 171 if (!BN_copy(&dest->field, &src->field)) 172 return 0; 173 if (!BN_copy(&dest->a, &src->a)) 174 return 0; 175 if (!BN_copy(&dest->b, &src->b)) 176 return 0; 177 dest->poly[0] = src->poly[0]; 178 dest->poly[1] = src->poly[1]; 179 dest->poly[2] = src->poly[2]; 180 dest->poly[3] = src->poly[3]; 181 dest->poly[4] = src->poly[4]; 182 if (bn_wexpand(&dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) 183 == NULL) 184 return 0; 185 if (bn_wexpand(&dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) 186 == NULL) 187 return 0; 188 for (i = dest->a.top; i < dest->a.dmax; i++) 189 dest->a.d[i] = 0; 190 for (i = dest->b.top; i < dest->b.dmax; i++) 191 dest->b.d[i] = 0; 192 return 1; 193} 194 195/* Set the curve parameters of an EC_GROUP structure. */ 196int ec_GF2m_simple_group_set_curve(EC_GROUP *group, 197 const BIGNUM *p, const BIGNUM *a, 198 const BIGNUM *b, BN_CTX *ctx) 199{ 200 int ret = 0, i; 201 202 /* group->field */ 203 if (!BN_copy(&group->field, p)) 204 goto err; 205 i = BN_GF2m_poly2arr(&group->field, group->poly, 5); 206 if ((i != 5) && (i != 3)) { 207 ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIELD); 208 goto err; 209 } 210 211 /* group->a */ 212 if (!BN_GF2m_mod_arr(&group->a, a, group->poly)) 213 goto err; 214 if (bn_wexpand(&group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2) 215 == NULL) 216 goto err; 217 for (i = group->a.top; i < group->a.dmax; i++) 218 group->a.d[i] = 0; 219 220 /* group->b */ 221 if (!BN_GF2m_mod_arr(&group->b, b, group->poly)) 222 goto err; 223 if (bn_wexpand(&group->b, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2) 224 == NULL) 225 goto err; 226 for (i = group->b.top; i < group->b.dmax; i++) 227 group->b.d[i] = 0; 228 229 ret = 1; 230 err: 231 return ret; 232} 233 234/* 235 * Get the curve parameters of an EC_GROUP structure. If p, a, or b are NULL 236 * then there values will not be set but the method will return with success. 237 */ 238int ec_GF2m_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, 239 BIGNUM *a, BIGNUM *b, BN_CTX *ctx) 240{ 241 int ret = 0; 242 243 if (p != NULL) { 244 if (!BN_copy(p, &group->field)) 245 return 0; 246 } 247 248 if (a != NULL) { 249 if (!BN_copy(a, &group->a)) 250 goto err; 251 } 252 253 if (b != NULL) { 254 if (!BN_copy(b, &group->b)) 255 goto err; 256 } 257 258 ret = 1; 259 260 err: 261 return ret; 262} 263 264/* 265 * Gets the degree of the field. For a curve over GF(2^m) this is the value 266 * m. 267 */ 268int ec_GF2m_simple_group_get_degree(const EC_GROUP *group) 269{ 270 return BN_num_bits(&group->field) - 1; 271} 272 273/* 274 * Checks the discriminant of the curve. y^2 + x*y = x^3 + a*x^2 + b is an 275 * elliptic curve <=> b != 0 (mod p) 276 */ 277int ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group, 278 BN_CTX *ctx) 279{ 280 int ret = 0; 281 BIGNUM *b; 282 BN_CTX *new_ctx = NULL; 283 284 if (ctx == NULL) { 285 ctx = new_ctx = BN_CTX_new(); 286 if (ctx == NULL) { 287 ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT, 288 ERR_R_MALLOC_FAILURE); 289 goto err; 290 } 291 } 292 BN_CTX_start(ctx); 293 b = BN_CTX_get(ctx); 294 if (b == NULL) 295 goto err; 296 297 if (!BN_GF2m_mod_arr(b, &group->b, group->poly)) 298 goto err; 299 300 /* 301 * check the discriminant: y^2 + x*y = x^3 + a*x^2 + b is an elliptic 302 * curve <=> b != 0 (mod p) 303 */ 304 if (BN_is_zero(b)) 305 goto err; 306 307 ret = 1; 308 309 err: 310 if (ctx != NULL) 311 BN_CTX_end(ctx); 312 if (new_ctx != NULL) 313 BN_CTX_free(new_ctx); 314 return ret; 315} 316 317/* Initializes an EC_POINT. */ 318int ec_GF2m_simple_point_init(EC_POINT *point) 319{ 320 BN_init(&point->X); 321 BN_init(&point->Y); 322 BN_init(&point->Z); 323 return 1; 324} 325 326/* Frees an EC_POINT. */ 327void ec_GF2m_simple_point_finish(EC_POINT *point) 328{ 329 BN_free(&point->X); 330 BN_free(&point->Y); 331 BN_free(&point->Z); 332} 333 334/* Clears and frees an EC_POINT. */ 335void ec_GF2m_simple_point_clear_finish(EC_POINT *point) 336{ 337 BN_clear_free(&point->X); 338 BN_clear_free(&point->Y); 339 BN_clear_free(&point->Z); 340 point->Z_is_one = 0; 341} 342 343/* 344 * Copy the contents of one EC_POINT into another. Assumes dest is 345 * initialized. 346 */ 347int ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src) 348{ 349 if (!BN_copy(&dest->X, &src->X)) 350 return 0; 351 if (!BN_copy(&dest->Y, &src->Y)) 352 return 0; 353 if (!BN_copy(&dest->Z, &src->Z)) 354 return 0; 355 dest->Z_is_one = src->Z_is_one; 356 357 return 1; 358} 359 360/* 361 * Set an EC_POINT to the point at infinity. A point at infinity is 362 * represented by having Z=0. 363 */ 364int ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group, 365 EC_POINT *point) 366{ 367 point->Z_is_one = 0; 368 BN_zero(&point->Z); 369 return 1; 370} 371 372/* 373 * Set the coordinates of an EC_POINT using affine coordinates. Note that 374 * the simple implementation only uses affine coordinates. 375 */ 376int ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group, 377 EC_POINT *point, 378 const BIGNUM *x, 379 const BIGNUM *y, BN_CTX *ctx) 380{ 381 int ret = 0; 382 if (x == NULL || y == NULL) { 383 ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES, 384 ERR_R_PASSED_NULL_PARAMETER); 385 return 0; 386 } 387 388 if (!BN_copy(&point->X, x)) 389 goto err; 390 BN_set_negative(&point->X, 0); 391 if (!BN_copy(&point->Y, y)) 392 goto err; 393 BN_set_negative(&point->Y, 0); 394 if (!BN_copy(&point->Z, BN_value_one())) 395 goto err; 396 BN_set_negative(&point->Z, 0); 397 point->Z_is_one = 1; 398 ret = 1; 399 400 err: 401 return ret; 402} 403 404/* 405 * Gets the affine coordinates of an EC_POINT. Note that the simple 406 * implementation only uses affine coordinates. 407 */ 408int ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group, 409 const EC_POINT *point, 410 BIGNUM *x, BIGNUM *y, 411 BN_CTX *ctx) 412{ 413 int ret = 0; 414 415 if (EC_POINT_is_at_infinity(group, point)) { 416 ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, 417 EC_R_POINT_AT_INFINITY); 418 return 0; 419 } 420 421 if (BN_cmp(&point->Z, BN_value_one())) { 422 ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, 423 ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 424 return 0; 425 } 426 if (x != NULL) { 427 if (!BN_copy(x, &point->X)) 428 goto err; 429 BN_set_negative(x, 0); 430 } 431 if (y != NULL) { 432 if (!BN_copy(y, &point->Y)) 433 goto err; 434 BN_set_negative(y, 0); 435 } 436 ret = 1; 437 438 err: 439 return ret; 440} 441 442/* Include patented algorithms. */ 443#include "ec2_smpt.c" 444 445/* 446 * Converts an EC_POINT to an octet string. If buf is NULL, the encoded 447 * length will be returned. If the length len of buf is smaller than required 448 * an error will be returned. The point compression section of this function 449 * is patented by Certicom Corp. under US Patent 6,141,420. Point 450 * compression is disabled by default and can be enabled by defining the 451 * preprocessor macro OPENSSL_EC_BIN_PT_COMP at Configure-time. 452 */ 453size_t ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, 454 point_conversion_form_t form, 455 unsigned char *buf, size_t len, BN_CTX *ctx) 456{ 457 size_t ret; 458 BN_CTX *new_ctx = NULL; 459 int used_ctx = 0; 460 BIGNUM *x, *y, *yxi; 461 size_t field_len, i, skip; 462 463#ifndef OPENSSL_EC_BIN_PT_COMP 464 if ((form == POINT_CONVERSION_COMPRESSED) 465 || (form == POINT_CONVERSION_HYBRID)) { 466 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_DISABLED); 467 goto err; 468 } 469#endif 470 471 if ((form != POINT_CONVERSION_COMPRESSED) 472 && (form != POINT_CONVERSION_UNCOMPRESSED) 473 && (form != POINT_CONVERSION_HYBRID)) { 474 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_INVALID_FORM); 475 goto err; 476 } 477 478 if (EC_POINT_is_at_infinity(group, point)) { 479 /* encodes to a single 0 octet */ 480 if (buf != NULL) { 481 if (len < 1) { 482 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 483 return 0; 484 } 485 buf[0] = 0; 486 } 487 return 1; 488 } 489 490 /* ret := required output buffer length */ 491 field_len = (EC_GROUP_get_degree(group) + 7) / 8; 492 ret = 493 (form == 494 POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 495 496 /* if 'buf' is NULL, just return required length */ 497 if (buf != NULL) { 498 if (len < ret) { 499 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 500 goto err; 501 } 502 503 if (ctx == NULL) { 504 ctx = new_ctx = BN_CTX_new(); 505 if (ctx == NULL) 506 return 0; 507 } 508 509 BN_CTX_start(ctx); 510 used_ctx = 1; 511 x = BN_CTX_get(ctx); 512 y = BN_CTX_get(ctx); 513 yxi = BN_CTX_get(ctx); 514 if (yxi == NULL) 515 goto err; 516 517 if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx)) 518 goto err; 519 520 buf[0] = form; 521#ifdef OPENSSL_EC_BIN_PT_COMP 522 if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x)) { 523 if (!group->meth->field_div(group, yxi, y, x, ctx)) 524 goto err; 525 if (BN_is_odd(yxi)) 526 buf[0]++; 527 } 528#endif 529 530 i = 1; 531 532 skip = field_len - BN_num_bytes(x); 533 if (skip > field_len) { 534 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 535 goto err; 536 } 537 while (skip > 0) { 538 buf[i++] = 0; 539 skip--; 540 } 541 skip = BN_bn2bin(x, buf + i); 542 i += skip; 543 if (i != 1 + field_len) { 544 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 545 goto err; 546 } 547 548 if (form == POINT_CONVERSION_UNCOMPRESSED 549 || form == POINT_CONVERSION_HYBRID) { 550 skip = field_len - BN_num_bytes(y); 551 if (skip > field_len) { 552 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 553 goto err; 554 } 555 while (skip > 0) { 556 buf[i++] = 0; 557 skip--; 558 } 559 skip = BN_bn2bin(y, buf + i); 560 i += skip; 561 } 562 563 if (i != ret) { 564 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 565 goto err; 566 } 567 } 568 569 if (used_ctx) 570 BN_CTX_end(ctx); 571 if (new_ctx != NULL) 572 BN_CTX_free(new_ctx); 573 return ret; 574 575 err: 576 if (used_ctx) 577 BN_CTX_end(ctx); 578 if (new_ctx != NULL) 579 BN_CTX_free(new_ctx); 580 return 0; 581} 582 583/* 584 * Converts an octet string representation to an EC_POINT. Note that the 585 * simple implementation only uses affine coordinates. 586 */ 587int ec_GF2m_simple_oct2point(const EC_GROUP *group, EC_POINT *point, 588 const unsigned char *buf, size_t len, 589 BN_CTX *ctx) 590{ 591 point_conversion_form_t form; 592 int y_bit; 593 BN_CTX *new_ctx = NULL; 594 BIGNUM *x, *y, *yxi; 595 size_t field_len, enc_len; 596 int ret = 0; 597 598 if (len == 0) { 599 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL); 600 return 0; 601 } 602 form = buf[0]; 603 y_bit = form & 1; 604 form = form & ~1U; 605 if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) 606 && (form != POINT_CONVERSION_UNCOMPRESSED) 607 && (form != POINT_CONVERSION_HYBRID)) { 608 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 609 return 0; 610 } 611 if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) { 612 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 613 return 0; 614 } 615 616 if (form == 0) { 617 if (len != 1) { 618 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 619 return 0; 620 } 621 622 return EC_POINT_set_to_infinity(group, point); 623 } 624 625 field_len = (EC_GROUP_get_degree(group) + 7) / 8; 626 enc_len = 627 (form == 628 POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 629 630 if (len != enc_len) { 631 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 632 return 0; 633 } 634 635 if (ctx == NULL) { 636 ctx = new_ctx = BN_CTX_new(); 637 if (ctx == NULL) 638 return 0; 639 } 640 641 BN_CTX_start(ctx); 642 x = BN_CTX_get(ctx); 643 y = BN_CTX_get(ctx); 644 yxi = BN_CTX_get(ctx); 645 if (yxi == NULL) 646 goto err; 647 648 if (!BN_bin2bn(buf + 1, field_len, x)) 649 goto err; 650 if (BN_ucmp(x, &group->field) >= 0) { 651 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 652 goto err; 653 } 654 655 if (form == POINT_CONVERSION_COMPRESSED) { 656 if (!EC_POINT_set_compressed_coordinates_GF2m 657 (group, point, x, y_bit, ctx)) 658 goto err; 659 } else { 660 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) 661 goto err; 662 if (BN_ucmp(y, &group->field) >= 0) { 663 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 664 goto err; 665 } 666 if (form == POINT_CONVERSION_HYBRID) { 667 if (!group->meth->field_div(group, yxi, y, x, ctx)) 668 goto err; 669 if (y_bit != BN_is_odd(yxi)) { 670 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 671 goto err; 672 } 673 } 674 675 if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx)) 676 goto err; 677 } 678 679 /* test required by X9.62 */ 680 if (EC_POINT_is_on_curve(group, point, ctx) <= 0) { 681 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE); 682 goto err; 683 } 684 685 ret = 1; 686 687 err: 688 BN_CTX_end(ctx); 689 if (new_ctx != NULL) 690 BN_CTX_free(new_ctx); 691 return ret; 692} 693 694/* 695 * Computes a + b and stores the result in r. r could be a or b, a could be 696 * b. Uses algorithm A.10.2 of IEEE P1363. 697 */ 698int ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 699 const EC_POINT *b, BN_CTX *ctx) 700{ 701 BN_CTX *new_ctx = NULL; 702 BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t; 703 int ret = 0; 704 705 if (EC_POINT_is_at_infinity(group, a)) { 706 if (!EC_POINT_copy(r, b)) 707 return 0; 708 return 1; 709 } 710 711 if (EC_POINT_is_at_infinity(group, b)) { 712 if (!EC_POINT_copy(r, a)) 713 return 0; 714 return 1; 715 } 716 717 if (ctx == NULL) { 718 ctx = new_ctx = BN_CTX_new(); 719 if (ctx == NULL) 720 return 0; 721 } 722 723 BN_CTX_start(ctx); 724 x0 = BN_CTX_get(ctx); 725 y0 = BN_CTX_get(ctx); 726 x1 = BN_CTX_get(ctx); 727 y1 = BN_CTX_get(ctx); 728 x2 = BN_CTX_get(ctx); 729 y2 = BN_CTX_get(ctx); 730 s = BN_CTX_get(ctx); 731 t = BN_CTX_get(ctx); 732 if (t == NULL) 733 goto err; 734 735 if (a->Z_is_one) { 736 if (!BN_copy(x0, &a->X)) 737 goto err; 738 if (!BN_copy(y0, &a->Y)) 739 goto err; 740 } else { 741 if (!EC_POINT_get_affine_coordinates_GF2m(group, a, x0, y0, ctx)) 742 goto err; 743 } 744 if (b->Z_is_one) { 745 if (!BN_copy(x1, &b->X)) 746 goto err; 747 if (!BN_copy(y1, &b->Y)) 748 goto err; 749 } else { 750 if (!EC_POINT_get_affine_coordinates_GF2m(group, b, x1, y1, ctx)) 751 goto err; 752 } 753 754 if (BN_GF2m_cmp(x0, x1)) { 755 if (!BN_GF2m_add(t, x0, x1)) 756 goto err; 757 if (!BN_GF2m_add(s, y0, y1)) 758 goto err; 759 if (!group->meth->field_div(group, s, s, t, ctx)) 760 goto err; 761 if (!group->meth->field_sqr(group, x2, s, ctx)) 762 goto err; 763 if (!BN_GF2m_add(x2, x2, &group->a)) 764 goto err; 765 if (!BN_GF2m_add(x2, x2, s)) 766 goto err; 767 if (!BN_GF2m_add(x2, x2, t)) 768 goto err; 769 } else { 770 if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) { 771 if (!EC_POINT_set_to_infinity(group, r)) 772 goto err; 773 ret = 1; 774 goto err; 775 } 776 if (!group->meth->field_div(group, s, y1, x1, ctx)) 777 goto err; 778 if (!BN_GF2m_add(s, s, x1)) 779 goto err; 780 781 if (!group->meth->field_sqr(group, x2, s, ctx)) 782 goto err; 783 if (!BN_GF2m_add(x2, x2, s)) 784 goto err; 785 if (!BN_GF2m_add(x2, x2, &group->a)) 786 goto err; 787 } 788 789 if (!BN_GF2m_add(y2, x1, x2)) 790 goto err; 791 if (!group->meth->field_mul(group, y2, y2, s, ctx)) 792 goto err; 793 if (!BN_GF2m_add(y2, y2, x2)) 794 goto err; 795 if (!BN_GF2m_add(y2, y2, y1)) 796 goto err; 797 798 if (!EC_POINT_set_affine_coordinates_GF2m(group, r, x2, y2, ctx)) 799 goto err; 800 801 ret = 1; 802 803 err: 804 BN_CTX_end(ctx); 805 if (new_ctx != NULL) 806 BN_CTX_free(new_ctx); 807 return ret; 808} 809 810/* 811 * Computes 2 * a and stores the result in r. r could be a. Uses algorithm 812 * A.10.2 of IEEE P1363. 813 */ 814int ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 815 BN_CTX *ctx) 816{ 817 return ec_GF2m_simple_add(group, r, a, a, ctx); 818} 819 820int ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 821{ 822 if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) 823 /* point is its own inverse */ 824 return 1; 825 826 if (!EC_POINT_make_affine(group, point, ctx)) 827 return 0; 828 return BN_GF2m_add(&point->Y, &point->X, &point->Y); 829} 830 831/* Indicates whether the given point is the point at infinity. */ 832int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group, 833 const EC_POINT *point) 834{ 835 return BN_is_zero(&point->Z); 836} 837 838/*- 839 * Determines whether the given EC_POINT is an actual point on the curve defined 840 * in the EC_GROUP. A point is valid if it satisfies the Weierstrass equation: 841 * y^2 + x*y = x^3 + a*x^2 + b. 842 */ 843int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, 844 BN_CTX *ctx) 845{ 846 int ret = -1; 847 BN_CTX *new_ctx = NULL; 848 BIGNUM *lh, *y2; 849 int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 850 const BIGNUM *, BN_CTX *); 851 int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 852 853 if (EC_POINT_is_at_infinity(group, point)) 854 return 1; 855 856 field_mul = group->meth->field_mul; 857 field_sqr = group->meth->field_sqr; 858 859 /* only support affine coordinates */ 860 if (!point->Z_is_one) 861 return -1; 862 863 if (ctx == NULL) { 864 ctx = new_ctx = BN_CTX_new(); 865 if (ctx == NULL) 866 return -1; 867 } 868 869 BN_CTX_start(ctx); 870 y2 = BN_CTX_get(ctx); 871 lh = BN_CTX_get(ctx); 872 if (lh == NULL) 873 goto err; 874 875 /*- 876 * We have a curve defined by a Weierstrass equation 877 * y^2 + x*y = x^3 + a*x^2 + b. 878 * <=> x^3 + a*x^2 + x*y + b + y^2 = 0 879 * <=> ((x + a) * x + y ) * x + b + y^2 = 0 880 */ 881 if (!BN_GF2m_add(lh, &point->X, &group->a)) 882 goto err; 883 if (!field_mul(group, lh, lh, &point->X, ctx)) 884 goto err; 885 if (!BN_GF2m_add(lh, lh, &point->Y)) 886 goto err; 887 if (!field_mul(group, lh, lh, &point->X, ctx)) 888 goto err; 889 if (!BN_GF2m_add(lh, lh, &group->b)) 890 goto err; 891 if (!field_sqr(group, y2, &point->Y, ctx)) 892 goto err; 893 if (!BN_GF2m_add(lh, lh, y2)) 894 goto err; 895 ret = BN_is_zero(lh); 896 err: 897 if (ctx) 898 BN_CTX_end(ctx); 899 if (new_ctx) 900 BN_CTX_free(new_ctx); 901 return ret; 902} 903 904/*- 905 * Indicates whether two points are equal. 906 * Return values: 907 * -1 error 908 * 0 equal (in affine coordinates) 909 * 1 not equal 910 */ 911int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a, 912 const EC_POINT *b, BN_CTX *ctx) 913{ 914 BIGNUM *aX, *aY, *bX, *bY; 915 BN_CTX *new_ctx = NULL; 916 int ret = -1; 917 918 if (EC_POINT_is_at_infinity(group, a)) { 919 return EC_POINT_is_at_infinity(group, b) ? 0 : 1; 920 } 921 922 if (EC_POINT_is_at_infinity(group, b)) 923 return 1; 924 925 if (a->Z_is_one && b->Z_is_one) { 926 return ((BN_cmp(&a->X, &b->X) == 0) 927 && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; 928 } 929 930 if (ctx == NULL) { 931 ctx = new_ctx = BN_CTX_new(); 932 if (ctx == NULL) 933 return -1; 934 } 935 936 BN_CTX_start(ctx); 937 aX = BN_CTX_get(ctx); 938 aY = BN_CTX_get(ctx); 939 bX = BN_CTX_get(ctx); 940 bY = BN_CTX_get(ctx); 941 if (bY == NULL) 942 goto err; 943 944 if (!EC_POINT_get_affine_coordinates_GF2m(group, a, aX, aY, ctx)) 945 goto err; 946 if (!EC_POINT_get_affine_coordinates_GF2m(group, b, bX, bY, ctx)) 947 goto err; 948 ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1; 949 950 err: 951 if (ctx) 952 BN_CTX_end(ctx); 953 if (new_ctx) 954 BN_CTX_free(new_ctx); 955 return ret; 956} 957 958/* Forces the given EC_POINT to internally use affine coordinates. */ 959int ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point, 960 BN_CTX *ctx) 961{ 962 BN_CTX *new_ctx = NULL; 963 BIGNUM *x, *y; 964 int ret = 0; 965 966 if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) 967 return 1; 968 969 if (ctx == NULL) { 970 ctx = new_ctx = BN_CTX_new(); 971 if (ctx == NULL) 972 return 0; 973 } 974 975 BN_CTX_start(ctx); 976 x = BN_CTX_get(ctx); 977 y = BN_CTX_get(ctx); 978 if (y == NULL) 979 goto err; 980 981 if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx)) 982 goto err; 983 if (!BN_copy(&point->X, x)) 984 goto err; 985 if (!BN_copy(&point->Y, y)) 986 goto err; 987 if (!BN_one(&point->Z)) 988 goto err; 989 990 ret = 1; 991 992 err: 993 if (ctx) 994 BN_CTX_end(ctx); 995 if (new_ctx) 996 BN_CTX_free(new_ctx); 997 return ret; 998} 999 1000/* 1001 * Forces each of the EC_POINTs in the given array to use affine coordinates. 1002 */ 1003int ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num, 1004 EC_POINT *points[], BN_CTX *ctx) 1005{ 1006 size_t i; 1007 1008 for (i = 0; i < num; i++) { 1009 if (!group->meth->make_affine(group, points[i], ctx)) 1010 return 0; 1011 } 1012 1013 return 1; 1014} 1015 1016/* Wrapper to simple binary polynomial field multiplication implementation. */ 1017int ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r, 1018 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 1019{ 1020 return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx); 1021} 1022 1023/* Wrapper to simple binary polynomial field squaring implementation. */ 1024int ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, 1025 const BIGNUM *a, BN_CTX *ctx) 1026{ 1027 return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx); 1028} 1029 1030/* Wrapper to simple binary polynomial field division implementation. */ 1031int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r, 1032 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 1033{ 1034 return BN_GF2m_mod_div(r, a, b, &group->field, ctx); 1035} 1036