1109998Smarkm/* crypto/ec/ecp_smpl.c */ 2296465Sdelphij/* 3296465Sdelphij * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> 4296465Sdelphij * for the OpenSSL project. Includes code written by Bodo Moeller for the 5296465Sdelphij * OpenSSL project. 6296465Sdelphij */ 7109998Smarkm/* ==================================================================== 8160814Ssimon * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved. 9109998Smarkm * 10109998Smarkm * Redistribution and use in source and binary forms, with or without 11109998Smarkm * modification, are permitted provided that the following conditions 12109998Smarkm * are met: 13109998Smarkm * 14109998Smarkm * 1. Redistributions of source code must retain the above copyright 15296465Sdelphij * notice, this list of conditions and the following disclaimer. 16109998Smarkm * 17109998Smarkm * 2. Redistributions in binary form must reproduce the above copyright 18109998Smarkm * notice, this list of conditions and the following disclaimer in 19109998Smarkm * the documentation and/or other materials provided with the 20109998Smarkm * distribution. 21109998Smarkm * 22109998Smarkm * 3. All advertising materials mentioning features or use of this 23109998Smarkm * software must display the following acknowledgment: 24109998Smarkm * "This product includes software developed by the OpenSSL Project 25109998Smarkm * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 26109998Smarkm * 27109998Smarkm * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 28109998Smarkm * endorse or promote products derived from this software without 29109998Smarkm * prior written permission. For written permission, please contact 30109998Smarkm * openssl-core@openssl.org. 31109998Smarkm * 32109998Smarkm * 5. Products derived from this software may not be called "OpenSSL" 33109998Smarkm * nor may "OpenSSL" appear in their names without prior written 34109998Smarkm * permission of the OpenSSL Project. 35109998Smarkm * 36109998Smarkm * 6. Redistributions of any form whatsoever must retain the following 37109998Smarkm * acknowledgment: 38109998Smarkm * "This product includes software developed by the OpenSSL Project 39109998Smarkm * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 40109998Smarkm * 41109998Smarkm * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 42109998Smarkm * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43109998Smarkm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 44109998Smarkm * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 45109998Smarkm * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 46109998Smarkm * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 47109998Smarkm * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 48109998Smarkm * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 49109998Smarkm * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 50109998Smarkm * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 51109998Smarkm * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 52109998Smarkm * OF THE POSSIBILITY OF SUCH DAMAGE. 53109998Smarkm * ==================================================================== 54109998Smarkm * 55109998Smarkm * This product includes cryptographic software written by Eric Young 56109998Smarkm * (eay@cryptsoft.com). This product includes software written by Tim 57109998Smarkm * Hudson (tjh@cryptsoft.com). 58109998Smarkm * 59109998Smarkm */ 60160814Ssimon/* ==================================================================== 61160814Ssimon * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 62160814Ssimon * Portions of this software developed by SUN MICROSYSTEMS, INC., 63160814Ssimon * and contributed to the OpenSSL project. 64160814Ssimon */ 65109998Smarkm 66109998Smarkm#include <openssl/err.h> 67160814Ssimon#include <openssl/symhacks.h> 68109998Smarkm 69109998Smarkm#include "ec_lcl.h" 70109998Smarkm 71109998Smarkmconst EC_METHOD *EC_GFp_simple_method(void) 72296465Sdelphij{ 73296465Sdelphij static const EC_METHOD ret = { 74296465Sdelphij NID_X9_62_prime_field, 75296465Sdelphij ec_GFp_simple_group_init, 76296465Sdelphij ec_GFp_simple_group_finish, 77296465Sdelphij ec_GFp_simple_group_clear_finish, 78296465Sdelphij ec_GFp_simple_group_copy, 79296465Sdelphij ec_GFp_simple_group_set_curve, 80296465Sdelphij ec_GFp_simple_group_get_curve, 81296465Sdelphij ec_GFp_simple_group_get_degree, 82296465Sdelphij ec_GFp_simple_group_check_discriminant, 83296465Sdelphij ec_GFp_simple_point_init, 84296465Sdelphij ec_GFp_simple_point_finish, 85296465Sdelphij ec_GFp_simple_point_clear_finish, 86296465Sdelphij ec_GFp_simple_point_copy, 87296465Sdelphij ec_GFp_simple_point_set_to_infinity, 88296465Sdelphij ec_GFp_simple_set_Jprojective_coordinates_GFp, 89296465Sdelphij ec_GFp_simple_get_Jprojective_coordinates_GFp, 90296465Sdelphij ec_GFp_simple_point_set_affine_coordinates, 91296465Sdelphij ec_GFp_simple_point_get_affine_coordinates, 92296465Sdelphij ec_GFp_simple_set_compressed_coordinates, 93296465Sdelphij ec_GFp_simple_point2oct, 94296465Sdelphij ec_GFp_simple_oct2point, 95296465Sdelphij ec_GFp_simple_add, 96296465Sdelphij ec_GFp_simple_dbl, 97296465Sdelphij ec_GFp_simple_invert, 98296465Sdelphij ec_GFp_simple_is_at_infinity, 99296465Sdelphij ec_GFp_simple_is_on_curve, 100296465Sdelphij ec_GFp_simple_cmp, 101296465Sdelphij ec_GFp_simple_make_affine, 102296465Sdelphij ec_GFp_simple_points_make_affine, 103296465Sdelphij 0 /* mul */ , 104296465Sdelphij 0 /* precompute_mult */ , 105296465Sdelphij 0 /* have_precompute_mult */ , 106296465Sdelphij ec_GFp_simple_field_mul, 107296465Sdelphij ec_GFp_simple_field_sqr, 108296465Sdelphij 0 /* field_div */ , 109296465Sdelphij 0 /* field_encode */ , 110296465Sdelphij 0 /* field_decode */ , 111296465Sdelphij 0 /* field_set_to_one */ 112296465Sdelphij }; 113109998Smarkm 114296465Sdelphij return &ret; 115296465Sdelphij} 116109998Smarkm 117296465Sdelphij/* 118296465Sdelphij * Most method functions in this file are designed to work with 119160814Ssimon * non-trivial representations of field elements if necessary 120160814Ssimon * (see ecp_mont.c): while standard modular addition and subtraction 121160814Ssimon * are used, the field_mul and field_sqr methods will be used for 122160814Ssimon * multiplication, and field_encode and field_decode (if defined) 123160814Ssimon * will be used for converting between representations. 124296465Sdelphij * 125160814Ssimon * Functions ec_GFp_simple_points_make_affine() and 126160814Ssimon * ec_GFp_simple_point_get_affine_coordinates() specifically assume 127160814Ssimon * that if a non-trivial representation is used, it is a Montgomery 128160814Ssimon * representation (i.e. 'encoding' means multiplying by some factor R). 129160814Ssimon */ 130160814Ssimon 131109998Smarkmint ec_GFp_simple_group_init(EC_GROUP *group) 132296465Sdelphij{ 133296465Sdelphij BN_init(&group->field); 134296465Sdelphij BN_init(&group->a); 135296465Sdelphij BN_init(&group->b); 136296465Sdelphij group->a_is_minus3 = 0; 137296465Sdelphij return 1; 138296465Sdelphij} 139109998Smarkm 140109998Smarkmvoid ec_GFp_simple_group_finish(EC_GROUP *group) 141296465Sdelphij{ 142296465Sdelphij BN_free(&group->field); 143296465Sdelphij BN_free(&group->a); 144296465Sdelphij BN_free(&group->b); 145296465Sdelphij} 146109998Smarkm 147109998Smarkmvoid ec_GFp_simple_group_clear_finish(EC_GROUP *group) 148296465Sdelphij{ 149296465Sdelphij BN_clear_free(&group->field); 150296465Sdelphij BN_clear_free(&group->a); 151296465Sdelphij BN_clear_free(&group->b); 152296465Sdelphij} 153109998Smarkm 154109998Smarkmint ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) 155296465Sdelphij{ 156296465Sdelphij if (!BN_copy(&dest->field, &src->field)) 157296465Sdelphij return 0; 158296465Sdelphij if (!BN_copy(&dest->a, &src->a)) 159296465Sdelphij return 0; 160296465Sdelphij if (!BN_copy(&dest->b, &src->b)) 161296465Sdelphij return 0; 162109998Smarkm 163296465Sdelphij dest->a_is_minus3 = src->a_is_minus3; 164109998Smarkm 165296465Sdelphij return 1; 166296465Sdelphij} 167109998Smarkm 168160814Ssimonint ec_GFp_simple_group_set_curve(EC_GROUP *group, 169296465Sdelphij const BIGNUM *p, const BIGNUM *a, 170296465Sdelphij const BIGNUM *b, BN_CTX *ctx) 171296465Sdelphij{ 172296465Sdelphij int ret = 0; 173296465Sdelphij BN_CTX *new_ctx = NULL; 174296465Sdelphij BIGNUM *tmp_a; 175109998Smarkm 176296465Sdelphij /* p must be a prime > 3 */ 177296465Sdelphij if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) { 178296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD); 179296465Sdelphij return 0; 180296465Sdelphij } 181109998Smarkm 182296465Sdelphij if (ctx == NULL) { 183296465Sdelphij ctx = new_ctx = BN_CTX_new(); 184296465Sdelphij if (ctx == NULL) 185296465Sdelphij return 0; 186296465Sdelphij } 187109998Smarkm 188296465Sdelphij BN_CTX_start(ctx); 189296465Sdelphij tmp_a = BN_CTX_get(ctx); 190296465Sdelphij if (tmp_a == NULL) 191296465Sdelphij goto err; 192109998Smarkm 193296465Sdelphij /* group->field */ 194296465Sdelphij if (!BN_copy(&group->field, p)) 195296465Sdelphij goto err; 196296465Sdelphij BN_set_negative(&group->field, 0); 197109998Smarkm 198296465Sdelphij /* group->a */ 199296465Sdelphij if (!BN_nnmod(tmp_a, a, p, ctx)) 200296465Sdelphij goto err; 201296465Sdelphij if (group->meth->field_encode) { 202296465Sdelphij if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) 203296465Sdelphij goto err; 204296465Sdelphij } else if (!BN_copy(&group->a, tmp_a)) 205296465Sdelphij goto err; 206109998Smarkm 207296465Sdelphij /* group->b */ 208296465Sdelphij if (!BN_nnmod(&group->b, b, p, ctx)) 209296465Sdelphij goto err; 210296465Sdelphij if (group->meth->field_encode) 211296465Sdelphij if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) 212296465Sdelphij goto err; 213296465Sdelphij 214296465Sdelphij /* group->a_is_minus3 */ 215296465Sdelphij if (!BN_add_word(tmp_a, 3)) 216296465Sdelphij goto err; 217296465Sdelphij group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field)); 218296465Sdelphij 219296465Sdelphij ret = 1; 220296465Sdelphij 221109998Smarkm err: 222296465Sdelphij BN_CTX_end(ctx); 223296465Sdelphij if (new_ctx != NULL) 224296465Sdelphij BN_CTX_free(new_ctx); 225296465Sdelphij return ret; 226296465Sdelphij} 227109998Smarkm 228296465Sdelphijint ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, 229296465Sdelphij BIGNUM *b, BN_CTX *ctx) 230296465Sdelphij{ 231296465Sdelphij int ret = 0; 232296465Sdelphij BN_CTX *new_ctx = NULL; 233109998Smarkm 234296465Sdelphij if (p != NULL) { 235296465Sdelphij if (!BN_copy(p, &group->field)) 236296465Sdelphij return 0; 237296465Sdelphij } 238109998Smarkm 239296465Sdelphij if (a != NULL || b != NULL) { 240296465Sdelphij if (group->meth->field_decode) { 241296465Sdelphij if (ctx == NULL) { 242296465Sdelphij ctx = new_ctx = BN_CTX_new(); 243296465Sdelphij if (ctx == NULL) 244296465Sdelphij return 0; 245296465Sdelphij } 246296465Sdelphij if (a != NULL) { 247296465Sdelphij if (!group->meth->field_decode(group, a, &group->a, ctx)) 248296465Sdelphij goto err; 249296465Sdelphij } 250296465Sdelphij if (b != NULL) { 251296465Sdelphij if (!group->meth->field_decode(group, b, &group->b, ctx)) 252296465Sdelphij goto err; 253296465Sdelphij } 254296465Sdelphij } else { 255296465Sdelphij if (a != NULL) { 256296465Sdelphij if (!BN_copy(a, &group->a)) 257296465Sdelphij goto err; 258296465Sdelphij } 259296465Sdelphij if (b != NULL) { 260296465Sdelphij if (!BN_copy(b, &group->b)) 261296465Sdelphij goto err; 262296465Sdelphij } 263296465Sdelphij } 264296465Sdelphij } 265296465Sdelphij 266296465Sdelphij ret = 1; 267296465Sdelphij 268109998Smarkm err: 269296465Sdelphij if (new_ctx) 270296465Sdelphij BN_CTX_free(new_ctx); 271296465Sdelphij return ret; 272296465Sdelphij} 273109998Smarkm 274160814Ssimonint ec_GFp_simple_group_get_degree(const EC_GROUP *group) 275296465Sdelphij{ 276296465Sdelphij return BN_num_bits(&group->field); 277296465Sdelphij} 278109998Smarkm 279160814Ssimonint ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx) 280296465Sdelphij{ 281296465Sdelphij int ret = 0; 282296465Sdelphij BIGNUM *a, *b, *order, *tmp_1, *tmp_2; 283296465Sdelphij const BIGNUM *p = &group->field; 284296465Sdelphij BN_CTX *new_ctx = NULL; 285160814Ssimon 286296465Sdelphij if (ctx == NULL) { 287296465Sdelphij ctx = new_ctx = BN_CTX_new(); 288296465Sdelphij if (ctx == NULL) { 289296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, 290296465Sdelphij ERR_R_MALLOC_FAILURE); 291296465Sdelphij goto err; 292296465Sdelphij } 293296465Sdelphij } 294296465Sdelphij BN_CTX_start(ctx); 295296465Sdelphij a = BN_CTX_get(ctx); 296296465Sdelphij b = BN_CTX_get(ctx); 297296465Sdelphij tmp_1 = BN_CTX_get(ctx); 298296465Sdelphij tmp_2 = BN_CTX_get(ctx); 299296465Sdelphij order = BN_CTX_get(ctx); 300296465Sdelphij if (order == NULL) 301296465Sdelphij goto err; 302109998Smarkm 303296465Sdelphij if (group->meth->field_decode) { 304296465Sdelphij if (!group->meth->field_decode(group, a, &group->a, ctx)) 305296465Sdelphij goto err; 306296465Sdelphij if (!group->meth->field_decode(group, b, &group->b, ctx)) 307296465Sdelphij goto err; 308296465Sdelphij } else { 309296465Sdelphij if (!BN_copy(a, &group->a)) 310296465Sdelphij goto err; 311296465Sdelphij if (!BN_copy(b, &group->b)) 312296465Sdelphij goto err; 313296465Sdelphij } 314109998Smarkm 315296465Sdelphij /*- 316296465Sdelphij * check the discriminant: 317296465Sdelphij * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p) 318296465Sdelphij * 0 =< a, b < p 319296465Sdelphij */ 320296465Sdelphij if (BN_is_zero(a)) { 321296465Sdelphij if (BN_is_zero(b)) 322296465Sdelphij goto err; 323296465Sdelphij } else if (!BN_is_zero(b)) { 324296465Sdelphij if (!BN_mod_sqr(tmp_1, a, p, ctx)) 325296465Sdelphij goto err; 326296465Sdelphij if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) 327296465Sdelphij goto err; 328296465Sdelphij if (!BN_lshift(tmp_1, tmp_2, 2)) 329296465Sdelphij goto err; 330296465Sdelphij /* tmp_1 = 4*a^3 */ 331109998Smarkm 332296465Sdelphij if (!BN_mod_sqr(tmp_2, b, p, ctx)) 333296465Sdelphij goto err; 334296465Sdelphij if (!BN_mul_word(tmp_2, 27)) 335296465Sdelphij goto err; 336296465Sdelphij /* tmp_2 = 27*b^2 */ 337109998Smarkm 338296465Sdelphij if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) 339296465Sdelphij goto err; 340296465Sdelphij if (BN_is_zero(a)) 341296465Sdelphij goto err; 342296465Sdelphij } 343296465Sdelphij ret = 1; 344109998Smarkm 345296465Sdelphij err: 346296465Sdelphij if (ctx != NULL) 347296465Sdelphij BN_CTX_end(ctx); 348296465Sdelphij if (new_ctx != NULL) 349296465Sdelphij BN_CTX_free(new_ctx); 350296465Sdelphij return ret; 351296465Sdelphij} 352109998Smarkm 353109998Smarkmint ec_GFp_simple_point_init(EC_POINT *point) 354296465Sdelphij{ 355296465Sdelphij BN_init(&point->X); 356296465Sdelphij BN_init(&point->Y); 357296465Sdelphij BN_init(&point->Z); 358296465Sdelphij point->Z_is_one = 0; 359109998Smarkm 360296465Sdelphij return 1; 361296465Sdelphij} 362109998Smarkm 363109998Smarkmvoid ec_GFp_simple_point_finish(EC_POINT *point) 364296465Sdelphij{ 365296465Sdelphij BN_free(&point->X); 366296465Sdelphij BN_free(&point->Y); 367296465Sdelphij BN_free(&point->Z); 368296465Sdelphij} 369109998Smarkm 370109998Smarkmvoid ec_GFp_simple_point_clear_finish(EC_POINT *point) 371296465Sdelphij{ 372296465Sdelphij BN_clear_free(&point->X); 373296465Sdelphij BN_clear_free(&point->Y); 374296465Sdelphij BN_clear_free(&point->Z); 375296465Sdelphij point->Z_is_one = 0; 376296465Sdelphij} 377109998Smarkm 378109998Smarkmint ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) 379296465Sdelphij{ 380296465Sdelphij if (!BN_copy(&dest->X, &src->X)) 381296465Sdelphij return 0; 382296465Sdelphij if (!BN_copy(&dest->Y, &src->Y)) 383296465Sdelphij return 0; 384296465Sdelphij if (!BN_copy(&dest->Z, &src->Z)) 385296465Sdelphij return 0; 386296465Sdelphij dest->Z_is_one = src->Z_is_one; 387109998Smarkm 388296465Sdelphij return 1; 389296465Sdelphij} 390109998Smarkm 391296465Sdelphijint ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, 392296465Sdelphij EC_POINT *point) 393296465Sdelphij{ 394296465Sdelphij point->Z_is_one = 0; 395296465Sdelphij BN_zero(&point->Z); 396296465Sdelphij return 1; 397296465Sdelphij} 398109998Smarkm 399296465Sdelphijint ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, 400296465Sdelphij EC_POINT *point, 401296465Sdelphij const BIGNUM *x, 402296465Sdelphij const BIGNUM *y, 403296465Sdelphij const BIGNUM *z, 404296465Sdelphij BN_CTX *ctx) 405296465Sdelphij{ 406296465Sdelphij BN_CTX *new_ctx = NULL; 407296465Sdelphij int ret = 0; 408109998Smarkm 409296465Sdelphij if (ctx == NULL) { 410296465Sdelphij ctx = new_ctx = BN_CTX_new(); 411296465Sdelphij if (ctx == NULL) 412296465Sdelphij return 0; 413296465Sdelphij } 414109998Smarkm 415296465Sdelphij if (x != NULL) { 416296465Sdelphij if (!BN_nnmod(&point->X, x, &group->field, ctx)) 417296465Sdelphij goto err; 418296465Sdelphij if (group->meth->field_encode) { 419296465Sdelphij if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) 420296465Sdelphij goto err; 421296465Sdelphij } 422296465Sdelphij } 423109998Smarkm 424296465Sdelphij if (y != NULL) { 425296465Sdelphij if (!BN_nnmod(&point->Y, y, &group->field, ctx)) 426296465Sdelphij goto err; 427296465Sdelphij if (group->meth->field_encode) { 428296465Sdelphij if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) 429296465Sdelphij goto err; 430296465Sdelphij } 431296465Sdelphij } 432109998Smarkm 433296465Sdelphij if (z != NULL) { 434296465Sdelphij int Z_is_one; 435296465Sdelphij 436296465Sdelphij if (!BN_nnmod(&point->Z, z, &group->field, ctx)) 437296465Sdelphij goto err; 438296465Sdelphij Z_is_one = BN_is_one(&point->Z); 439296465Sdelphij if (group->meth->field_encode) { 440296465Sdelphij if (Z_is_one && (group->meth->field_set_to_one != 0)) { 441296465Sdelphij if (!group->meth->field_set_to_one(group, &point->Z, ctx)) 442296465Sdelphij goto err; 443296465Sdelphij } else { 444296465Sdelphij if (!group-> 445296465Sdelphij meth->field_encode(group, &point->Z, &point->Z, ctx)) 446296465Sdelphij goto err; 447296465Sdelphij } 448296465Sdelphij } 449296465Sdelphij point->Z_is_one = Z_is_one; 450296465Sdelphij } 451296465Sdelphij 452296465Sdelphij ret = 1; 453296465Sdelphij 454109998Smarkm err: 455296465Sdelphij if (new_ctx != NULL) 456296465Sdelphij BN_CTX_free(new_ctx); 457296465Sdelphij return ret; 458296465Sdelphij} 459109998Smarkm 460296465Sdelphijint ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, 461296465Sdelphij const EC_POINT *point, 462296465Sdelphij BIGNUM *x, BIGNUM *y, 463296465Sdelphij BIGNUM *z, BN_CTX *ctx) 464296465Sdelphij{ 465296465Sdelphij BN_CTX *new_ctx = NULL; 466296465Sdelphij int ret = 0; 467109998Smarkm 468296465Sdelphij if (group->meth->field_decode != 0) { 469296465Sdelphij if (ctx == NULL) { 470296465Sdelphij ctx = new_ctx = BN_CTX_new(); 471296465Sdelphij if (ctx == NULL) 472296465Sdelphij return 0; 473296465Sdelphij } 474109998Smarkm 475296465Sdelphij if (x != NULL) { 476296465Sdelphij if (!group->meth->field_decode(group, x, &point->X, ctx)) 477296465Sdelphij goto err; 478296465Sdelphij } 479296465Sdelphij if (y != NULL) { 480296465Sdelphij if (!group->meth->field_decode(group, y, &point->Y, ctx)) 481296465Sdelphij goto err; 482296465Sdelphij } 483296465Sdelphij if (z != NULL) { 484296465Sdelphij if (!group->meth->field_decode(group, z, &point->Z, ctx)) 485296465Sdelphij goto err; 486296465Sdelphij } 487296465Sdelphij } else { 488296465Sdelphij if (x != NULL) { 489296465Sdelphij if (!BN_copy(x, &point->X)) 490296465Sdelphij goto err; 491296465Sdelphij } 492296465Sdelphij if (y != NULL) { 493296465Sdelphij if (!BN_copy(y, &point->Y)) 494296465Sdelphij goto err; 495296465Sdelphij } 496296465Sdelphij if (z != NULL) { 497296465Sdelphij if (!BN_copy(z, &point->Z)) 498296465Sdelphij goto err; 499296465Sdelphij } 500296465Sdelphij } 501109998Smarkm 502296465Sdelphij ret = 1; 503296465Sdelphij 504109998Smarkm err: 505296465Sdelphij if (new_ctx != NULL) 506296465Sdelphij BN_CTX_free(new_ctx); 507296465Sdelphij return ret; 508296465Sdelphij} 509109998Smarkm 510296465Sdelphijint ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, 511296465Sdelphij EC_POINT *point, 512296465Sdelphij const BIGNUM *x, 513296465Sdelphij const BIGNUM *y, BN_CTX *ctx) 514296465Sdelphij{ 515296465Sdelphij if (x == NULL || y == NULL) { 516296465Sdelphij /* 517296465Sdelphij * unlike for projective coordinates, we do not tolerate this 518296465Sdelphij */ 519296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, 520296465Sdelphij ERR_R_PASSED_NULL_PARAMETER); 521296465Sdelphij return 0; 522296465Sdelphij } 523109998Smarkm 524296465Sdelphij return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, 525296465Sdelphij BN_value_one(), ctx); 526296465Sdelphij} 527109998Smarkm 528296465Sdelphijint ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, 529296465Sdelphij const EC_POINT *point, 530296465Sdelphij BIGNUM *x, BIGNUM *y, 531296465Sdelphij BN_CTX *ctx) 532296465Sdelphij{ 533296465Sdelphij BN_CTX *new_ctx = NULL; 534296465Sdelphij BIGNUM *Z, *Z_1, *Z_2, *Z_3; 535296465Sdelphij const BIGNUM *Z_; 536296465Sdelphij int ret = 0; 537109998Smarkm 538296465Sdelphij if (EC_POINT_is_at_infinity(group, point)) { 539296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, 540296465Sdelphij EC_R_POINT_AT_INFINITY); 541296465Sdelphij return 0; 542296465Sdelphij } 543109998Smarkm 544296465Sdelphij if (ctx == NULL) { 545296465Sdelphij ctx = new_ctx = BN_CTX_new(); 546296465Sdelphij if (ctx == NULL) 547296465Sdelphij return 0; 548296465Sdelphij } 549109998Smarkm 550296465Sdelphij BN_CTX_start(ctx); 551296465Sdelphij Z = BN_CTX_get(ctx); 552296465Sdelphij Z_1 = BN_CTX_get(ctx); 553296465Sdelphij Z_2 = BN_CTX_get(ctx); 554296465Sdelphij Z_3 = BN_CTX_get(ctx); 555296465Sdelphij if (Z_3 == NULL) 556296465Sdelphij goto err; 557109998Smarkm 558296465Sdelphij /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */ 559109998Smarkm 560296465Sdelphij if (group->meth->field_decode) { 561296465Sdelphij if (!group->meth->field_decode(group, Z, &point->Z, ctx)) 562296465Sdelphij goto err; 563296465Sdelphij Z_ = Z; 564296465Sdelphij } else { 565296465Sdelphij Z_ = &point->Z; 566296465Sdelphij } 567109998Smarkm 568296465Sdelphij if (BN_is_one(Z_)) { 569296465Sdelphij if (group->meth->field_decode) { 570296465Sdelphij if (x != NULL) { 571296465Sdelphij if (!group->meth->field_decode(group, x, &point->X, ctx)) 572296465Sdelphij goto err; 573296465Sdelphij } 574296465Sdelphij if (y != NULL) { 575296465Sdelphij if (!group->meth->field_decode(group, y, &point->Y, ctx)) 576296465Sdelphij goto err; 577296465Sdelphij } 578296465Sdelphij } else { 579296465Sdelphij if (x != NULL) { 580296465Sdelphij if (!BN_copy(x, &point->X)) 581296465Sdelphij goto err; 582296465Sdelphij } 583296465Sdelphij if (y != NULL) { 584296465Sdelphij if (!BN_copy(y, &point->Y)) 585296465Sdelphij goto err; 586296465Sdelphij } 587296465Sdelphij } 588296465Sdelphij } else { 589296465Sdelphij if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx)) { 590296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, 591296465Sdelphij ERR_R_BN_LIB); 592296465Sdelphij goto err; 593296465Sdelphij } 594109998Smarkm 595296465Sdelphij if (group->meth->field_encode == 0) { 596296465Sdelphij /* field_sqr works on standard representation */ 597296465Sdelphij if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) 598296465Sdelphij goto err; 599296465Sdelphij } else { 600296465Sdelphij if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) 601296465Sdelphij goto err; 602296465Sdelphij } 603160814Ssimon 604296465Sdelphij if (x != NULL) { 605296465Sdelphij /* 606296465Sdelphij * in the Montgomery case, field_mul will cancel out Montgomery 607296465Sdelphij * factor in X: 608296465Sdelphij */ 609296465Sdelphij if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) 610296465Sdelphij goto err; 611296465Sdelphij } 612109998Smarkm 613296465Sdelphij if (y != NULL) { 614296465Sdelphij if (group->meth->field_encode == 0) { 615296465Sdelphij /* 616296465Sdelphij * field_mul works on standard representation 617296465Sdelphij */ 618296465Sdelphij if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) 619296465Sdelphij goto err; 620296465Sdelphij } else { 621296465Sdelphij if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) 622296465Sdelphij goto err; 623296465Sdelphij } 624109998Smarkm 625296465Sdelphij /* 626296465Sdelphij * in the Montgomery case, field_mul will cancel out Montgomery 627296465Sdelphij * factor in Y: 628296465Sdelphij */ 629296465Sdelphij if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) 630296465Sdelphij goto err; 631296465Sdelphij } 632296465Sdelphij } 633296465Sdelphij 634296465Sdelphij ret = 1; 635296465Sdelphij 636109998Smarkm err: 637296465Sdelphij BN_CTX_end(ctx); 638296465Sdelphij if (new_ctx != NULL) 639296465Sdelphij BN_CTX_free(new_ctx); 640296465Sdelphij return ret; 641296465Sdelphij} 642109998Smarkm 643296465Sdelphijint ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, 644296465Sdelphij EC_POINT *point, 645296465Sdelphij const BIGNUM *x_, int y_bit, 646296465Sdelphij BN_CTX *ctx) 647296465Sdelphij{ 648296465Sdelphij BN_CTX *new_ctx = NULL; 649296465Sdelphij BIGNUM *tmp1, *tmp2, *x, *y; 650296465Sdelphij int ret = 0; 651109998Smarkm 652296465Sdelphij /* clear error queue */ 653296465Sdelphij ERR_clear_error(); 654109998Smarkm 655296465Sdelphij if (ctx == NULL) { 656296465Sdelphij ctx = new_ctx = BN_CTX_new(); 657296465Sdelphij if (ctx == NULL) 658296465Sdelphij return 0; 659296465Sdelphij } 660160814Ssimon 661296465Sdelphij y_bit = (y_bit != 0); 662109998Smarkm 663296465Sdelphij BN_CTX_start(ctx); 664296465Sdelphij tmp1 = BN_CTX_get(ctx); 665296465Sdelphij tmp2 = BN_CTX_get(ctx); 666296465Sdelphij x = BN_CTX_get(ctx); 667296465Sdelphij y = BN_CTX_get(ctx); 668296465Sdelphij if (y == NULL) 669296465Sdelphij goto err; 670109998Smarkm 671296465Sdelphij /*- 672296465Sdelphij * Recover y. We have a Weierstrass equation 673296465Sdelphij * y^2 = x^3 + a*x + b, 674296465Sdelphij * so y is one of the square roots of x^3 + a*x + b. 675296465Sdelphij */ 676109998Smarkm 677296465Sdelphij /* tmp1 := x^3 */ 678296465Sdelphij if (!BN_nnmod(x, x_, &group->field, ctx)) 679296465Sdelphij goto err; 680296465Sdelphij if (group->meth->field_decode == 0) { 681296465Sdelphij /* field_{sqr,mul} work on standard representation */ 682296465Sdelphij if (!group->meth->field_sqr(group, tmp2, x_, ctx)) 683296465Sdelphij goto err; 684296465Sdelphij if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) 685296465Sdelphij goto err; 686296465Sdelphij } else { 687296465Sdelphij if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) 688296465Sdelphij goto err; 689296465Sdelphij if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) 690296465Sdelphij goto err; 691296465Sdelphij } 692109998Smarkm 693296465Sdelphij /* tmp1 := tmp1 + a*x */ 694296465Sdelphij if (group->a_is_minus3) { 695296465Sdelphij if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) 696296465Sdelphij goto err; 697296465Sdelphij if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) 698296465Sdelphij goto err; 699296465Sdelphij if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) 700296465Sdelphij goto err; 701296465Sdelphij } else { 702296465Sdelphij if (group->meth->field_decode) { 703296465Sdelphij if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) 704296465Sdelphij goto err; 705296465Sdelphij if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) 706296465Sdelphij goto err; 707296465Sdelphij } else { 708296465Sdelphij /* field_mul works on standard representation */ 709296465Sdelphij if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) 710296465Sdelphij goto err; 711296465Sdelphij } 712109998Smarkm 713296465Sdelphij if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) 714296465Sdelphij goto err; 715296465Sdelphij } 716109998Smarkm 717296465Sdelphij /* tmp1 := tmp1 + b */ 718296465Sdelphij if (group->meth->field_decode) { 719296465Sdelphij if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) 720296465Sdelphij goto err; 721296465Sdelphij if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) 722296465Sdelphij goto err; 723296465Sdelphij } else { 724296465Sdelphij if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) 725296465Sdelphij goto err; 726296465Sdelphij } 727109998Smarkm 728296465Sdelphij if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) { 729296465Sdelphij unsigned long err = ERR_peek_last_error(); 730109998Smarkm 731296465Sdelphij if (ERR_GET_LIB(err) == ERR_LIB_BN 732296465Sdelphij && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) { 733296465Sdelphij ERR_clear_error(); 734296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 735296465Sdelphij EC_R_INVALID_COMPRESSED_POINT); 736296465Sdelphij } else 737296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 738296465Sdelphij ERR_R_BN_LIB); 739296465Sdelphij goto err; 740296465Sdelphij } 741109998Smarkm 742296465Sdelphij if (y_bit != BN_is_odd(y)) { 743296465Sdelphij if (BN_is_zero(y)) { 744296465Sdelphij int kron; 745109998Smarkm 746296465Sdelphij kron = BN_kronecker(x, &group->field, ctx); 747296465Sdelphij if (kron == -2) 748296465Sdelphij goto err; 749296465Sdelphij 750296465Sdelphij if (kron == 1) 751296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 752296465Sdelphij EC_R_INVALID_COMPRESSION_BIT); 753296465Sdelphij else 754296465Sdelphij /* 755296465Sdelphij * BN_mod_sqrt() should have cought this error (not a square) 756296465Sdelphij */ 757296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 758296465Sdelphij EC_R_INVALID_COMPRESSED_POINT); 759296465Sdelphij goto err; 760296465Sdelphij } 761296465Sdelphij if (!BN_usub(y, &group->field, y)) 762296465Sdelphij goto err; 763296465Sdelphij } 764296465Sdelphij if (y_bit != BN_is_odd(y)) { 765296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 766296465Sdelphij ERR_R_INTERNAL_ERROR); 767296465Sdelphij goto err; 768296465Sdelphij } 769296465Sdelphij 770296465Sdelphij if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) 771296465Sdelphij goto err; 772296465Sdelphij 773296465Sdelphij ret = 1; 774296465Sdelphij 775109998Smarkm err: 776296465Sdelphij BN_CTX_end(ctx); 777296465Sdelphij if (new_ctx != NULL) 778296465Sdelphij BN_CTX_free(new_ctx); 779296465Sdelphij return ret; 780296465Sdelphij} 781109998Smarkm 782296465Sdelphijsize_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, 783296465Sdelphij point_conversion_form_t form, 784296465Sdelphij unsigned char *buf, size_t len, BN_CTX *ctx) 785296465Sdelphij{ 786296465Sdelphij size_t ret; 787296465Sdelphij BN_CTX *new_ctx = NULL; 788296465Sdelphij int used_ctx = 0; 789296465Sdelphij BIGNUM *x, *y; 790296465Sdelphij size_t field_len, i, skip; 791109998Smarkm 792296465Sdelphij if ((form != POINT_CONVERSION_COMPRESSED) 793296465Sdelphij && (form != POINT_CONVERSION_UNCOMPRESSED) 794296465Sdelphij && (form != POINT_CONVERSION_HYBRID)) { 795296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM); 796296465Sdelphij goto err; 797296465Sdelphij } 798109998Smarkm 799296465Sdelphij if (EC_POINT_is_at_infinity(group, point)) { 800296465Sdelphij /* encodes to a single 0 octet */ 801296465Sdelphij if (buf != NULL) { 802296465Sdelphij if (len < 1) { 803296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 804296465Sdelphij return 0; 805296465Sdelphij } 806296465Sdelphij buf[0] = 0; 807296465Sdelphij } 808296465Sdelphij return 1; 809296465Sdelphij } 810109998Smarkm 811296465Sdelphij /* ret := required output buffer length */ 812296465Sdelphij field_len = BN_num_bytes(&group->field); 813296465Sdelphij ret = 814296465Sdelphij (form == 815296465Sdelphij POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 816109998Smarkm 817296465Sdelphij /* if 'buf' is NULL, just return required length */ 818296465Sdelphij if (buf != NULL) { 819296465Sdelphij if (len < ret) { 820296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 821296465Sdelphij goto err; 822296465Sdelphij } 823109998Smarkm 824296465Sdelphij if (ctx == NULL) { 825296465Sdelphij ctx = new_ctx = BN_CTX_new(); 826296465Sdelphij if (ctx == NULL) 827296465Sdelphij return 0; 828296465Sdelphij } 829109998Smarkm 830296465Sdelphij BN_CTX_start(ctx); 831296465Sdelphij used_ctx = 1; 832296465Sdelphij x = BN_CTX_get(ctx); 833296465Sdelphij y = BN_CTX_get(ctx); 834296465Sdelphij if (y == NULL) 835296465Sdelphij goto err; 836109998Smarkm 837296465Sdelphij if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) 838296465Sdelphij goto err; 839109998Smarkm 840296465Sdelphij if ((form == POINT_CONVERSION_COMPRESSED 841296465Sdelphij || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y)) 842296465Sdelphij buf[0] = form + 1; 843296465Sdelphij else 844296465Sdelphij buf[0] = form; 845109998Smarkm 846296465Sdelphij i = 1; 847109998Smarkm 848296465Sdelphij skip = field_len - BN_num_bytes(x); 849296465Sdelphij if (skip > field_len) { 850296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 851296465Sdelphij goto err; 852296465Sdelphij } 853296465Sdelphij while (skip > 0) { 854296465Sdelphij buf[i++] = 0; 855296465Sdelphij skip--; 856296465Sdelphij } 857296465Sdelphij skip = BN_bn2bin(x, buf + i); 858296465Sdelphij i += skip; 859296465Sdelphij if (i != 1 + field_len) { 860296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 861296465Sdelphij goto err; 862296465Sdelphij } 863109998Smarkm 864296465Sdelphij if (form == POINT_CONVERSION_UNCOMPRESSED 865296465Sdelphij || form == POINT_CONVERSION_HYBRID) { 866296465Sdelphij skip = field_len - BN_num_bytes(y); 867296465Sdelphij if (skip > field_len) { 868296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 869296465Sdelphij goto err; 870296465Sdelphij } 871296465Sdelphij while (skip > 0) { 872296465Sdelphij buf[i++] = 0; 873296465Sdelphij skip--; 874296465Sdelphij } 875296465Sdelphij skip = BN_bn2bin(y, buf + i); 876296465Sdelphij i += skip; 877296465Sdelphij } 878109998Smarkm 879296465Sdelphij if (i != ret) { 880296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 881296465Sdelphij goto err; 882296465Sdelphij } 883296465Sdelphij } 884109998Smarkm 885296465Sdelphij if (used_ctx) 886296465Sdelphij BN_CTX_end(ctx); 887296465Sdelphij if (new_ctx != NULL) 888296465Sdelphij BN_CTX_free(new_ctx); 889296465Sdelphij return ret; 890296465Sdelphij 891109998Smarkm err: 892296465Sdelphij if (used_ctx) 893296465Sdelphij BN_CTX_end(ctx); 894296465Sdelphij if (new_ctx != NULL) 895296465Sdelphij BN_CTX_free(new_ctx); 896296465Sdelphij return 0; 897296465Sdelphij} 898109998Smarkm 899109998Smarkmint ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, 900296465Sdelphij const unsigned char *buf, size_t len, BN_CTX *ctx) 901296465Sdelphij{ 902296465Sdelphij point_conversion_form_t form; 903296465Sdelphij int y_bit; 904296465Sdelphij BN_CTX *new_ctx = NULL; 905296465Sdelphij BIGNUM *x, *y; 906296465Sdelphij size_t field_len, enc_len; 907296465Sdelphij int ret = 0; 908109998Smarkm 909296465Sdelphij if (len == 0) { 910296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL); 911296465Sdelphij return 0; 912296465Sdelphij } 913296465Sdelphij form = buf[0]; 914296465Sdelphij y_bit = form & 1; 915296465Sdelphij form = form & ~1U; 916296465Sdelphij if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) 917296465Sdelphij && (form != POINT_CONVERSION_UNCOMPRESSED) 918296465Sdelphij && (form != POINT_CONVERSION_HYBRID)) { 919296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 920296465Sdelphij return 0; 921296465Sdelphij } 922296465Sdelphij if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) { 923296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 924296465Sdelphij return 0; 925296465Sdelphij } 926109998Smarkm 927296465Sdelphij if (form == 0) { 928296465Sdelphij if (len != 1) { 929296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 930296465Sdelphij return 0; 931296465Sdelphij } 932109998Smarkm 933296465Sdelphij return EC_POINT_set_to_infinity(group, point); 934296465Sdelphij } 935109998Smarkm 936296465Sdelphij field_len = BN_num_bytes(&group->field); 937296465Sdelphij enc_len = 938296465Sdelphij (form == 939296465Sdelphij POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 940109998Smarkm 941296465Sdelphij if (len != enc_len) { 942296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 943296465Sdelphij return 0; 944296465Sdelphij } 945109998Smarkm 946296465Sdelphij if (ctx == NULL) { 947296465Sdelphij ctx = new_ctx = BN_CTX_new(); 948296465Sdelphij if (ctx == NULL) 949296465Sdelphij return 0; 950296465Sdelphij } 951109998Smarkm 952296465Sdelphij BN_CTX_start(ctx); 953296465Sdelphij x = BN_CTX_get(ctx); 954296465Sdelphij y = BN_CTX_get(ctx); 955296465Sdelphij if (y == NULL) 956296465Sdelphij goto err; 957109998Smarkm 958296465Sdelphij if (!BN_bin2bn(buf + 1, field_len, x)) 959296465Sdelphij goto err; 960296465Sdelphij if (BN_ucmp(x, &group->field) >= 0) { 961296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 962296465Sdelphij goto err; 963296465Sdelphij } 964109998Smarkm 965296465Sdelphij if (form == POINT_CONVERSION_COMPRESSED) { 966296465Sdelphij if (!EC_POINT_set_compressed_coordinates_GFp 967296465Sdelphij (group, point, x, y_bit, ctx)) 968296465Sdelphij goto err; 969296465Sdelphij } else { 970296465Sdelphij if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) 971296465Sdelphij goto err; 972296465Sdelphij if (BN_ucmp(y, &group->field) >= 0) { 973296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 974296465Sdelphij goto err; 975296465Sdelphij } 976296465Sdelphij if (form == POINT_CONVERSION_HYBRID) { 977296465Sdelphij if (y_bit != BN_is_odd(y)) { 978296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 979296465Sdelphij goto err; 980296465Sdelphij } 981296465Sdelphij } 982109998Smarkm 983296465Sdelphij if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) 984296465Sdelphij goto err; 985296465Sdelphij } 986296465Sdelphij 987296465Sdelphij /* test required by X9.62 */ 988296465Sdelphij if (EC_POINT_is_on_curve(group, point, ctx) <= 0) { 989296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE); 990296465Sdelphij goto err; 991296465Sdelphij } 992296465Sdelphij 993296465Sdelphij ret = 1; 994296465Sdelphij 995109998Smarkm err: 996296465Sdelphij BN_CTX_end(ctx); 997296465Sdelphij if (new_ctx != NULL) 998296465Sdelphij BN_CTX_free(new_ctx); 999296465Sdelphij return ret; 1000296465Sdelphij} 1001109998Smarkm 1002296465Sdelphijint ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 1003296465Sdelphij const EC_POINT *b, BN_CTX *ctx) 1004296465Sdelphij{ 1005296465Sdelphij int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 1006296465Sdelphij const BIGNUM *, BN_CTX *); 1007296465Sdelphij int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1008296465Sdelphij const BIGNUM *p; 1009296465Sdelphij BN_CTX *new_ctx = NULL; 1010296465Sdelphij BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6; 1011296465Sdelphij int ret = 0; 1012109998Smarkm 1013296465Sdelphij if (a == b) 1014296465Sdelphij return EC_POINT_dbl(group, r, a, ctx); 1015296465Sdelphij if (EC_POINT_is_at_infinity(group, a)) 1016296465Sdelphij return EC_POINT_copy(r, b); 1017296465Sdelphij if (EC_POINT_is_at_infinity(group, b)) 1018296465Sdelphij return EC_POINT_copy(r, a); 1019109998Smarkm 1020296465Sdelphij field_mul = group->meth->field_mul; 1021296465Sdelphij field_sqr = group->meth->field_sqr; 1022296465Sdelphij p = &group->field; 1023109998Smarkm 1024296465Sdelphij if (ctx == NULL) { 1025296465Sdelphij ctx = new_ctx = BN_CTX_new(); 1026296465Sdelphij if (ctx == NULL) 1027296465Sdelphij return 0; 1028296465Sdelphij } 1029109998Smarkm 1030296465Sdelphij BN_CTX_start(ctx); 1031296465Sdelphij n0 = BN_CTX_get(ctx); 1032296465Sdelphij n1 = BN_CTX_get(ctx); 1033296465Sdelphij n2 = BN_CTX_get(ctx); 1034296465Sdelphij n3 = BN_CTX_get(ctx); 1035296465Sdelphij n4 = BN_CTX_get(ctx); 1036296465Sdelphij n5 = BN_CTX_get(ctx); 1037296465Sdelphij n6 = BN_CTX_get(ctx); 1038296465Sdelphij if (n6 == NULL) 1039296465Sdelphij goto end; 1040109998Smarkm 1041296465Sdelphij /* 1042296465Sdelphij * Note that in this function we must not read components of 'a' or 'b' 1043296465Sdelphij * once we have written the corresponding components of 'r'. ('r' might 1044296465Sdelphij * be one of 'a' or 'b'.) 1045296465Sdelphij */ 1046109998Smarkm 1047296465Sdelphij /* n1, n2 */ 1048296465Sdelphij if (b->Z_is_one) { 1049296465Sdelphij if (!BN_copy(n1, &a->X)) 1050296465Sdelphij goto end; 1051296465Sdelphij if (!BN_copy(n2, &a->Y)) 1052296465Sdelphij goto end; 1053296465Sdelphij /* n1 = X_a */ 1054296465Sdelphij /* n2 = Y_a */ 1055296465Sdelphij } else { 1056296465Sdelphij if (!field_sqr(group, n0, &b->Z, ctx)) 1057296465Sdelphij goto end; 1058296465Sdelphij if (!field_mul(group, n1, &a->X, n0, ctx)) 1059296465Sdelphij goto end; 1060296465Sdelphij /* n1 = X_a * Z_b^2 */ 1061109998Smarkm 1062296465Sdelphij if (!field_mul(group, n0, n0, &b->Z, ctx)) 1063296465Sdelphij goto end; 1064296465Sdelphij if (!field_mul(group, n2, &a->Y, n0, ctx)) 1065296465Sdelphij goto end; 1066296465Sdelphij /* n2 = Y_a * Z_b^3 */ 1067296465Sdelphij } 1068109998Smarkm 1069296465Sdelphij /* n3, n4 */ 1070296465Sdelphij if (a->Z_is_one) { 1071296465Sdelphij if (!BN_copy(n3, &b->X)) 1072296465Sdelphij goto end; 1073296465Sdelphij if (!BN_copy(n4, &b->Y)) 1074296465Sdelphij goto end; 1075296465Sdelphij /* n3 = X_b */ 1076296465Sdelphij /* n4 = Y_b */ 1077296465Sdelphij } else { 1078296465Sdelphij if (!field_sqr(group, n0, &a->Z, ctx)) 1079296465Sdelphij goto end; 1080296465Sdelphij if (!field_mul(group, n3, &b->X, n0, ctx)) 1081296465Sdelphij goto end; 1082296465Sdelphij /* n3 = X_b * Z_a^2 */ 1083109998Smarkm 1084296465Sdelphij if (!field_mul(group, n0, n0, &a->Z, ctx)) 1085296465Sdelphij goto end; 1086296465Sdelphij if (!field_mul(group, n4, &b->Y, n0, ctx)) 1087296465Sdelphij goto end; 1088296465Sdelphij /* n4 = Y_b * Z_a^3 */ 1089296465Sdelphij } 1090109998Smarkm 1091296465Sdelphij /* n5, n6 */ 1092296465Sdelphij if (!BN_mod_sub_quick(n5, n1, n3, p)) 1093296465Sdelphij goto end; 1094296465Sdelphij if (!BN_mod_sub_quick(n6, n2, n4, p)) 1095296465Sdelphij goto end; 1096296465Sdelphij /* n5 = n1 - n3 */ 1097296465Sdelphij /* n6 = n2 - n4 */ 1098109998Smarkm 1099296465Sdelphij if (BN_is_zero(n5)) { 1100296465Sdelphij if (BN_is_zero(n6)) { 1101296465Sdelphij /* a is the same point as b */ 1102296465Sdelphij BN_CTX_end(ctx); 1103296465Sdelphij ret = EC_POINT_dbl(group, r, a, ctx); 1104296465Sdelphij ctx = NULL; 1105296465Sdelphij goto end; 1106296465Sdelphij } else { 1107296465Sdelphij /* a is the inverse of b */ 1108296465Sdelphij BN_zero(&r->Z); 1109296465Sdelphij r->Z_is_one = 0; 1110296465Sdelphij ret = 1; 1111296465Sdelphij goto end; 1112296465Sdelphij } 1113296465Sdelphij } 1114109998Smarkm 1115296465Sdelphij /* 'n7', 'n8' */ 1116296465Sdelphij if (!BN_mod_add_quick(n1, n1, n3, p)) 1117296465Sdelphij goto end; 1118296465Sdelphij if (!BN_mod_add_quick(n2, n2, n4, p)) 1119296465Sdelphij goto end; 1120296465Sdelphij /* 'n7' = n1 + n3 */ 1121296465Sdelphij /* 'n8' = n2 + n4 */ 1122109998Smarkm 1123296465Sdelphij /* Z_r */ 1124296465Sdelphij if (a->Z_is_one && b->Z_is_one) { 1125296465Sdelphij if (!BN_copy(&r->Z, n5)) 1126296465Sdelphij goto end; 1127296465Sdelphij } else { 1128296465Sdelphij if (a->Z_is_one) { 1129296465Sdelphij if (!BN_copy(n0, &b->Z)) 1130296465Sdelphij goto end; 1131296465Sdelphij } else if (b->Z_is_one) { 1132296465Sdelphij if (!BN_copy(n0, &a->Z)) 1133296465Sdelphij goto end; 1134296465Sdelphij } else { 1135296465Sdelphij if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) 1136296465Sdelphij goto end; 1137296465Sdelphij } 1138296465Sdelphij if (!field_mul(group, &r->Z, n0, n5, ctx)) 1139296465Sdelphij goto end; 1140296465Sdelphij } 1141296465Sdelphij r->Z_is_one = 0; 1142296465Sdelphij /* Z_r = Z_a * Z_b * n5 */ 1143109998Smarkm 1144296465Sdelphij /* X_r */ 1145296465Sdelphij if (!field_sqr(group, n0, n6, ctx)) 1146296465Sdelphij goto end; 1147296465Sdelphij if (!field_sqr(group, n4, n5, ctx)) 1148296465Sdelphij goto end; 1149296465Sdelphij if (!field_mul(group, n3, n1, n4, ctx)) 1150296465Sdelphij goto end; 1151296465Sdelphij if (!BN_mod_sub_quick(&r->X, n0, n3, p)) 1152296465Sdelphij goto end; 1153296465Sdelphij /* X_r = n6^2 - n5^2 * 'n7' */ 1154109998Smarkm 1155296465Sdelphij /* 'n9' */ 1156296465Sdelphij if (!BN_mod_lshift1_quick(n0, &r->X, p)) 1157296465Sdelphij goto end; 1158296465Sdelphij if (!BN_mod_sub_quick(n0, n3, n0, p)) 1159296465Sdelphij goto end; 1160296465Sdelphij /* n9 = n5^2 * 'n7' - 2 * X_r */ 1161109998Smarkm 1162296465Sdelphij /* Y_r */ 1163296465Sdelphij if (!field_mul(group, n0, n0, n6, ctx)) 1164296465Sdelphij goto end; 1165296465Sdelphij if (!field_mul(group, n5, n4, n5, ctx)) 1166296465Sdelphij goto end; /* now n5 is n5^3 */ 1167296465Sdelphij if (!field_mul(group, n1, n2, n5, ctx)) 1168296465Sdelphij goto end; 1169296465Sdelphij if (!BN_mod_sub_quick(n0, n0, n1, p)) 1170296465Sdelphij goto end; 1171296465Sdelphij if (BN_is_odd(n0)) 1172296465Sdelphij if (!BN_add(n0, n0, p)) 1173296465Sdelphij goto end; 1174296465Sdelphij /* now 0 <= n0 < 2*p, and n0 is even */ 1175296465Sdelphij if (!BN_rshift1(&r->Y, n0)) 1176296465Sdelphij goto end; 1177296465Sdelphij /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */ 1178296465Sdelphij 1179296465Sdelphij ret = 1; 1180296465Sdelphij 1181109998Smarkm end: 1182296465Sdelphij if (ctx) /* otherwise we already called BN_CTX_end */ 1183296465Sdelphij BN_CTX_end(ctx); 1184296465Sdelphij if (new_ctx != NULL) 1185296465Sdelphij BN_CTX_free(new_ctx); 1186296465Sdelphij return ret; 1187296465Sdelphij} 1188109998Smarkm 1189296465Sdelphijint ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 1190296465Sdelphij BN_CTX *ctx) 1191296465Sdelphij{ 1192296465Sdelphij int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 1193296465Sdelphij const BIGNUM *, BN_CTX *); 1194296465Sdelphij int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1195296465Sdelphij const BIGNUM *p; 1196296465Sdelphij BN_CTX *new_ctx = NULL; 1197296465Sdelphij BIGNUM *n0, *n1, *n2, *n3; 1198296465Sdelphij int ret = 0; 1199109998Smarkm 1200296465Sdelphij if (EC_POINT_is_at_infinity(group, a)) { 1201296465Sdelphij BN_zero(&r->Z); 1202296465Sdelphij r->Z_is_one = 0; 1203296465Sdelphij return 1; 1204296465Sdelphij } 1205109998Smarkm 1206296465Sdelphij field_mul = group->meth->field_mul; 1207296465Sdelphij field_sqr = group->meth->field_sqr; 1208296465Sdelphij p = &group->field; 1209109998Smarkm 1210296465Sdelphij if (ctx == NULL) { 1211296465Sdelphij ctx = new_ctx = BN_CTX_new(); 1212296465Sdelphij if (ctx == NULL) 1213296465Sdelphij return 0; 1214296465Sdelphij } 1215109998Smarkm 1216296465Sdelphij BN_CTX_start(ctx); 1217296465Sdelphij n0 = BN_CTX_get(ctx); 1218296465Sdelphij n1 = BN_CTX_get(ctx); 1219296465Sdelphij n2 = BN_CTX_get(ctx); 1220296465Sdelphij n3 = BN_CTX_get(ctx); 1221296465Sdelphij if (n3 == NULL) 1222296465Sdelphij goto err; 1223109998Smarkm 1224296465Sdelphij /* 1225296465Sdelphij * Note that in this function we must not read components of 'a' once we 1226296465Sdelphij * have written the corresponding components of 'r'. ('r' might the same 1227296465Sdelphij * as 'a'.) 1228296465Sdelphij */ 1229109998Smarkm 1230296465Sdelphij /* n1 */ 1231296465Sdelphij if (a->Z_is_one) { 1232296465Sdelphij if (!field_sqr(group, n0, &a->X, ctx)) 1233296465Sdelphij goto err; 1234296465Sdelphij if (!BN_mod_lshift1_quick(n1, n0, p)) 1235296465Sdelphij goto err; 1236296465Sdelphij if (!BN_mod_add_quick(n0, n0, n1, p)) 1237296465Sdelphij goto err; 1238296465Sdelphij if (!BN_mod_add_quick(n1, n0, &group->a, p)) 1239296465Sdelphij goto err; 1240296465Sdelphij /* n1 = 3 * X_a^2 + a_curve */ 1241296465Sdelphij } else if (group->a_is_minus3) { 1242296465Sdelphij if (!field_sqr(group, n1, &a->Z, ctx)) 1243296465Sdelphij goto err; 1244296465Sdelphij if (!BN_mod_add_quick(n0, &a->X, n1, p)) 1245296465Sdelphij goto err; 1246296465Sdelphij if (!BN_mod_sub_quick(n2, &a->X, n1, p)) 1247296465Sdelphij goto err; 1248296465Sdelphij if (!field_mul(group, n1, n0, n2, ctx)) 1249296465Sdelphij goto err; 1250296465Sdelphij if (!BN_mod_lshift1_quick(n0, n1, p)) 1251296465Sdelphij goto err; 1252296465Sdelphij if (!BN_mod_add_quick(n1, n0, n1, p)) 1253296465Sdelphij goto err; 1254296465Sdelphij /*- 1255296465Sdelphij * n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) 1256296465Sdelphij * = 3 * X_a^2 - 3 * Z_a^4 1257296465Sdelphij */ 1258296465Sdelphij } else { 1259296465Sdelphij if (!field_sqr(group, n0, &a->X, ctx)) 1260296465Sdelphij goto err; 1261296465Sdelphij if (!BN_mod_lshift1_quick(n1, n0, p)) 1262296465Sdelphij goto err; 1263296465Sdelphij if (!BN_mod_add_quick(n0, n0, n1, p)) 1264296465Sdelphij goto err; 1265296465Sdelphij if (!field_sqr(group, n1, &a->Z, ctx)) 1266296465Sdelphij goto err; 1267296465Sdelphij if (!field_sqr(group, n1, n1, ctx)) 1268296465Sdelphij goto err; 1269296465Sdelphij if (!field_mul(group, n1, n1, &group->a, ctx)) 1270296465Sdelphij goto err; 1271296465Sdelphij if (!BN_mod_add_quick(n1, n1, n0, p)) 1272296465Sdelphij goto err; 1273296465Sdelphij /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */ 1274296465Sdelphij } 1275109998Smarkm 1276296465Sdelphij /* Z_r */ 1277296465Sdelphij if (a->Z_is_one) { 1278296465Sdelphij if (!BN_copy(n0, &a->Y)) 1279296465Sdelphij goto err; 1280296465Sdelphij } else { 1281296465Sdelphij if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) 1282296465Sdelphij goto err; 1283296465Sdelphij } 1284296465Sdelphij if (!BN_mod_lshift1_quick(&r->Z, n0, p)) 1285296465Sdelphij goto err; 1286296465Sdelphij r->Z_is_one = 0; 1287296465Sdelphij /* Z_r = 2 * Y_a * Z_a */ 1288109998Smarkm 1289296465Sdelphij /* n2 */ 1290296465Sdelphij if (!field_sqr(group, n3, &a->Y, ctx)) 1291296465Sdelphij goto err; 1292296465Sdelphij if (!field_mul(group, n2, &a->X, n3, ctx)) 1293296465Sdelphij goto err; 1294296465Sdelphij if (!BN_mod_lshift_quick(n2, n2, 2, p)) 1295296465Sdelphij goto err; 1296296465Sdelphij /* n2 = 4 * X_a * Y_a^2 */ 1297109998Smarkm 1298296465Sdelphij /* X_r */ 1299296465Sdelphij if (!BN_mod_lshift1_quick(n0, n2, p)) 1300296465Sdelphij goto err; 1301296465Sdelphij if (!field_sqr(group, &r->X, n1, ctx)) 1302296465Sdelphij goto err; 1303296465Sdelphij if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) 1304296465Sdelphij goto err; 1305296465Sdelphij /* X_r = n1^2 - 2 * n2 */ 1306109998Smarkm 1307296465Sdelphij /* n3 */ 1308296465Sdelphij if (!field_sqr(group, n0, n3, ctx)) 1309296465Sdelphij goto err; 1310296465Sdelphij if (!BN_mod_lshift_quick(n3, n0, 3, p)) 1311296465Sdelphij goto err; 1312296465Sdelphij /* n3 = 8 * Y_a^4 */ 1313109998Smarkm 1314296465Sdelphij /* Y_r */ 1315296465Sdelphij if (!BN_mod_sub_quick(n0, n2, &r->X, p)) 1316296465Sdelphij goto err; 1317296465Sdelphij if (!field_mul(group, n0, n1, n0, ctx)) 1318296465Sdelphij goto err; 1319296465Sdelphij if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) 1320296465Sdelphij goto err; 1321296465Sdelphij /* Y_r = n1 * (n2 - X_r) - n3 */ 1322296465Sdelphij 1323296465Sdelphij ret = 1; 1324296465Sdelphij 1325109998Smarkm err: 1326296465Sdelphij BN_CTX_end(ctx); 1327296465Sdelphij if (new_ctx != NULL) 1328296465Sdelphij BN_CTX_free(new_ctx); 1329296465Sdelphij return ret; 1330296465Sdelphij} 1331109998Smarkm 1332109998Smarkmint ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 1333296465Sdelphij{ 1334296465Sdelphij if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) 1335296465Sdelphij /* point is its own inverse */ 1336296465Sdelphij return 1; 1337109998Smarkm 1338296465Sdelphij return BN_usub(&point->Y, &group->field, &point->Y); 1339296465Sdelphij} 1340109998Smarkm 1341109998Smarkmint ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) 1342296465Sdelphij{ 1343296465Sdelphij return BN_is_zero(&point->Z); 1344296465Sdelphij} 1345109998Smarkm 1346296465Sdelphijint ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, 1347296465Sdelphij BN_CTX *ctx) 1348296465Sdelphij{ 1349296465Sdelphij int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 1350296465Sdelphij const BIGNUM *, BN_CTX *); 1351296465Sdelphij int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1352296465Sdelphij const BIGNUM *p; 1353296465Sdelphij BN_CTX *new_ctx = NULL; 1354296465Sdelphij BIGNUM *rh, *tmp, *Z4, *Z6; 1355296465Sdelphij int ret = -1; 1356109998Smarkm 1357296465Sdelphij if (EC_POINT_is_at_infinity(group, point)) 1358296465Sdelphij return 1; 1359109998Smarkm 1360296465Sdelphij field_mul = group->meth->field_mul; 1361296465Sdelphij field_sqr = group->meth->field_sqr; 1362296465Sdelphij p = &group->field; 1363109998Smarkm 1364296465Sdelphij if (ctx == NULL) { 1365296465Sdelphij ctx = new_ctx = BN_CTX_new(); 1366296465Sdelphij if (ctx == NULL) 1367296465Sdelphij return -1; 1368296465Sdelphij } 1369109998Smarkm 1370296465Sdelphij BN_CTX_start(ctx); 1371296465Sdelphij rh = BN_CTX_get(ctx); 1372296465Sdelphij tmp = BN_CTX_get(ctx); 1373296465Sdelphij Z4 = BN_CTX_get(ctx); 1374296465Sdelphij Z6 = BN_CTX_get(ctx); 1375296465Sdelphij if (Z6 == NULL) 1376296465Sdelphij goto err; 1377109998Smarkm 1378296465Sdelphij /*- 1379296465Sdelphij * We have a curve defined by a Weierstrass equation 1380296465Sdelphij * y^2 = x^3 + a*x + b. 1381296465Sdelphij * The point to consider is given in Jacobian projective coordinates 1382296465Sdelphij * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). 1383296465Sdelphij * Substituting this and multiplying by Z^6 transforms the above equation into 1384296465Sdelphij * Y^2 = X^3 + a*X*Z^4 + b*Z^6. 1385296465Sdelphij * To test this, we add up the right-hand side in 'rh'. 1386296465Sdelphij */ 1387109998Smarkm 1388296465Sdelphij /* rh := X^2 */ 1389296465Sdelphij if (!field_sqr(group, rh, &point->X, ctx)) 1390296465Sdelphij goto err; 1391109998Smarkm 1392296465Sdelphij if (!point->Z_is_one) { 1393296465Sdelphij if (!field_sqr(group, tmp, &point->Z, ctx)) 1394296465Sdelphij goto err; 1395296465Sdelphij if (!field_sqr(group, Z4, tmp, ctx)) 1396296465Sdelphij goto err; 1397296465Sdelphij if (!field_mul(group, Z6, Z4, tmp, ctx)) 1398296465Sdelphij goto err; 1399109998Smarkm 1400296465Sdelphij /* rh := (rh + a*Z^4)*X */ 1401296465Sdelphij if (group->a_is_minus3) { 1402296465Sdelphij if (!BN_mod_lshift1_quick(tmp, Z4, p)) 1403296465Sdelphij goto err; 1404296465Sdelphij if (!BN_mod_add_quick(tmp, tmp, Z4, p)) 1405296465Sdelphij goto err; 1406296465Sdelphij if (!BN_mod_sub_quick(rh, rh, tmp, p)) 1407296465Sdelphij goto err; 1408296465Sdelphij if (!field_mul(group, rh, rh, &point->X, ctx)) 1409296465Sdelphij goto err; 1410296465Sdelphij } else { 1411296465Sdelphij if (!field_mul(group, tmp, Z4, &group->a, ctx)) 1412296465Sdelphij goto err; 1413296465Sdelphij if (!BN_mod_add_quick(rh, rh, tmp, p)) 1414296465Sdelphij goto err; 1415296465Sdelphij if (!field_mul(group, rh, rh, &point->X, ctx)) 1416296465Sdelphij goto err; 1417296465Sdelphij } 1418109998Smarkm 1419296465Sdelphij /* rh := rh + b*Z^6 */ 1420296465Sdelphij if (!field_mul(group, tmp, &group->b, Z6, ctx)) 1421296465Sdelphij goto err; 1422296465Sdelphij if (!BN_mod_add_quick(rh, rh, tmp, p)) 1423296465Sdelphij goto err; 1424296465Sdelphij } else { 1425296465Sdelphij /* point->Z_is_one */ 1426109998Smarkm 1427296465Sdelphij /* rh := (rh + a)*X */ 1428296465Sdelphij if (!BN_mod_add_quick(rh, rh, &group->a, p)) 1429296465Sdelphij goto err; 1430296465Sdelphij if (!field_mul(group, rh, rh, &point->X, ctx)) 1431296465Sdelphij goto err; 1432296465Sdelphij /* rh := rh + b */ 1433296465Sdelphij if (!BN_mod_add_quick(rh, rh, &group->b, p)) 1434296465Sdelphij goto err; 1435296465Sdelphij } 1436109998Smarkm 1437296465Sdelphij /* 'lh' := Y^2 */ 1438296465Sdelphij if (!field_sqr(group, tmp, &point->Y, ctx)) 1439296465Sdelphij goto err; 1440109998Smarkm 1441296465Sdelphij ret = (0 == BN_ucmp(tmp, rh)); 1442109998Smarkm 1443109998Smarkm err: 1444296465Sdelphij BN_CTX_end(ctx); 1445296465Sdelphij if (new_ctx != NULL) 1446296465Sdelphij BN_CTX_free(new_ctx); 1447296465Sdelphij return ret; 1448296465Sdelphij} 1449109998Smarkm 1450296465Sdelphijint ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, 1451296465Sdelphij const EC_POINT *b, BN_CTX *ctx) 1452296465Sdelphij{ 1453296465Sdelphij /*- 1454296465Sdelphij * return values: 1455296465Sdelphij * -1 error 1456296465Sdelphij * 0 equal (in affine coordinates) 1457296465Sdelphij * 1 not equal 1458296465Sdelphij */ 1459109998Smarkm 1460296465Sdelphij int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, 1461296465Sdelphij const BIGNUM *, BN_CTX *); 1462296465Sdelphij int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1463296465Sdelphij BN_CTX *new_ctx = NULL; 1464296465Sdelphij BIGNUM *tmp1, *tmp2, *Za23, *Zb23; 1465296465Sdelphij const BIGNUM *tmp1_, *tmp2_; 1466296465Sdelphij int ret = -1; 1467109998Smarkm 1468296465Sdelphij if (EC_POINT_is_at_infinity(group, a)) { 1469296465Sdelphij return EC_POINT_is_at_infinity(group, b) ? 0 : 1; 1470296465Sdelphij } 1471237998Sjkim 1472296465Sdelphij if (EC_POINT_is_at_infinity(group, b)) 1473296465Sdelphij return 1; 1474109998Smarkm 1475296465Sdelphij if (a->Z_is_one && b->Z_is_one) { 1476296465Sdelphij return ((BN_cmp(&a->X, &b->X) == 0) 1477296465Sdelphij && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; 1478296465Sdelphij } 1479109998Smarkm 1480296465Sdelphij field_mul = group->meth->field_mul; 1481296465Sdelphij field_sqr = group->meth->field_sqr; 1482109998Smarkm 1483296465Sdelphij if (ctx == NULL) { 1484296465Sdelphij ctx = new_ctx = BN_CTX_new(); 1485296465Sdelphij if (ctx == NULL) 1486296465Sdelphij return -1; 1487296465Sdelphij } 1488109998Smarkm 1489296465Sdelphij BN_CTX_start(ctx); 1490296465Sdelphij tmp1 = BN_CTX_get(ctx); 1491296465Sdelphij tmp2 = BN_CTX_get(ctx); 1492296465Sdelphij Za23 = BN_CTX_get(ctx); 1493296465Sdelphij Zb23 = BN_CTX_get(ctx); 1494296465Sdelphij if (Zb23 == NULL) 1495296465Sdelphij goto end; 1496109998Smarkm 1497296465Sdelphij /*- 1498296465Sdelphij * We have to decide whether 1499296465Sdelphij * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), 1500296465Sdelphij * or equivalently, whether 1501296465Sdelphij * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). 1502296465Sdelphij */ 1503109998Smarkm 1504296465Sdelphij if (!b->Z_is_one) { 1505296465Sdelphij if (!field_sqr(group, Zb23, &b->Z, ctx)) 1506296465Sdelphij goto end; 1507296465Sdelphij if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) 1508296465Sdelphij goto end; 1509296465Sdelphij tmp1_ = tmp1; 1510296465Sdelphij } else 1511296465Sdelphij tmp1_ = &a->X; 1512296465Sdelphij if (!a->Z_is_one) { 1513296465Sdelphij if (!field_sqr(group, Za23, &a->Z, ctx)) 1514296465Sdelphij goto end; 1515296465Sdelphij if (!field_mul(group, tmp2, &b->X, Za23, ctx)) 1516296465Sdelphij goto end; 1517296465Sdelphij tmp2_ = tmp2; 1518296465Sdelphij } else 1519296465Sdelphij tmp2_ = &b->X; 1520109998Smarkm 1521296465Sdelphij /* compare X_a*Z_b^2 with X_b*Z_a^2 */ 1522296465Sdelphij if (BN_cmp(tmp1_, tmp2_) != 0) { 1523296465Sdelphij ret = 1; /* points differ */ 1524296465Sdelphij goto end; 1525296465Sdelphij } 1526109998Smarkm 1527296465Sdelphij if (!b->Z_is_one) { 1528296465Sdelphij if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) 1529296465Sdelphij goto end; 1530296465Sdelphij if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) 1531296465Sdelphij goto end; 1532296465Sdelphij /* tmp1_ = tmp1 */ 1533296465Sdelphij } else 1534296465Sdelphij tmp1_ = &a->Y; 1535296465Sdelphij if (!a->Z_is_one) { 1536296465Sdelphij if (!field_mul(group, Za23, Za23, &a->Z, ctx)) 1537296465Sdelphij goto end; 1538296465Sdelphij if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) 1539296465Sdelphij goto end; 1540296465Sdelphij /* tmp2_ = tmp2 */ 1541296465Sdelphij } else 1542296465Sdelphij tmp2_ = &b->Y; 1543109998Smarkm 1544296465Sdelphij /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ 1545296465Sdelphij if (BN_cmp(tmp1_, tmp2_) != 0) { 1546296465Sdelphij ret = 1; /* points differ */ 1547296465Sdelphij goto end; 1548296465Sdelphij } 1549109998Smarkm 1550296465Sdelphij /* points are equal */ 1551296465Sdelphij ret = 0; 1552296465Sdelphij 1553109998Smarkm end: 1554296465Sdelphij BN_CTX_end(ctx); 1555296465Sdelphij if (new_ctx != NULL) 1556296465Sdelphij BN_CTX_free(new_ctx); 1557296465Sdelphij return ret; 1558296465Sdelphij} 1559109998Smarkm 1560296465Sdelphijint ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, 1561296465Sdelphij BN_CTX *ctx) 1562296465Sdelphij{ 1563296465Sdelphij BN_CTX *new_ctx = NULL; 1564296465Sdelphij BIGNUM *x, *y; 1565296465Sdelphij int ret = 0; 1566109998Smarkm 1567296465Sdelphij if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) 1568296465Sdelphij return 1; 1569109998Smarkm 1570296465Sdelphij if (ctx == NULL) { 1571296465Sdelphij ctx = new_ctx = BN_CTX_new(); 1572296465Sdelphij if (ctx == NULL) 1573296465Sdelphij return 0; 1574296465Sdelphij } 1575109998Smarkm 1576296465Sdelphij BN_CTX_start(ctx); 1577296465Sdelphij x = BN_CTX_get(ctx); 1578296465Sdelphij y = BN_CTX_get(ctx); 1579296465Sdelphij if (y == NULL) 1580296465Sdelphij goto err; 1581109998Smarkm 1582296465Sdelphij if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) 1583296465Sdelphij goto err; 1584296465Sdelphij if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) 1585296465Sdelphij goto err; 1586296465Sdelphij if (!point->Z_is_one) { 1587296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR); 1588296465Sdelphij goto err; 1589296465Sdelphij } 1590109998Smarkm 1591296465Sdelphij ret = 1; 1592109998Smarkm 1593109998Smarkm err: 1594296465Sdelphij BN_CTX_end(ctx); 1595296465Sdelphij if (new_ctx != NULL) 1596296465Sdelphij BN_CTX_free(new_ctx); 1597296465Sdelphij return ret; 1598296465Sdelphij} 1599109998Smarkm 1600296465Sdelphijint ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, 1601296465Sdelphij EC_POINT *points[], BN_CTX *ctx) 1602296465Sdelphij{ 1603296465Sdelphij BN_CTX *new_ctx = NULL; 1604296465Sdelphij BIGNUM *tmp, *tmp_Z; 1605296465Sdelphij BIGNUM **prod_Z = NULL; 1606296465Sdelphij size_t i; 1607296465Sdelphij int ret = 0; 1608109998Smarkm 1609296465Sdelphij if (num == 0) 1610296465Sdelphij return 1; 1611109998Smarkm 1612296465Sdelphij if (ctx == NULL) { 1613296465Sdelphij ctx = new_ctx = BN_CTX_new(); 1614296465Sdelphij if (ctx == NULL) 1615296465Sdelphij return 0; 1616296465Sdelphij } 1617109998Smarkm 1618296465Sdelphij BN_CTX_start(ctx); 1619296465Sdelphij tmp = BN_CTX_get(ctx); 1620296465Sdelphij tmp_Z = BN_CTX_get(ctx); 1621296465Sdelphij if (tmp == NULL || tmp_Z == NULL) 1622296465Sdelphij goto err; 1623109998Smarkm 1624296465Sdelphij prod_Z = OPENSSL_malloc(num * sizeof prod_Z[0]); 1625296465Sdelphij if (prod_Z == NULL) 1626296465Sdelphij goto err; 1627296465Sdelphij for (i = 0; i < num; i++) { 1628296465Sdelphij prod_Z[i] = BN_new(); 1629296465Sdelphij if (prod_Z[i] == NULL) 1630296465Sdelphij goto err; 1631296465Sdelphij } 1632109998Smarkm 1633296465Sdelphij /* 1634296465Sdelphij * Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z, 1635296465Sdelphij * skipping any zero-valued inputs (pretend that they're 1). 1636296465Sdelphij */ 1637109998Smarkm 1638296465Sdelphij if (!BN_is_zero(&points[0]->Z)) { 1639296465Sdelphij if (!BN_copy(prod_Z[0], &points[0]->Z)) 1640296465Sdelphij goto err; 1641296465Sdelphij } else { 1642296465Sdelphij if (group->meth->field_set_to_one != 0) { 1643296465Sdelphij if (!group->meth->field_set_to_one(group, prod_Z[0], ctx)) 1644296465Sdelphij goto err; 1645296465Sdelphij } else { 1646296465Sdelphij if (!BN_one(prod_Z[0])) 1647296465Sdelphij goto err; 1648296465Sdelphij } 1649296465Sdelphij } 1650109998Smarkm 1651296465Sdelphij for (i = 1; i < num; i++) { 1652296465Sdelphij if (!BN_is_zero(&points[i]->Z)) { 1653296465Sdelphij if (!group->meth->field_mul(group, prod_Z[i], prod_Z[i - 1], 1654296465Sdelphij &points[i]->Z, ctx)) 1655296465Sdelphij goto err; 1656296465Sdelphij } else { 1657296465Sdelphij if (!BN_copy(prod_Z[i], prod_Z[i - 1])) 1658296465Sdelphij goto err; 1659296465Sdelphij } 1660296465Sdelphij } 1661109998Smarkm 1662296465Sdelphij /* 1663296465Sdelphij * Now use a single explicit inversion to replace every non-zero 1664296465Sdelphij * points[i]->Z by its inverse. 1665296465Sdelphij */ 1666279265Sdelphij 1667296465Sdelphij if (!BN_mod_inverse(tmp, prod_Z[num - 1], &group->field, ctx)) { 1668296465Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB); 1669296465Sdelphij goto err; 1670296465Sdelphij } 1671296465Sdelphij if (group->meth->field_encode != 0) { 1672296465Sdelphij /* 1673296465Sdelphij * In the Montgomery case, we just turned R*H (representing H) into 1674296465Sdelphij * 1/(R*H), but we need R*(1/H) (representing 1/H); i.e. we need to 1675296465Sdelphij * multiply by the Montgomery factor twice. 1676296465Sdelphij */ 1677296465Sdelphij if (!group->meth->field_encode(group, tmp, tmp, ctx)) 1678296465Sdelphij goto err; 1679296465Sdelphij if (!group->meth->field_encode(group, tmp, tmp, ctx)) 1680296465Sdelphij goto err; 1681296465Sdelphij } 1682279265Sdelphij 1683296465Sdelphij for (i = num - 1; i > 0; --i) { 1684296465Sdelphij /* 1685296465Sdelphij * Loop invariant: tmp is the product of the inverses of points[0]->Z 1686296465Sdelphij * .. points[i]->Z (zero-valued inputs skipped). 1687296465Sdelphij */ 1688296465Sdelphij if (!BN_is_zero(&points[i]->Z)) { 1689296465Sdelphij /* 1690296465Sdelphij * Set tmp_Z to the inverse of points[i]->Z (as product of Z 1691296465Sdelphij * inverses 0 .. i, Z values 0 .. i - 1). 1692296465Sdelphij */ 1693296465Sdelphij if (!group-> 1694296465Sdelphij meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx)) 1695296465Sdelphij goto err; 1696296465Sdelphij /* 1697296465Sdelphij * Update tmp to satisfy the loop invariant for i - 1. 1698296465Sdelphij */ 1699296465Sdelphij if (!group->meth->field_mul(group, tmp, tmp, &points[i]->Z, ctx)) 1700296465Sdelphij goto err; 1701296465Sdelphij /* Replace points[i]->Z by its inverse. */ 1702296465Sdelphij if (!BN_copy(&points[i]->Z, tmp_Z)) 1703296465Sdelphij goto err; 1704296465Sdelphij } 1705296465Sdelphij } 1706109998Smarkm 1707296465Sdelphij if (!BN_is_zero(&points[0]->Z)) { 1708296465Sdelphij /* Replace points[0]->Z by its inverse. */ 1709296465Sdelphij if (!BN_copy(&points[0]->Z, tmp)) 1710296465Sdelphij goto err; 1711296465Sdelphij } 1712109998Smarkm 1713296465Sdelphij /* Finally, fix up the X and Y coordinates for all points. */ 1714279265Sdelphij 1715296465Sdelphij for (i = 0; i < num; i++) { 1716296465Sdelphij EC_POINT *p = points[i]; 1717279265Sdelphij 1718296465Sdelphij if (!BN_is_zero(&p->Z)) { 1719296465Sdelphij /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */ 1720279265Sdelphij 1721296465Sdelphij if (!group->meth->field_sqr(group, tmp, &p->Z, ctx)) 1722296465Sdelphij goto err; 1723296465Sdelphij if (!group->meth->field_mul(group, &p->X, &p->X, tmp, ctx)) 1724296465Sdelphij goto err; 1725109998Smarkm 1726296465Sdelphij if (!group->meth->field_mul(group, tmp, tmp, &p->Z, ctx)) 1727296465Sdelphij goto err; 1728296465Sdelphij if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp, ctx)) 1729296465Sdelphij goto err; 1730109998Smarkm 1731296465Sdelphij if (group->meth->field_set_to_one != 0) { 1732296465Sdelphij if (!group->meth->field_set_to_one(group, &p->Z, ctx)) 1733296465Sdelphij goto err; 1734296465Sdelphij } else { 1735296465Sdelphij if (!BN_one(&p->Z)) 1736296465Sdelphij goto err; 1737296465Sdelphij } 1738296465Sdelphij p->Z_is_one = 1; 1739296465Sdelphij } 1740296465Sdelphij } 1741279265Sdelphij 1742296465Sdelphij ret = 1; 1743109998Smarkm 1744109998Smarkm err: 1745296465Sdelphij BN_CTX_end(ctx); 1746296465Sdelphij if (new_ctx != NULL) 1747296465Sdelphij BN_CTX_free(new_ctx); 1748296465Sdelphij if (prod_Z != NULL) { 1749296465Sdelphij for (i = 0; i < num; i++) { 1750296465Sdelphij if (prod_Z[i] == NULL) 1751296465Sdelphij break; 1752296465Sdelphij BN_clear_free(prod_Z[i]); 1753296465Sdelphij } 1754296465Sdelphij OPENSSL_free(prod_Z); 1755296465Sdelphij } 1756296465Sdelphij return ret; 1757296465Sdelphij} 1758109998Smarkm 1759296465Sdelphijint ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1760296465Sdelphij const BIGNUM *b, BN_CTX *ctx) 1761296465Sdelphij{ 1762296465Sdelphij return BN_mod_mul(r, a, b, &group->field, ctx); 1763296465Sdelphij} 1764109998Smarkm 1765296465Sdelphijint ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1766296465Sdelphij BN_CTX *ctx) 1767296465Sdelphij{ 1768296465Sdelphij return BN_mod_sqr(r, a, &group->field, ctx); 1769296465Sdelphij} 1770