ecp_smpl.c revision 279265
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 68109998Smarkm#include "ec_lcl.h" 69109998Smarkm 70109998Smarkmconst EC_METHOD *EC_GFp_simple_method(void) 71109998Smarkm { 72109998Smarkm static const EC_METHOD ret = { 73160814Ssimon NID_X9_62_prime_field, 74109998Smarkm ec_GFp_simple_group_init, 75109998Smarkm ec_GFp_simple_group_finish, 76109998Smarkm ec_GFp_simple_group_clear_finish, 77109998Smarkm ec_GFp_simple_group_copy, 78160814Ssimon ec_GFp_simple_group_set_curve, 79160814Ssimon ec_GFp_simple_group_get_curve, 80160814Ssimon ec_GFp_simple_group_get_degree, 81160814Ssimon ec_GFp_simple_group_check_discriminant, 82109998Smarkm ec_GFp_simple_point_init, 83109998Smarkm ec_GFp_simple_point_finish, 84109998Smarkm ec_GFp_simple_point_clear_finish, 85109998Smarkm ec_GFp_simple_point_copy, 86109998Smarkm ec_GFp_simple_point_set_to_infinity, 87109998Smarkm ec_GFp_simple_set_Jprojective_coordinates_GFp, 88109998Smarkm ec_GFp_simple_get_Jprojective_coordinates_GFp, 89160814Ssimon ec_GFp_simple_point_set_affine_coordinates, 90160814Ssimon ec_GFp_simple_point_get_affine_coordinates, 91160814Ssimon ec_GFp_simple_set_compressed_coordinates, 92109998Smarkm ec_GFp_simple_point2oct, 93109998Smarkm ec_GFp_simple_oct2point, 94109998Smarkm ec_GFp_simple_add, 95109998Smarkm ec_GFp_simple_dbl, 96109998Smarkm ec_GFp_simple_invert, 97109998Smarkm ec_GFp_simple_is_at_infinity, 98109998Smarkm ec_GFp_simple_is_on_curve, 99109998Smarkm ec_GFp_simple_cmp, 100109998Smarkm ec_GFp_simple_make_affine, 101109998Smarkm ec_GFp_simple_points_make_affine, 102160814Ssimon 0 /* mul */, 103160814Ssimon 0 /* precompute_mult */, 104160814Ssimon 0 /* have_precompute_mult */, 105109998Smarkm ec_GFp_simple_field_mul, 106109998Smarkm ec_GFp_simple_field_sqr, 107160814Ssimon 0 /* field_div */, 108109998Smarkm 0 /* field_encode */, 109109998Smarkm 0 /* field_decode */, 110109998Smarkm 0 /* field_set_to_one */ }; 111109998Smarkm 112109998Smarkm return &ret; 113109998Smarkm } 114109998Smarkm 115109998Smarkm 116160814Ssimon/* Most method functions in this file are designed to work with 117160814Ssimon * non-trivial representations of field elements if necessary 118160814Ssimon * (see ecp_mont.c): while standard modular addition and subtraction 119160814Ssimon * are used, the field_mul and field_sqr methods will be used for 120160814Ssimon * multiplication, and field_encode and field_decode (if defined) 121160814Ssimon * will be used for converting between representations. 122160814Ssimon 123160814Ssimon * Functions ec_GFp_simple_points_make_affine() and 124160814Ssimon * ec_GFp_simple_point_get_affine_coordinates() specifically assume 125160814Ssimon * that if a non-trivial representation is used, it is a Montgomery 126160814Ssimon * representation (i.e. 'encoding' means multiplying by some factor R). 127160814Ssimon */ 128160814Ssimon 129160814Ssimon 130109998Smarkmint ec_GFp_simple_group_init(EC_GROUP *group) 131109998Smarkm { 132109998Smarkm BN_init(&group->field); 133109998Smarkm BN_init(&group->a); 134109998Smarkm BN_init(&group->b); 135109998Smarkm group->a_is_minus3 = 0; 136109998Smarkm return 1; 137109998Smarkm } 138109998Smarkm 139109998Smarkm 140109998Smarkmvoid ec_GFp_simple_group_finish(EC_GROUP *group) 141109998Smarkm { 142109998Smarkm BN_free(&group->field); 143109998Smarkm BN_free(&group->a); 144109998Smarkm BN_free(&group->b); 145109998Smarkm } 146109998Smarkm 147109998Smarkm 148109998Smarkmvoid ec_GFp_simple_group_clear_finish(EC_GROUP *group) 149109998Smarkm { 150109998Smarkm BN_clear_free(&group->field); 151109998Smarkm BN_clear_free(&group->a); 152109998Smarkm BN_clear_free(&group->b); 153109998Smarkm } 154109998Smarkm 155109998Smarkm 156109998Smarkmint ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) 157109998Smarkm { 158109998Smarkm if (!BN_copy(&dest->field, &src->field)) return 0; 159109998Smarkm if (!BN_copy(&dest->a, &src->a)) return 0; 160109998Smarkm if (!BN_copy(&dest->b, &src->b)) return 0; 161109998Smarkm 162109998Smarkm dest->a_is_minus3 = src->a_is_minus3; 163109998Smarkm 164109998Smarkm return 1; 165109998Smarkm } 166109998Smarkm 167109998Smarkm 168160814Ssimonint ec_GFp_simple_group_set_curve(EC_GROUP *group, 169109998Smarkm const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 170109998Smarkm { 171109998Smarkm int ret = 0; 172109998Smarkm BN_CTX *new_ctx = NULL; 173109998Smarkm BIGNUM *tmp_a; 174109998Smarkm 175109998Smarkm /* p must be a prime > 3 */ 176109998Smarkm if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) 177109998Smarkm { 178160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD); 179109998Smarkm return 0; 180109998Smarkm } 181109998Smarkm 182109998Smarkm if (ctx == NULL) 183109998Smarkm { 184109998Smarkm ctx = new_ctx = BN_CTX_new(); 185109998Smarkm if (ctx == NULL) 186109998Smarkm return 0; 187109998Smarkm } 188109998Smarkm 189109998Smarkm BN_CTX_start(ctx); 190109998Smarkm tmp_a = BN_CTX_get(ctx); 191109998Smarkm if (tmp_a == NULL) goto err; 192109998Smarkm 193109998Smarkm /* group->field */ 194109998Smarkm if (!BN_copy(&group->field, p)) goto err; 195160814Ssimon BN_set_negative(&group->field, 0); 196109998Smarkm 197109998Smarkm /* group->a */ 198109998Smarkm if (!BN_nnmod(tmp_a, a, p, ctx)) goto err; 199109998Smarkm if (group->meth->field_encode) 200109998Smarkm { if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) goto err; } 201109998Smarkm else 202109998Smarkm if (!BN_copy(&group->a, tmp_a)) goto err; 203109998Smarkm 204109998Smarkm /* group->b */ 205109998Smarkm if (!BN_nnmod(&group->b, b, p, ctx)) goto err; 206109998Smarkm if (group->meth->field_encode) 207109998Smarkm if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) goto err; 208109998Smarkm 209109998Smarkm /* group->a_is_minus3 */ 210109998Smarkm if (!BN_add_word(tmp_a, 3)) goto err; 211109998Smarkm group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field)); 212109998Smarkm 213109998Smarkm ret = 1; 214109998Smarkm 215109998Smarkm err: 216109998Smarkm BN_CTX_end(ctx); 217109998Smarkm if (new_ctx != NULL) 218109998Smarkm BN_CTX_free(new_ctx); 219109998Smarkm return ret; 220109998Smarkm } 221109998Smarkm 222109998Smarkm 223160814Ssimonint ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx) 224109998Smarkm { 225109998Smarkm int ret = 0; 226109998Smarkm BN_CTX *new_ctx = NULL; 227109998Smarkm 228109998Smarkm if (p != NULL) 229109998Smarkm { 230109998Smarkm if (!BN_copy(p, &group->field)) return 0; 231109998Smarkm } 232109998Smarkm 233109998Smarkm if (a != NULL || b != NULL) 234109998Smarkm { 235109998Smarkm if (group->meth->field_decode) 236109998Smarkm { 237109998Smarkm if (ctx == NULL) 238109998Smarkm { 239109998Smarkm ctx = new_ctx = BN_CTX_new(); 240109998Smarkm if (ctx == NULL) 241109998Smarkm return 0; 242109998Smarkm } 243109998Smarkm if (a != NULL) 244109998Smarkm { 245109998Smarkm if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err; 246109998Smarkm } 247109998Smarkm if (b != NULL) 248109998Smarkm { 249109998Smarkm if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err; 250109998Smarkm } 251109998Smarkm } 252109998Smarkm else 253109998Smarkm { 254109998Smarkm if (a != NULL) 255109998Smarkm { 256109998Smarkm if (!BN_copy(a, &group->a)) goto err; 257109998Smarkm } 258109998Smarkm if (b != NULL) 259109998Smarkm { 260109998Smarkm if (!BN_copy(b, &group->b)) goto err; 261109998Smarkm } 262109998Smarkm } 263109998Smarkm } 264109998Smarkm 265109998Smarkm ret = 1; 266109998Smarkm 267109998Smarkm err: 268109998Smarkm if (new_ctx) 269109998Smarkm BN_CTX_free(new_ctx); 270109998Smarkm return ret; 271109998Smarkm } 272109998Smarkm 273109998Smarkm 274160814Ssimonint ec_GFp_simple_group_get_degree(const EC_GROUP *group) 275160814Ssimon { 276160814Ssimon return BN_num_bits(&group->field); 277160814Ssimon } 278109998Smarkm 279160814Ssimon 280160814Ssimonint ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx) 281109998Smarkm { 282160814Ssimon int ret = 0; 283160814Ssimon BIGNUM *a,*b,*order,*tmp_1,*tmp_2; 284160814Ssimon const BIGNUM *p = &group->field; 285160814Ssimon BN_CTX *new_ctx = NULL; 286160814Ssimon 287160814Ssimon if (ctx == NULL) 288109998Smarkm { 289160814Ssimon ctx = new_ctx = BN_CTX_new(); 290160814Ssimon if (ctx == NULL) 291160814Ssimon { 292160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE); 293160814Ssimon goto err; 294160814Ssimon } 295109998Smarkm } 296160814Ssimon BN_CTX_start(ctx); 297160814Ssimon a = BN_CTX_get(ctx); 298160814Ssimon b = BN_CTX_get(ctx); 299160814Ssimon tmp_1 = BN_CTX_get(ctx); 300160814Ssimon tmp_2 = BN_CTX_get(ctx); 301160814Ssimon order = BN_CTX_get(ctx); 302160814Ssimon if (order == NULL) goto err; 303109998Smarkm 304160814Ssimon if (group->meth->field_decode) 305109998Smarkm { 306160814Ssimon if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err; 307160814Ssimon if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err; 308109998Smarkm } 309109998Smarkm else 310160814Ssimon { 311160814Ssimon if (!BN_copy(a, &group->a)) goto err; 312160814Ssimon if (!BN_copy(b, &group->b)) goto err; 313160814Ssimon } 314160814Ssimon 315160814Ssimon /* check the discriminant: 316160814Ssimon * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p) 317160814Ssimon * 0 =< a, b < p */ 318160814Ssimon if (BN_is_zero(a)) 319160814Ssimon { 320160814Ssimon if (BN_is_zero(b)) goto err; 321160814Ssimon } 322160814Ssimon else if (!BN_is_zero(b)) 323160814Ssimon { 324160814Ssimon if (!BN_mod_sqr(tmp_1, a, p, ctx)) goto err; 325160814Ssimon if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) goto err; 326160814Ssimon if (!BN_lshift(tmp_1, tmp_2, 2)) goto err; 327160814Ssimon /* tmp_1 = 4*a^3 */ 328109998Smarkm 329160814Ssimon if (!BN_mod_sqr(tmp_2, b, p, ctx)) goto err; 330160814Ssimon if (!BN_mul_word(tmp_2, 27)) goto err; 331160814Ssimon /* tmp_2 = 27*b^2 */ 332109998Smarkm 333160814Ssimon if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) goto err; 334160814Ssimon if (BN_is_zero(a)) goto err; 335160814Ssimon } 336160814Ssimon ret = 1; 337109998Smarkm 338160814Ssimonerr: 339160814Ssimon if (ctx != NULL) 340160814Ssimon BN_CTX_end(ctx); 341160814Ssimon if (new_ctx != NULL) 342160814Ssimon BN_CTX_free(new_ctx); 343160814Ssimon return ret; 344109998Smarkm } 345109998Smarkm 346109998Smarkm 347109998Smarkmint ec_GFp_simple_point_init(EC_POINT *point) 348109998Smarkm { 349109998Smarkm BN_init(&point->X); 350109998Smarkm BN_init(&point->Y); 351109998Smarkm BN_init(&point->Z); 352109998Smarkm point->Z_is_one = 0; 353109998Smarkm 354109998Smarkm return 1; 355109998Smarkm } 356109998Smarkm 357109998Smarkm 358109998Smarkmvoid ec_GFp_simple_point_finish(EC_POINT *point) 359109998Smarkm { 360109998Smarkm BN_free(&point->X); 361109998Smarkm BN_free(&point->Y); 362109998Smarkm BN_free(&point->Z); 363109998Smarkm } 364109998Smarkm 365109998Smarkm 366109998Smarkmvoid ec_GFp_simple_point_clear_finish(EC_POINT *point) 367109998Smarkm { 368109998Smarkm BN_clear_free(&point->X); 369109998Smarkm BN_clear_free(&point->Y); 370109998Smarkm BN_clear_free(&point->Z); 371109998Smarkm point->Z_is_one = 0; 372109998Smarkm } 373109998Smarkm 374109998Smarkm 375109998Smarkmint ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) 376109998Smarkm { 377109998Smarkm if (!BN_copy(&dest->X, &src->X)) return 0; 378109998Smarkm if (!BN_copy(&dest->Y, &src->Y)) return 0; 379109998Smarkm if (!BN_copy(&dest->Z, &src->Z)) return 0; 380109998Smarkm dest->Z_is_one = src->Z_is_one; 381109998Smarkm 382109998Smarkm return 1; 383109998Smarkm } 384109998Smarkm 385109998Smarkm 386109998Smarkmint ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point) 387109998Smarkm { 388109998Smarkm point->Z_is_one = 0; 389160814Ssimon BN_zero(&point->Z); 390160814Ssimon return 1; 391109998Smarkm } 392109998Smarkm 393109998Smarkm 394109998Smarkmint ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, 395109998Smarkm const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx) 396109998Smarkm { 397109998Smarkm BN_CTX *new_ctx = NULL; 398109998Smarkm int ret = 0; 399109998Smarkm 400109998Smarkm if (ctx == NULL) 401109998Smarkm { 402109998Smarkm ctx = new_ctx = BN_CTX_new(); 403109998Smarkm if (ctx == NULL) 404109998Smarkm return 0; 405109998Smarkm } 406109998Smarkm 407109998Smarkm if (x != NULL) 408109998Smarkm { 409109998Smarkm if (!BN_nnmod(&point->X, x, &group->field, ctx)) goto err; 410109998Smarkm if (group->meth->field_encode) 411109998Smarkm { 412109998Smarkm if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err; 413109998Smarkm } 414109998Smarkm } 415109998Smarkm 416109998Smarkm if (y != NULL) 417109998Smarkm { 418109998Smarkm if (!BN_nnmod(&point->Y, y, &group->field, ctx)) goto err; 419109998Smarkm if (group->meth->field_encode) 420109998Smarkm { 421109998Smarkm if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err; 422109998Smarkm } 423109998Smarkm } 424109998Smarkm 425109998Smarkm if (z != NULL) 426109998Smarkm { 427109998Smarkm int Z_is_one; 428109998Smarkm 429109998Smarkm if (!BN_nnmod(&point->Z, z, &group->field, ctx)) goto err; 430109998Smarkm Z_is_one = BN_is_one(&point->Z); 431109998Smarkm if (group->meth->field_encode) 432109998Smarkm { 433109998Smarkm if (Z_is_one && (group->meth->field_set_to_one != 0)) 434109998Smarkm { 435109998Smarkm if (!group->meth->field_set_to_one(group, &point->Z, ctx)) goto err; 436109998Smarkm } 437109998Smarkm else 438109998Smarkm { 439109998Smarkm if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err; 440109998Smarkm } 441109998Smarkm } 442109998Smarkm point->Z_is_one = Z_is_one; 443109998Smarkm } 444109998Smarkm 445109998Smarkm ret = 1; 446109998Smarkm 447109998Smarkm err: 448109998Smarkm if (new_ctx != NULL) 449109998Smarkm BN_CTX_free(new_ctx); 450109998Smarkm return ret; 451109998Smarkm } 452109998Smarkm 453109998Smarkm 454109998Smarkmint ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point, 455109998Smarkm BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx) 456109998Smarkm { 457109998Smarkm BN_CTX *new_ctx = NULL; 458109998Smarkm int ret = 0; 459109998Smarkm 460109998Smarkm if (group->meth->field_decode != 0) 461109998Smarkm { 462109998Smarkm if (ctx == NULL) 463109998Smarkm { 464109998Smarkm ctx = new_ctx = BN_CTX_new(); 465109998Smarkm if (ctx == NULL) 466109998Smarkm return 0; 467109998Smarkm } 468109998Smarkm 469109998Smarkm if (x != NULL) 470109998Smarkm { 471109998Smarkm if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err; 472109998Smarkm } 473109998Smarkm if (y != NULL) 474109998Smarkm { 475109998Smarkm if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err; 476109998Smarkm } 477109998Smarkm if (z != NULL) 478109998Smarkm { 479109998Smarkm if (!group->meth->field_decode(group, z, &point->Z, ctx)) goto err; 480109998Smarkm } 481109998Smarkm } 482109998Smarkm else 483109998Smarkm { 484109998Smarkm if (x != NULL) 485109998Smarkm { 486109998Smarkm if (!BN_copy(x, &point->X)) goto err; 487109998Smarkm } 488109998Smarkm if (y != NULL) 489109998Smarkm { 490109998Smarkm if (!BN_copy(y, &point->Y)) goto err; 491109998Smarkm } 492109998Smarkm if (z != NULL) 493109998Smarkm { 494109998Smarkm if (!BN_copy(z, &point->Z)) goto err; 495109998Smarkm } 496109998Smarkm } 497109998Smarkm 498109998Smarkm ret = 1; 499109998Smarkm 500109998Smarkm err: 501109998Smarkm if (new_ctx != NULL) 502109998Smarkm BN_CTX_free(new_ctx); 503109998Smarkm return ret; 504109998Smarkm } 505109998Smarkm 506109998Smarkm 507160814Ssimonint ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point, 508109998Smarkm const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) 509109998Smarkm { 510109998Smarkm if (x == NULL || y == NULL) 511109998Smarkm { 512109998Smarkm /* unlike for projective coordinates, we do not tolerate this */ 513160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER); 514109998Smarkm return 0; 515109998Smarkm } 516109998Smarkm 517109998Smarkm return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx); 518109998Smarkm } 519109998Smarkm 520109998Smarkm 521160814Ssimonint ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point, 522109998Smarkm BIGNUM *x, BIGNUM *y, BN_CTX *ctx) 523109998Smarkm { 524109998Smarkm BN_CTX *new_ctx = NULL; 525160814Ssimon BIGNUM *Z, *Z_1, *Z_2, *Z_3; 526160814Ssimon const BIGNUM *Z_; 527109998Smarkm int ret = 0; 528109998Smarkm 529109998Smarkm if (EC_POINT_is_at_infinity(group, point)) 530109998Smarkm { 531160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY); 532109998Smarkm return 0; 533109998Smarkm } 534109998Smarkm 535109998Smarkm if (ctx == NULL) 536109998Smarkm { 537109998Smarkm ctx = new_ctx = BN_CTX_new(); 538109998Smarkm if (ctx == NULL) 539109998Smarkm return 0; 540109998Smarkm } 541109998Smarkm 542109998Smarkm BN_CTX_start(ctx); 543109998Smarkm Z = BN_CTX_get(ctx); 544109998Smarkm Z_1 = BN_CTX_get(ctx); 545109998Smarkm Z_2 = BN_CTX_get(ctx); 546109998Smarkm Z_3 = BN_CTX_get(ctx); 547109998Smarkm if (Z_3 == NULL) goto err; 548109998Smarkm 549109998Smarkm /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */ 550109998Smarkm 551109998Smarkm if (group->meth->field_decode) 552109998Smarkm { 553109998Smarkm if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto err; 554160814Ssimon Z_ = Z; 555109998Smarkm } 556109998Smarkm else 557109998Smarkm { 558109998Smarkm Z_ = &point->Z; 559109998Smarkm } 560109998Smarkm 561109998Smarkm if (BN_is_one(Z_)) 562109998Smarkm { 563160814Ssimon if (group->meth->field_decode) 564109998Smarkm { 565160814Ssimon if (x != NULL) 566160814Ssimon { 567160814Ssimon if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err; 568160814Ssimon } 569160814Ssimon if (y != NULL) 570160814Ssimon { 571160814Ssimon if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err; 572160814Ssimon } 573109998Smarkm } 574160814Ssimon else 575109998Smarkm { 576160814Ssimon if (x != NULL) 577160814Ssimon { 578160814Ssimon if (!BN_copy(x, &point->X)) goto err; 579160814Ssimon } 580160814Ssimon if (y != NULL) 581160814Ssimon { 582160814Ssimon if (!BN_copy(y, &point->Y)) goto err; 583160814Ssimon } 584109998Smarkm } 585109998Smarkm } 586109998Smarkm else 587109998Smarkm { 588109998Smarkm if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx)) 589109998Smarkm { 590160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_BN_LIB); 591109998Smarkm goto err; 592109998Smarkm } 593109998Smarkm 594109998Smarkm if (group->meth->field_encode == 0) 595109998Smarkm { 596109998Smarkm /* field_sqr works on standard representation */ 597109998Smarkm if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) goto err; 598109998Smarkm } 599109998Smarkm else 600109998Smarkm { 601109998Smarkm if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err; 602109998Smarkm } 603109998Smarkm 604109998Smarkm if (x != NULL) 605109998Smarkm { 606160814Ssimon /* in the Montgomery case, field_mul will cancel out Montgomery factor in X: */ 607160814Ssimon if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) goto err; 608109998Smarkm } 609109998Smarkm 610109998Smarkm if (y != NULL) 611109998Smarkm { 612109998Smarkm if (group->meth->field_encode == 0) 613109998Smarkm { 614109998Smarkm /* field_mul works on standard representation */ 615109998Smarkm if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) goto err; 616109998Smarkm } 617109998Smarkm else 618109998Smarkm { 619109998Smarkm if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err; 620109998Smarkm } 621160814Ssimon 622160814Ssimon /* in the Montgomery case, field_mul will cancel out Montgomery factor in Y: */ 623160814Ssimon if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) goto err; 624109998Smarkm } 625109998Smarkm } 626109998Smarkm 627109998Smarkm ret = 1; 628109998Smarkm 629109998Smarkm err: 630109998Smarkm BN_CTX_end(ctx); 631109998Smarkm if (new_ctx != NULL) 632109998Smarkm BN_CTX_free(new_ctx); 633109998Smarkm return ret; 634109998Smarkm } 635109998Smarkm 636109998Smarkm 637160814Ssimonint ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *point, 638109998Smarkm const BIGNUM *x_, int y_bit, BN_CTX *ctx) 639109998Smarkm { 640109998Smarkm BN_CTX *new_ctx = NULL; 641109998Smarkm BIGNUM *tmp1, *tmp2, *x, *y; 642109998Smarkm int ret = 0; 643109998Smarkm 644160814Ssimon /* clear error queue*/ 645160814Ssimon ERR_clear_error(); 646160814Ssimon 647109998Smarkm if (ctx == NULL) 648109998Smarkm { 649109998Smarkm ctx = new_ctx = BN_CTX_new(); 650109998Smarkm if (ctx == NULL) 651109998Smarkm return 0; 652109998Smarkm } 653109998Smarkm 654109998Smarkm y_bit = (y_bit != 0); 655109998Smarkm 656109998Smarkm BN_CTX_start(ctx); 657109998Smarkm tmp1 = BN_CTX_get(ctx); 658109998Smarkm tmp2 = BN_CTX_get(ctx); 659109998Smarkm x = BN_CTX_get(ctx); 660109998Smarkm y = BN_CTX_get(ctx); 661109998Smarkm if (y == NULL) goto err; 662109998Smarkm 663109998Smarkm /* Recover y. We have a Weierstrass equation 664109998Smarkm * y^2 = x^3 + a*x + b, 665109998Smarkm * so y is one of the square roots of x^3 + a*x + b. 666109998Smarkm */ 667109998Smarkm 668109998Smarkm /* tmp1 := x^3 */ 669109998Smarkm if (!BN_nnmod(x, x_, &group->field,ctx)) goto err; 670109998Smarkm if (group->meth->field_decode == 0) 671109998Smarkm { 672109998Smarkm /* field_{sqr,mul} work on standard representation */ 673109998Smarkm if (!group->meth->field_sqr(group, tmp2, x_, ctx)) goto err; 674109998Smarkm if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) goto err; 675109998Smarkm } 676109998Smarkm else 677109998Smarkm { 678109998Smarkm if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) goto err; 679109998Smarkm if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) goto err; 680109998Smarkm } 681109998Smarkm 682109998Smarkm /* tmp1 := tmp1 + a*x */ 683109998Smarkm if (group->a_is_minus3) 684109998Smarkm { 685109998Smarkm if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) goto err; 686109998Smarkm if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) goto err; 687109998Smarkm if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) goto err; 688109998Smarkm } 689109998Smarkm else 690109998Smarkm { 691109998Smarkm if (group->meth->field_decode) 692109998Smarkm { 693109998Smarkm if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) goto err; 694109998Smarkm if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) goto err; 695109998Smarkm } 696109998Smarkm else 697109998Smarkm { 698109998Smarkm /* field_mul works on standard representation */ 699109998Smarkm if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) goto err; 700109998Smarkm } 701109998Smarkm 702109998Smarkm if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err; 703109998Smarkm } 704109998Smarkm 705109998Smarkm /* tmp1 := tmp1 + b */ 706109998Smarkm if (group->meth->field_decode) 707109998Smarkm { 708109998Smarkm if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) goto err; 709109998Smarkm if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err; 710109998Smarkm } 711109998Smarkm else 712109998Smarkm { 713109998Smarkm if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err; 714109998Smarkm } 715109998Smarkm 716109998Smarkm if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) 717109998Smarkm { 718160814Ssimon unsigned long err = ERR_peek_last_error(); 719109998Smarkm 720109998Smarkm if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) 721109998Smarkm { 722160814Ssimon ERR_clear_error(); 723160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT); 724109998Smarkm } 725109998Smarkm else 726160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_BN_LIB); 727109998Smarkm goto err; 728109998Smarkm } 729109998Smarkm 730109998Smarkm if (y_bit != BN_is_odd(y)) 731109998Smarkm { 732109998Smarkm if (BN_is_zero(y)) 733109998Smarkm { 734109998Smarkm int kron; 735109998Smarkm 736109998Smarkm kron = BN_kronecker(x, &group->field, ctx); 737109998Smarkm if (kron == -2) goto err; 738109998Smarkm 739109998Smarkm if (kron == 1) 740160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSION_BIT); 741109998Smarkm else 742160814Ssimon /* BN_mod_sqrt() should have cought this error (not a square) */ 743160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT); 744109998Smarkm goto err; 745109998Smarkm } 746109998Smarkm if (!BN_usub(y, &group->field, y)) goto err; 747109998Smarkm } 748109998Smarkm if (y_bit != BN_is_odd(y)) 749109998Smarkm { 750160814Ssimon ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_INTERNAL_ERROR); 751109998Smarkm goto err; 752109998Smarkm } 753109998Smarkm 754109998Smarkm if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err; 755109998Smarkm 756109998Smarkm ret = 1; 757109998Smarkm 758109998Smarkm err: 759109998Smarkm BN_CTX_end(ctx); 760109998Smarkm if (new_ctx != NULL) 761109998Smarkm BN_CTX_free(new_ctx); 762109998Smarkm return ret; 763109998Smarkm } 764109998Smarkm 765109998Smarkm 766109998Smarkmsize_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form, 767109998Smarkm unsigned char *buf, size_t len, BN_CTX *ctx) 768109998Smarkm { 769109998Smarkm size_t ret; 770109998Smarkm BN_CTX *new_ctx = NULL; 771109998Smarkm int used_ctx = 0; 772109998Smarkm BIGNUM *x, *y; 773109998Smarkm size_t field_len, i, skip; 774109998Smarkm 775109998Smarkm if ((form != POINT_CONVERSION_COMPRESSED) 776109998Smarkm && (form != POINT_CONVERSION_UNCOMPRESSED) 777109998Smarkm && (form != POINT_CONVERSION_HYBRID)) 778109998Smarkm { 779109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM); 780109998Smarkm goto err; 781109998Smarkm } 782109998Smarkm 783109998Smarkm if (EC_POINT_is_at_infinity(group, point)) 784109998Smarkm { 785109998Smarkm /* encodes to a single 0 octet */ 786109998Smarkm if (buf != NULL) 787109998Smarkm { 788109998Smarkm if (len < 1) 789109998Smarkm { 790109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 791109998Smarkm return 0; 792109998Smarkm } 793109998Smarkm buf[0] = 0; 794109998Smarkm } 795109998Smarkm return 1; 796109998Smarkm } 797109998Smarkm 798109998Smarkm 799109998Smarkm /* ret := required output buffer length */ 800109998Smarkm field_len = BN_num_bytes(&group->field); 801109998Smarkm ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len; 802109998Smarkm 803109998Smarkm /* if 'buf' is NULL, just return required length */ 804109998Smarkm if (buf != NULL) 805109998Smarkm { 806109998Smarkm if (len < ret) 807109998Smarkm { 808109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 809109998Smarkm goto err; 810109998Smarkm } 811109998Smarkm 812109998Smarkm if (ctx == NULL) 813109998Smarkm { 814109998Smarkm ctx = new_ctx = BN_CTX_new(); 815109998Smarkm if (ctx == NULL) 816109998Smarkm return 0; 817109998Smarkm } 818109998Smarkm 819109998Smarkm BN_CTX_start(ctx); 820109998Smarkm used_ctx = 1; 821109998Smarkm x = BN_CTX_get(ctx); 822109998Smarkm y = BN_CTX_get(ctx); 823109998Smarkm if (y == NULL) goto err; 824109998Smarkm 825109998Smarkm if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err; 826109998Smarkm 827109998Smarkm if ((form == POINT_CONVERSION_COMPRESSED || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y)) 828109998Smarkm buf[0] = form + 1; 829109998Smarkm else 830109998Smarkm buf[0] = form; 831109998Smarkm 832109998Smarkm i = 1; 833109998Smarkm 834109998Smarkm skip = field_len - BN_num_bytes(x); 835109998Smarkm if (skip > field_len) 836109998Smarkm { 837109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 838109998Smarkm goto err; 839109998Smarkm } 840109998Smarkm while (skip > 0) 841109998Smarkm { 842109998Smarkm buf[i++] = 0; 843109998Smarkm skip--; 844109998Smarkm } 845109998Smarkm skip = BN_bn2bin(x, buf + i); 846109998Smarkm i += skip; 847109998Smarkm if (i != 1 + field_len) 848109998Smarkm { 849109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 850109998Smarkm goto err; 851109998Smarkm } 852109998Smarkm 853109998Smarkm if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID) 854109998Smarkm { 855109998Smarkm skip = field_len - BN_num_bytes(y); 856109998Smarkm if (skip > field_len) 857109998Smarkm { 858109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 859109998Smarkm goto err; 860109998Smarkm } 861109998Smarkm while (skip > 0) 862109998Smarkm { 863109998Smarkm buf[i++] = 0; 864109998Smarkm skip--; 865109998Smarkm } 866109998Smarkm skip = BN_bn2bin(y, buf + i); 867109998Smarkm i += skip; 868109998Smarkm } 869109998Smarkm 870109998Smarkm if (i != ret) 871109998Smarkm { 872109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 873109998Smarkm goto err; 874109998Smarkm } 875109998Smarkm } 876109998Smarkm 877109998Smarkm if (used_ctx) 878109998Smarkm BN_CTX_end(ctx); 879109998Smarkm if (new_ctx != NULL) 880109998Smarkm BN_CTX_free(new_ctx); 881109998Smarkm return ret; 882109998Smarkm 883109998Smarkm err: 884109998Smarkm if (used_ctx) 885109998Smarkm BN_CTX_end(ctx); 886109998Smarkm if (new_ctx != NULL) 887109998Smarkm BN_CTX_free(new_ctx); 888109998Smarkm return 0; 889109998Smarkm } 890109998Smarkm 891109998Smarkm 892109998Smarkmint ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, 893109998Smarkm const unsigned char *buf, size_t len, BN_CTX *ctx) 894109998Smarkm { 895109998Smarkm point_conversion_form_t form; 896109998Smarkm int y_bit; 897109998Smarkm BN_CTX *new_ctx = NULL; 898109998Smarkm BIGNUM *x, *y; 899109998Smarkm size_t field_len, enc_len; 900109998Smarkm int ret = 0; 901109998Smarkm 902109998Smarkm if (len == 0) 903109998Smarkm { 904109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL); 905109998Smarkm return 0; 906109998Smarkm } 907109998Smarkm form = buf[0]; 908109998Smarkm y_bit = form & 1; 909127128Snectar form = form & ~1U; 910109998Smarkm if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) 911109998Smarkm && (form != POINT_CONVERSION_UNCOMPRESSED) 912109998Smarkm && (form != POINT_CONVERSION_HYBRID)) 913109998Smarkm { 914109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 915109998Smarkm return 0; 916109998Smarkm } 917109998Smarkm if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) 918109998Smarkm { 919109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 920109998Smarkm return 0; 921109998Smarkm } 922109998Smarkm 923109998Smarkm if (form == 0) 924109998Smarkm { 925109998Smarkm if (len != 1) 926109998Smarkm { 927109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 928109998Smarkm return 0; 929109998Smarkm } 930109998Smarkm 931109998Smarkm return EC_POINT_set_to_infinity(group, point); 932109998Smarkm } 933109998Smarkm 934109998Smarkm field_len = BN_num_bytes(&group->field); 935109998Smarkm enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len; 936109998Smarkm 937109998Smarkm if (len != enc_len) 938109998Smarkm { 939109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 940109998Smarkm return 0; 941109998Smarkm } 942109998Smarkm 943109998Smarkm if (ctx == NULL) 944109998Smarkm { 945109998Smarkm ctx = new_ctx = BN_CTX_new(); 946109998Smarkm if (ctx == NULL) 947109998Smarkm return 0; 948109998Smarkm } 949109998Smarkm 950109998Smarkm BN_CTX_start(ctx); 951109998Smarkm x = BN_CTX_get(ctx); 952109998Smarkm y = BN_CTX_get(ctx); 953109998Smarkm if (y == NULL) goto err; 954109998Smarkm 955109998Smarkm if (!BN_bin2bn(buf + 1, field_len, x)) goto err; 956109998Smarkm if (BN_ucmp(x, &group->field) >= 0) 957109998Smarkm { 958109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 959109998Smarkm goto err; 960109998Smarkm } 961109998Smarkm 962109998Smarkm if (form == POINT_CONVERSION_COMPRESSED) 963109998Smarkm { 964109998Smarkm if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) goto err; 965109998Smarkm } 966109998Smarkm else 967109998Smarkm { 968109998Smarkm if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err; 969109998Smarkm if (BN_ucmp(y, &group->field) >= 0) 970109998Smarkm { 971109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 972109998Smarkm goto err; 973109998Smarkm } 974109998Smarkm if (form == POINT_CONVERSION_HYBRID) 975109998Smarkm { 976109998Smarkm if (y_bit != BN_is_odd(y)) 977109998Smarkm { 978109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 979109998Smarkm goto err; 980109998Smarkm } 981109998Smarkm } 982109998Smarkm 983109998Smarkm if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err; 984109998Smarkm } 985109998Smarkm 986109998Smarkm if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */ 987109998Smarkm { 988109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE); 989109998Smarkm goto err; 990109998Smarkm } 991109998Smarkm 992109998Smarkm ret = 1; 993109998Smarkm 994109998Smarkm err: 995109998Smarkm BN_CTX_end(ctx); 996109998Smarkm if (new_ctx != NULL) 997109998Smarkm BN_CTX_free(new_ctx); 998109998Smarkm return ret; 999109998Smarkm } 1000109998Smarkm 1001109998Smarkm 1002109998Smarkmint ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx) 1003109998Smarkm { 1004109998Smarkm int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 1005109998Smarkm int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1006109998Smarkm const BIGNUM *p; 1007109998Smarkm BN_CTX *new_ctx = NULL; 1008109998Smarkm BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6; 1009109998Smarkm int ret = 0; 1010109998Smarkm 1011109998Smarkm if (a == b) 1012109998Smarkm return EC_POINT_dbl(group, r, a, ctx); 1013109998Smarkm if (EC_POINT_is_at_infinity(group, a)) 1014109998Smarkm return EC_POINT_copy(r, b); 1015109998Smarkm if (EC_POINT_is_at_infinity(group, b)) 1016109998Smarkm return EC_POINT_copy(r, a); 1017109998Smarkm 1018109998Smarkm field_mul = group->meth->field_mul; 1019109998Smarkm field_sqr = group->meth->field_sqr; 1020109998Smarkm p = &group->field; 1021109998Smarkm 1022109998Smarkm if (ctx == NULL) 1023109998Smarkm { 1024109998Smarkm ctx = new_ctx = BN_CTX_new(); 1025109998Smarkm if (ctx == NULL) 1026109998Smarkm return 0; 1027109998Smarkm } 1028109998Smarkm 1029109998Smarkm BN_CTX_start(ctx); 1030109998Smarkm n0 = BN_CTX_get(ctx); 1031109998Smarkm n1 = BN_CTX_get(ctx); 1032109998Smarkm n2 = BN_CTX_get(ctx); 1033109998Smarkm n3 = BN_CTX_get(ctx); 1034109998Smarkm n4 = BN_CTX_get(ctx); 1035109998Smarkm n5 = BN_CTX_get(ctx); 1036109998Smarkm n6 = BN_CTX_get(ctx); 1037109998Smarkm if (n6 == NULL) goto end; 1038109998Smarkm 1039109998Smarkm /* Note that in this function we must not read components of 'a' or 'b' 1040109998Smarkm * once we have written the corresponding components of 'r'. 1041109998Smarkm * ('r' might be one of 'a' or 'b'.) 1042109998Smarkm */ 1043109998Smarkm 1044109998Smarkm /* n1, n2 */ 1045109998Smarkm if (b->Z_is_one) 1046109998Smarkm { 1047109998Smarkm if (!BN_copy(n1, &a->X)) goto end; 1048109998Smarkm if (!BN_copy(n2, &a->Y)) goto end; 1049109998Smarkm /* n1 = X_a */ 1050109998Smarkm /* n2 = Y_a */ 1051109998Smarkm } 1052109998Smarkm else 1053109998Smarkm { 1054109998Smarkm if (!field_sqr(group, n0, &b->Z, ctx)) goto end; 1055109998Smarkm if (!field_mul(group, n1, &a->X, n0, ctx)) goto end; 1056109998Smarkm /* n1 = X_a * Z_b^2 */ 1057109998Smarkm 1058109998Smarkm if (!field_mul(group, n0, n0, &b->Z, ctx)) goto end; 1059109998Smarkm if (!field_mul(group, n2, &a->Y, n0, ctx)) goto end; 1060109998Smarkm /* n2 = Y_a * Z_b^3 */ 1061109998Smarkm } 1062109998Smarkm 1063109998Smarkm /* n3, n4 */ 1064109998Smarkm if (a->Z_is_one) 1065109998Smarkm { 1066109998Smarkm if (!BN_copy(n3, &b->X)) goto end; 1067109998Smarkm if (!BN_copy(n4, &b->Y)) goto end; 1068109998Smarkm /* n3 = X_b */ 1069109998Smarkm /* n4 = Y_b */ 1070109998Smarkm } 1071109998Smarkm else 1072109998Smarkm { 1073109998Smarkm if (!field_sqr(group, n0, &a->Z, ctx)) goto end; 1074109998Smarkm if (!field_mul(group, n3, &b->X, n0, ctx)) goto end; 1075109998Smarkm /* n3 = X_b * Z_a^2 */ 1076109998Smarkm 1077109998Smarkm if (!field_mul(group, n0, n0, &a->Z, ctx)) goto end; 1078109998Smarkm if (!field_mul(group, n4, &b->Y, n0, ctx)) goto end; 1079109998Smarkm /* n4 = Y_b * Z_a^3 */ 1080109998Smarkm } 1081109998Smarkm 1082109998Smarkm /* n5, n6 */ 1083109998Smarkm if (!BN_mod_sub_quick(n5, n1, n3, p)) goto end; 1084109998Smarkm if (!BN_mod_sub_quick(n6, n2, n4, p)) goto end; 1085109998Smarkm /* n5 = n1 - n3 */ 1086109998Smarkm /* n6 = n2 - n4 */ 1087109998Smarkm 1088109998Smarkm if (BN_is_zero(n5)) 1089109998Smarkm { 1090109998Smarkm if (BN_is_zero(n6)) 1091109998Smarkm { 1092109998Smarkm /* a is the same point as b */ 1093109998Smarkm BN_CTX_end(ctx); 1094109998Smarkm ret = EC_POINT_dbl(group, r, a, ctx); 1095109998Smarkm ctx = NULL; 1096109998Smarkm goto end; 1097109998Smarkm } 1098109998Smarkm else 1099109998Smarkm { 1100109998Smarkm /* a is the inverse of b */ 1101160814Ssimon BN_zero(&r->Z); 1102109998Smarkm r->Z_is_one = 0; 1103109998Smarkm ret = 1; 1104109998Smarkm goto end; 1105109998Smarkm } 1106109998Smarkm } 1107109998Smarkm 1108109998Smarkm /* 'n7', 'n8' */ 1109109998Smarkm if (!BN_mod_add_quick(n1, n1, n3, p)) goto end; 1110109998Smarkm if (!BN_mod_add_quick(n2, n2, n4, p)) goto end; 1111109998Smarkm /* 'n7' = n1 + n3 */ 1112109998Smarkm /* 'n8' = n2 + n4 */ 1113109998Smarkm 1114109998Smarkm /* Z_r */ 1115109998Smarkm if (a->Z_is_one && b->Z_is_one) 1116109998Smarkm { 1117109998Smarkm if (!BN_copy(&r->Z, n5)) goto end; 1118109998Smarkm } 1119109998Smarkm else 1120109998Smarkm { 1121109998Smarkm if (a->Z_is_one) 1122109998Smarkm { if (!BN_copy(n0, &b->Z)) goto end; } 1123109998Smarkm else if (b->Z_is_one) 1124109998Smarkm { if (!BN_copy(n0, &a->Z)) goto end; } 1125109998Smarkm else 1126109998Smarkm { if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) goto end; } 1127109998Smarkm if (!field_mul(group, &r->Z, n0, n5, ctx)) goto end; 1128109998Smarkm } 1129109998Smarkm r->Z_is_one = 0; 1130109998Smarkm /* Z_r = Z_a * Z_b * n5 */ 1131109998Smarkm 1132109998Smarkm /* X_r */ 1133109998Smarkm if (!field_sqr(group, n0, n6, ctx)) goto end; 1134109998Smarkm if (!field_sqr(group, n4, n5, ctx)) goto end; 1135109998Smarkm if (!field_mul(group, n3, n1, n4, ctx)) goto end; 1136109998Smarkm if (!BN_mod_sub_quick(&r->X, n0, n3, p)) goto end; 1137109998Smarkm /* X_r = n6^2 - n5^2 * 'n7' */ 1138109998Smarkm 1139109998Smarkm /* 'n9' */ 1140109998Smarkm if (!BN_mod_lshift1_quick(n0, &r->X, p)) goto end; 1141109998Smarkm if (!BN_mod_sub_quick(n0, n3, n0, p)) goto end; 1142109998Smarkm /* n9 = n5^2 * 'n7' - 2 * X_r */ 1143109998Smarkm 1144109998Smarkm /* Y_r */ 1145109998Smarkm if (!field_mul(group, n0, n0, n6, ctx)) goto end; 1146109998Smarkm if (!field_mul(group, n5, n4, n5, ctx)) goto end; /* now n5 is n5^3 */ 1147109998Smarkm if (!field_mul(group, n1, n2, n5, ctx)) goto end; 1148109998Smarkm if (!BN_mod_sub_quick(n0, n0, n1, p)) goto end; 1149109998Smarkm if (BN_is_odd(n0)) 1150109998Smarkm if (!BN_add(n0, n0, p)) goto end; 1151109998Smarkm /* now 0 <= n0 < 2*p, and n0 is even */ 1152109998Smarkm if (!BN_rshift1(&r->Y, n0)) goto end; 1153109998Smarkm /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */ 1154109998Smarkm 1155109998Smarkm ret = 1; 1156109998Smarkm 1157109998Smarkm end: 1158109998Smarkm if (ctx) /* otherwise we already called BN_CTX_end */ 1159109998Smarkm BN_CTX_end(ctx); 1160109998Smarkm if (new_ctx != NULL) 1161109998Smarkm BN_CTX_free(new_ctx); 1162109998Smarkm return ret; 1163109998Smarkm } 1164109998Smarkm 1165109998Smarkm 1166109998Smarkmint ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx) 1167109998Smarkm { 1168109998Smarkm int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 1169109998Smarkm int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1170109998Smarkm const BIGNUM *p; 1171109998Smarkm BN_CTX *new_ctx = NULL; 1172109998Smarkm BIGNUM *n0, *n1, *n2, *n3; 1173109998Smarkm int ret = 0; 1174109998Smarkm 1175109998Smarkm if (EC_POINT_is_at_infinity(group, a)) 1176109998Smarkm { 1177160814Ssimon BN_zero(&r->Z); 1178109998Smarkm r->Z_is_one = 0; 1179109998Smarkm return 1; 1180109998Smarkm } 1181109998Smarkm 1182109998Smarkm field_mul = group->meth->field_mul; 1183109998Smarkm field_sqr = group->meth->field_sqr; 1184109998Smarkm p = &group->field; 1185109998Smarkm 1186109998Smarkm if (ctx == NULL) 1187109998Smarkm { 1188109998Smarkm ctx = new_ctx = BN_CTX_new(); 1189109998Smarkm if (ctx == NULL) 1190109998Smarkm return 0; 1191109998Smarkm } 1192109998Smarkm 1193109998Smarkm BN_CTX_start(ctx); 1194109998Smarkm n0 = BN_CTX_get(ctx); 1195109998Smarkm n1 = BN_CTX_get(ctx); 1196109998Smarkm n2 = BN_CTX_get(ctx); 1197109998Smarkm n3 = BN_CTX_get(ctx); 1198109998Smarkm if (n3 == NULL) goto err; 1199109998Smarkm 1200109998Smarkm /* Note that in this function we must not read components of 'a' 1201109998Smarkm * once we have written the corresponding components of 'r'. 1202109998Smarkm * ('r' might the same as 'a'.) 1203109998Smarkm */ 1204109998Smarkm 1205109998Smarkm /* n1 */ 1206109998Smarkm if (a->Z_is_one) 1207109998Smarkm { 1208109998Smarkm if (!field_sqr(group, n0, &a->X, ctx)) goto err; 1209109998Smarkm if (!BN_mod_lshift1_quick(n1, n0, p)) goto err; 1210109998Smarkm if (!BN_mod_add_quick(n0, n0, n1, p)) goto err; 1211109998Smarkm if (!BN_mod_add_quick(n1, n0, &group->a, p)) goto err; 1212109998Smarkm /* n1 = 3 * X_a^2 + a_curve */ 1213109998Smarkm } 1214109998Smarkm else if (group->a_is_minus3) 1215109998Smarkm { 1216109998Smarkm if (!field_sqr(group, n1, &a->Z, ctx)) goto err; 1217109998Smarkm if (!BN_mod_add_quick(n0, &a->X, n1, p)) goto err; 1218109998Smarkm if (!BN_mod_sub_quick(n2, &a->X, n1, p)) goto err; 1219109998Smarkm if (!field_mul(group, n1, n0, n2, ctx)) goto err; 1220109998Smarkm if (!BN_mod_lshift1_quick(n0, n1, p)) goto err; 1221109998Smarkm if (!BN_mod_add_quick(n1, n0, n1, p)) goto err; 1222109998Smarkm /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) 1223109998Smarkm * = 3 * X_a^2 - 3 * Z_a^4 */ 1224109998Smarkm } 1225109998Smarkm else 1226109998Smarkm { 1227109998Smarkm if (!field_sqr(group, n0, &a->X, ctx)) goto err; 1228109998Smarkm if (!BN_mod_lshift1_quick(n1, n0, p)) goto err; 1229109998Smarkm if (!BN_mod_add_quick(n0, n0, n1, p)) goto err; 1230109998Smarkm if (!field_sqr(group, n1, &a->Z, ctx)) goto err; 1231109998Smarkm if (!field_sqr(group, n1, n1, ctx)) goto err; 1232109998Smarkm if (!field_mul(group, n1, n1, &group->a, ctx)) goto err; 1233109998Smarkm if (!BN_mod_add_quick(n1, n1, n0, p)) goto err; 1234109998Smarkm /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */ 1235109998Smarkm } 1236109998Smarkm 1237109998Smarkm /* Z_r */ 1238109998Smarkm if (a->Z_is_one) 1239109998Smarkm { 1240109998Smarkm if (!BN_copy(n0, &a->Y)) goto err; 1241109998Smarkm } 1242109998Smarkm else 1243109998Smarkm { 1244109998Smarkm if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) goto err; 1245109998Smarkm } 1246109998Smarkm if (!BN_mod_lshift1_quick(&r->Z, n0, p)) goto err; 1247109998Smarkm r->Z_is_one = 0; 1248109998Smarkm /* Z_r = 2 * Y_a * Z_a */ 1249109998Smarkm 1250109998Smarkm /* n2 */ 1251109998Smarkm if (!field_sqr(group, n3, &a->Y, ctx)) goto err; 1252109998Smarkm if (!field_mul(group, n2, &a->X, n3, ctx)) goto err; 1253109998Smarkm if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err; 1254109998Smarkm /* n2 = 4 * X_a * Y_a^2 */ 1255109998Smarkm 1256109998Smarkm /* X_r */ 1257109998Smarkm if (!BN_mod_lshift1_quick(n0, n2, p)) goto err; 1258109998Smarkm if (!field_sqr(group, &r->X, n1, ctx)) goto err; 1259109998Smarkm if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) goto err; 1260109998Smarkm /* X_r = n1^2 - 2 * n2 */ 1261109998Smarkm 1262109998Smarkm /* n3 */ 1263109998Smarkm if (!field_sqr(group, n0, n3, ctx)) goto err; 1264109998Smarkm if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err; 1265109998Smarkm /* n3 = 8 * Y_a^4 */ 1266109998Smarkm 1267109998Smarkm /* Y_r */ 1268109998Smarkm if (!BN_mod_sub_quick(n0, n2, &r->X, p)) goto err; 1269109998Smarkm if (!field_mul(group, n0, n1, n0, ctx)) goto err; 1270109998Smarkm if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) goto err; 1271109998Smarkm /* Y_r = n1 * (n2 - X_r) - n3 */ 1272109998Smarkm 1273109998Smarkm ret = 1; 1274109998Smarkm 1275109998Smarkm err: 1276109998Smarkm BN_CTX_end(ctx); 1277109998Smarkm if (new_ctx != NULL) 1278109998Smarkm BN_CTX_free(new_ctx); 1279109998Smarkm return ret; 1280109998Smarkm } 1281109998Smarkm 1282109998Smarkm 1283109998Smarkmint ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 1284109998Smarkm { 1285109998Smarkm if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) 1286109998Smarkm /* point is its own inverse */ 1287109998Smarkm return 1; 1288109998Smarkm 1289109998Smarkm return BN_usub(&point->Y, &group->field, &point->Y); 1290109998Smarkm } 1291109998Smarkm 1292109998Smarkm 1293109998Smarkmint ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) 1294109998Smarkm { 1295109998Smarkm return BN_is_zero(&point->Z); 1296109998Smarkm } 1297109998Smarkm 1298109998Smarkm 1299109998Smarkmint ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx) 1300109998Smarkm { 1301109998Smarkm int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 1302109998Smarkm int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1303109998Smarkm const BIGNUM *p; 1304109998Smarkm BN_CTX *new_ctx = NULL; 1305160814Ssimon BIGNUM *rh, *tmp, *Z4, *Z6; 1306109998Smarkm int ret = -1; 1307109998Smarkm 1308109998Smarkm if (EC_POINT_is_at_infinity(group, point)) 1309109998Smarkm return 1; 1310109998Smarkm 1311109998Smarkm field_mul = group->meth->field_mul; 1312109998Smarkm field_sqr = group->meth->field_sqr; 1313109998Smarkm p = &group->field; 1314109998Smarkm 1315109998Smarkm if (ctx == NULL) 1316109998Smarkm { 1317109998Smarkm ctx = new_ctx = BN_CTX_new(); 1318109998Smarkm if (ctx == NULL) 1319109998Smarkm return -1; 1320109998Smarkm } 1321109998Smarkm 1322109998Smarkm BN_CTX_start(ctx); 1323109998Smarkm rh = BN_CTX_get(ctx); 1324160814Ssimon tmp = BN_CTX_get(ctx); 1325109998Smarkm Z4 = BN_CTX_get(ctx); 1326109998Smarkm Z6 = BN_CTX_get(ctx); 1327109998Smarkm if (Z6 == NULL) goto err; 1328109998Smarkm 1329109998Smarkm /* We have a curve defined by a Weierstrass equation 1330109998Smarkm * y^2 = x^3 + a*x + b. 1331109998Smarkm * The point to consider is given in Jacobian projective coordinates 1332109998Smarkm * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). 1333109998Smarkm * Substituting this and multiplying by Z^6 transforms the above equation into 1334109998Smarkm * Y^2 = X^3 + a*X*Z^4 + b*Z^6. 1335109998Smarkm * To test this, we add up the right-hand side in 'rh'. 1336109998Smarkm */ 1337109998Smarkm 1338160814Ssimon /* rh := X^2 */ 1339109998Smarkm if (!field_sqr(group, rh, &point->X, ctx)) goto err; 1340109998Smarkm 1341109998Smarkm if (!point->Z_is_one) 1342109998Smarkm { 1343160814Ssimon if (!field_sqr(group, tmp, &point->Z, ctx)) goto err; 1344160814Ssimon if (!field_sqr(group, Z4, tmp, ctx)) goto err; 1345160814Ssimon if (!field_mul(group, Z6, Z4, tmp, ctx)) goto err; 1346109998Smarkm 1347160814Ssimon /* rh := (rh + a*Z^4)*X */ 1348109998Smarkm if (group->a_is_minus3) 1349109998Smarkm { 1350160814Ssimon if (!BN_mod_lshift1_quick(tmp, Z4, p)) goto err; 1351160814Ssimon if (!BN_mod_add_quick(tmp, tmp, Z4, p)) goto err; 1352160814Ssimon if (!BN_mod_sub_quick(rh, rh, tmp, p)) goto err; 1353160814Ssimon if (!field_mul(group, rh, rh, &point->X, ctx)) goto err; 1354109998Smarkm } 1355109998Smarkm else 1356109998Smarkm { 1357160814Ssimon if (!field_mul(group, tmp, Z4, &group->a, ctx)) goto err; 1358160814Ssimon if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err; 1359160814Ssimon if (!field_mul(group, rh, rh, &point->X, ctx)) goto err; 1360109998Smarkm } 1361109998Smarkm 1362109998Smarkm /* rh := rh + b*Z^6 */ 1363160814Ssimon if (!field_mul(group, tmp, &group->b, Z6, ctx)) goto err; 1364160814Ssimon if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err; 1365109998Smarkm } 1366109998Smarkm else 1367109998Smarkm { 1368109998Smarkm /* point->Z_is_one */ 1369109998Smarkm 1370160814Ssimon /* rh := (rh + a)*X */ 1371160814Ssimon if (!BN_mod_add_quick(rh, rh, &group->a, p)) goto err; 1372160814Ssimon if (!field_mul(group, rh, rh, &point->X, ctx)) goto err; 1373109998Smarkm /* rh := rh + b */ 1374109998Smarkm if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err; 1375109998Smarkm } 1376109998Smarkm 1377109998Smarkm /* 'lh' := Y^2 */ 1378160814Ssimon if (!field_sqr(group, tmp, &point->Y, ctx)) goto err; 1379109998Smarkm 1380160814Ssimon ret = (0 == BN_ucmp(tmp, rh)); 1381109998Smarkm 1382109998Smarkm err: 1383109998Smarkm BN_CTX_end(ctx); 1384109998Smarkm if (new_ctx != NULL) 1385109998Smarkm BN_CTX_free(new_ctx); 1386109998Smarkm return ret; 1387109998Smarkm } 1388109998Smarkm 1389109998Smarkm 1390109998Smarkmint ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx) 1391109998Smarkm { 1392109998Smarkm /* return values: 1393109998Smarkm * -1 error 1394109998Smarkm * 0 equal (in affine coordinates) 1395109998Smarkm * 1 not equal 1396109998Smarkm */ 1397109998Smarkm 1398109998Smarkm int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); 1399109998Smarkm int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1400109998Smarkm BN_CTX *new_ctx = NULL; 1401109998Smarkm BIGNUM *tmp1, *tmp2, *Za23, *Zb23; 1402109998Smarkm const BIGNUM *tmp1_, *tmp2_; 1403109998Smarkm int ret = -1; 1404109998Smarkm 1405109998Smarkm if (EC_POINT_is_at_infinity(group, a)) 1406109998Smarkm { 1407109998Smarkm return EC_POINT_is_at_infinity(group, b) ? 0 : 1; 1408109998Smarkm } 1409237998Sjkim 1410237998Sjkim if (EC_POINT_is_at_infinity(group, b)) 1411237998Sjkim return 1; 1412109998Smarkm 1413109998Smarkm if (a->Z_is_one && b->Z_is_one) 1414109998Smarkm { 1415109998Smarkm return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; 1416109998Smarkm } 1417109998Smarkm 1418109998Smarkm field_mul = group->meth->field_mul; 1419109998Smarkm field_sqr = group->meth->field_sqr; 1420109998Smarkm 1421109998Smarkm if (ctx == NULL) 1422109998Smarkm { 1423109998Smarkm ctx = new_ctx = BN_CTX_new(); 1424109998Smarkm if (ctx == NULL) 1425109998Smarkm return -1; 1426109998Smarkm } 1427109998Smarkm 1428109998Smarkm BN_CTX_start(ctx); 1429109998Smarkm tmp1 = BN_CTX_get(ctx); 1430109998Smarkm tmp2 = BN_CTX_get(ctx); 1431109998Smarkm Za23 = BN_CTX_get(ctx); 1432109998Smarkm Zb23 = BN_CTX_get(ctx); 1433109998Smarkm if (Zb23 == NULL) goto end; 1434109998Smarkm 1435109998Smarkm /* We have to decide whether 1436109998Smarkm * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), 1437109998Smarkm * or equivalently, whether 1438109998Smarkm * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). 1439109998Smarkm */ 1440109998Smarkm 1441109998Smarkm if (!b->Z_is_one) 1442109998Smarkm { 1443109998Smarkm if (!field_sqr(group, Zb23, &b->Z, ctx)) goto end; 1444109998Smarkm if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) goto end; 1445109998Smarkm tmp1_ = tmp1; 1446109998Smarkm } 1447109998Smarkm else 1448109998Smarkm tmp1_ = &a->X; 1449109998Smarkm if (!a->Z_is_one) 1450109998Smarkm { 1451109998Smarkm if (!field_sqr(group, Za23, &a->Z, ctx)) goto end; 1452109998Smarkm if (!field_mul(group, tmp2, &b->X, Za23, ctx)) goto end; 1453109998Smarkm tmp2_ = tmp2; 1454109998Smarkm } 1455109998Smarkm else 1456109998Smarkm tmp2_ = &b->X; 1457109998Smarkm 1458109998Smarkm /* compare X_a*Z_b^2 with X_b*Z_a^2 */ 1459109998Smarkm if (BN_cmp(tmp1_, tmp2_) != 0) 1460109998Smarkm { 1461109998Smarkm ret = 1; /* points differ */ 1462109998Smarkm goto end; 1463109998Smarkm } 1464109998Smarkm 1465109998Smarkm 1466109998Smarkm if (!b->Z_is_one) 1467109998Smarkm { 1468109998Smarkm if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) goto end; 1469109998Smarkm if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) goto end; 1470109998Smarkm /* tmp1_ = tmp1 */ 1471109998Smarkm } 1472109998Smarkm else 1473109998Smarkm tmp1_ = &a->Y; 1474109998Smarkm if (!a->Z_is_one) 1475109998Smarkm { 1476109998Smarkm if (!field_mul(group, Za23, Za23, &a->Z, ctx)) goto end; 1477109998Smarkm if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) goto end; 1478109998Smarkm /* tmp2_ = tmp2 */ 1479109998Smarkm } 1480109998Smarkm else 1481109998Smarkm tmp2_ = &b->Y; 1482109998Smarkm 1483109998Smarkm /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ 1484109998Smarkm if (BN_cmp(tmp1_, tmp2_) != 0) 1485109998Smarkm { 1486109998Smarkm ret = 1; /* points differ */ 1487109998Smarkm goto end; 1488109998Smarkm } 1489109998Smarkm 1490109998Smarkm /* points are equal */ 1491109998Smarkm ret = 0; 1492109998Smarkm 1493109998Smarkm end: 1494109998Smarkm BN_CTX_end(ctx); 1495109998Smarkm if (new_ctx != NULL) 1496109998Smarkm BN_CTX_free(new_ctx); 1497109998Smarkm return ret; 1498109998Smarkm } 1499109998Smarkm 1500109998Smarkm 1501109998Smarkmint ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) 1502109998Smarkm { 1503109998Smarkm BN_CTX *new_ctx = NULL; 1504109998Smarkm BIGNUM *x, *y; 1505109998Smarkm int ret = 0; 1506109998Smarkm 1507109998Smarkm if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) 1508109998Smarkm return 1; 1509109998Smarkm 1510109998Smarkm if (ctx == NULL) 1511109998Smarkm { 1512109998Smarkm ctx = new_ctx = BN_CTX_new(); 1513109998Smarkm if (ctx == NULL) 1514109998Smarkm return 0; 1515109998Smarkm } 1516109998Smarkm 1517109998Smarkm BN_CTX_start(ctx); 1518109998Smarkm x = BN_CTX_get(ctx); 1519109998Smarkm y = BN_CTX_get(ctx); 1520109998Smarkm if (y == NULL) goto err; 1521109998Smarkm 1522109998Smarkm if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err; 1523109998Smarkm if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err; 1524109998Smarkm if (!point->Z_is_one) 1525109998Smarkm { 1526109998Smarkm ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR); 1527109998Smarkm goto err; 1528109998Smarkm } 1529109998Smarkm 1530109998Smarkm ret = 1; 1531109998Smarkm 1532109998Smarkm err: 1533109998Smarkm BN_CTX_end(ctx); 1534109998Smarkm if (new_ctx != NULL) 1535109998Smarkm BN_CTX_free(new_ctx); 1536109998Smarkm return ret; 1537109998Smarkm } 1538109998Smarkm 1539109998Smarkm 1540109998Smarkmint ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx) 1541109998Smarkm { 1542109998Smarkm BN_CTX *new_ctx = NULL; 1543279265Sdelphij BIGNUM *tmp, *tmp_Z; 1544279265Sdelphij BIGNUM **prod_Z = NULL; 1545109998Smarkm size_t i; 1546109998Smarkm int ret = 0; 1547109998Smarkm 1548109998Smarkm if (num == 0) 1549109998Smarkm return 1; 1550109998Smarkm 1551109998Smarkm if (ctx == NULL) 1552109998Smarkm { 1553109998Smarkm ctx = new_ctx = BN_CTX_new(); 1554109998Smarkm if (ctx == NULL) 1555109998Smarkm return 0; 1556109998Smarkm } 1557109998Smarkm 1558109998Smarkm BN_CTX_start(ctx); 1559279265Sdelphij tmp = BN_CTX_get(ctx); 1560279265Sdelphij tmp_Z = BN_CTX_get(ctx); 1561279265Sdelphij if (tmp == NULL || tmp_Z == NULL) goto err; 1562109998Smarkm 1563279265Sdelphij prod_Z = OPENSSL_malloc(num * sizeof prod_Z[0]); 1564279265Sdelphij if (prod_Z == NULL) goto err; 1565279265Sdelphij for (i = 0; i < num; i++) 1566279265Sdelphij { 1567279265Sdelphij prod_Z[i] = BN_new(); 1568279265Sdelphij if (prod_Z[i] == NULL) goto err; 1569279265Sdelphij } 1570109998Smarkm 1571279265Sdelphij /* Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z, 1572279265Sdelphij * skipping any zero-valued inputs (pretend that they're 1). */ 1573109998Smarkm 1574279265Sdelphij if (!BN_is_zero(&points[0]->Z)) 1575109998Smarkm { 1576279265Sdelphij if (!BN_copy(prod_Z[0], &points[0]->Z)) goto err; 1577279265Sdelphij } 1578279265Sdelphij else 1579279265Sdelphij { 1580279265Sdelphij if (group->meth->field_set_to_one != 0) 1581109998Smarkm { 1582279265Sdelphij if (!group->meth->field_set_to_one(group, prod_Z[0], ctx)) goto err; 1583109998Smarkm } 1584279265Sdelphij else 1585279265Sdelphij { 1586279265Sdelphij if (!BN_one(prod_Z[0])) goto err; 1587279265Sdelphij } 1588109998Smarkm } 1589109998Smarkm 1590279265Sdelphij for (i = 1; i < num; i++) 1591109998Smarkm { 1592279265Sdelphij if (!BN_is_zero(&points[i]->Z)) 1593109998Smarkm { 1594279265Sdelphij if (!group->meth->field_mul(group, prod_Z[i], prod_Z[i - 1], &points[i]->Z, ctx)) goto err; 1595109998Smarkm } 1596279265Sdelphij else 1597279265Sdelphij { 1598279265Sdelphij if (!BN_copy(prod_Z[i], prod_Z[i - 1])) goto err; 1599279265Sdelphij } 1600109998Smarkm } 1601279265Sdelphij 1602279265Sdelphij /* Now use a single explicit inversion to replace every 1603279265Sdelphij * non-zero points[i]->Z by its inverse. */ 1604279265Sdelphij 1605279265Sdelphij if (!BN_mod_inverse(tmp, prod_Z[num - 1], &group->field, ctx)) 1606279265Sdelphij { 1607279265Sdelphij ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB); 1608279265Sdelphij goto err; 1609279265Sdelphij } 1610109998Smarkm if (group->meth->field_encode != 0) 1611109998Smarkm { 1612279265Sdelphij /* In the Montgomery case, we just turned R*H (representing H) 1613109998Smarkm * into 1/(R*H), but we need R*(1/H) (representing 1/H); 1614279265Sdelphij * i.e. we need to multiply by the Montgomery factor twice. */ 1615279265Sdelphij if (!group->meth->field_encode(group, tmp, tmp, ctx)) goto err; 1616279265Sdelphij if (!group->meth->field_encode(group, tmp, tmp, ctx)) goto err; 1617109998Smarkm } 1618109998Smarkm 1619279265Sdelphij for (i = num - 1; i > 0; --i) 1620109998Smarkm { 1621279265Sdelphij /* Loop invariant: tmp is the product of the inverses of 1622279265Sdelphij * points[0]->Z .. points[i]->Z (zero-valued inputs skipped). */ 1623279265Sdelphij if (!BN_is_zero(&points[i]->Z)) 1624109998Smarkm { 1625279265Sdelphij /* Set tmp_Z to the inverse of points[i]->Z (as product 1626279265Sdelphij * of Z inverses 0 .. i, Z values 0 .. i - 1). */ 1627279265Sdelphij if (!group->meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx)) goto err; 1628279265Sdelphij /* Update tmp to satisfy the loop invariant for i - 1. */ 1629279265Sdelphij if (!group->meth->field_mul(group, tmp, tmp, &points[i]->Z, ctx)) goto err; 1630279265Sdelphij /* Replace points[i]->Z by its inverse. */ 1631279265Sdelphij if (!BN_copy(&points[i]->Z, tmp_Z)) goto err; 1632109998Smarkm } 1633109998Smarkm } 1634109998Smarkm 1635279265Sdelphij if (!BN_is_zero(&points[0]->Z)) 1636279265Sdelphij { 1637279265Sdelphij /* Replace points[0]->Z by its inverse. */ 1638279265Sdelphij if (!BN_copy(&points[0]->Z, tmp)) goto err; 1639279265Sdelphij } 1640279265Sdelphij 1641279265Sdelphij /* Finally, fix up the X and Y coordinates for all points. */ 1642279265Sdelphij 1643109998Smarkm for (i = 0; i < num; i++) 1644109998Smarkm { 1645109998Smarkm EC_POINT *p = points[i]; 1646279265Sdelphij 1647109998Smarkm if (!BN_is_zero(&p->Z)) 1648109998Smarkm { 1649109998Smarkm /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */ 1650109998Smarkm 1651279265Sdelphij if (!group->meth->field_sqr(group, tmp, &p->Z, ctx)) goto err; 1652279265Sdelphij if (!group->meth->field_mul(group, &p->X, &p->X, tmp, ctx)) goto err; 1653109998Smarkm 1654279265Sdelphij if (!group->meth->field_mul(group, tmp, tmp, &p->Z, ctx)) goto err; 1655279265Sdelphij if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp, ctx)) goto err; 1656279265Sdelphij 1657109998Smarkm if (group->meth->field_set_to_one != 0) 1658109998Smarkm { 1659109998Smarkm if (!group->meth->field_set_to_one(group, &p->Z, ctx)) goto err; 1660109998Smarkm } 1661109998Smarkm else 1662109998Smarkm { 1663109998Smarkm if (!BN_one(&p->Z)) goto err; 1664109998Smarkm } 1665109998Smarkm p->Z_is_one = 1; 1666109998Smarkm } 1667109998Smarkm } 1668109998Smarkm 1669109998Smarkm ret = 1; 1670279265Sdelphij 1671109998Smarkm err: 1672109998Smarkm BN_CTX_end(ctx); 1673109998Smarkm if (new_ctx != NULL) 1674109998Smarkm BN_CTX_free(new_ctx); 1675279265Sdelphij if (prod_Z != NULL) 1676109998Smarkm { 1677279265Sdelphij for (i = 0; i < num; i++) 1678109998Smarkm { 1679279265Sdelphij if (prod_Z[i] == NULL) break; 1680279265Sdelphij BN_clear_free(prod_Z[i]); 1681109998Smarkm } 1682279265Sdelphij OPENSSL_free(prod_Z); 1683109998Smarkm } 1684109998Smarkm return ret; 1685109998Smarkm } 1686109998Smarkm 1687109998Smarkm 1688109998Smarkmint ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 1689109998Smarkm { 1690109998Smarkm return BN_mod_mul(r, a, b, &group->field, ctx); 1691109998Smarkm } 1692109998Smarkm 1693109998Smarkm 1694109998Smarkmint ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) 1695109998Smarkm { 1696109998Smarkm return BN_mod_sqr(r, a, &group->field, ctx); 1697109998Smarkm } 1698