1/* crypto/ec/ecp_oct.c */ 2/* 3 * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> 4 * for the OpenSSL project. Includes code written by Bodo Moeller for the 5 * OpenSSL project. 6 */ 7/* ==================================================================== 8 * Copyright (c) 1998-2019 The OpenSSL Project. All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in 19 * the documentation and/or other materials provided with the 20 * distribution. 21 * 22 * 3. All advertising materials mentioning features or use of this 23 * software must display the following acknowledgment: 24 * "This product includes software developed by the OpenSSL Project 25 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 26 * 27 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 28 * endorse or promote products derived from this software without 29 * prior written permission. For written permission, please contact 30 * openssl-core@openssl.org. 31 * 32 * 5. Products derived from this software may not be called "OpenSSL" 33 * nor may "OpenSSL" appear in their names without prior written 34 * permission of the OpenSSL Project. 35 * 36 * 6. Redistributions of any form whatsoever must retain the following 37 * acknowledgment: 38 * "This product includes software developed by the OpenSSL Project 39 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 40 * 41 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 42 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 44 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 45 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 46 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 47 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 48 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 49 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 50 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 51 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 52 * OF THE POSSIBILITY OF SUCH DAMAGE. 53 * ==================================================================== 54 * 55 * This product includes cryptographic software written by Eric Young 56 * (eay@cryptsoft.com). This product includes software written by Tim 57 * Hudson (tjh@cryptsoft.com). 58 * 59 */ 60/* ==================================================================== 61 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 62 * Portions of this software developed by SUN MICROSYSTEMS, INC., 63 * and contributed to the OpenSSL project. 64 */ 65 66#include <openssl/err.h> 67#include <openssl/symhacks.h> 68 69#include "ec_lcl.h" 70 71int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, 72 EC_POINT *point, 73 const BIGNUM *x_, int y_bit, 74 BN_CTX *ctx) 75{ 76 BN_CTX *new_ctx = NULL; 77 BIGNUM *tmp1, *tmp2, *x, *y; 78 int ret = 0; 79 80 /* clear error queue */ 81 ERR_clear_error(); 82 83 if (ctx == NULL) { 84 ctx = new_ctx = BN_CTX_new(); 85 if (ctx == NULL) 86 return 0; 87 } 88 89 y_bit = (y_bit != 0); 90 91 BN_CTX_start(ctx); 92 tmp1 = BN_CTX_get(ctx); 93 tmp2 = BN_CTX_get(ctx); 94 x = BN_CTX_get(ctx); 95 y = BN_CTX_get(ctx); 96 if (y == NULL) 97 goto err; 98 99 /*- 100 * Recover y. We have a Weierstrass equation 101 * y^2 = x^3 + a*x + b, 102 * so y is one of the square roots of x^3 + a*x + b. 103 */ 104 105 /* tmp1 := x^3 */ 106 if (!BN_nnmod(x, x_, &group->field, ctx)) 107 goto err; 108 if (group->meth->field_decode == 0) { 109 /* field_{sqr,mul} work on standard representation */ 110 if (!group->meth->field_sqr(group, tmp2, x_, ctx)) 111 goto err; 112 if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) 113 goto err; 114 } else { 115 if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) 116 goto err; 117 if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) 118 goto err; 119 } 120 121 /* tmp1 := tmp1 + a*x */ 122 if (group->a_is_minus3) { 123 if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) 124 goto err; 125 if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) 126 goto err; 127 if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) 128 goto err; 129 } else { 130 if (group->meth->field_decode) { 131 if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) 132 goto err; 133 if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) 134 goto err; 135 } else { 136 /* field_mul works on standard representation */ 137 if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) 138 goto err; 139 } 140 141 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) 142 goto err; 143 } 144 145 /* tmp1 := tmp1 + b */ 146 if (group->meth->field_decode) { 147 if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) 148 goto err; 149 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) 150 goto err; 151 } else { 152 if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) 153 goto err; 154 } 155 156 if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) { 157 unsigned long err = ERR_peek_last_error(); 158 159 if (ERR_GET_LIB(err) == ERR_LIB_BN 160 && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) { 161 ERR_clear_error(); 162 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 163 EC_R_INVALID_COMPRESSED_POINT); 164 } else 165 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 166 ERR_R_BN_LIB); 167 goto err; 168 } 169 170 if (y_bit != BN_is_odd(y)) { 171 if (BN_is_zero(y)) { 172 int kron; 173 174 kron = BN_kronecker(x, &group->field, ctx); 175 if (kron == -2) 176 goto err; 177 178 if (kron == 1) 179 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 180 EC_R_INVALID_COMPRESSION_BIT); 181 else 182 /* 183 * BN_mod_sqrt() should have cought this error (not a square) 184 */ 185 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 186 EC_R_INVALID_COMPRESSED_POINT); 187 goto err; 188 } 189 if (!BN_usub(y, &group->field, y)) 190 goto err; 191 } 192 if (y_bit != BN_is_odd(y)) { 193 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, 194 ERR_R_INTERNAL_ERROR); 195 goto err; 196 } 197 198 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) 199 goto err; 200 201 ret = 1; 202 203 err: 204 BN_CTX_end(ctx); 205 if (new_ctx != NULL) 206 BN_CTX_free(new_ctx); 207 return ret; 208} 209 210size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, 211 point_conversion_form_t form, 212 unsigned char *buf, size_t len, BN_CTX *ctx) 213{ 214 size_t ret; 215 BN_CTX *new_ctx = NULL; 216 int used_ctx = 0; 217 BIGNUM *x, *y; 218 size_t field_len, i, skip; 219 220 if ((form != POINT_CONVERSION_COMPRESSED) 221 && (form != POINT_CONVERSION_UNCOMPRESSED) 222 && (form != POINT_CONVERSION_HYBRID)) { 223 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM); 224 goto err; 225 } 226 227 if (EC_POINT_is_at_infinity(group, point)) { 228 /* encodes to a single 0 octet */ 229 if (buf != NULL) { 230 if (len < 1) { 231 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 232 return 0; 233 } 234 buf[0] = 0; 235 } 236 return 1; 237 } 238 239 /* ret := required output buffer length */ 240 field_len = BN_num_bytes(&group->field); 241 ret = 242 (form == 243 POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 244 245 /* if 'buf' is NULL, just return required length */ 246 if (buf != NULL) { 247 if (len < ret) { 248 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 249 goto err; 250 } 251 252 if (ctx == NULL) { 253 ctx = new_ctx = BN_CTX_new(); 254 if (ctx == NULL) 255 return 0; 256 } 257 258 BN_CTX_start(ctx); 259 used_ctx = 1; 260 x = BN_CTX_get(ctx); 261 y = BN_CTX_get(ctx); 262 if (y == NULL) 263 goto err; 264 265 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) 266 goto err; 267 268 if ((form == POINT_CONVERSION_COMPRESSED 269 || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y)) 270 buf[0] = form + 1; 271 else 272 buf[0] = form; 273 274 i = 1; 275 276 skip = field_len - BN_num_bytes(x); 277 if (skip > field_len) { 278 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 279 goto err; 280 } 281 while (skip > 0) { 282 buf[i++] = 0; 283 skip--; 284 } 285 skip = BN_bn2bin(x, buf + i); 286 i += skip; 287 if (i != 1 + field_len) { 288 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 289 goto err; 290 } 291 292 if (form == POINT_CONVERSION_UNCOMPRESSED 293 || form == POINT_CONVERSION_HYBRID) { 294 skip = field_len - BN_num_bytes(y); 295 if (skip > field_len) { 296 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 297 goto err; 298 } 299 while (skip > 0) { 300 buf[i++] = 0; 301 skip--; 302 } 303 skip = BN_bn2bin(y, buf + i); 304 i += skip; 305 } 306 307 if (i != ret) { 308 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 309 goto err; 310 } 311 } 312 313 if (used_ctx) 314 BN_CTX_end(ctx); 315 if (new_ctx != NULL) 316 BN_CTX_free(new_ctx); 317 return ret; 318 319 err: 320 if (used_ctx) 321 BN_CTX_end(ctx); 322 if (new_ctx != NULL) 323 BN_CTX_free(new_ctx); 324 return 0; 325} 326 327int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, 328 const unsigned char *buf, size_t len, BN_CTX *ctx) 329{ 330 point_conversion_form_t form; 331 int y_bit; 332 BN_CTX *new_ctx = NULL; 333 BIGNUM *x, *y; 334 size_t field_len, enc_len; 335 int ret = 0; 336 337 if (len == 0) { 338 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL); 339 return 0; 340 } 341 form = buf[0]; 342 y_bit = form & 1; 343 form = form & ~1U; 344 if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) 345 && (form != POINT_CONVERSION_UNCOMPRESSED) 346 && (form != POINT_CONVERSION_HYBRID)) { 347 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 348 return 0; 349 } 350 if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) { 351 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 352 return 0; 353 } 354 355 if (form == 0) { 356 if (len != 1) { 357 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 358 return 0; 359 } 360 361 return EC_POINT_set_to_infinity(group, point); 362 } 363 364 field_len = BN_num_bytes(&group->field); 365 enc_len = 366 (form == 367 POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 368 369 if (len != enc_len) { 370 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 371 return 0; 372 } 373 374 if (ctx == NULL) { 375 ctx = new_ctx = BN_CTX_new(); 376 if (ctx == NULL) 377 return 0; 378 } 379 380 BN_CTX_start(ctx); 381 x = BN_CTX_get(ctx); 382 y = BN_CTX_get(ctx); 383 if (y == NULL) 384 goto err; 385 386 if (!BN_bin2bn(buf + 1, field_len, x)) 387 goto err; 388 if (BN_ucmp(x, &group->field) >= 0) { 389 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 390 goto err; 391 } 392 393 if (form == POINT_CONVERSION_COMPRESSED) { 394 if (!EC_POINT_set_compressed_coordinates_GFp 395 (group, point, x, y_bit, ctx)) 396 goto err; 397 } else { 398 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) 399 goto err; 400 if (BN_ucmp(y, &group->field) >= 0) { 401 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 402 goto err; 403 } 404 if (form == POINT_CONVERSION_HYBRID) { 405 if (y_bit != BN_is_odd(y)) { 406 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 407 goto err; 408 } 409 } 410 411 /* 412 * EC_POINT_set_affine_coordinates_GFp is responsible for checking that 413 * the point is on the curve. 414 */ 415 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) 416 goto err; 417 } 418 419 ret = 1; 420 421 err: 422 BN_CTX_end(ctx); 423 if (new_ctx != NULL) 424 BN_CTX_free(new_ctx); 425 return ret; 426} 427