ec2_smpl.c revision 279264
190075Sobrien/* crypto/ec/ec2_smpl.c */ 2169689Skan/* ==================================================================== 390075Sobrien * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 490075Sobrien * 590075Sobrien * The Elliptic Curve Public-Key Crypto Library (ECC Code) included 690075Sobrien * herein is developed by SUN MICROSYSTEMS, INC., and is contributed 790075Sobrien * to the OpenSSL project. 890075Sobrien * 990075Sobrien * The ECC Code is licensed pursuant to the OpenSSL open source 1090075Sobrien * license provided below. 1190075Sobrien * 1290075Sobrien * The software is originally written by Sheueling Chang Shantz and 1390075Sobrien * Douglas Stebila of Sun Microsystems Laboratories. 1490075Sobrien * 1590075Sobrien */ 1690075Sobrien/* ==================================================================== 1790075Sobrien * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. 18169689Skan * 19169689Skan * Redistribution and use in source and binary forms, with or without 2090075Sobrien * modification, are permitted provided that the following conditions 21132718Skan * are met: 22132718Skan * 23132718Skan * 1. Redistributions of source code must retain the above copyright 24132718Skan * notice, this list of conditions and the following disclaimer. 25132718Skan * 26132718Skan * 2. Redistributions in binary form must reproduce the above copyright 2790075Sobrien * notice, this list of conditions and the following disclaimer in 28132718Skan * the documentation and/or other materials provided with the 29132718Skan * distribution. 30132718Skan * 31132718Skan * 3. All advertising materials mentioning features or use of this 32132718Skan * software must display the following acknowledgment: 33132718Skan * "This product includes software developed by the OpenSSL Project 34132718Skan * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 3590075Sobrien * 36132718Skan * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 37132718Skan * endorse or promote products derived from this software without 38132718Skan * prior written permission. For written permission, please contact 39132718Skan * openssl-core@openssl.org. 40132718Skan * 41132718Skan * 5. Products derived from this software may not be called "OpenSSL" 42132718Skan * nor may "OpenSSL" appear in their names without prior written 43132718Skan * permission of the OpenSSL Project. 44132718Skan * 45132718Skan * 6. Redistributions of any form whatsoever must retain the following 46132718Skan * acknowledgment: 47132718Skan * "This product includes software developed by the OpenSSL Project 48132718Skan * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 4990075Sobrien * 50132718Skan * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 51132718Skan * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 52132718Skan * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 53132718Skan * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 54132718Skan * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 55132718Skan * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 56132718Skan * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 57132718Skan * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 5890075Sobrien * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 5990075Sobrien * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 60132718Skan * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 6190075Sobrien * OF THE POSSIBILITY OF SUCH DAMAGE. 62132718Skan * ==================================================================== 63132718Skan * 64132718Skan * This product includes cryptographic software written by Eric Young 6590075Sobrien * (eay@cryptsoft.com). This product includes software written by Tim 6690075Sobrien * Hudson (tjh@cryptsoft.com). 6790075Sobrien * 6890075Sobrien */ 6990075Sobrien 70132718Skan#include <openssl/err.h> 71132718Skan 7290075Sobrien#include "ec_lcl.h" 73169689Skan 7490075Sobrien#ifndef OPENSSL_NO_EC2M 75132718Skan 7690075Sobrien#ifdef OPENSSL_FIPS 7790075Sobrien#include <openssl/fips.h> 78132718Skan#endif 7996263Sobrien 80169689Skan 81169689Skanconst EC_METHOD *EC_GF2m_simple_method(void) 82169689Skan { 83169689Skan static const EC_METHOD ret = { 84169689Skan EC_FLAGS_DEFAULT_OCT, 85169689Skan NID_X9_62_characteristic_two_field, 86169689Skan ec_GF2m_simple_group_init, 8790075Sobrien ec_GF2m_simple_group_finish, 88169689Skan ec_GF2m_simple_group_clear_finish, 89169689Skan ec_GF2m_simple_group_copy, 90169689Skan ec_GF2m_simple_group_set_curve, 91132718Skan ec_GF2m_simple_group_get_curve, 92169689Skan ec_GF2m_simple_group_get_degree, 93169689Skan ec_GF2m_simple_group_check_discriminant, 94169689Skan ec_GF2m_simple_point_init, 95169689Skan ec_GF2m_simple_point_finish, 96169689Skan ec_GF2m_simple_point_clear_finish, 97169689Skan ec_GF2m_simple_point_copy, 98169689Skan ec_GF2m_simple_point_set_to_infinity, 99169689Skan 0 /* set_Jprojective_coordinates_GFp */, 100169689Skan 0 /* get_Jprojective_coordinates_GFp */, 101169689Skan ec_GF2m_simple_point_set_affine_coordinates, 102169689Skan ec_GF2m_simple_point_get_affine_coordinates, 103169689Skan 0,0,0, 104169689Skan ec_GF2m_simple_add, 105169689Skan ec_GF2m_simple_dbl, 106132718Skan ec_GF2m_simple_invert, 107169689Skan ec_GF2m_simple_is_at_infinity, 108132718Skan ec_GF2m_simple_is_on_curve, 109132718Skan ec_GF2m_simple_cmp, 110169689Skan ec_GF2m_simple_make_affine, 111132718Skan ec_GF2m_simple_points_make_affine, 112132718Skan 113132718Skan /* the following three method functions are defined in ec2_mult.c */ 114132718Skan ec_GF2m_simple_mul, 115132718Skan ec_GF2m_precompute_mult, 116132718Skan ec_GF2m_have_precompute_mult, 117132718Skan 118132718Skan ec_GF2m_simple_field_mul, 119132718Skan ec_GF2m_simple_field_sqr, 120132718Skan ec_GF2m_simple_field_div, 121132718Skan 0 /* field_encode */, 122132718Skan 0 /* field_decode */, 123132718Skan 0 /* field_set_to_one */ }; 124132718Skan 125132718Skan#ifdef OPENSSL_FIPS 126132718Skan if (FIPS_mode()) 127132718Skan return fips_ec_gf2m_simple_method(); 128169689Skan#endif 129169689Skan 130169689Skan return &ret; 131132718Skan } 132132718Skan 133132718Skan 134132718Skan/* Initialize a GF(2^m)-based EC_GROUP structure. 135132718Skan * Note that all other members are handled by EC_GROUP_new. 136132718Skan */ 137132718Skanint ec_GF2m_simple_group_init(EC_GROUP *group) 138132718Skan { 139132718Skan BN_init(&group->field); 140132718Skan BN_init(&group->a); 141132718Skan BN_init(&group->b); 142132718Skan return 1; 143132718Skan } 144132718Skan 145132718Skan 146132718Skan/* Free a GF(2^m)-based EC_GROUP structure. 147132718Skan * Note that all other members are handled by EC_GROUP_free. 148132718Skan */ 149169689Skanvoid ec_GF2m_simple_group_finish(EC_GROUP *group) 150132718Skan { 151132718Skan BN_free(&group->field); 152132718Skan BN_free(&group->a); 153132718Skan BN_free(&group->b); 154132718Skan } 155132718Skan 156132718Skan 157132718Skan/* Clear and free a GF(2^m)-based EC_GROUP structure. 158132718Skan * Note that all other members are handled by EC_GROUP_clear_free. 159132718Skan */ 160132718Skanvoid ec_GF2m_simple_group_clear_finish(EC_GROUP *group) 161132718Skan { 162132718Skan BN_clear_free(&group->field); 163132718Skan BN_clear_free(&group->a); 164132718Skan BN_clear_free(&group->b); 165169689Skan group->poly[0] = 0; 166169689Skan group->poly[1] = 0; 167132718Skan group->poly[2] = 0; 16890075Sobrien group->poly[3] = 0; 169132718Skan group->poly[4] = 0; 170132718Skan group->poly[5] = -1; 171132718Skan } 172132718Skan 173169689Skan 174132718Skan/* Copy a GF(2^m)-based EC_GROUP structure. 175132718Skan * Note that all other members are handled by EC_GROUP_copy. 176169689Skan */ 177132718Skanint ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) 178132718Skan { 179132718Skan int i; 180169689Skan if (!BN_copy(&dest->field, &src->field)) return 0; 181169689Skan if (!BN_copy(&dest->a, &src->a)) return 0; 182169689Skan if (!BN_copy(&dest->b, &src->b)) return 0; 183169689Skan dest->poly[0] = src->poly[0]; 184169689Skan dest->poly[1] = src->poly[1]; 185169689Skan dest->poly[2] = src->poly[2]; 186169689Skan dest->poly[3] = src->poly[3]; 187169689Skan dest->poly[4] = src->poly[4]; 188169689Skan dest->poly[5] = src->poly[5]; 189169689Skan if (bn_wexpand(&dest->a, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL) return 0; 19090075Sobrien if (bn_wexpand(&dest->b, (int)(dest->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL) return 0; 191169689Skan for (i = dest->a.top; i < dest->a.dmax; i++) dest->a.d[i] = 0; 192169689Skan for (i = dest->b.top; i < dest->b.dmax; i++) dest->b.d[i] = 0; 193169689Skan return 1; 194169689Skan } 195169689Skan 196169689Skan 197169689Skan/* Set the curve parameters of an EC_GROUP structure. */ 198169689Skanint ec_GF2m_simple_group_set_curve(EC_GROUP *group, 199169689Skan const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 200169689Skan { 201169689Skan int ret = 0, i; 202169689Skan 203169689Skan /* group->field */ 204169689Skan if (!BN_copy(&group->field, p)) goto err; 205169689Skan i = BN_GF2m_poly2arr(&group->field, group->poly, 6) - 1; 206169689Skan if ((i != 5) && (i != 3)) 207169689Skan { 208169689Skan ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIELD); 209169689Skan goto err; 210169689Skan } 211169689Skan 212169689Skan /* group->a */ 213169689Skan if (!BN_GF2m_mod_arr(&group->a, a, group->poly)) goto err; 214169689Skan if(bn_wexpand(&group->a, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL) goto err; 215169689Skan for (i = group->a.top; i < group->a.dmax; i++) group->a.d[i] = 0; 216169689Skan 217169689Skan /* group->b */ 218169689Skan if (!BN_GF2m_mod_arr(&group->b, b, group->poly)) goto err; 219132718Skan if(bn_wexpand(&group->b, (int)(group->poly[0] + BN_BITS2 - 1) / BN_BITS2) == NULL) goto err; 220132718Skan for (i = group->b.top; i < group->b.dmax; i++) group->b.d[i] = 0; 221132718Skan 22290075Sobrien ret = 1; 22390075Sobrien err: 224132718Skan return ret; 22590075Sobrien } 226132718Skan 227169689Skan 228132718Skan/* Get the curve parameters of an EC_GROUP structure. 229169689Skan * If p, a, or b are NULL then there values will not be set but the method will return with success. 230132718Skan */ 23190075Sobrienint ec_GF2m_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx) 232169689Skan { 233169689Skan int ret = 0; 234169689Skan 235169689Skan if (p != NULL) 236169689Skan { 237169689Skan if (!BN_copy(p, &group->field)) return 0; 238132718Skan } 239132718Skan 240132718Skan if (a != NULL) 241132718Skan { 242169689Skan if (!BN_copy(a, &group->a)) goto err; 24390075Sobrien } 244132718Skan 245132718Skan if (b != NULL) 246132718Skan { 247132718Skan if (!BN_copy(b, &group->b)) goto err; 248132718Skan } 249132718Skan 250132718Skan ret = 1; 251132718Skan 25290075Sobrien err: 253132718Skan return ret; 254169689Skan } 255132718Skan 256132718Skan 25790075Sobrien/* Gets the degree of the field. For a curve over GF(2^m) this is the value m. */ 258169689Skanint ec_GF2m_simple_group_get_degree(const EC_GROUP *group) 259169689Skan { 260117395Skan return BN_num_bits(&group->field)-1; 261132718Skan } 262132718Skan 263132718Skan 264132718Skan/* Checks the discriminant of the curve. 265132718Skan * y^2 + x*y = x^3 + a*x^2 + b is an elliptic curve <=> b != 0 (mod p) 266132718Skan */ 267132718Skanint ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx) 268169689Skan { 269169689Skan int ret = 0; 27090075Sobrien BIGNUM *b; 271132718Skan BN_CTX *new_ctx = NULL; 272132718Skan 273169689Skan if (ctx == NULL) 274132718Skan { 275132718Skan ctx = new_ctx = BN_CTX_new(); 276132718Skan if (ctx == NULL) 277132718Skan { 278169689Skan ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE); 279132718Skan goto err; 280169689Skan } 281169689Skan } 282169689Skan BN_CTX_start(ctx); 283132718Skan b = BN_CTX_get(ctx); 284169689Skan if (b == NULL) goto err; 285132718Skan 28690075Sobrien if (!BN_GF2m_mod_arr(b, &group->b, group->poly)) goto err; 28790075Sobrien 288132718Skan /* check the discriminant: 289132718Skan * y^2 + x*y = x^3 + a*x^2 + b is an elliptic curve <=> b != 0 (mod p) 290117395Skan */ 291132718Skan if (BN_is_zero(b)) goto err; 292132718Skan 293117395Skan ret = 1; 294132718Skan 295117395Skanerr: 296132718Skan if (ctx != NULL) 297132718Skan BN_CTX_end(ctx); 298132718Skan if (new_ctx != NULL) 299132718Skan BN_CTX_free(new_ctx); 300132718Skan return ret; 301132718Skan } 302132718Skan 303132718Skan 304117395Skan/* Initializes an EC_POINT. */ 305132718Skanint ec_GF2m_simple_point_init(EC_POINT *point) 306132718Skan { 307132718Skan BN_init(&point->X); 308132718Skan BN_init(&point->Y); 309132718Skan BN_init(&point->Z); 310169689Skan return 1; 311169689Skan } 312169689Skan 313132718Skan 314169689Skan/* Frees an EC_POINT. */ 315132718Skanvoid ec_GF2m_simple_point_finish(EC_POINT *point) 316132718Skan { 317132718Skan BN_free(&point->X); 318132718Skan BN_free(&point->Y); 319132718Skan BN_free(&point->Z); 320132718Skan } 321169689Skan 322132718Skan 323132718Skan/* Clears and frees an EC_POINT. */ 324132718Skanvoid ec_GF2m_simple_point_clear_finish(EC_POINT *point) 325132718Skan { 326132718Skan BN_clear_free(&point->X); 327132718Skan BN_clear_free(&point->Y); 328132718Skan BN_clear_free(&point->Z); 329132718Skan point->Z_is_one = 0; 330132718Skan } 331132718Skan 332132718Skan 333132718Skan/* Copy the contents of one EC_POINT into another. Assumes dest is initialized. */ 334132718Skanint ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src) 335132718Skan { 336132718Skan if (!BN_copy(&dest->X, &src->X)) return 0; 337169689Skan if (!BN_copy(&dest->Y, &src->Y)) return 0; 338132718Skan if (!BN_copy(&dest->Z, &src->Z)) return 0; 339132718Skan dest->Z_is_one = src->Z_is_one; 340132718Skan 341132718Skan return 1; 342132718Skan } 343132718Skan 344132718Skan 345132718Skan/* Set an EC_POINT to the point at infinity. 346132718Skan * A point at infinity is represented by having Z=0. 347132718Skan */ 348132718Skanint ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point) 349132718Skan { 350132718Skan point->Z_is_one = 0; 351132718Skan BN_zero(&point->Z); 352132718Skan return 1; 353132718Skan } 354132718Skan 355132718Skan 356132718Skan/* Set the coordinates of an EC_POINT using affine coordinates. 357132718Skan * Note that the simple implementation only uses affine coordinates. 358132718Skan */ 359132718Skanint ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point, 360169689Skan const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) 361132718Skan { 362132718Skan int ret = 0; 363117395Skan if (x == NULL || y == NULL) 364132718Skan { 365132718Skan ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER); 366132718Skan return 0; 367132718Skan } 368132718Skan 369132718Skan if (!BN_copy(&point->X, x)) goto err; 370169689Skan BN_set_negative(&point->X, 0); 371132718Skan if (!BN_copy(&point->Y, y)) goto err; 372132718Skan BN_set_negative(&point->Y, 0); 373132718Skan if (!BN_copy(&point->Z, BN_value_one())) goto err; 374132718Skan BN_set_negative(&point->Z, 0); 375117395Skan point->Z_is_one = 1; 376132718Skan ret = 1; 377169689Skan 378169689Skan err: 379132718Skan return ret; 380169689Skan } 381132718Skan 382132718Skan 383169689Skan/* Gets the affine coordinates of an EC_POINT. 384132718Skan * Note that the simple implementation only uses affine coordinates. 385169689Skan */ 386132718Skanint ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point, 387132718Skan BIGNUM *x, BIGNUM *y, BN_CTX *ctx) 388132718Skan { 389169689Skan int ret = 0; 390169689Skan 391169689Skan if (EC_POINT_is_at_infinity(group, point)) 392169689Skan { 393132718Skan ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY); 394132718Skan return 0; 395132718Skan } 396132718Skan 397117395Skan if (BN_cmp(&point->Z, BN_value_one())) 398132718Skan { 399132718Skan ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 400117395Skan return 0; 401169689Skan } 402132718Skan if (x != NULL) 403132718Skan { 404117395Skan if (!BN_copy(x, &point->X)) goto err; 405132718Skan BN_set_negative(x, 0); 406132718Skan } 407132718Skan if (y != NULL) 408132718Skan { 409132718Skan if (!BN_copy(y, &point->Y)) goto err; 410169689Skan BN_set_negative(y, 0); 411132718Skan } 412132718Skan ret = 1; 413132718Skan 414132718Skan err: 415132718Skan return ret; 416132718Skan } 417117395Skan 418117395Skan/* Computes a + b and stores the result in r. r could be a or b, a could be b. 419132718Skan * Uses algorithm A.10.2 of IEEE P1363. 420132718Skan */ 421132718Skanint ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx) 422132718Skan { 423132718Skan BN_CTX *new_ctx = NULL; 424132718Skan BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t; 425132718Skan int ret = 0; 42690075Sobrien 427132718Skan if (EC_POINT_is_at_infinity(group, a)) 428132718Skan { 429132718Skan if (!EC_POINT_copy(r, b)) return 0; 430169689Skan return 1; 431132718Skan } 432132718Skan 433132718Skan if (EC_POINT_is_at_infinity(group, b)) 434132718Skan { 43590075Sobrien if (!EC_POINT_copy(r, a)) return 0; 436132718Skan return 1; 437132718Skan } 438132718Skan 439132718Skan if (ctx == NULL) 440132718Skan { 441132718Skan ctx = new_ctx = BN_CTX_new(); 442169689Skan if (ctx == NULL) 44390075Sobrien return 0; 444132718Skan } 445132718Skan 446132718Skan BN_CTX_start(ctx); 447132718Skan x0 = BN_CTX_get(ctx); 448169689Skan y0 = BN_CTX_get(ctx); 449169689Skan x1 = BN_CTX_get(ctx); 450132718Skan y1 = BN_CTX_get(ctx); 451169689Skan x2 = BN_CTX_get(ctx); 452169689Skan y2 = BN_CTX_get(ctx); 453169689Skan s = BN_CTX_get(ctx); 454169689Skan t = BN_CTX_get(ctx); 455169689Skan if (t == NULL) goto err; 456169689Skan 457169689Skan if (a->Z_is_one) 458132718Skan { 459132718Skan if (!BN_copy(x0, &a->X)) goto err; 460132718Skan if (!BN_copy(y0, &a->Y)) goto err; 461132718Skan } 462132718Skan else 463169689Skan { 464169689Skan if (!EC_POINT_get_affine_coordinates_GF2m(group, a, x0, y0, ctx)) goto err; 465132718Skan } 466132718Skan if (b->Z_is_one) 467132718Skan { 468132718Skan if (!BN_copy(x1, &b->X)) goto err; 469132718Skan if (!BN_copy(y1, &b->Y)) goto err; 470132718Skan } 471132718Skan else 472132718Skan { 473132718Skan if (!EC_POINT_get_affine_coordinates_GF2m(group, b, x1, y1, ctx)) goto err; 474169689Skan } 475132718Skan 476132718Skan 477132718Skan if (BN_GF2m_cmp(x0, x1)) 478132718Skan { 479132718Skan if (!BN_GF2m_add(t, x0, x1)) goto err; 480169689Skan if (!BN_GF2m_add(s, y0, y1)) goto err; 481132718Skan if (!group->meth->field_div(group, s, s, t, ctx)) goto err; 482132718Skan if (!group->meth->field_sqr(group, x2, s, ctx)) goto err; 483132718Skan if (!BN_GF2m_add(x2, x2, &group->a)) goto err; 484132718Skan if (!BN_GF2m_add(x2, x2, s)) goto err; 485132718Skan if (!BN_GF2m_add(x2, x2, t)) goto err; 486132718Skan } 487132718Skan else 488132718Skan { 489132718Skan if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1)) 490169689Skan { 491169689Skan if (!EC_POINT_set_to_infinity(group, r)) goto err; 492132718Skan ret = 1; 493132718Skan goto err; 494169689Skan } 495169689Skan if (!group->meth->field_div(group, s, y1, x1, ctx)) goto err; 496132718Skan if (!BN_GF2m_add(s, s, x1)) goto err; 497169689Skan 498132718Skan if (!group->meth->field_sqr(group, x2, s, ctx)) goto err; 499169689Skan if (!BN_GF2m_add(x2, x2, s)) goto err; 500132718Skan if (!BN_GF2m_add(x2, x2, &group->a)) goto err; 501132718Skan } 502132718Skan 503132718Skan if (!BN_GF2m_add(y2, x1, x2)) goto err; 504169689Skan if (!group->meth->field_mul(group, y2, y2, s, ctx)) goto err; 505169689Skan if (!BN_GF2m_add(y2, y2, x2)) goto err; 506132718Skan if (!BN_GF2m_add(y2, y2, y1)) goto err; 507132718Skan 508169689Skan if (!EC_POINT_set_affine_coordinates_GF2m(group, r, x2, y2, ctx)) goto err; 509169689Skan 510169689Skan ret = 1; 511132718Skan 512169689Skan err: 513132718Skan BN_CTX_end(ctx); 514169689Skan if (new_ctx != NULL) 515169689Skan BN_CTX_free(new_ctx); 516169689Skan return ret; 517169689Skan } 518169689Skan 519169689Skan 520169689Skan/* Computes 2 * a and stores the result in r. r could be a. 521169689Skan * Uses algorithm A.10.2 of IEEE P1363. 522169689Skan */ 523169689Skanint ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx) 524169689Skan { 525169689Skan return ec_GF2m_simple_add(group, r, a, a, ctx); 526169689Skan } 527132718Skan 528169689Skan 529132718Skanint ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 530169689Skan { 531169689Skan if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) 532132718Skan /* point is its own inverse */ 533132718Skan return 1; 534169689Skan 535169689Skan if (!EC_POINT_make_affine(group, point, ctx)) return 0; 536169689Skan return BN_GF2m_add(&point->Y, &point->X, &point->Y); 537169689Skan } 538169689Skan 539132718Skan 540132718Skan/* Indicates whether the given point is the point at infinity. */ 541132718Skanint ec_GF2m_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) 542132718Skan { 543132718Skan return BN_is_zero(&point->Z); 544132718Skan } 545132718Skan 546132718Skan 547132718Skan/* Determines whether the given EC_POINT is an actual point on the curve defined 548132718Skan * in the EC_GROUP. A point is valid if it satisfies the Weierstrass equation: 549169689Skan * y^2 + x*y = x^3 + a*x^2 + b. 550132718Skan */ 551132718Skanint ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx) 552132718Skan { 553132718Skan int ret = -1; 554169689Skan BN_CTX *new_ctx = NULL; 555132718Skan BIGNUM *lh, *y2; 556132718Skan int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 557132718Skan int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 558169689Skan 559132718Skan if (EC_POINT_is_at_infinity(group, point)) 560132718Skan return 1; 561132718Skan 562132718Skan field_mul = group->meth->field_mul; 563132718Skan field_sqr = group->meth->field_sqr; 564132718Skan 565132718Skan /* only support affine coordinates */ 566132718Skan if (!point->Z_is_one) return -1; 567132718Skan 568169689Skan if (ctx == NULL) 569132718Skan { 570169689Skan ctx = new_ctx = BN_CTX_new(); 571132718Skan if (ctx == NULL) 572132718Skan return -1; 573132718Skan } 574132718Skan 575132718Skan BN_CTX_start(ctx); 576132718Skan y2 = BN_CTX_get(ctx); 577132718Skan lh = BN_CTX_get(ctx); 578132718Skan if (lh == NULL) goto err; 579132718Skan 580132718Skan /* We have a curve defined by a Weierstrass equation 581132718Skan * y^2 + x*y = x^3 + a*x^2 + b. 582132718Skan * <=> x^3 + a*x^2 + x*y + b + y^2 = 0 583132718Skan * <=> ((x + a) * x + y ) * x + b + y^2 = 0 584132718Skan */ 585132718Skan if (!BN_GF2m_add(lh, &point->X, &group->a)) goto err; 586132718Skan if (!field_mul(group, lh, lh, &point->X, ctx)) goto err; 587132718Skan if (!BN_GF2m_add(lh, lh, &point->Y)) goto err; 588132718Skan if (!field_mul(group, lh, lh, &point->X, ctx)) goto err; 589132718Skan if (!BN_GF2m_add(lh, lh, &group->b)) goto err; 590132718Skan if (!field_sqr(group, y2, &point->Y, ctx)) goto err; 591132718Skan if (!BN_GF2m_add(lh, lh, y2)) goto err; 592169689Skan ret = BN_is_zero(lh); 593169689Skan err: 594169689Skan if (ctx) BN_CTX_end(ctx); 595169689Skan if (new_ctx) BN_CTX_free(new_ctx); 596169689Skan return ret; 597169689Skan } 598169689Skan 599132718Skan 600132718Skan/* Indicates whether two points are equal. 601132718Skan * Return values: 602132718Skan * -1 error 603132718Skan * 0 equal (in affine coordinates) 604132718Skan * 1 not equal 605132718Skan */ 606169689Skanint ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx) 607132718Skan { 608169689Skan BIGNUM *aX, *aY, *bX, *bY; 609132718Skan BN_CTX *new_ctx = NULL; 610132718Skan int ret = -1; 611132718Skan 612132718Skan if (EC_POINT_is_at_infinity(group, a)) 613132718Skan { 614132718Skan return EC_POINT_is_at_infinity(group, b) ? 0 : 1; 615132718Skan } 616132718Skan 617132718Skan if (EC_POINT_is_at_infinity(group, b)) 618132718Skan return 1; 619169689Skan 620132718Skan if (a->Z_is_one && b->Z_is_one) 621132718Skan { 622132718Skan return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; 623132718Skan } 624132718Skan 625132718Skan if (ctx == NULL) 626132718Skan { 627132718Skan ctx = new_ctx = BN_CTX_new(); 628132718Skan if (ctx == NULL) 629132718Skan return -1; 630132718Skan } 631132718Skan 632132718Skan BN_CTX_start(ctx); 633169689Skan aX = BN_CTX_get(ctx); 634132718Skan aY = BN_CTX_get(ctx); 635169689Skan bX = BN_CTX_get(ctx); 636132718Skan bY = BN_CTX_get(ctx); 637132718Skan if (bY == NULL) goto err; 638132718Skan 639169689Skan if (!EC_POINT_get_affine_coordinates_GF2m(group, a, aX, aY, ctx)) goto err; 640169689Skan if (!EC_POINT_get_affine_coordinates_GF2m(group, b, bX, bY, ctx)) goto err; 641169689Skan ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1; 642132718Skan 643132718Skan err: 644132718Skan if (ctx) BN_CTX_end(ctx); 645132718Skan if (new_ctx) BN_CTX_free(new_ctx); 646132718Skan return ret; 647132718Skan } 648132718Skan 649169689Skan 650169689Skan/* Forces the given EC_POINT to internally use affine coordinates. */ 651132718Skanint ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 652132718Skan { 653132718Skan BN_CTX *new_ctx = NULL; 654169689Skan BIGNUM *x, *y; 655132718Skan int ret = 0; 656132718Skan 657132718Skan if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) 658132718Skan return 1; 659132718Skan 660132718Skan if (ctx == NULL) 661132718Skan { 662132718Skan ctx = new_ctx = BN_CTX_new(); 663132718Skan if (ctx == NULL) 664132718Skan return 0; 665132718Skan } 666132718Skan 667132718Skan BN_CTX_start(ctx); 668132718Skan x = BN_CTX_get(ctx); 669132718Skan y = BN_CTX_get(ctx); 670132718Skan if (y == NULL) goto err; 671132718Skan 672132718Skan if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx)) goto err; 673132718Skan if (!BN_copy(&point->X, x)) goto err; 674132718Skan if (!BN_copy(&point->Y, y)) goto err; 675132718Skan if (!BN_one(&point->Z)) goto err; 676132718Skan 677132718Skan ret = 1; 678132718Skan 679132718Skan err: 680132718Skan if (ctx) BN_CTX_end(ctx); 681132718Skan if (new_ctx) BN_CTX_free(new_ctx); 682132718Skan return ret; 683132718Skan } 684132718Skan 685169689Skan 686132718Skan/* Forces each of the EC_POINTs in the given array to use affine coordinates. */ 687132718Skanint ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx) 688132718Skan { 689169689Skan size_t i; 690169689Skan 691169689Skan for (i = 0; i < num; i++) 692169689Skan { 693169689Skan if (!group->meth->make_affine(group, points[i], ctx)) return 0; 694169689Skan } 695169689Skan 696169689Skan return 1; 697132718Skan } 698132718Skan 699132718Skan 700169689Skan/* Wrapper to simple binary polynomial field multiplication implementation. */ 701169689Skanint ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 702132718Skan { 703132718Skan return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx); 704132718Skan } 705132718Skan 706169689Skan 707169689Skan/* Wrapper to simple binary polynomial field squaring implementation. */ 708132718Skanint ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) 709132718Skan { 710132718Skan return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx); 711132718Skan } 712132718Skan 713132718Skan 714132718Skan/* Wrapper to simple binary polynomial field division implementation. */ 715132718Skanint ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 716132718Skan { 717132718Skan return BN_GF2m_mod_div(r, a, b, &group->field, ctx); 718132718Skan } 719132718Skan 720169689Skan#endif 721132718Skan