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