1109998Smarkm/* crypto/ec/ecp_smpl.c */ 2109998Smarkm/* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> 3160814Ssimon * for the OpenSSL project. 4160814Ssimon * Includes code written by Bodo Moeller for the OpenSSL project. 5160814Ssimon*/ 6109998Smarkm/* ==================================================================== 7160814Ssimon * Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved. 8109998Smarkm * 9109998Smarkm * Redistribution and use in source and binary forms, with or without 10109998Smarkm * modification, are permitted provided that the following conditions 11109998Smarkm * are met: 12109998Smarkm * 13109998Smarkm * 1. Redistributions of source code must retain the above copyright 14109998Smarkm * notice, this list of conditions and the following disclaimer. 15109998Smarkm * 16109998Smarkm * 2. Redistributions in binary form must reproduce the above copyright 17109998Smarkm * notice, this list of conditions and the following disclaimer in 18109998Smarkm * the documentation and/or other materials provided with the 19109998Smarkm * distribution. 20109998Smarkm * 21109998Smarkm * 3. All advertising materials mentioning features or use of this 22109998Smarkm * software must display the following acknowledgment: 23109998Smarkm * "This product includes software developed by the OpenSSL Project 24109998Smarkm * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 25109998Smarkm * 26109998Smarkm * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 27109998Smarkm * endorse or promote products derived from this software without 28109998Smarkm * prior written permission. For written permission, please contact 29109998Smarkm * openssl-core@openssl.org. 30109998Smarkm * 31109998Smarkm * 5. Products derived from this software may not be called "OpenSSL" 32109998Smarkm * nor may "OpenSSL" appear in their names without prior written 33109998Smarkm * permission of the OpenSSL Project. 34109998Smarkm * 35109998Smarkm * 6. Redistributions of any form whatsoever must retain the following 36109998Smarkm * acknowledgment: 37109998Smarkm * "This product includes software developed by the OpenSSL Project 38109998Smarkm * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 39109998Smarkm * 40109998Smarkm * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 41109998Smarkm * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42109998Smarkm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 43109998Smarkm * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 44109998Smarkm * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 45109998Smarkm * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 46109998Smarkm * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 47109998Smarkm * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48109998Smarkm * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 49109998Smarkm * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 50109998Smarkm * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 51109998Smarkm * OF THE POSSIBILITY OF SUCH DAMAGE. 52109998Smarkm * ==================================================================== 53109998Smarkm * 54109998Smarkm * This product includes cryptographic software written by Eric Young 55109998Smarkm * (eay@cryptsoft.com). This product includes software written by Tim 56109998Smarkm * Hudson (tjh@cryptsoft.com). 57109998Smarkm * 58109998Smarkm */ 59160814Ssimon/* ==================================================================== 60160814Ssimon * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 61160814Ssimon * Portions of this software developed by SUN MICROSYSTEMS, INC., 62160814Ssimon * and contributed to the OpenSSL project. 63160814Ssimon */ 64109998Smarkm 65109998Smarkm#include <openssl/err.h> 66160814Ssimon#include <openssl/symhacks.h> 67109998Smarkm 68238405Sjkim#ifdef OPENSSL_FIPS 69238405Sjkim#include <openssl/fips.h> 70238405Sjkim#endif 71238405Sjkim 72109998Smarkm#include "ec_lcl.h" 73109998Smarkm 74109998Smarkmconst EC_METHOD *EC_GFp_simple_method(void) 75109998Smarkm { 76109998Smarkm static const EC_METHOD ret = { 77238405Sjkim EC_FLAGS_DEFAULT_OCT, 78160814Ssimon NID_X9_62_prime_field, 79109998Smarkm ec_GFp_simple_group_init, 80109998Smarkm ec_GFp_simple_group_finish, 81109998Smarkm ec_GFp_simple_group_clear_finish, 82109998Smarkm ec_GFp_simple_group_copy, 83160814Ssimon ec_GFp_simple_group_set_curve, 84160814Ssimon ec_GFp_simple_group_get_curve, 85160814Ssimon ec_GFp_simple_group_get_degree, 86160814Ssimon ec_GFp_simple_group_check_discriminant, 87109998Smarkm ec_GFp_simple_point_init, 88109998Smarkm ec_GFp_simple_point_finish, 89109998Smarkm ec_GFp_simple_point_clear_finish, 90109998Smarkm ec_GFp_simple_point_copy, 91109998Smarkm ec_GFp_simple_point_set_to_infinity, 92109998Smarkm ec_GFp_simple_set_Jprojective_coordinates_GFp, 93109998Smarkm ec_GFp_simple_get_Jprojective_coordinates_GFp, 94160814Ssimon ec_GFp_simple_point_set_affine_coordinates, 95160814Ssimon ec_GFp_simple_point_get_affine_coordinates, 96238405Sjkim 0,0,0, 97109998Smarkm ec_GFp_simple_add, 98109998Smarkm ec_GFp_simple_dbl, 99109998Smarkm ec_GFp_simple_invert, 100109998Smarkm ec_GFp_simple_is_at_infinity, 101109998Smarkm ec_GFp_simple_is_on_curve, 102109998Smarkm ec_GFp_simple_cmp, 103109998Smarkm ec_GFp_simple_make_affine, 104109998Smarkm ec_GFp_simple_points_make_affine, 105160814Ssimon 0 /* mul */, 106160814Ssimon 0 /* precompute_mult */, 107160814Ssimon 0 /* have_precompute_mult */, 108109998Smarkm ec_GFp_simple_field_mul, 109109998Smarkm ec_GFp_simple_field_sqr, 110160814Ssimon 0 /* field_div */, 111109998Smarkm 0 /* field_encode */, 112109998Smarkm 0 /* field_decode */, 113109998Smarkm 0 /* field_set_to_one */ }; 114109998Smarkm 115279264Sdelphij#ifdef OPENSSL_FIPS 116279264Sdelphij if (FIPS_mode()) 117279264Sdelphij return fips_ec_gfp_simple_method(); 118279264Sdelphij#endif 119279264Sdelphij 120109998Smarkm return &ret; 121109998Smarkm } 122109998Smarkm 123109998Smarkm 124160814Ssimon/* Most method functions in this file are designed to work with 125160814Ssimon * non-trivial representations of field elements if necessary 126160814Ssimon * (see ecp_mont.c): while standard modular addition and subtraction 127160814Ssimon * are used, the field_mul and field_sqr methods will be used for 128160814Ssimon * multiplication, and field_encode and field_decode (if defined) 129160814Ssimon * will be used for converting between representations. 130160814Ssimon 131160814Ssimon * Functions ec_GFp_simple_points_make_affine() and 132160814Ssimon * ec_GFp_simple_point_get_affine_coordinates() specifically assume 133160814Ssimon * that if a non-trivial representation is used, it is a Montgomery 134160814Ssimon * representation (i.e. 'encoding' means multiplying by some factor R). 135160814Ssimon */ 136160814Ssimon 137160814Ssimon 138109998Smarkmint ec_GFp_simple_group_init(EC_GROUP *group) 139109998Smarkm { 140109998Smarkm BN_init(&group->field); 141109998Smarkm BN_init(&group->a); 142109998Smarkm BN_init(&group->b); 143109998Smarkm group->a_is_minus3 = 0; 144109998Smarkm return 1; 145109998Smarkm } 146109998Smarkm 147109998Smarkm 148109998Smarkmvoid ec_GFp_simple_group_finish(EC_GROUP *group) 149109998Smarkm { 150109998Smarkm BN_free(&group->field); 151109998Smarkm BN_free(&group->a); 152109998Smarkm BN_free(&group->b); 153109998Smarkm } 154109998Smarkm 155109998Smarkm 156109998Smarkmvoid ec_GFp_simple_group_clear_finish(EC_GROUP *group) 157109998Smarkm { 158109998Smarkm BN_clear_free(&group->field); 159109998Smarkm BN_clear_free(&group->a); 160109998Smarkm BN_clear_free(&group->b); 161109998Smarkm } 162109998Smarkm 163109998Smarkm 164109998Smarkmint ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) 165109998Smarkm { 166109998Smarkm if (!BN_copy(&dest->field, &src->field)) return 0; 167109998Smarkm if (!BN_copy(&dest->a, &src->a)) return 0; 168109998Smarkm if (!BN_copy(&dest->b, &src->b)) return 0; 169109998Smarkm 170109998Smarkm dest->a_is_minus3 = src->a_is_minus3; 171109998Smarkm 172109998Smarkm return 1; 173109998Smarkm } 174109998Smarkm 175109998Smarkm 176160814Ssimonint ec_GFp_simple_group_set_curve(EC_GROUP *group, 177109998Smarkm const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 178109998Smarkm { 179109998Smarkm int ret = 0; 180109998Smarkm BN_CTX *new_ctx = NULL; 181109998Smarkm BIGNUM *tmp_a; 182109998Smarkm 183109998Smarkm /* p must be a prime > 3 */ 184109998Smarkm if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) 185109998Smarkm { 186160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD); 187109998Smarkm return 0; 188109998Smarkm } 189109998Smarkm 190109998Smarkm if (ctx == NULL) 191109998Smarkm { 192109998Smarkm ctx = new_ctx = BN_CTX_new(); 193109998Smarkm if (ctx == NULL) 194109998Smarkm return 0; 195109998Smarkm } 196109998Smarkm 197109998Smarkm BN_CTX_start(ctx); 198109998Smarkm tmp_a = BN_CTX_get(ctx); 199109998Smarkm if (tmp_a == NULL) goto err; 200109998Smarkm 201109998Smarkm /* group->field */ 202109998Smarkm if (!BN_copy(&group->field, p)) goto err; 203160814Ssimon BN_set_negative(&group->field, 0); 204109998Smarkm 205109998Smarkm /* group->a */ 206109998Smarkm if (!BN_nnmod(tmp_a, a, p, ctx)) goto err; 207109998Smarkm if (group->meth->field_encode) 208109998Smarkm { if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) goto err; } 209109998Smarkm else 210109998Smarkm if (!BN_copy(&group->a, tmp_a)) goto err; 211109998Smarkm 212109998Smarkm /* group->b */ 213109998Smarkm if (!BN_nnmod(&group->b, b, p, ctx)) goto err; 214109998Smarkm if (group->meth->field_encode) 215109998Smarkm if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) goto err; 216109998Smarkm 217109998Smarkm /* group->a_is_minus3 */ 218109998Smarkm if (!BN_add_word(tmp_a, 3)) goto err; 219109998Smarkm group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field)); 220109998Smarkm 221109998Smarkm ret = 1; 222109998Smarkm 223109998Smarkm err: 224109998Smarkm BN_CTX_end(ctx); 225109998Smarkm if (new_ctx != NULL) 226109998Smarkm BN_CTX_free(new_ctx); 227109998Smarkm return ret; 228109998Smarkm } 229109998Smarkm 230109998Smarkm 231160814Ssimonint ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx) 232109998Smarkm { 233109998Smarkm int ret = 0; 234109998Smarkm BN_CTX *new_ctx = NULL; 235109998Smarkm 236109998Smarkm if (p != NULL) 237109998Smarkm { 238109998Smarkm if (!BN_copy(p, &group->field)) return 0; 239109998Smarkm } 240109998Smarkm 241109998Smarkm if (a != NULL || b != NULL) 242109998Smarkm { 243109998Smarkm if (group->meth->field_decode) 244109998Smarkm { 245109998Smarkm if (ctx == NULL) 246109998Smarkm { 247109998Smarkm ctx = new_ctx = BN_CTX_new(); 248109998Smarkm if (ctx == NULL) 249109998Smarkm return 0; 250109998Smarkm } 251109998Smarkm if (a != NULL) 252109998Smarkm { 253109998Smarkm if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err; 254109998Smarkm } 255109998Smarkm if (b != NULL) 256109998Smarkm { 257109998Smarkm if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err; 258109998Smarkm } 259109998Smarkm } 260109998Smarkm else 261109998Smarkm { 262109998Smarkm if (a != NULL) 263109998Smarkm { 264109998Smarkm if (!BN_copy(a, &group->a)) goto err; 265109998Smarkm } 266109998Smarkm if (b != NULL) 267109998Smarkm { 268109998Smarkm if (!BN_copy(b, &group->b)) goto err; 269109998Smarkm } 270109998Smarkm } 271109998Smarkm } 272109998Smarkm 273109998Smarkm ret = 1; 274109998Smarkm 275109998Smarkm err: 276109998Smarkm if (new_ctx) 277109998Smarkm BN_CTX_free(new_ctx); 278109998Smarkm return ret; 279109998Smarkm } 280109998Smarkm 281109998Smarkm 282160814Ssimonint ec_GFp_simple_group_get_degree(const EC_GROUP *group) 283160814Ssimon { 284160814Ssimon return BN_num_bits(&group->field); 285160814Ssimon } 286109998Smarkm 287160814Ssimon 288160814Ssimonint ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx) 289109998Smarkm { 290160814Ssimon int ret = 0; 291160814Ssimon BIGNUM *a,*b,*order,*tmp_1,*tmp_2; 292160814Ssimon const BIGNUM *p = &group->field; 293160814Ssimon BN_CTX *new_ctx = NULL; 294160814Ssimon 295160814Ssimon if (ctx == NULL) 296109998Smarkm { 297160814Ssimon ctx = new_ctx = BN_CTX_new(); 298160814Ssimon if (ctx == NULL) 299160814Ssimon { 300160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE); 301160814Ssimon goto err; 302160814Ssimon } 303109998Smarkm } 304160814Ssimon BN_CTX_start(ctx); 305160814Ssimon a = BN_CTX_get(ctx); 306160814Ssimon b = BN_CTX_get(ctx); 307160814Ssimon tmp_1 = BN_CTX_get(ctx); 308160814Ssimon tmp_2 = BN_CTX_get(ctx); 309160814Ssimon order = BN_CTX_get(ctx); 310160814Ssimon if (order == NULL) goto err; 311109998Smarkm 312160814Ssimon if (group->meth->field_decode) 313109998Smarkm { 314160814Ssimon if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err; 315160814Ssimon if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err; 316109998Smarkm } 317109998Smarkm else 318160814Ssimon { 319160814Ssimon if (!BN_copy(a, &group->a)) goto err; 320160814Ssimon if (!BN_copy(b, &group->b)) goto err; 321160814Ssimon } 322160814Ssimon 323160814Ssimon /* check the discriminant: 324160814Ssimon * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p) 325160814Ssimon * 0 =< a, b < p */ 326160814Ssimon if (BN_is_zero(a)) 327160814Ssimon { 328160814Ssimon if (BN_is_zero(b)) goto err; 329160814Ssimon } 330160814Ssimon else if (!BN_is_zero(b)) 331160814Ssimon { 332160814Ssimon if (!BN_mod_sqr(tmp_1, a, p, ctx)) goto err; 333160814Ssimon if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) goto err; 334160814Ssimon if (!BN_lshift(tmp_1, tmp_2, 2)) goto err; 335160814Ssimon /* tmp_1 = 4*a^3 */ 336109998Smarkm 337160814Ssimon if (!BN_mod_sqr(tmp_2, b, p, ctx)) goto err; 338160814Ssimon if (!BN_mul_word(tmp_2, 27)) goto err; 339160814Ssimon /* tmp_2 = 27*b^2 */ 340109998Smarkm 341160814Ssimon if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) goto err; 342160814Ssimon if (BN_is_zero(a)) goto err; 343160814Ssimon } 344160814Ssimon ret = 1; 345109998Smarkm 346160814Ssimonerr: 347160814Ssimon if (ctx != NULL) 348160814Ssimon BN_CTX_end(ctx); 349160814Ssimon if (new_ctx != NULL) 350160814Ssimon BN_CTX_free(new_ctx); 351160814Ssimon return ret; 352109998Smarkm } 353109998Smarkm 354109998Smarkm 355109998Smarkmint ec_GFp_simple_point_init(EC_POINT *point) 356109998Smarkm { 357109998Smarkm BN_init(&point->X); 358109998Smarkm BN_init(&point->Y); 359109998Smarkm BN_init(&point->Z); 360109998Smarkm point->Z_is_one = 0; 361109998Smarkm 362109998Smarkm return 1; 363109998Smarkm } 364109998Smarkm 365109998Smarkm 366109998Smarkmvoid ec_GFp_simple_point_finish(EC_POINT *point) 367109998Smarkm { 368109998Smarkm BN_free(&point->X); 369109998Smarkm BN_free(&point->Y); 370109998Smarkm BN_free(&point->Z); 371109998Smarkm } 372109998Smarkm 373109998Smarkm 374109998Smarkmvoid ec_GFp_simple_point_clear_finish(EC_POINT *point) 375109998Smarkm { 376109998Smarkm BN_clear_free(&point->X); 377109998Smarkm BN_clear_free(&point->Y); 378109998Smarkm BN_clear_free(&point->Z); 379109998Smarkm point->Z_is_one = 0; 380109998Smarkm } 381109998Smarkm 382109998Smarkm 383109998Smarkmint ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) 384109998Smarkm { 385109998Smarkm if (!BN_copy(&dest->X, &src->X)) return 0; 386109998Smarkm if (!BN_copy(&dest->Y, &src->Y)) return 0; 387109998Smarkm if (!BN_copy(&dest->Z, &src->Z)) return 0; 388109998Smarkm dest->Z_is_one = src->Z_is_one; 389109998Smarkm 390109998Smarkm return 1; 391109998Smarkm } 392109998Smarkm 393109998Smarkm 394109998Smarkmint ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point) 395109998Smarkm { 396109998Smarkm point->Z_is_one = 0; 397160814Ssimon BN_zero(&point->Z); 398160814Ssimon return 1; 399109998Smarkm } 400109998Smarkm 401109998Smarkm 402109998Smarkmint ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, 403109998Smarkm const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx) 404109998Smarkm { 405109998Smarkm BN_CTX *new_ctx = NULL; 406109998Smarkm int ret = 0; 407109998Smarkm 408109998Smarkm if (ctx == NULL) 409109998Smarkm { 410109998Smarkm ctx = new_ctx = BN_CTX_new(); 411109998Smarkm if (ctx == NULL) 412109998Smarkm return 0; 413109998Smarkm } 414109998Smarkm 415109998Smarkm if (x != NULL) 416109998Smarkm { 417109998Smarkm if (!BN_nnmod(&point->X, x, &group->field, ctx)) goto err; 418109998Smarkm if (group->meth->field_encode) 419109998Smarkm { 420109998Smarkm if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err; 421109998Smarkm } 422109998Smarkm } 423109998Smarkm 424109998Smarkm if (y != NULL) 425109998Smarkm { 426109998Smarkm if (!BN_nnmod(&point->Y, y, &group->field, ctx)) goto err; 427109998Smarkm if (group->meth->field_encode) 428109998Smarkm { 429109998Smarkm if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err; 430109998Smarkm } 431109998Smarkm } 432109998Smarkm 433109998Smarkm if (z != NULL) 434109998Smarkm { 435109998Smarkm int Z_is_one; 436109998Smarkm 437109998Smarkm if (!BN_nnmod(&point->Z, z, &group->field, ctx)) goto err; 438109998Smarkm Z_is_one = BN_is_one(&point->Z); 439109998Smarkm if (group->meth->field_encode) 440109998Smarkm { 441109998Smarkm if (Z_is_one && (group->meth->field_set_to_one != 0)) 442109998Smarkm { 443109998Smarkm if (!group->meth->field_set_to_one(group, &point->Z, ctx)) goto err; 444109998Smarkm } 445109998Smarkm else 446109998Smarkm { 447109998Smarkm if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err; 448109998Smarkm } 449109998Smarkm } 450109998Smarkm point->Z_is_one = Z_is_one; 451109998Smarkm } 452109998Smarkm 453109998Smarkm ret = 1; 454109998Smarkm 455109998Smarkm err: 456109998Smarkm if (new_ctx != NULL) 457109998Smarkm BN_CTX_free(new_ctx); 458109998Smarkm return ret; 459109998Smarkm } 460109998Smarkm 461109998Smarkm 462109998Smarkmint ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point, 463109998Smarkm BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx) 464109998Smarkm { 465109998Smarkm BN_CTX *new_ctx = NULL; 466109998Smarkm int ret = 0; 467109998Smarkm 468109998Smarkm if (group->meth->field_decode != 0) 469109998Smarkm { 470109998Smarkm if (ctx == NULL) 471109998Smarkm { 472109998Smarkm ctx = new_ctx = BN_CTX_new(); 473109998Smarkm if (ctx == NULL) 474109998Smarkm return 0; 475109998Smarkm } 476109998Smarkm 477109998Smarkm if (x != NULL) 478109998Smarkm { 479109998Smarkm if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err; 480109998Smarkm } 481109998Smarkm if (y != NULL) 482109998Smarkm { 483109998Smarkm if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err; 484109998Smarkm } 485109998Smarkm if (z != NULL) 486109998Smarkm { 487109998Smarkm if (!group->meth->field_decode(group, z, &point->Z, ctx)) goto err; 488109998Smarkm } 489109998Smarkm } 490109998Smarkm else 491109998Smarkm { 492109998Smarkm if (x != NULL) 493109998Smarkm { 494109998Smarkm if (!BN_copy(x, &point->X)) goto err; 495109998Smarkm } 496109998Smarkm if (y != NULL) 497109998Smarkm { 498109998Smarkm if (!BN_copy(y, &point->Y)) goto err; 499109998Smarkm } 500109998Smarkm if (z != NULL) 501109998Smarkm { 502109998Smarkm if (!BN_copy(z, &point->Z)) goto err; 503109998Smarkm } 504109998Smarkm } 505109998Smarkm 506109998Smarkm ret = 1; 507109998Smarkm 508109998Smarkm err: 509109998Smarkm if (new_ctx != NULL) 510109998Smarkm BN_CTX_free(new_ctx); 511109998Smarkm return ret; 512109998Smarkm } 513109998Smarkm 514109998Smarkm 515160814Ssimonint ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point, 516109998Smarkm const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) 517109998Smarkm { 518109998Smarkm if (x == NULL || y == NULL) 519109998Smarkm { 520109998Smarkm /* unlike for projective coordinates, we do not tolerate this */ 521160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER); 522109998Smarkm return 0; 523109998Smarkm } 524109998Smarkm 525109998Smarkm return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx); 526109998Smarkm } 527109998Smarkm 528109998Smarkm 529160814Ssimonint ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point, 530109998Smarkm BIGNUM *x, BIGNUM *y, BN_CTX *ctx) 531109998Smarkm { 532109998Smarkm BN_CTX *new_ctx = NULL; 533160814Ssimon BIGNUM *Z, *Z_1, *Z_2, *Z_3; 534160814Ssimon const BIGNUM *Z_; 535109998Smarkm int ret = 0; 536109998Smarkm 537109998Smarkm if (EC_POINT_is_at_infinity(group, point)) 538109998Smarkm { 539160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY); 540109998Smarkm return 0; 541109998Smarkm } 542109998Smarkm 543109998Smarkm if (ctx == NULL) 544109998Smarkm { 545109998Smarkm ctx = new_ctx = BN_CTX_new(); 546109998Smarkm if (ctx == NULL) 547109998Smarkm return 0; 548109998Smarkm } 549109998Smarkm 550109998Smarkm BN_CTX_start(ctx); 551109998Smarkm Z = BN_CTX_get(ctx); 552109998Smarkm Z_1 = BN_CTX_get(ctx); 553109998Smarkm Z_2 = BN_CTX_get(ctx); 554109998Smarkm Z_3 = BN_CTX_get(ctx); 555109998Smarkm if (Z_3 == NULL) goto err; 556109998Smarkm 557109998Smarkm /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */ 558109998Smarkm 559109998Smarkm if (group->meth->field_decode) 560109998Smarkm { 561109998Smarkm if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto err; 562160814Ssimon Z_ = Z; 563109998Smarkm } 564109998Smarkm else 565109998Smarkm { 566109998Smarkm Z_ = &point->Z; 567109998Smarkm } 568109998Smarkm 569109998Smarkm if (BN_is_one(Z_)) 570109998Smarkm { 571160814Ssimon if (group->meth->field_decode) 572109998Smarkm { 573160814Ssimon if (x != NULL) 574160814Ssimon { 575160814Ssimon if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err; 576160814Ssimon } 577160814Ssimon if (y != NULL) 578160814Ssimon { 579160814Ssimon if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err; 580160814Ssimon } 581109998Smarkm } 582160814Ssimon else 583109998Smarkm { 584160814Ssimon if (x != NULL) 585160814Ssimon { 586160814Ssimon if (!BN_copy(x, &point->X)) goto err; 587160814Ssimon } 588160814Ssimon if (y != NULL) 589160814Ssimon { 590160814Ssimon if (!BN_copy(y, &point->Y)) goto err; 591160814Ssimon } 592109998Smarkm } 593109998Smarkm } 594109998Smarkm else 595109998Smarkm { 596109998Smarkm if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx)) 597109998Smarkm { 598160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_BN_LIB); 599109998Smarkm goto err; 600109998Smarkm } 601109998Smarkm 602109998Smarkm if (group->meth->field_encode == 0) 603109998Smarkm { 604109998Smarkm /* field_sqr works on standard representation */ 605109998Smarkm if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) goto err; 606109998Smarkm } 607109998Smarkm else 608109998Smarkm { 609109998Smarkm if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err; 610109998Smarkm } 611109998Smarkm 612109998Smarkm if (x != NULL) 613109998Smarkm { 614160814Ssimon /* in the Montgomery case, field_mul will cancel out Montgomery factor in X: */ 615160814Ssimon if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) goto err; 616109998Smarkm } 617109998Smarkm 618109998Smarkm if (y != NULL) 619109998Smarkm { 620109998Smarkm if (group->meth->field_encode == 0) 621109998Smarkm { 622109998Smarkm /* field_mul works on standard representation */ 623109998Smarkm if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) goto err; 624109998Smarkm } 625109998Smarkm else 626109998Smarkm { 627109998Smarkm if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err; 628109998Smarkm } 629160814Ssimon 630160814Ssimon /* in the Montgomery case, field_mul will cancel out Montgomery factor in Y: */ 631160814Ssimon if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) goto err; 632109998Smarkm } 633109998Smarkm } 634109998Smarkm 635109998Smarkm ret = 1; 636109998Smarkm 637109998Smarkm err: 638109998Smarkm BN_CTX_end(ctx); 639109998Smarkm if (new_ctx != NULL) 640109998Smarkm BN_CTX_free(new_ctx); 641109998Smarkm return ret; 642109998Smarkm } 643109998Smarkm 644109998Smarkmint ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx) 645109998Smarkm { 646109998Smarkm int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 647109998Smarkm int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 648109998Smarkm const BIGNUM *p; 649109998Smarkm BN_CTX *new_ctx = NULL; 650109998Smarkm BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6; 651109998Smarkm int ret = 0; 652109998Smarkm 653109998Smarkm if (a == b) 654109998Smarkm return EC_POINT_dbl(group, r, a, ctx); 655109998Smarkm if (EC_POINT_is_at_infinity(group, a)) 656109998Smarkm return EC_POINT_copy(r, b); 657109998Smarkm if (EC_POINT_is_at_infinity(group, b)) 658109998Smarkm return EC_POINT_copy(r, a); 659109998Smarkm 660109998Smarkm field_mul = group->meth->field_mul; 661109998Smarkm field_sqr = group->meth->field_sqr; 662109998Smarkm p = &group->field; 663109998Smarkm 664109998Smarkm if (ctx == NULL) 665109998Smarkm { 666109998Smarkm ctx = new_ctx = BN_CTX_new(); 667109998Smarkm if (ctx == NULL) 668109998Smarkm return 0; 669109998Smarkm } 670109998Smarkm 671109998Smarkm BN_CTX_start(ctx); 672109998Smarkm n0 = BN_CTX_get(ctx); 673109998Smarkm n1 = BN_CTX_get(ctx); 674109998Smarkm n2 = BN_CTX_get(ctx); 675109998Smarkm n3 = BN_CTX_get(ctx); 676109998Smarkm n4 = BN_CTX_get(ctx); 677109998Smarkm n5 = BN_CTX_get(ctx); 678109998Smarkm n6 = BN_CTX_get(ctx); 679109998Smarkm if (n6 == NULL) goto end; 680109998Smarkm 681109998Smarkm /* Note that in this function we must not read components of 'a' or 'b' 682109998Smarkm * once we have written the corresponding components of 'r'. 683109998Smarkm * ('r' might be one of 'a' or 'b'.) 684109998Smarkm */ 685109998Smarkm 686109998Smarkm /* n1, n2 */ 687109998Smarkm if (b->Z_is_one) 688109998Smarkm { 689109998Smarkm if (!BN_copy(n1, &a->X)) goto end; 690109998Smarkm if (!BN_copy(n2, &a->Y)) goto end; 691109998Smarkm /* n1 = X_a */ 692109998Smarkm /* n2 = Y_a */ 693109998Smarkm } 694109998Smarkm else 695109998Smarkm { 696109998Smarkm if (!field_sqr(group, n0, &b->Z, ctx)) goto end; 697109998Smarkm if (!field_mul(group, n1, &a->X, n0, ctx)) goto end; 698109998Smarkm /* n1 = X_a * Z_b^2 */ 699109998Smarkm 700109998Smarkm if (!field_mul(group, n0, n0, &b->Z, ctx)) goto end; 701109998Smarkm if (!field_mul(group, n2, &a->Y, n0, ctx)) goto end; 702109998Smarkm /* n2 = Y_a * Z_b^3 */ 703109998Smarkm } 704109998Smarkm 705109998Smarkm /* n3, n4 */ 706109998Smarkm if (a->Z_is_one) 707109998Smarkm { 708109998Smarkm if (!BN_copy(n3, &b->X)) goto end; 709109998Smarkm if (!BN_copy(n4, &b->Y)) goto end; 710109998Smarkm /* n3 = X_b */ 711109998Smarkm /* n4 = Y_b */ 712109998Smarkm } 713109998Smarkm else 714109998Smarkm { 715109998Smarkm if (!field_sqr(group, n0, &a->Z, ctx)) goto end; 716109998Smarkm if (!field_mul(group, n3, &b->X, n0, ctx)) goto end; 717109998Smarkm /* n3 = X_b * Z_a^2 */ 718109998Smarkm 719109998Smarkm if (!field_mul(group, n0, n0, &a->Z, ctx)) goto end; 720109998Smarkm if (!field_mul(group, n4, &b->Y, n0, ctx)) goto end; 721109998Smarkm /* n4 = Y_b * Z_a^3 */ 722109998Smarkm } 723109998Smarkm 724109998Smarkm /* n5, n6 */ 725109998Smarkm if (!BN_mod_sub_quick(n5, n1, n3, p)) goto end; 726109998Smarkm if (!BN_mod_sub_quick(n6, n2, n4, p)) goto end; 727109998Smarkm /* n5 = n1 - n3 */ 728109998Smarkm /* n6 = n2 - n4 */ 729109998Smarkm 730109998Smarkm if (BN_is_zero(n5)) 731109998Smarkm { 732109998Smarkm if (BN_is_zero(n6)) 733109998Smarkm { 734109998Smarkm /* a is the same point as b */ 735109998Smarkm BN_CTX_end(ctx); 736109998Smarkm ret = EC_POINT_dbl(group, r, a, ctx); 737109998Smarkm ctx = NULL; 738109998Smarkm goto end; 739109998Smarkm } 740109998Smarkm else 741109998Smarkm { 742109998Smarkm /* a is the inverse of b */ 743160814Ssimon BN_zero(&r->Z); 744109998Smarkm r->Z_is_one = 0; 745109998Smarkm ret = 1; 746109998Smarkm goto end; 747109998Smarkm } 748109998Smarkm } 749109998Smarkm 750109998Smarkm /* 'n7', 'n8' */ 751109998Smarkm if (!BN_mod_add_quick(n1, n1, n3, p)) goto end; 752109998Smarkm if (!BN_mod_add_quick(n2, n2, n4, p)) goto end; 753109998Smarkm /* 'n7' = n1 + n3 */ 754109998Smarkm /* 'n8' = n2 + n4 */ 755109998Smarkm 756109998Smarkm /* Z_r */ 757109998Smarkm if (a->Z_is_one && b->Z_is_one) 758109998Smarkm { 759109998Smarkm if (!BN_copy(&r->Z, n5)) goto end; 760109998Smarkm } 761109998Smarkm else 762109998Smarkm { 763109998Smarkm if (a->Z_is_one) 764109998Smarkm { if (!BN_copy(n0, &b->Z)) goto end; } 765109998Smarkm else if (b->Z_is_one) 766109998Smarkm { if (!BN_copy(n0, &a->Z)) goto end; } 767109998Smarkm else 768109998Smarkm { if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) goto end; } 769109998Smarkm if (!field_mul(group, &r->Z, n0, n5, ctx)) goto end; 770109998Smarkm } 771109998Smarkm r->Z_is_one = 0; 772109998Smarkm /* Z_r = Z_a * Z_b * n5 */ 773109998Smarkm 774109998Smarkm /* X_r */ 775109998Smarkm if (!field_sqr(group, n0, n6, ctx)) goto end; 776109998Smarkm if (!field_sqr(group, n4, n5, ctx)) goto end; 777109998Smarkm if (!field_mul(group, n3, n1, n4, ctx)) goto end; 778109998Smarkm if (!BN_mod_sub_quick(&r->X, n0, n3, p)) goto end; 779109998Smarkm /* X_r = n6^2 - n5^2 * 'n7' */ 780109998Smarkm 781109998Smarkm /* 'n9' */ 782109998Smarkm if (!BN_mod_lshift1_quick(n0, &r->X, p)) goto end; 783109998Smarkm if (!BN_mod_sub_quick(n0, n3, n0, p)) goto end; 784109998Smarkm /* n9 = n5^2 * 'n7' - 2 * X_r */ 785109998Smarkm 786109998Smarkm /* Y_r */ 787109998Smarkm if (!field_mul(group, n0, n0, n6, ctx)) goto end; 788109998Smarkm if (!field_mul(group, n5, n4, n5, ctx)) goto end; /* now n5 is n5^3 */ 789109998Smarkm if (!field_mul(group, n1, n2, n5, ctx)) goto end; 790109998Smarkm if (!BN_mod_sub_quick(n0, n0, n1, p)) goto end; 791109998Smarkm if (BN_is_odd(n0)) 792109998Smarkm if (!BN_add(n0, n0, p)) goto end; 793109998Smarkm /* now 0 <= n0 < 2*p, and n0 is even */ 794109998Smarkm if (!BN_rshift1(&r->Y, n0)) goto end; 795109998Smarkm /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */ 796109998Smarkm 797109998Smarkm ret = 1; 798109998Smarkm 799109998Smarkm end: 800109998Smarkm if (ctx) /* otherwise we already called BN_CTX_end */ 801109998Smarkm BN_CTX_end(ctx); 802109998Smarkm if (new_ctx != NULL) 803109998Smarkm BN_CTX_free(new_ctx); 804109998Smarkm return ret; 805109998Smarkm } 806109998Smarkm 807109998Smarkm 808109998Smarkmint ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx) 809109998Smarkm { 810109998Smarkm int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 811109998Smarkm int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 812109998Smarkm const BIGNUM *p; 813109998Smarkm BN_CTX *new_ctx = NULL; 814109998Smarkm BIGNUM *n0, *n1, *n2, *n3; 815109998Smarkm int ret = 0; 816109998Smarkm 817109998Smarkm if (EC_POINT_is_at_infinity(group, a)) 818109998Smarkm { 819160814Ssimon BN_zero(&r->Z); 820109998Smarkm r->Z_is_one = 0; 821109998Smarkm return 1; 822109998Smarkm } 823109998Smarkm 824109998Smarkm field_mul = group->meth->field_mul; 825109998Smarkm field_sqr = group->meth->field_sqr; 826109998Smarkm p = &group->field; 827109998Smarkm 828109998Smarkm if (ctx == NULL) 829109998Smarkm { 830109998Smarkm ctx = new_ctx = BN_CTX_new(); 831109998Smarkm if (ctx == NULL) 832109998Smarkm return 0; 833109998Smarkm } 834109998Smarkm 835109998Smarkm BN_CTX_start(ctx); 836109998Smarkm n0 = BN_CTX_get(ctx); 837109998Smarkm n1 = BN_CTX_get(ctx); 838109998Smarkm n2 = BN_CTX_get(ctx); 839109998Smarkm n3 = BN_CTX_get(ctx); 840109998Smarkm if (n3 == NULL) goto err; 841109998Smarkm 842109998Smarkm /* Note that in this function we must not read components of 'a' 843109998Smarkm * once we have written the corresponding components of 'r'. 844109998Smarkm * ('r' might the same as 'a'.) 845109998Smarkm */ 846109998Smarkm 847109998Smarkm /* n1 */ 848109998Smarkm if (a->Z_is_one) 849109998Smarkm { 850109998Smarkm if (!field_sqr(group, n0, &a->X, ctx)) goto err; 851109998Smarkm if (!BN_mod_lshift1_quick(n1, n0, p)) goto err; 852109998Smarkm if (!BN_mod_add_quick(n0, n0, n1, p)) goto err; 853109998Smarkm if (!BN_mod_add_quick(n1, n0, &group->a, p)) goto err; 854109998Smarkm /* n1 = 3 * X_a^2 + a_curve */ 855109998Smarkm } 856109998Smarkm else if (group->a_is_minus3) 857109998Smarkm { 858109998Smarkm if (!field_sqr(group, n1, &a->Z, ctx)) goto err; 859109998Smarkm if (!BN_mod_add_quick(n0, &a->X, n1, p)) goto err; 860109998Smarkm if (!BN_mod_sub_quick(n2, &a->X, n1, p)) goto err; 861109998Smarkm if (!field_mul(group, n1, n0, n2, ctx)) goto err; 862109998Smarkm if (!BN_mod_lshift1_quick(n0, n1, p)) goto err; 863109998Smarkm if (!BN_mod_add_quick(n1, n0, n1, p)) goto err; 864109998Smarkm /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) 865109998Smarkm * = 3 * X_a^2 - 3 * Z_a^4 */ 866109998Smarkm } 867109998Smarkm else 868109998Smarkm { 869109998Smarkm if (!field_sqr(group, n0, &a->X, ctx)) goto err; 870109998Smarkm if (!BN_mod_lshift1_quick(n1, n0, p)) goto err; 871109998Smarkm if (!BN_mod_add_quick(n0, n0, n1, p)) goto err; 872109998Smarkm if (!field_sqr(group, n1, &a->Z, ctx)) goto err; 873109998Smarkm if (!field_sqr(group, n1, n1, ctx)) goto err; 874109998Smarkm if (!field_mul(group, n1, n1, &group->a, ctx)) goto err; 875109998Smarkm if (!BN_mod_add_quick(n1, n1, n0, p)) goto err; 876109998Smarkm /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */ 877109998Smarkm } 878109998Smarkm 879109998Smarkm /* Z_r */ 880109998Smarkm if (a->Z_is_one) 881109998Smarkm { 882109998Smarkm if (!BN_copy(n0, &a->Y)) goto err; 883109998Smarkm } 884109998Smarkm else 885109998Smarkm { 886109998Smarkm if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) goto err; 887109998Smarkm } 888109998Smarkm if (!BN_mod_lshift1_quick(&r->Z, n0, p)) goto err; 889109998Smarkm r->Z_is_one = 0; 890109998Smarkm /* Z_r = 2 * Y_a * Z_a */ 891109998Smarkm 892109998Smarkm /* n2 */ 893109998Smarkm if (!field_sqr(group, n3, &a->Y, ctx)) goto err; 894109998Smarkm if (!field_mul(group, n2, &a->X, n3, ctx)) goto err; 895109998Smarkm if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err; 896109998Smarkm /* n2 = 4 * X_a * Y_a^2 */ 897109998Smarkm 898109998Smarkm /* X_r */ 899109998Smarkm if (!BN_mod_lshift1_quick(n0, n2, p)) goto err; 900109998Smarkm if (!field_sqr(group, &r->X, n1, ctx)) goto err; 901109998Smarkm if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) goto err; 902109998Smarkm /* X_r = n1^2 - 2 * n2 */ 903109998Smarkm 904109998Smarkm /* n3 */ 905109998Smarkm if (!field_sqr(group, n0, n3, ctx)) goto err; 906109998Smarkm if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err; 907109998Smarkm /* n3 = 8 * Y_a^4 */ 908109998Smarkm 909109998Smarkm /* Y_r */ 910109998Smarkm if (!BN_mod_sub_quick(n0, n2, &r->X, p)) goto err; 911109998Smarkm if (!field_mul(group, n0, n1, n0, ctx)) goto err; 912109998Smarkm if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) goto err; 913109998Smarkm /* Y_r = n1 * (n2 - X_r) - n3 */ 914109998Smarkm 915109998Smarkm ret = 1; 916109998Smarkm 917109998Smarkm err: 918109998Smarkm BN_CTX_end(ctx); 919109998Smarkm if (new_ctx != NULL) 920109998Smarkm BN_CTX_free(new_ctx); 921109998Smarkm return ret; 922109998Smarkm } 923109998Smarkm 924109998Smarkm 925109998Smarkmint ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 926109998Smarkm { 927109998Smarkm if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) 928109998Smarkm /* point is its own inverse */ 929109998Smarkm return 1; 930109998Smarkm 931109998Smarkm return BN_usub(&point->Y, &group->field, &point->Y); 932109998Smarkm } 933109998Smarkm 934109998Smarkm 935109998Smarkmint ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) 936109998Smarkm { 937109998Smarkm return BN_is_zero(&point->Z); 938109998Smarkm } 939109998Smarkm 940109998Smarkm 941109998Smarkmint ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx) 942109998Smarkm { 943109998Smarkm int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 944109998Smarkm int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 945109998Smarkm const BIGNUM *p; 946109998Smarkm BN_CTX *new_ctx = NULL; 947160814Ssimon BIGNUM *rh, *tmp, *Z4, *Z6; 948109998Smarkm int ret = -1; 949109998Smarkm 950109998Smarkm if (EC_POINT_is_at_infinity(group, point)) 951109998Smarkm return 1; 952109998Smarkm 953109998Smarkm field_mul = group->meth->field_mul; 954109998Smarkm field_sqr = group->meth->field_sqr; 955109998Smarkm p = &group->field; 956109998Smarkm 957109998Smarkm if (ctx == NULL) 958109998Smarkm { 959109998Smarkm ctx = new_ctx = BN_CTX_new(); 960109998Smarkm if (ctx == NULL) 961109998Smarkm return -1; 962109998Smarkm } 963109998Smarkm 964109998Smarkm BN_CTX_start(ctx); 965109998Smarkm rh = BN_CTX_get(ctx); 966160814Ssimon tmp = BN_CTX_get(ctx); 967109998Smarkm Z4 = BN_CTX_get(ctx); 968109998Smarkm Z6 = BN_CTX_get(ctx); 969109998Smarkm if (Z6 == NULL) goto err; 970109998Smarkm 971109998Smarkm /* We have a curve defined by a Weierstrass equation 972109998Smarkm * y^2 = x^3 + a*x + b. 973109998Smarkm * The point to consider is given in Jacobian projective coordinates 974109998Smarkm * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). 975109998Smarkm * Substituting this and multiplying by Z^6 transforms the above equation into 976109998Smarkm * Y^2 = X^3 + a*X*Z^4 + b*Z^6. 977109998Smarkm * To test this, we add up the right-hand side in 'rh'. 978109998Smarkm */ 979109998Smarkm 980160814Ssimon /* rh := X^2 */ 981109998Smarkm if (!field_sqr(group, rh, &point->X, ctx)) goto err; 982109998Smarkm 983109998Smarkm if (!point->Z_is_one) 984109998Smarkm { 985160814Ssimon if (!field_sqr(group, tmp, &point->Z, ctx)) goto err; 986160814Ssimon if (!field_sqr(group, Z4, tmp, ctx)) goto err; 987160814Ssimon if (!field_mul(group, Z6, Z4, tmp, ctx)) goto err; 988109998Smarkm 989160814Ssimon /* rh := (rh + a*Z^4)*X */ 990109998Smarkm if (group->a_is_minus3) 991109998Smarkm { 992160814Ssimon if (!BN_mod_lshift1_quick(tmp, Z4, p)) goto err; 993160814Ssimon if (!BN_mod_add_quick(tmp, tmp, Z4, p)) goto err; 994160814Ssimon if (!BN_mod_sub_quick(rh, rh, tmp, p)) goto err; 995160814Ssimon if (!field_mul(group, rh, rh, &point->X, ctx)) goto err; 996109998Smarkm } 997109998Smarkm else 998109998Smarkm { 999160814Ssimon if (!field_mul(group, tmp, Z4, &group->a, ctx)) goto err; 1000160814Ssimon if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err; 1001160814Ssimon if (!field_mul(group, rh, rh, &point->X, ctx)) goto err; 1002109998Smarkm } 1003109998Smarkm 1004109998Smarkm /* rh := rh + b*Z^6 */ 1005160814Ssimon if (!field_mul(group, tmp, &group->b, Z6, ctx)) goto err; 1006160814Ssimon if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err; 1007109998Smarkm } 1008109998Smarkm else 1009109998Smarkm { 1010109998Smarkm /* point->Z_is_one */ 1011109998Smarkm 1012160814Ssimon /* rh := (rh + a)*X */ 1013160814Ssimon if (!BN_mod_add_quick(rh, rh, &group->a, p)) goto err; 1014160814Ssimon if (!field_mul(group, rh, rh, &point->X, ctx)) goto err; 1015109998Smarkm /* rh := rh + b */ 1016109998Smarkm if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err; 1017109998Smarkm } 1018109998Smarkm 1019109998Smarkm /* 'lh' := Y^2 */ 1020160814Ssimon if (!field_sqr(group, tmp, &point->Y, ctx)) goto err; 1021109998Smarkm 1022160814Ssimon ret = (0 == BN_ucmp(tmp, rh)); 1023109998Smarkm 1024109998Smarkm err: 1025109998Smarkm BN_CTX_end(ctx); 1026109998Smarkm if (new_ctx != NULL) 1027109998Smarkm BN_CTX_free(new_ctx); 1028109998Smarkm return ret; 1029109998Smarkm } 1030109998Smarkm 1031109998Smarkm 1032109998Smarkmint ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx) 1033109998Smarkm { 1034109998Smarkm /* return values: 1035109998Smarkm * -1 error 1036109998Smarkm * 0 equal (in affine coordinates) 1037109998Smarkm * 1 not equal 1038109998Smarkm */ 1039109998Smarkm 1040109998Smarkm int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 1041109998Smarkm int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1042109998Smarkm BN_CTX *new_ctx = NULL; 1043109998Smarkm BIGNUM *tmp1, *tmp2, *Za23, *Zb23; 1044109998Smarkm const BIGNUM *tmp1_, *tmp2_; 1045109998Smarkm int ret = -1; 1046109998Smarkm 1047109998Smarkm if (EC_POINT_is_at_infinity(group, a)) 1048109998Smarkm { 1049109998Smarkm return EC_POINT_is_at_infinity(group, b) ? 0 : 1; 1050109998Smarkm } 1051237657Sjkim 1052237657Sjkim if (EC_POINT_is_at_infinity(group, b)) 1053237657Sjkim return 1; 1054109998Smarkm 1055109998Smarkm if (a->Z_is_one && b->Z_is_one) 1056109998Smarkm { 1057109998Smarkm return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; 1058109998Smarkm } 1059109998Smarkm 1060109998Smarkm field_mul = group->meth->field_mul; 1061109998Smarkm field_sqr = group->meth->field_sqr; 1062109998Smarkm 1063109998Smarkm if (ctx == NULL) 1064109998Smarkm { 1065109998Smarkm ctx = new_ctx = BN_CTX_new(); 1066109998Smarkm if (ctx == NULL) 1067109998Smarkm return -1; 1068109998Smarkm } 1069109998Smarkm 1070109998Smarkm BN_CTX_start(ctx); 1071109998Smarkm tmp1 = BN_CTX_get(ctx); 1072109998Smarkm tmp2 = BN_CTX_get(ctx); 1073109998Smarkm Za23 = BN_CTX_get(ctx); 1074109998Smarkm Zb23 = BN_CTX_get(ctx); 1075109998Smarkm if (Zb23 == NULL) goto end; 1076109998Smarkm 1077109998Smarkm /* We have to decide whether 1078109998Smarkm * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), 1079109998Smarkm * or equivalently, whether 1080109998Smarkm * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). 1081109998Smarkm */ 1082109998Smarkm 1083109998Smarkm if (!b->Z_is_one) 1084109998Smarkm { 1085109998Smarkm if (!field_sqr(group, Zb23, &b->Z, ctx)) goto end; 1086109998Smarkm if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) goto end; 1087109998Smarkm tmp1_ = tmp1; 1088109998Smarkm } 1089109998Smarkm else 1090109998Smarkm tmp1_ = &a->X; 1091109998Smarkm if (!a->Z_is_one) 1092109998Smarkm { 1093109998Smarkm if (!field_sqr(group, Za23, &a->Z, ctx)) goto end; 1094109998Smarkm if (!field_mul(group, tmp2, &b->X, Za23, ctx)) goto end; 1095109998Smarkm tmp2_ = tmp2; 1096109998Smarkm } 1097109998Smarkm else 1098109998Smarkm tmp2_ = &b->X; 1099109998Smarkm 1100109998Smarkm /* compare X_a*Z_b^2 with X_b*Z_a^2 */ 1101109998Smarkm if (BN_cmp(tmp1_, tmp2_) != 0) 1102109998Smarkm { 1103109998Smarkm ret = 1; /* points differ */ 1104109998Smarkm goto end; 1105109998Smarkm } 1106109998Smarkm 1107109998Smarkm 1108109998Smarkm if (!b->Z_is_one) 1109109998Smarkm { 1110109998Smarkm if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) goto end; 1111109998Smarkm if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) goto end; 1112109998Smarkm /* tmp1_ = tmp1 */ 1113109998Smarkm } 1114109998Smarkm else 1115109998Smarkm tmp1_ = &a->Y; 1116109998Smarkm if (!a->Z_is_one) 1117109998Smarkm { 1118109998Smarkm if (!field_mul(group, Za23, Za23, &a->Z, ctx)) goto end; 1119109998Smarkm if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) goto end; 1120109998Smarkm /* tmp2_ = tmp2 */ 1121109998Smarkm } 1122109998Smarkm else 1123109998Smarkm tmp2_ = &b->Y; 1124109998Smarkm 1125109998Smarkm /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ 1126109998Smarkm if (BN_cmp(tmp1_, tmp2_) != 0) 1127109998Smarkm { 1128109998Smarkm ret = 1; /* points differ */ 1129109998Smarkm goto end; 1130109998Smarkm } 1131109998Smarkm 1132109998Smarkm /* points are equal */ 1133109998Smarkm ret = 0; 1134109998Smarkm 1135109998Smarkm end: 1136109998Smarkm BN_CTX_end(ctx); 1137109998Smarkm if (new_ctx != NULL) 1138109998Smarkm BN_CTX_free(new_ctx); 1139109998Smarkm return ret; 1140109998Smarkm } 1141109998Smarkm 1142109998Smarkm 1143109998Smarkmint ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 1144109998Smarkm { 1145109998Smarkm BN_CTX *new_ctx = NULL; 1146109998Smarkm BIGNUM *x, *y; 1147109998Smarkm int ret = 0; 1148109998Smarkm 1149109998Smarkm if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) 1150109998Smarkm return 1; 1151109998Smarkm 1152109998Smarkm if (ctx == NULL) 1153109998Smarkm { 1154109998Smarkm ctx = new_ctx = BN_CTX_new(); 1155109998Smarkm if (ctx == NULL) 1156109998Smarkm return 0; 1157109998Smarkm } 1158109998Smarkm 1159109998Smarkm BN_CTX_start(ctx); 1160109998Smarkm x = BN_CTX_get(ctx); 1161109998Smarkm y = BN_CTX_get(ctx); 1162109998Smarkm if (y == NULL) goto err; 1163109998Smarkm 1164109998Smarkm if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err; 1165109998Smarkm if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err; 1166109998Smarkm if (!point->Z_is_one) 1167109998Smarkm { 1168109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR); 1169109998Smarkm goto err; 1170109998Smarkm } 1171109998Smarkm 1172109998Smarkm ret = 1; 1173109998Smarkm 1174109998Smarkm err: 1175109998Smarkm BN_CTX_end(ctx); 1176109998Smarkm if (new_ctx != NULL) 1177109998Smarkm BN_CTX_free(new_ctx); 1178109998Smarkm return ret; 1179109998Smarkm } 1180109998Smarkm 1181109998Smarkm 1182109998Smarkmint ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx) 1183109998Smarkm { 1184109998Smarkm BN_CTX *new_ctx = NULL; 1185279264Sdelphij BIGNUM *tmp, *tmp_Z; 1186279264Sdelphij BIGNUM **prod_Z = NULL; 1187109998Smarkm size_t i; 1188109998Smarkm int ret = 0; 1189109998Smarkm 1190109998Smarkm if (num == 0) 1191109998Smarkm return 1; 1192109998Smarkm 1193109998Smarkm if (ctx == NULL) 1194109998Smarkm { 1195109998Smarkm ctx = new_ctx = BN_CTX_new(); 1196109998Smarkm if (ctx == NULL) 1197109998Smarkm return 0; 1198109998Smarkm } 1199109998Smarkm 1200109998Smarkm BN_CTX_start(ctx); 1201279264Sdelphij tmp = BN_CTX_get(ctx); 1202279264Sdelphij tmp_Z = BN_CTX_get(ctx); 1203279264Sdelphij if (tmp == NULL || tmp_Z == NULL) goto err; 1204109998Smarkm 1205279264Sdelphij prod_Z = OPENSSL_malloc(num * sizeof prod_Z[0]); 1206279264Sdelphij if (prod_Z == NULL) goto err; 1207279264Sdelphij for (i = 0; i < num; i++) 1208279264Sdelphij { 1209279264Sdelphij prod_Z[i] = BN_new(); 1210279264Sdelphij if (prod_Z[i] == NULL) goto err; 1211279264Sdelphij } 1212109998Smarkm 1213279264Sdelphij /* Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z, 1214279264Sdelphij * skipping any zero-valued inputs (pretend that they're 1). */ 1215109998Smarkm 1216279264Sdelphij if (!BN_is_zero(&points[0]->Z)) 1217109998Smarkm { 1218279264Sdelphij if (!BN_copy(prod_Z[0], &points[0]->Z)) goto err; 1219279264Sdelphij } 1220279264Sdelphij else 1221279264Sdelphij { 1222279264Sdelphij if (group->meth->field_set_to_one != 0) 1223109998Smarkm { 1224279264Sdelphij if (!group->meth->field_set_to_one(group, prod_Z[0], ctx)) goto err; 1225109998Smarkm } 1226279264Sdelphij else 1227279264Sdelphij { 1228279264Sdelphij if (!BN_one(prod_Z[0])) goto err; 1229279264Sdelphij } 1230109998Smarkm } 1231109998Smarkm 1232279264Sdelphij for (i = 1; i < num; i++) 1233109998Smarkm { 1234279264Sdelphij if (!BN_is_zero(&points[i]->Z)) 1235109998Smarkm { 1236279264Sdelphij if (!group->meth->field_mul(group, prod_Z[i], prod_Z[i - 1], &points[i]->Z, ctx)) goto err; 1237109998Smarkm } 1238279264Sdelphij else 1239279264Sdelphij { 1240279264Sdelphij if (!BN_copy(prod_Z[i], prod_Z[i - 1])) goto err; 1241279264Sdelphij } 1242109998Smarkm } 1243279264Sdelphij 1244279264Sdelphij /* Now use a single explicit inversion to replace every 1245279264Sdelphij * non-zero points[i]->Z by its inverse. */ 1246279264Sdelphij 1247279264Sdelphij if (!BN_mod_inverse(tmp, prod_Z[num - 1], &group->field, ctx)) 1248279264Sdelphij { 1249279264Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB); 1250279264Sdelphij goto err; 1251279264Sdelphij } 1252109998Smarkm if (group->meth->field_encode != 0) 1253109998Smarkm { 1254279264Sdelphij /* In the Montgomery case, we just turned R*H (representing H) 1255109998Smarkm * into 1/(R*H), but we need R*(1/H) (representing 1/H); 1256279264Sdelphij * i.e. we need to multiply by the Montgomery factor twice. */ 1257279264Sdelphij if (!group->meth->field_encode(group, tmp, tmp, ctx)) goto err; 1258279264Sdelphij if (!group->meth->field_encode(group, tmp, tmp, ctx)) goto err; 1259109998Smarkm } 1260109998Smarkm 1261279264Sdelphij for (i = num - 1; i > 0; --i) 1262109998Smarkm { 1263279264Sdelphij /* Loop invariant: tmp is the product of the inverses of 1264279264Sdelphij * points[0]->Z .. points[i]->Z (zero-valued inputs skipped). */ 1265279264Sdelphij if (!BN_is_zero(&points[i]->Z)) 1266109998Smarkm { 1267279264Sdelphij /* Set tmp_Z to the inverse of points[i]->Z (as product 1268279264Sdelphij * of Z inverses 0 .. i, Z values 0 .. i - 1). */ 1269279264Sdelphij if (!group->meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx)) goto err; 1270279264Sdelphij /* Update tmp to satisfy the loop invariant for i - 1. */ 1271279264Sdelphij if (!group->meth->field_mul(group, tmp, tmp, &points[i]->Z, ctx)) goto err; 1272279264Sdelphij /* Replace points[i]->Z by its inverse. */ 1273279264Sdelphij if (!BN_copy(&points[i]->Z, tmp_Z)) goto err; 1274109998Smarkm } 1275109998Smarkm } 1276109998Smarkm 1277279264Sdelphij if (!BN_is_zero(&points[0]->Z)) 1278279264Sdelphij { 1279279264Sdelphij /* Replace points[0]->Z by its inverse. */ 1280279264Sdelphij if (!BN_copy(&points[0]->Z, tmp)) goto err; 1281279264Sdelphij } 1282279264Sdelphij 1283279264Sdelphij /* Finally, fix up the X and Y coordinates for all points. */ 1284279264Sdelphij 1285109998Smarkm for (i = 0; i < num; i++) 1286109998Smarkm { 1287109998Smarkm EC_POINT *p = points[i]; 1288279264Sdelphij 1289109998Smarkm if (!BN_is_zero(&p->Z)) 1290109998Smarkm { 1291109998Smarkm /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */ 1292109998Smarkm 1293279264Sdelphij if (!group->meth->field_sqr(group, tmp, &p->Z, ctx)) goto err; 1294279264Sdelphij if (!group->meth->field_mul(group, &p->X, &p->X, tmp, ctx)) goto err; 1295109998Smarkm 1296279264Sdelphij if (!group->meth->field_mul(group, tmp, tmp, &p->Z, ctx)) goto err; 1297279264Sdelphij if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp, ctx)) goto err; 1298279264Sdelphij 1299109998Smarkm if (group->meth->field_set_to_one != 0) 1300109998Smarkm { 1301109998Smarkm if (!group->meth->field_set_to_one(group, &p->Z, ctx)) goto err; 1302109998Smarkm } 1303109998Smarkm else 1304109998Smarkm { 1305109998Smarkm if (!BN_one(&p->Z)) goto err; 1306109998Smarkm } 1307109998Smarkm p->Z_is_one = 1; 1308109998Smarkm } 1309109998Smarkm } 1310109998Smarkm 1311109998Smarkm ret = 1; 1312279264Sdelphij 1313109998Smarkm err: 1314109998Smarkm BN_CTX_end(ctx); 1315109998Smarkm if (new_ctx != NULL) 1316109998Smarkm BN_CTX_free(new_ctx); 1317279264Sdelphij if (prod_Z != NULL) 1318109998Smarkm { 1319279264Sdelphij for (i = 0; i < num; i++) 1320109998Smarkm { 1321279264Sdelphij if (prod_Z[i] == NULL) break; 1322279264Sdelphij BN_clear_free(prod_Z[i]); 1323109998Smarkm } 1324279264Sdelphij OPENSSL_free(prod_Z); 1325109998Smarkm } 1326109998Smarkm return ret; 1327109998Smarkm } 1328109998Smarkm 1329109998Smarkm 1330109998Smarkmint ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 1331109998Smarkm { 1332109998Smarkm return BN_mod_mul(r, a, b, &group->field, ctx); 1333109998Smarkm } 1334109998Smarkm 1335109998Smarkm 1336109998Smarkmint ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) 1337109998Smarkm { 1338109998Smarkm return BN_mod_sqr(r, a, &group->field, ctx); 1339109998Smarkm } 1340