1160814Ssimon/* crypto/ec/ec2_smpl.c */ 2160814Ssimon/* ==================================================================== 3160814Ssimon * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 4160814Ssimon * 5160814Ssimon * The Elliptic Curve Public-Key Crypto Library (ECC Code) included 6160814Ssimon * herein is developed by SUN MICROSYSTEMS, INC., and is contributed 7160814Ssimon * to the OpenSSL project. 8160814Ssimon * 9160814Ssimon * The ECC Code is licensed pursuant to the OpenSSL open source 10160814Ssimon * license provided below. 11160814Ssimon * 12160814Ssimon * The software is originally written by Sheueling Chang Shantz and 13160814Ssimon * Douglas Stebila of Sun Microsystems Laboratories. 14160814Ssimon * 15160814Ssimon */ 16160814Ssimon/* ==================================================================== 17238405Sjkim * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. 18160814Ssimon * 19160814Ssimon * Redistribution and use in source and binary forms, with or without 20160814Ssimon * modification, are permitted provided that the following conditions 21160814Ssimon * are met: 22160814Ssimon * 23160814Ssimon * 1. Redistributions of source code must retain the above copyright 24280304Sjkim * notice, this list of conditions and the following disclaimer. 25160814Ssimon * 26160814Ssimon * 2. Redistributions in binary form must reproduce the above copyright 27160814Ssimon * notice, this list of conditions and the following disclaimer in 28160814Ssimon * the documentation and/or other materials provided with the 29160814Ssimon * distribution. 30160814Ssimon * 31160814Ssimon * 3. All advertising materials mentioning features or use of this 32160814Ssimon * software must display the following acknowledgment: 33160814Ssimon * "This product includes software developed by the OpenSSL Project 34160814Ssimon * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 35160814Ssimon * 36160814Ssimon * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 37160814Ssimon * endorse or promote products derived from this software without 38160814Ssimon * prior written permission. For written permission, please contact 39160814Ssimon * openssl-core@openssl.org. 40160814Ssimon * 41160814Ssimon * 5. Products derived from this software may not be called "OpenSSL" 42160814Ssimon * nor may "OpenSSL" appear in their names without prior written 43160814Ssimon * permission of the OpenSSL Project. 44160814Ssimon * 45160814Ssimon * 6. Redistributions of any form whatsoever must retain the following 46160814Ssimon * acknowledgment: 47160814Ssimon * "This product includes software developed by the OpenSSL Project 48160814Ssimon * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 49160814Ssimon * 50160814Ssimon * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 51160814Ssimon * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 52160814Ssimon * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 53160814Ssimon * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 54160814Ssimon * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 55160814Ssimon * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 56160814Ssimon * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 57160814Ssimon * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 58160814Ssimon * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 59160814Ssimon * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 60160814Ssimon * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 61160814Ssimon * OF THE POSSIBILITY OF SUCH DAMAGE. 62160814Ssimon * ==================================================================== 63160814Ssimon * 64160814Ssimon * This product includes cryptographic software written by Eric Young 65160814Ssimon * (eay@cryptsoft.com). This product includes software written by Tim 66160814Ssimon * Hudson (tjh@cryptsoft.com). 67160814Ssimon * 68160814Ssimon */ 69160814Ssimon 70160814Ssimon#include <openssl/err.h> 71160814Ssimon 72160814Ssimon#include "ec_lcl.h" 73160814Ssimon 74238405Sjkim#ifndef OPENSSL_NO_EC2M 75160814Ssimon 76280304Sjkim# ifdef OPENSSL_FIPS 77280304Sjkim# include <openssl/fips.h> 78280304Sjkim# endif 79238405Sjkim 80160814Ssimonconst EC_METHOD *EC_GF2m_simple_method(void) 81280304Sjkim{ 82280304Sjkim static const EC_METHOD ret = { 83280304Sjkim EC_FLAGS_DEFAULT_OCT, 84280304Sjkim NID_X9_62_characteristic_two_field, 85280304Sjkim ec_GF2m_simple_group_init, 86280304Sjkim ec_GF2m_simple_group_finish, 87280304Sjkim ec_GF2m_simple_group_clear_finish, 88280304Sjkim ec_GF2m_simple_group_copy, 89280304Sjkim ec_GF2m_simple_group_set_curve, 90280304Sjkim ec_GF2m_simple_group_get_curve, 91280304Sjkim ec_GF2m_simple_group_get_degree, 92280304Sjkim ec_GF2m_simple_group_check_discriminant, 93280304Sjkim ec_GF2m_simple_point_init, 94280304Sjkim ec_GF2m_simple_point_finish, 95280304Sjkim ec_GF2m_simple_point_clear_finish, 96280304Sjkim ec_GF2m_simple_point_copy, 97280304Sjkim ec_GF2m_simple_point_set_to_infinity, 98280304Sjkim 0 /* set_Jprojective_coordinates_GFp */ , 99280304Sjkim 0 /* get_Jprojective_coordinates_GFp */ , 100280304Sjkim ec_GF2m_simple_point_set_affine_coordinates, 101280304Sjkim ec_GF2m_simple_point_get_affine_coordinates, 102280304Sjkim 0, 0, 0, 103280304Sjkim ec_GF2m_simple_add, 104280304Sjkim ec_GF2m_simple_dbl, 105280304Sjkim ec_GF2m_simple_invert, 106280304Sjkim ec_GF2m_simple_is_at_infinity, 107280304Sjkim ec_GF2m_simple_is_on_curve, 108280304Sjkim ec_GF2m_simple_cmp, 109280304Sjkim ec_GF2m_simple_make_affine, 110280304Sjkim ec_GF2m_simple_points_make_affine, 111160814Ssimon 112280304Sjkim /* 113280304Sjkim * the following three method functions are defined in ec2_mult.c 114280304Sjkim */ 115280304Sjkim ec_GF2m_simple_mul, 116280304Sjkim ec_GF2m_precompute_mult, 117280304Sjkim ec_GF2m_have_precompute_mult, 118160814Ssimon 119280304Sjkim ec_GF2m_simple_field_mul, 120280304Sjkim ec_GF2m_simple_field_sqr, 121280304Sjkim ec_GF2m_simple_field_div, 122280304Sjkim 0 /* field_encode */ , 123280304Sjkim 0 /* field_decode */ , 124280304Sjkim 0 /* field_set_to_one */ 125280304Sjkim }; 126160814Ssimon 127280304Sjkim# ifdef OPENSSL_FIPS 128280304Sjkim if (FIPS_mode()) 129280304Sjkim return fips_ec_gf2m_simple_method(); 130280304Sjkim# endif 131273149Sjkim 132280304Sjkim return &ret; 133280304Sjkim} 134160814Ssimon 135280304Sjkim/* 136280304Sjkim * Initialize a GF(2^m)-based EC_GROUP structure. Note that all other members 137280304Sjkim * are handled by EC_GROUP_new. 138160814Ssimon */ 139160814Ssimonint ec_GF2m_simple_group_init(EC_GROUP *group) 140280304Sjkim{ 141280304Sjkim BN_init(&group->field); 142280304Sjkim BN_init(&group->a); 143280304Sjkim BN_init(&group->b); 144280304Sjkim return 1; 145280304Sjkim} 146160814Ssimon 147280304Sjkim/* 148280304Sjkim * Free a GF(2^m)-based EC_GROUP structure. Note that all other members are 149280304Sjkim * handled by EC_GROUP_free. 150160814Ssimon */ 151160814Ssimonvoid ec_GF2m_simple_group_finish(EC_GROUP *group) 152280304Sjkim{ 153280304Sjkim BN_free(&group->field); 154280304Sjkim BN_free(&group->a); 155280304Sjkim BN_free(&group->b); 156280304Sjkim} 157160814Ssimon 158280304Sjkim/* 159280304Sjkim * Clear and free a GF(2^m)-based EC_GROUP structure. Note that all other 160280304Sjkim * members are handled by EC_GROUP_clear_free. 161160814Ssimon */ 162160814Ssimonvoid ec_GF2m_simple_group_clear_finish(EC_GROUP *group) 163280304Sjkim{ 164280304Sjkim BN_clear_free(&group->field); 165280304Sjkim BN_clear_free(&group->a); 166280304Sjkim BN_clear_free(&group->b); 167280304Sjkim group->poly[0] = 0; 168280304Sjkim group->poly[1] = 0; 169280304Sjkim group->poly[2] = 0; 170280304Sjkim group->poly[3] = 0; 171280304Sjkim group->poly[4] = 0; 172280304Sjkim group->poly[5] = -1; 173280304Sjkim} 174160814Ssimon 175280304Sjkim/* 176280304Sjkim * Copy a GF(2^m)-based EC_GROUP structure. Note that all other members are 177280304Sjkim * handled by EC_GROUP_copy. 178160814Ssimon */ 179160814Ssimonint ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) 180280304Sjkim{ 181280304Sjkim int i; 182280304Sjkim if (!BN_copy(&dest->field, &src->field)) 183280304Sjkim return 0; 184280304Sjkim if (!BN_copy(&dest->a, &src->a)) 185280304Sjkim return 0; 186280304Sjkim if (!BN_copy(&dest->b, &src->b)) 187280304Sjkim return 0; 188280304Sjkim dest->poly[0] = src->poly[0]; 189280304Sjkim dest->poly[1] = src->poly[1]; 190280304Sjkim dest->poly[2] = src->poly[2]; 191280304Sjkim dest->poly[3] = src->poly[3]; 192280304Sjkim dest->poly[4] = src->poly[4]; 193280304Sjkim dest->poly[5] = src->poly[5]; 194280304Sjkim if (bn_wexpand(&dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) 195280304Sjkim == NULL) 196280304Sjkim return 0; 197280304Sjkim if (bn_wexpand(&dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) 198280304Sjkim == NULL) 199280304Sjkim return 0; 200280304Sjkim for (i = dest->a.top; i < dest->a.dmax; i++) 201280304Sjkim dest->a.d[i] = 0; 202280304Sjkim for (i = dest->b.top; i < dest->b.dmax; i++) 203280304Sjkim dest->b.d[i] = 0; 204280304Sjkim return 1; 205280304Sjkim} 206160814Ssimon 207160814Ssimon/* Set the curve parameters of an EC_GROUP structure. */ 208160814Ssimonint ec_GF2m_simple_group_set_curve(EC_GROUP *group, 209280304Sjkim const BIGNUM *p, const BIGNUM *a, 210280304Sjkim const BIGNUM *b, BN_CTX *ctx) 211280304Sjkim{ 212280304Sjkim int ret = 0, i; 213160814Ssimon 214280304Sjkim /* group->field */ 215280304Sjkim if (!BN_copy(&group->field, p)) 216280304Sjkim goto err; 217280304Sjkim i = BN_GF2m_poly2arr(&group->field, group->poly, 6) - 1; 218280304Sjkim if ((i != 5) && (i != 3)) { 219280304Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIELD); 220280304Sjkim goto err; 221280304Sjkim } 222160814Ssimon 223280304Sjkim /* group->a */ 224280304Sjkim if (!BN_GF2m_mod_arr(&group->a, a, group->poly)) 225280304Sjkim goto err; 226280304Sjkim if (bn_wexpand(&group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2) 227280304Sjkim == NULL) 228280304Sjkim goto err; 229280304Sjkim for (i = group->a.top; i < group->a.dmax; i++) 230280304Sjkim group->a.d[i] = 0; 231160814Ssimon 232280304Sjkim /* group->b */ 233280304Sjkim if (!BN_GF2m_mod_arr(&group->b, b, group->poly)) 234280304Sjkim goto err; 235280304Sjkim if (bn_wexpand(&group->b, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2) 236280304Sjkim == NULL) 237280304Sjkim goto err; 238280304Sjkim for (i = group->b.top; i < group->b.dmax; i++) 239280304Sjkim group->b.d[i] = 0; 240160814Ssimon 241280304Sjkim ret = 1; 242280304Sjkim err: 243280304Sjkim return ret; 244280304Sjkim} 245280304Sjkim 246280304Sjkim/* 247280304Sjkim * Get the curve parameters of an EC_GROUP structure. If p, a, or b are NULL 248280304Sjkim * then there values will not be set but the method will return with success. 249160814Ssimon */ 250280304Sjkimint ec_GF2m_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, 251280304Sjkim BIGNUM *a, BIGNUM *b, BN_CTX *ctx) 252280304Sjkim{ 253280304Sjkim int ret = 0; 254160814Ssimon 255280304Sjkim if (p != NULL) { 256280304Sjkim if (!BN_copy(p, &group->field)) 257280304Sjkim return 0; 258280304Sjkim } 259160814Ssimon 260280304Sjkim if (a != NULL) { 261280304Sjkim if (!BN_copy(a, &group->a)) 262280304Sjkim goto err; 263280304Sjkim } 264160814Ssimon 265280304Sjkim if (b != NULL) { 266280304Sjkim if (!BN_copy(b, &group->b)) 267280304Sjkim goto err; 268280304Sjkim } 269160814Ssimon 270280304Sjkim ret = 1; 271160814Ssimon 272280304Sjkim err: 273280304Sjkim return ret; 274280304Sjkim} 275160814Ssimon 276280304Sjkim/* 277280304Sjkim * Gets the degree of the field. For a curve over GF(2^m) this is the value 278280304Sjkim * m. 279160814Ssimon */ 280280304Sjkimint ec_GF2m_simple_group_get_degree(const EC_GROUP *group) 281280304Sjkim{ 282280304Sjkim return BN_num_bits(&group->field) - 1; 283280304Sjkim} 284160814Ssimon 285280304Sjkim/* 286280304Sjkim * Checks the discriminant of the curve. y^2 + x*y = x^3 + a*x^2 + b is an 287280304Sjkim * elliptic curve <=> b != 0 (mod p) 288280304Sjkim */ 289280304Sjkimint ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group, 290280304Sjkim BN_CTX *ctx) 291280304Sjkim{ 292280304Sjkim int ret = 0; 293280304Sjkim BIGNUM *b; 294280304Sjkim BN_CTX *new_ctx = NULL; 295160814Ssimon 296280304Sjkim if (ctx == NULL) { 297280304Sjkim ctx = new_ctx = BN_CTX_new(); 298280304Sjkim if (ctx == NULL) { 299280304Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT, 300280304Sjkim ERR_R_MALLOC_FAILURE); 301280304Sjkim goto err; 302280304Sjkim } 303280304Sjkim } 304280304Sjkim BN_CTX_start(ctx); 305280304Sjkim b = BN_CTX_get(ctx); 306280304Sjkim if (b == NULL) 307280304Sjkim goto err; 308160814Ssimon 309280304Sjkim if (!BN_GF2m_mod_arr(b, &group->b, group->poly)) 310280304Sjkim goto err; 311160814Ssimon 312280304Sjkim /* 313280304Sjkim * check the discriminant: y^2 + x*y = x^3 + a*x^2 + b is an elliptic 314280304Sjkim * curve <=> b != 0 (mod p) 315280304Sjkim */ 316280304Sjkim if (BN_is_zero(b)) 317280304Sjkim goto err; 318160814Ssimon 319280304Sjkim ret = 1; 320160814Ssimon 321280304Sjkim err: 322280304Sjkim if (ctx != NULL) 323280304Sjkim BN_CTX_end(ctx); 324280304Sjkim if (new_ctx != NULL) 325280304Sjkim BN_CTX_free(new_ctx); 326280304Sjkim return ret; 327280304Sjkim} 328280304Sjkim 329160814Ssimon/* Initializes an EC_POINT. */ 330160814Ssimonint ec_GF2m_simple_point_init(EC_POINT *point) 331280304Sjkim{ 332280304Sjkim BN_init(&point->X); 333280304Sjkim BN_init(&point->Y); 334280304Sjkim BN_init(&point->Z); 335280304Sjkim return 1; 336280304Sjkim} 337160814Ssimon 338160814Ssimon/* Frees an EC_POINT. */ 339160814Ssimonvoid ec_GF2m_simple_point_finish(EC_POINT *point) 340280304Sjkim{ 341280304Sjkim BN_free(&point->X); 342280304Sjkim BN_free(&point->Y); 343280304Sjkim BN_free(&point->Z); 344280304Sjkim} 345160814Ssimon 346160814Ssimon/* Clears and frees an EC_POINT. */ 347160814Ssimonvoid ec_GF2m_simple_point_clear_finish(EC_POINT *point) 348280304Sjkim{ 349280304Sjkim BN_clear_free(&point->X); 350280304Sjkim BN_clear_free(&point->Y); 351280304Sjkim BN_clear_free(&point->Z); 352280304Sjkim point->Z_is_one = 0; 353280304Sjkim} 354160814Ssimon 355280304Sjkim/* 356280304Sjkim * Copy the contents of one EC_POINT into another. Assumes dest is 357280304Sjkim * initialized. 358280304Sjkim */ 359160814Ssimonint ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src) 360280304Sjkim{ 361280304Sjkim if (!BN_copy(&dest->X, &src->X)) 362280304Sjkim return 0; 363280304Sjkim if (!BN_copy(&dest->Y, &src->Y)) 364280304Sjkim return 0; 365280304Sjkim if (!BN_copy(&dest->Z, &src->Z)) 366280304Sjkim return 0; 367280304Sjkim dest->Z_is_one = src->Z_is_one; 368160814Ssimon 369280304Sjkim return 1; 370280304Sjkim} 371160814Ssimon 372280304Sjkim/* 373280304Sjkim * Set an EC_POINT to the point at infinity. A point at infinity is 374280304Sjkim * represented by having Z=0. 375160814Ssimon */ 376280304Sjkimint ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group, 377280304Sjkim EC_POINT *point) 378280304Sjkim{ 379280304Sjkim point->Z_is_one = 0; 380280304Sjkim BN_zero(&point->Z); 381280304Sjkim return 1; 382280304Sjkim} 383160814Ssimon 384280304Sjkim/* 385280304Sjkim * Set the coordinates of an EC_POINT using affine coordinates. Note that 386280304Sjkim * the simple implementation only uses affine coordinates. 387160814Ssimon */ 388280304Sjkimint ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group, 389280304Sjkim EC_POINT *point, 390280304Sjkim const BIGNUM *x, 391280304Sjkim const BIGNUM *y, BN_CTX *ctx) 392280304Sjkim{ 393280304Sjkim int ret = 0; 394280304Sjkim if (x == NULL || y == NULL) { 395280304Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES, 396280304Sjkim ERR_R_PASSED_NULL_PARAMETER); 397280304Sjkim return 0; 398280304Sjkim } 399160814Ssimon 400280304Sjkim if (!BN_copy(&point->X, x)) 401280304Sjkim goto err; 402280304Sjkim BN_set_negative(&point->X, 0); 403280304Sjkim if (!BN_copy(&point->Y, y)) 404280304Sjkim goto err; 405280304Sjkim BN_set_negative(&point->Y, 0); 406280304Sjkim if (!BN_copy(&point->Z, BN_value_one())) 407280304Sjkim goto err; 408280304Sjkim BN_set_negative(&point->Z, 0); 409280304Sjkim point->Z_is_one = 1; 410280304Sjkim ret = 1; 411160814Ssimon 412280304Sjkim err: 413280304Sjkim return ret; 414280304Sjkim} 415160814Ssimon 416280304Sjkim/* 417280304Sjkim * Gets the affine coordinates of an EC_POINT. Note that the simple 418280304Sjkim * implementation only uses affine coordinates. 419160814Ssimon */ 420280304Sjkimint ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group, 421280304Sjkim const EC_POINT *point, 422280304Sjkim BIGNUM *x, BIGNUM *y, 423280304Sjkim BN_CTX *ctx) 424280304Sjkim{ 425280304Sjkim int ret = 0; 426160814Ssimon 427280304Sjkim if (EC_POINT_is_at_infinity(group, point)) { 428280304Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, 429280304Sjkim EC_R_POINT_AT_INFINITY); 430280304Sjkim return 0; 431280304Sjkim } 432160814Ssimon 433280304Sjkim if (BN_cmp(&point->Z, BN_value_one())) { 434280304Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, 435280304Sjkim ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 436280304Sjkim return 0; 437280304Sjkim } 438280304Sjkim if (x != NULL) { 439280304Sjkim if (!BN_copy(x, &point->X)) 440280304Sjkim goto err; 441280304Sjkim BN_set_negative(x, 0); 442280304Sjkim } 443280304Sjkim if (y != NULL) { 444280304Sjkim if (!BN_copy(y, &point->Y)) 445280304Sjkim goto err; 446280304Sjkim BN_set_negative(y, 0); 447280304Sjkim } 448280304Sjkim ret = 1; 449280304Sjkim 450160814Ssimon err: 451280304Sjkim return ret; 452280304Sjkim} 453160814Ssimon 454280304Sjkim/* 455280304Sjkim * Computes a + b and stores the result in r. r could be a or b, a could be 456280304Sjkim * b. Uses algorithm A.10.2 of IEEE P1363. 457160814Ssimon */ 458280304Sjkimint ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 459280304Sjkim const EC_POINT *b, BN_CTX *ctx) 460280304Sjkim{ 461280304Sjkim BN_CTX *new_ctx = NULL; 462280304Sjkim BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t; 463280304Sjkim int ret = 0; 464160814Ssimon 465280304Sjkim if (EC_POINT_is_at_infinity(group, a)) { 466280304Sjkim if (!EC_POINT_copy(r, b)) 467280304Sjkim return 0; 468280304Sjkim return 1; 469280304Sjkim } 470160814Ssimon 471280304Sjkim if (EC_POINT_is_at_infinity(group, b)) { 472280304Sjkim if (!EC_POINT_copy(r, a)) 473280304Sjkim return 0; 474280304Sjkim return 1; 475280304Sjkim } 476160814Ssimon 477280304Sjkim if (ctx == NULL) { 478280304Sjkim ctx = new_ctx = BN_CTX_new(); 479280304Sjkim if (ctx == NULL) 480280304Sjkim return 0; 481280304Sjkim } 482160814Ssimon 483280304Sjkim BN_CTX_start(ctx); 484280304Sjkim x0 = BN_CTX_get(ctx); 485280304Sjkim y0 = BN_CTX_get(ctx); 486280304Sjkim x1 = BN_CTX_get(ctx); 487280304Sjkim y1 = BN_CTX_get(ctx); 488280304Sjkim x2 = BN_CTX_get(ctx); 489280304Sjkim y2 = BN_CTX_get(ctx); 490280304Sjkim s = BN_CTX_get(ctx); 491280304Sjkim t = BN_CTX_get(ctx); 492280304Sjkim if (t == NULL) 493280304Sjkim goto err; 494160814Ssimon 495280304Sjkim if (a->Z_is_one) { 496280304Sjkim if (!BN_copy(x0, &a->X)) 497280304Sjkim goto err; 498280304Sjkim if (!BN_copy(y0, &a->Y)) 499280304Sjkim goto err; 500280304Sjkim } else { 501280304Sjkim if (!EC_POINT_get_affine_coordinates_GF2m(group, a, x0, y0, ctx)) 502280304Sjkim goto err; 503280304Sjkim } 504280304Sjkim if (b->Z_is_one) { 505280304Sjkim if (!BN_copy(x1, &b->X)) 506280304Sjkim goto err; 507280304Sjkim if (!BN_copy(y1, &b->Y)) 508280304Sjkim goto err; 509280304Sjkim } else { 510280304Sjkim if (!EC_POINT_get_affine_coordinates_GF2m(group, b, x1, y1, ctx)) 511280304Sjkim goto err; 512280304Sjkim } 513160814Ssimon 514280304Sjkim if (BN_GF2m_cmp(x0, x1)) { 515280304Sjkim if (!BN_GF2m_add(t, x0, x1)) 516280304Sjkim goto err; 517280304Sjkim if (!BN_GF2m_add(s, y0, y1)) 518280304Sjkim goto err; 519280304Sjkim if (!group->meth->field_div(group, s, s, t, ctx)) 520280304Sjkim goto err; 521280304Sjkim if (!group->meth->field_sqr(group, x2, s, ctx)) 522280304Sjkim goto err; 523280304Sjkim if (!BN_GF2m_add(x2, x2, &group->a)) 524280304Sjkim goto err; 525280304Sjkim if (!BN_GF2m_add(x2, x2, s)) 526280304Sjkim goto err; 527280304Sjkim if (!BN_GF2m_add(x2, x2, t)) 528280304Sjkim goto err; 529280304Sjkim } else { 530280304Sjkim if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) { 531280304Sjkim if (!EC_POINT_set_to_infinity(group, r)) 532280304Sjkim goto err; 533280304Sjkim ret = 1; 534280304Sjkim goto err; 535280304Sjkim } 536280304Sjkim if (!group->meth->field_div(group, s, y1, x1, ctx)) 537280304Sjkim goto err; 538280304Sjkim if (!BN_GF2m_add(s, s, x1)) 539280304Sjkim goto err; 540160814Ssimon 541280304Sjkim if (!group->meth->field_sqr(group, x2, s, ctx)) 542280304Sjkim goto err; 543280304Sjkim if (!BN_GF2m_add(x2, x2, s)) 544280304Sjkim goto err; 545280304Sjkim if (!BN_GF2m_add(x2, x2, &group->a)) 546280304Sjkim goto err; 547280304Sjkim } 548160814Ssimon 549280304Sjkim if (!BN_GF2m_add(y2, x1, x2)) 550280304Sjkim goto err; 551280304Sjkim if (!group->meth->field_mul(group, y2, y2, s, ctx)) 552280304Sjkim goto err; 553280304Sjkim if (!BN_GF2m_add(y2, y2, x2)) 554280304Sjkim goto err; 555280304Sjkim if (!BN_GF2m_add(y2, y2, y1)) 556280304Sjkim goto err; 557160814Ssimon 558280304Sjkim if (!EC_POINT_set_affine_coordinates_GF2m(group, r, x2, y2, ctx)) 559280304Sjkim goto err; 560160814Ssimon 561280304Sjkim ret = 1; 562280304Sjkim 563160814Ssimon err: 564280304Sjkim BN_CTX_end(ctx); 565280304Sjkim if (new_ctx != NULL) 566280304Sjkim BN_CTX_free(new_ctx); 567280304Sjkim return ret; 568280304Sjkim} 569160814Ssimon 570280304Sjkim/* 571280304Sjkim * Computes 2 * a and stores the result in r. r could be a. Uses algorithm 572280304Sjkim * A.10.2 of IEEE P1363. 573160814Ssimon */ 574280304Sjkimint ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 575280304Sjkim BN_CTX *ctx) 576280304Sjkim{ 577280304Sjkim return ec_GF2m_simple_add(group, r, a, a, ctx); 578280304Sjkim} 579160814Ssimon 580160814Ssimonint ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 581280304Sjkim{ 582280304Sjkim if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) 583280304Sjkim /* point is its own inverse */ 584280304Sjkim return 1; 585160814Ssimon 586280304Sjkim if (!EC_POINT_make_affine(group, point, ctx)) 587280304Sjkim return 0; 588280304Sjkim return BN_GF2m_add(&point->Y, &point->X, &point->Y); 589280304Sjkim} 590160814Ssimon 591160814Ssimon/* Indicates whether the given point is the point at infinity. */ 592280304Sjkimint ec_GF2m_simple_is_at_infinity(const EC_GROUP *group, 593280304Sjkim const EC_POINT *point) 594280304Sjkim{ 595280304Sjkim return BN_is_zero(&point->Z); 596280304Sjkim} 597160814Ssimon 598280304Sjkim/*- 599280304Sjkim * Determines whether the given EC_POINT is an actual point on the curve defined 600160814Ssimon * in the EC_GROUP. A point is valid if it satisfies the Weierstrass equation: 601160814Ssimon * y^2 + x*y = x^3 + a*x^2 + b. 602160814Ssimon */ 603280304Sjkimint ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, 604280304Sjkim BN_CTX *ctx) 605280304Sjkim{ 606280304Sjkim int ret = -1; 607280304Sjkim BN_CTX *new_ctx = NULL; 608280304Sjkim BIGNUM *lh, *y2; 609280304Sjkim int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 610280304Sjkim const BIGNUM *, BN_CTX *); 611280304Sjkim int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 612160814Ssimon 613280304Sjkim if (EC_POINT_is_at_infinity(group, point)) 614280304Sjkim return 1; 615160814Ssimon 616280304Sjkim field_mul = group->meth->field_mul; 617280304Sjkim field_sqr = group->meth->field_sqr; 618160814Ssimon 619280304Sjkim /* only support affine coordinates */ 620280304Sjkim if (!point->Z_is_one) 621280304Sjkim return -1; 622160814Ssimon 623280304Sjkim if (ctx == NULL) { 624280304Sjkim ctx = new_ctx = BN_CTX_new(); 625280304Sjkim if (ctx == NULL) 626280304Sjkim return -1; 627280304Sjkim } 628160814Ssimon 629280304Sjkim BN_CTX_start(ctx); 630280304Sjkim y2 = BN_CTX_get(ctx); 631280304Sjkim lh = BN_CTX_get(ctx); 632280304Sjkim if (lh == NULL) 633280304Sjkim goto err; 634160814Ssimon 635280304Sjkim /*- 636280304Sjkim * We have a curve defined by a Weierstrass equation 637280304Sjkim * y^2 + x*y = x^3 + a*x^2 + b. 638280304Sjkim * <=> x^3 + a*x^2 + x*y + b + y^2 = 0 639280304Sjkim * <=> ((x + a) * x + y ) * x + b + y^2 = 0 640280304Sjkim */ 641280304Sjkim if (!BN_GF2m_add(lh, &point->X, &group->a)) 642280304Sjkim goto err; 643280304Sjkim if (!field_mul(group, lh, lh, &point->X, ctx)) 644280304Sjkim goto err; 645280304Sjkim if (!BN_GF2m_add(lh, lh, &point->Y)) 646280304Sjkim goto err; 647280304Sjkim if (!field_mul(group, lh, lh, &point->X, ctx)) 648280304Sjkim goto err; 649280304Sjkim if (!BN_GF2m_add(lh, lh, &group->b)) 650280304Sjkim goto err; 651280304Sjkim if (!field_sqr(group, y2, &point->Y, ctx)) 652280304Sjkim goto err; 653280304Sjkim if (!BN_GF2m_add(lh, lh, y2)) 654280304Sjkim goto err; 655280304Sjkim ret = BN_is_zero(lh); 656160814Ssimon err: 657280304Sjkim if (ctx) 658280304Sjkim BN_CTX_end(ctx); 659280304Sjkim if (new_ctx) 660280304Sjkim BN_CTX_free(new_ctx); 661280304Sjkim return ret; 662280304Sjkim} 663160814Ssimon 664280304Sjkim/*- 665280304Sjkim * Indicates whether two points are equal. 666160814Ssimon * Return values: 667160814Ssimon * -1 error 668160814Ssimon * 0 equal (in affine coordinates) 669160814Ssimon * 1 not equal 670160814Ssimon */ 671280304Sjkimint ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a, 672280304Sjkim const EC_POINT *b, BN_CTX *ctx) 673280304Sjkim{ 674280304Sjkim BIGNUM *aX, *aY, *bX, *bY; 675280304Sjkim BN_CTX *new_ctx = NULL; 676280304Sjkim int ret = -1; 677160814Ssimon 678280304Sjkim if (EC_POINT_is_at_infinity(group, a)) { 679280304Sjkim return EC_POINT_is_at_infinity(group, b) ? 0 : 1; 680280304Sjkim } 681237657Sjkim 682280304Sjkim if (EC_POINT_is_at_infinity(group, b)) 683280304Sjkim return 1; 684160814Ssimon 685280304Sjkim if (a->Z_is_one && b->Z_is_one) { 686280304Sjkim return ((BN_cmp(&a->X, &b->X) == 0) 687280304Sjkim && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; 688280304Sjkim } 689160814Ssimon 690280304Sjkim if (ctx == NULL) { 691280304Sjkim ctx = new_ctx = BN_CTX_new(); 692280304Sjkim if (ctx == NULL) 693280304Sjkim return -1; 694280304Sjkim } 695160814Ssimon 696280304Sjkim BN_CTX_start(ctx); 697280304Sjkim aX = BN_CTX_get(ctx); 698280304Sjkim aY = BN_CTX_get(ctx); 699280304Sjkim bX = BN_CTX_get(ctx); 700280304Sjkim bY = BN_CTX_get(ctx); 701280304Sjkim if (bY == NULL) 702280304Sjkim goto err; 703160814Ssimon 704280304Sjkim if (!EC_POINT_get_affine_coordinates_GF2m(group, a, aX, aY, ctx)) 705280304Sjkim goto err; 706280304Sjkim if (!EC_POINT_get_affine_coordinates_GF2m(group, b, bX, bY, ctx)) 707280304Sjkim goto err; 708280304Sjkim ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1; 709160814Ssimon 710280304Sjkim err: 711280304Sjkim if (ctx) 712280304Sjkim BN_CTX_end(ctx); 713280304Sjkim if (new_ctx) 714280304Sjkim BN_CTX_free(new_ctx); 715280304Sjkim return ret; 716280304Sjkim} 717160814Ssimon 718160814Ssimon/* Forces the given EC_POINT to internally use affine coordinates. */ 719280304Sjkimint ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point, 720280304Sjkim BN_CTX *ctx) 721280304Sjkim{ 722280304Sjkim BN_CTX *new_ctx = NULL; 723280304Sjkim BIGNUM *x, *y; 724280304Sjkim int ret = 0; 725160814Ssimon 726280304Sjkim if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) 727280304Sjkim return 1; 728160814Ssimon 729280304Sjkim if (ctx == NULL) { 730280304Sjkim ctx = new_ctx = BN_CTX_new(); 731280304Sjkim if (ctx == NULL) 732280304Sjkim return 0; 733280304Sjkim } 734160814Ssimon 735280304Sjkim BN_CTX_start(ctx); 736280304Sjkim x = BN_CTX_get(ctx); 737280304Sjkim y = BN_CTX_get(ctx); 738280304Sjkim if (y == NULL) 739280304Sjkim goto err; 740160814Ssimon 741280304Sjkim if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx)) 742280304Sjkim goto err; 743280304Sjkim if (!BN_copy(&point->X, x)) 744280304Sjkim goto err; 745280304Sjkim if (!BN_copy(&point->Y, y)) 746280304Sjkim goto err; 747280304Sjkim if (!BN_one(&point->Z)) 748280304Sjkim goto err; 749160814Ssimon 750280304Sjkim ret = 1; 751160814Ssimon 752280304Sjkim err: 753280304Sjkim if (ctx) 754280304Sjkim BN_CTX_end(ctx); 755280304Sjkim if (new_ctx) 756280304Sjkim BN_CTX_free(new_ctx); 757280304Sjkim return ret; 758280304Sjkim} 759160814Ssimon 760280304Sjkim/* 761280304Sjkim * Forces each of the EC_POINTs in the given array to use affine coordinates. 762280304Sjkim */ 763280304Sjkimint ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num, 764280304Sjkim EC_POINT *points[], BN_CTX *ctx) 765280304Sjkim{ 766280304Sjkim size_t i; 767160814Ssimon 768280304Sjkim for (i = 0; i < num; i++) { 769280304Sjkim if (!group->meth->make_affine(group, points[i], ctx)) 770280304Sjkim return 0; 771280304Sjkim } 772160814Ssimon 773280304Sjkim return 1; 774280304Sjkim} 775280304Sjkim 776160814Ssimon/* Wrapper to simple binary polynomial field multiplication implementation. */ 777280304Sjkimint ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r, 778280304Sjkim const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 779280304Sjkim{ 780280304Sjkim return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx); 781280304Sjkim} 782160814Ssimon 783160814Ssimon/* Wrapper to simple binary polynomial field squaring implementation. */ 784280304Sjkimint ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, 785280304Sjkim const BIGNUM *a, BN_CTX *ctx) 786280304Sjkim{ 787280304Sjkim return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx); 788280304Sjkim} 789160814Ssimon 790160814Ssimon/* Wrapper to simple binary polynomial field division implementation. */ 791280304Sjkimint ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r, 792280304Sjkim const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 793280304Sjkim{ 794280304Sjkim return BN_GF2m_mod_div(r, a, b, &group->field, ctx); 795280304Sjkim} 796238405Sjkim 797238405Sjkim#endif 798