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