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