1238384Sjkim/* crypto/ec/ecp_oct.c */ 2280297Sjkim/* 3280297Sjkim * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> 4280297Sjkim * for the OpenSSL project. Includes code written by Bodo Moeller for the 5280297Sjkim * OpenSSL project. 6280297Sjkim */ 7238384Sjkim/* ==================================================================== 8348343Sjkim * Copyright (c) 1998-2019 The OpenSSL Project. All rights reserved. 9238384Sjkim * 10238384Sjkim * Redistribution and use in source and binary forms, with or without 11238384Sjkim * modification, are permitted provided that the following conditions 12238384Sjkim * are met: 13238384Sjkim * 14238384Sjkim * 1. Redistributions of source code must retain the above copyright 15280297Sjkim * notice, this list of conditions and the following disclaimer. 16238384Sjkim * 17238384Sjkim * 2. Redistributions in binary form must reproduce the above copyright 18238384Sjkim * notice, this list of conditions and the following disclaimer in 19238384Sjkim * the documentation and/or other materials provided with the 20238384Sjkim * distribution. 21238384Sjkim * 22238384Sjkim * 3. All advertising materials mentioning features or use of this 23238384Sjkim * software must display the following acknowledgment: 24238384Sjkim * "This product includes software developed by the OpenSSL Project 25238384Sjkim * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 26238384Sjkim * 27238384Sjkim * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 28238384Sjkim * endorse or promote products derived from this software without 29238384Sjkim * prior written permission. For written permission, please contact 30238384Sjkim * openssl-core@openssl.org. 31238384Sjkim * 32238384Sjkim * 5. Products derived from this software may not be called "OpenSSL" 33238384Sjkim * nor may "OpenSSL" appear in their names without prior written 34238384Sjkim * permission of the OpenSSL Project. 35238384Sjkim * 36238384Sjkim * 6. Redistributions of any form whatsoever must retain the following 37238384Sjkim * acknowledgment: 38238384Sjkim * "This product includes software developed by the OpenSSL Project 39238384Sjkim * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 40238384Sjkim * 41238384Sjkim * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 42238384Sjkim * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43238384Sjkim * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 44238384Sjkim * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 45238384Sjkim * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 46238384Sjkim * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 47238384Sjkim * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 48238384Sjkim * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 49238384Sjkim * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 50238384Sjkim * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 51238384Sjkim * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 52238384Sjkim * OF THE POSSIBILITY OF SUCH DAMAGE. 53238384Sjkim * ==================================================================== 54238384Sjkim * 55238384Sjkim * This product includes cryptographic software written by Eric Young 56238384Sjkim * (eay@cryptsoft.com). This product includes software written by Tim 57238384Sjkim * Hudson (tjh@cryptsoft.com). 58238384Sjkim * 59238384Sjkim */ 60238384Sjkim/* ==================================================================== 61238384Sjkim * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 62238384Sjkim * Portions of this software developed by SUN MICROSYSTEMS, INC., 63238384Sjkim * and contributed to the OpenSSL project. 64238384Sjkim */ 65238384Sjkim 66238384Sjkim#include <openssl/err.h> 67238384Sjkim#include <openssl/symhacks.h> 68238384Sjkim 69238384Sjkim#include "ec_lcl.h" 70238384Sjkim 71280297Sjkimint ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, 72280297Sjkim EC_POINT *point, 73280297Sjkim const BIGNUM *x_, int y_bit, 74280297Sjkim BN_CTX *ctx) 75280297Sjkim{ 76280297Sjkim BN_CTX *new_ctx = NULL; 77280297Sjkim BIGNUM *tmp1, *tmp2, *x, *y; 78280297Sjkim int ret = 0; 79238384Sjkim 80280297Sjkim /* clear error queue */ 81280297Sjkim ERR_clear_error(); 82238384Sjkim 83280297Sjkim if (ctx == NULL) { 84280297Sjkim ctx = new_ctx = BN_CTX_new(); 85280297Sjkim if (ctx == NULL) 86280297Sjkim return 0; 87280297Sjkim } 88238384Sjkim 89280297Sjkim y_bit = (y_bit != 0); 90238384Sjkim 91280297Sjkim BN_CTX_start(ctx); 92280297Sjkim tmp1 = BN_CTX_get(ctx); 93280297Sjkim tmp2 = BN_CTX_get(ctx); 94280297Sjkim x = BN_CTX_get(ctx); 95280297Sjkim y = BN_CTX_get(ctx); 96280297Sjkim if (y == NULL) 97280297Sjkim goto err; 98238384Sjkim 99280297Sjkim /*- 100280297Sjkim * Recover y. We have a Weierstrass equation 101280297Sjkim * y^2 = x^3 + a*x + b, 102280297Sjkim * so y is one of the square roots of x^3 + a*x + b. 103280297Sjkim */ 104238384Sjkim 105280297Sjkim /* tmp1 := x^3 */ 106280297Sjkim if (!BN_nnmod(x, x_, &group->field, ctx)) 107280297Sjkim goto err; 108280297Sjkim if (group->meth->field_decode == 0) { 109280297Sjkim /* field_{sqr,mul} work on standard representation */ 110280297Sjkim if (!group->meth->field_sqr(group, tmp2, x_, ctx)) 111280297Sjkim goto err; 112280297Sjkim if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) 113280297Sjkim goto err; 114280297Sjkim } else { 115280297Sjkim if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) 116280297Sjkim goto err; 117280297Sjkim if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) 118280297Sjkim goto err; 119280297Sjkim } 120238384Sjkim 121280297Sjkim /* tmp1 := tmp1 + a*x */ 122280297Sjkim if (group->a_is_minus3) { 123280297Sjkim if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) 124280297Sjkim goto err; 125280297Sjkim if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) 126280297Sjkim goto err; 127280297Sjkim if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) 128280297Sjkim goto err; 129280297Sjkim } else { 130280297Sjkim if (group->meth->field_decode) { 131280297Sjkim if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) 132280297Sjkim goto err; 133280297Sjkim if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) 134280297Sjkim goto err; 135280297Sjkim } else { 136280297Sjkim /* field_mul works on standard representation */ 137280297Sjkim if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) 138280297Sjkim goto err; 139280297Sjkim } 140238384Sjkim 141280297Sjkim if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) 142280297Sjkim goto err; 143280297Sjkim } 144238384Sjkim 145280297Sjkim /* tmp1 := tmp1 + b */ 146280297Sjkim if (group->meth->field_decode) { 147280297Sjkim if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) 148280297Sjkim goto err; 149280297Sjkim if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) 150280297Sjkim goto err; 151280297Sjkim } else { 152280297Sjkim if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) 153280297Sjkim goto err; 154280297Sjkim } 155238384Sjkim 156280297Sjkim if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) { 157280297Sjkim unsigned long err = ERR_peek_last_error(); 158238384Sjkim 159280297Sjkim if (ERR_GET_LIB(err) == ERR_LIB_BN 160280297Sjkim && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) { 161280297Sjkim ERR_clear_error(); 162280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 163280297Sjkim EC_R_INVALID_COMPRESSED_POINT); 164280297Sjkim } else 165280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 166280297Sjkim ERR_R_BN_LIB); 167280297Sjkim goto err; 168280297Sjkim } 169238384Sjkim 170280297Sjkim if (y_bit != BN_is_odd(y)) { 171280297Sjkim if (BN_is_zero(y)) { 172280297Sjkim int kron; 173280297Sjkim 174280297Sjkim kron = BN_kronecker(x, &group->field, ctx); 175280297Sjkim if (kron == -2) 176280297Sjkim goto err; 177280297Sjkim 178280297Sjkim if (kron == 1) 179280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 180280297Sjkim EC_R_INVALID_COMPRESSION_BIT); 181280297Sjkim else 182280297Sjkim /* 183280297Sjkim * BN_mod_sqrt() should have cought this error (not a square) 184280297Sjkim */ 185280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 186280297Sjkim EC_R_INVALID_COMPRESSED_POINT); 187280297Sjkim goto err; 188280297Sjkim } 189280297Sjkim if (!BN_usub(y, &group->field, y)) 190280297Sjkim goto err; 191280297Sjkim } 192280297Sjkim if (y_bit != BN_is_odd(y)) { 193280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 194280297Sjkim ERR_R_INTERNAL_ERROR); 195280297Sjkim goto err; 196280297Sjkim } 197280297Sjkim 198280297Sjkim if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) 199280297Sjkim goto err; 200280297Sjkim 201280297Sjkim ret = 1; 202280297Sjkim 203238384Sjkim err: 204280297Sjkim BN_CTX_end(ctx); 205280297Sjkim if (new_ctx != NULL) 206280297Sjkim BN_CTX_free(new_ctx); 207280297Sjkim return ret; 208280297Sjkim} 209238384Sjkim 210280297Sjkimsize_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, 211280297Sjkim point_conversion_form_t form, 212280297Sjkim unsigned char *buf, size_t len, BN_CTX *ctx) 213280297Sjkim{ 214280297Sjkim size_t ret; 215280297Sjkim BN_CTX *new_ctx = NULL; 216280297Sjkim int used_ctx = 0; 217280297Sjkim BIGNUM *x, *y; 218280297Sjkim size_t field_len, i, skip; 219238384Sjkim 220280297Sjkim if ((form != POINT_CONVERSION_COMPRESSED) 221280297Sjkim && (form != POINT_CONVERSION_UNCOMPRESSED) 222280297Sjkim && (form != POINT_CONVERSION_HYBRID)) { 223280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM); 224280297Sjkim goto err; 225280297Sjkim } 226238384Sjkim 227280297Sjkim if (EC_POINT_is_at_infinity(group, point)) { 228280297Sjkim /* encodes to a single 0 octet */ 229280297Sjkim if (buf != NULL) { 230280297Sjkim if (len < 1) { 231280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 232280297Sjkim return 0; 233280297Sjkim } 234280297Sjkim buf[0] = 0; 235280297Sjkim } 236280297Sjkim return 1; 237280297Sjkim } 238238384Sjkim 239280297Sjkim /* ret := required output buffer length */ 240280297Sjkim field_len = BN_num_bytes(&group->field); 241280297Sjkim ret = 242280297Sjkim (form == 243280297Sjkim POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 244238384Sjkim 245280297Sjkim /* if 'buf' is NULL, just return required length */ 246280297Sjkim if (buf != NULL) { 247280297Sjkim if (len < ret) { 248280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 249280297Sjkim goto err; 250280297Sjkim } 251238384Sjkim 252280297Sjkim if (ctx == NULL) { 253280297Sjkim ctx = new_ctx = BN_CTX_new(); 254280297Sjkim if (ctx == NULL) 255280297Sjkim return 0; 256280297Sjkim } 257238384Sjkim 258280297Sjkim BN_CTX_start(ctx); 259280297Sjkim used_ctx = 1; 260280297Sjkim x = BN_CTX_get(ctx); 261280297Sjkim y = BN_CTX_get(ctx); 262280297Sjkim if (y == NULL) 263280297Sjkim goto err; 264238384Sjkim 265280297Sjkim if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) 266280297Sjkim goto err; 267238384Sjkim 268280297Sjkim if ((form == POINT_CONVERSION_COMPRESSED 269280297Sjkim || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y)) 270280297Sjkim buf[0] = form + 1; 271280297Sjkim else 272280297Sjkim buf[0] = form; 273238384Sjkim 274280297Sjkim i = 1; 275238384Sjkim 276280297Sjkim skip = field_len - BN_num_bytes(x); 277280297Sjkim if (skip > field_len) { 278280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 279280297Sjkim goto err; 280280297Sjkim } 281280297Sjkim while (skip > 0) { 282280297Sjkim buf[i++] = 0; 283280297Sjkim skip--; 284280297Sjkim } 285280297Sjkim skip = BN_bn2bin(x, buf + i); 286280297Sjkim i += skip; 287280297Sjkim if (i != 1 + field_len) { 288280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 289280297Sjkim goto err; 290280297Sjkim } 291238384Sjkim 292280297Sjkim if (form == POINT_CONVERSION_UNCOMPRESSED 293280297Sjkim || form == POINT_CONVERSION_HYBRID) { 294280297Sjkim skip = field_len - BN_num_bytes(y); 295280297Sjkim if (skip > field_len) { 296280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 297280297Sjkim goto err; 298280297Sjkim } 299280297Sjkim while (skip > 0) { 300280297Sjkim buf[i++] = 0; 301280297Sjkim skip--; 302280297Sjkim } 303280297Sjkim skip = BN_bn2bin(y, buf + i); 304280297Sjkim i += skip; 305280297Sjkim } 306238384Sjkim 307280297Sjkim if (i != ret) { 308280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 309280297Sjkim goto err; 310280297Sjkim } 311280297Sjkim } 312238384Sjkim 313280297Sjkim if (used_ctx) 314280297Sjkim BN_CTX_end(ctx); 315280297Sjkim if (new_ctx != NULL) 316280297Sjkim BN_CTX_free(new_ctx); 317280297Sjkim return ret; 318280297Sjkim 319238384Sjkim err: 320280297Sjkim if (used_ctx) 321280297Sjkim BN_CTX_end(ctx); 322280297Sjkim if (new_ctx != NULL) 323280297Sjkim BN_CTX_free(new_ctx); 324280297Sjkim return 0; 325280297Sjkim} 326238384Sjkim 327238384Sjkimint ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, 328280297Sjkim const unsigned char *buf, size_t len, BN_CTX *ctx) 329280297Sjkim{ 330280297Sjkim point_conversion_form_t form; 331280297Sjkim int y_bit; 332280297Sjkim BN_CTX *new_ctx = NULL; 333280297Sjkim BIGNUM *x, *y; 334280297Sjkim size_t field_len, enc_len; 335280297Sjkim int ret = 0; 336238384Sjkim 337280297Sjkim if (len == 0) { 338280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL); 339280297Sjkim return 0; 340280297Sjkim } 341280297Sjkim form = buf[0]; 342280297Sjkim y_bit = form & 1; 343280297Sjkim form = form & ~1U; 344280297Sjkim if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) 345280297Sjkim && (form != POINT_CONVERSION_UNCOMPRESSED) 346280297Sjkim && (form != POINT_CONVERSION_HYBRID)) { 347280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 348280297Sjkim return 0; 349280297Sjkim } 350280297Sjkim if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) { 351280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 352280297Sjkim return 0; 353280297Sjkim } 354238384Sjkim 355280297Sjkim if (form == 0) { 356280297Sjkim if (len != 1) { 357280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 358280297Sjkim return 0; 359280297Sjkim } 360238384Sjkim 361280297Sjkim return EC_POINT_set_to_infinity(group, point); 362280297Sjkim } 363238384Sjkim 364280297Sjkim field_len = BN_num_bytes(&group->field); 365280297Sjkim enc_len = 366280297Sjkim (form == 367280297Sjkim POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 368238384Sjkim 369280297Sjkim if (len != enc_len) { 370280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 371280297Sjkim return 0; 372280297Sjkim } 373238384Sjkim 374280297Sjkim if (ctx == NULL) { 375280297Sjkim ctx = new_ctx = BN_CTX_new(); 376280297Sjkim if (ctx == NULL) 377280297Sjkim return 0; 378280297Sjkim } 379238384Sjkim 380280297Sjkim BN_CTX_start(ctx); 381280297Sjkim x = BN_CTX_get(ctx); 382280297Sjkim y = BN_CTX_get(ctx); 383280297Sjkim if (y == NULL) 384280297Sjkim goto err; 385238384Sjkim 386280297Sjkim if (!BN_bin2bn(buf + 1, field_len, x)) 387280297Sjkim goto err; 388280297Sjkim if (BN_ucmp(x, &group->field) >= 0) { 389280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 390280297Sjkim goto err; 391280297Sjkim } 392238384Sjkim 393280297Sjkim if (form == POINT_CONVERSION_COMPRESSED) { 394280297Sjkim if (!EC_POINT_set_compressed_coordinates_GFp 395280297Sjkim (group, point, x, y_bit, ctx)) 396280297Sjkim goto err; 397280297Sjkim } else { 398280297Sjkim if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) 399280297Sjkim goto err; 400280297Sjkim if (BN_ucmp(y, &group->field) >= 0) { 401280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 402280297Sjkim goto err; 403280297Sjkim } 404280297Sjkim if (form == POINT_CONVERSION_HYBRID) { 405280297Sjkim if (y_bit != BN_is_odd(y)) { 406280297Sjkim ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 407280297Sjkim goto err; 408280297Sjkim } 409280297Sjkim } 410238384Sjkim 411348343Sjkim /* 412348343Sjkim * EC_POINT_set_affine_coordinates_GFp is responsible for checking that 413348343Sjkim * the point is on the curve. 414348343Sjkim */ 415280297Sjkim if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) 416280297Sjkim goto err; 417280297Sjkim } 418280297Sjkim 419280297Sjkim ret = 1; 420280297Sjkim 421238384Sjkim err: 422280297Sjkim BN_CTX_end(ctx); 423280297Sjkim if (new_ctx != NULL) 424280297Sjkim BN_CTX_free(new_ctx); 425280297Sjkim return ret; 426280297Sjkim} 427