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, skip; 85 86 if ((form != POINT_CONVERSION_COMPRESSED) && 87 (form != POINT_CONVERSION_UNCOMPRESSED) && 88 (form != POINT_CONVERSION_HYBRID)) { 89 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, EC_R_INVALID_FORM); 90 goto err; 91 } 92 93 if (EC_POINT_is_at_infinity(group, point)) { 94 /* encodes to a single 0 octet */ 95 if (buf != NULL) { 96 if (len < 1) { 97 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, EC_R_BUFFER_TOO_SMALL); 98 return 0; 99 } 100 buf[0] = 0; 101 } 102 return 1; 103 } 104 105 106 /* ret := required output buffer length */ 107 field_len = BN_num_bytes(&group->field); 108 ret = 109 (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 110 111 /* if 'buf' is NULL, just return required length */ 112 if (buf != NULL) { 113 if (len < ret) { 114 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, EC_R_BUFFER_TOO_SMALL); 115 goto err; 116 } 117 118 if (ctx == NULL) { 119 ctx = new_ctx = BN_CTX_new(); 120 if (ctx == NULL) 121 return 0; 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 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) 132 goto err; 133 134 if ((form == POINT_CONVERSION_COMPRESSED || 135 form == POINT_CONVERSION_HYBRID) && 136 BN_is_odd(y)) 137 buf[0] = form + 1; 138 else 139 buf[0] = form; 140 141 i = 1; 142 143 skip = field_len - BN_num_bytes(x); 144 if (skip > field_len) { 145 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR); 146 goto err; 147 } 148 while (skip > 0) { 149 buf[i++] = 0; 150 skip--; 151 } 152 skip = BN_bn2bin(x, buf + i); 153 i += skip; 154 if (i != 1 + field_len) { 155 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR); 156 goto err; 157 } 158 159 if (form == POINT_CONVERSION_UNCOMPRESSED || 160 form == POINT_CONVERSION_HYBRID) { 161 skip = field_len - BN_num_bytes(y); 162 if (skip > field_len) { 163 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR); 164 goto err; 165 } 166 while (skip > 0) { 167 buf[i++] = 0; 168 skip--; 169 } 170 skip = BN_bn2bin(y, buf + i); 171 i += skip; 172 } 173 174 if (i != ret) { 175 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR); 176 goto err; 177 } 178 } 179 180 if (used_ctx) 181 BN_CTX_end(ctx); 182 if (new_ctx != NULL) 183 BN_CTX_free(new_ctx); 184 return ret; 185 186err: 187 if (used_ctx) 188 BN_CTX_end(ctx); 189 if (new_ctx != NULL) 190 BN_CTX_free(new_ctx); 191 return 0; 192} 193 194 195static int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, 196 const uint8_t *buf, size_t len, 197 BN_CTX *ctx) { 198 point_conversion_form_t form; 199 int y_bit; 200 BN_CTX *new_ctx = NULL; 201 BIGNUM *x, *y; 202 size_t field_len, enc_len; 203 int ret = 0; 204 205 if (len == 0) { 206 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_BUFFER_TOO_SMALL); 207 return 0; 208 } 209 form = buf[0]; 210 y_bit = form & 1; 211 form = form & ~1U; 212 if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) && 213 (form != POINT_CONVERSION_UNCOMPRESSED) && 214 (form != POINT_CONVERSION_HYBRID)) { 215 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); 216 return 0; 217 } 218 if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) { 219 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); 220 return 0; 221 } 222 223 if (form == 0) { 224 if (len != 1) { 225 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); 226 return 0; 227 } 228 229 return EC_POINT_set_to_infinity(group, point); 230 } 231 232 field_len = BN_num_bytes(&group->field); 233 enc_len = 234 (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 235 236 if (len != enc_len) { 237 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); 238 return 0; 239 } 240 241 if (ctx == NULL) { 242 ctx = new_ctx = BN_CTX_new(); 243 if (ctx == NULL) 244 return 0; 245 } 246 247 BN_CTX_start(ctx); 248 x = BN_CTX_get(ctx); 249 y = BN_CTX_get(ctx); 250 if (y == NULL) 251 goto err; 252 253 if (!BN_bin2bn(buf + 1, field_len, x)) 254 goto err; 255 if (BN_ucmp(x, &group->field) >= 0) { 256 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); 257 goto err; 258 } 259 260 if (form == POINT_CONVERSION_COMPRESSED) { 261 if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) 262 goto err; 263 } else { 264 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) 265 goto err; 266 if (BN_ucmp(y, &group->field) >= 0) { 267 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); 268 goto err; 269 } 270 if (form == POINT_CONVERSION_HYBRID) { 271 if (y_bit != BN_is_odd(y)) { 272 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); 273 goto err; 274 } 275 } 276 277 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) 278 goto err; 279 } 280 281 if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */ 282 { 283 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_POINT_IS_NOT_ON_CURVE); 284 goto err; 285 } 286 287 ret = 1; 288 289err: 290 BN_CTX_end(ctx); 291 if (new_ctx != NULL) 292 BN_CTX_free(new_ctx); 293 return ret; 294} 295 296int EC_POINT_oct2point(const EC_GROUP *group, EC_POINT *point, 297 const uint8_t *buf, size_t len, BN_CTX *ctx) { 298 if (group->meth->oct2point == 0 && 299 !(group->meth->flags & EC_FLAGS_DEFAULT_OCT)) { 300 OPENSSL_PUT_ERROR(EC, EC_POINT_oct2point, 301 ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 302 return 0; 303 } 304 if (group->meth != point->meth) { 305 OPENSSL_PUT_ERROR(EC, EC_POINT_oct2point, EC_R_INCOMPATIBLE_OBJECTS); 306 return 0; 307 } 308 if (group->meth->flags & EC_FLAGS_DEFAULT_OCT) { 309 return ec_GFp_simple_oct2point(group, point, buf, len, ctx); 310 } 311 312 return group->meth->oct2point(group, point, buf, len, ctx); 313} 314 315size_t EC_POINT_point2oct(const EC_GROUP *group, const EC_POINT *point, 316 point_conversion_form_t form, uint8_t *buf, 317 size_t len, BN_CTX *ctx) { 318 if (group->meth->point2oct == 0 && 319 !(group->meth->flags & EC_FLAGS_DEFAULT_OCT)) { 320 OPENSSL_PUT_ERROR(EC, EC_POINT_point2oct, 321 ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 322 return 0; 323 } 324 if (group->meth != point->meth) { 325 OPENSSL_PUT_ERROR(EC, EC_POINT_point2oct, EC_R_INCOMPATIBLE_OBJECTS); 326 return 0; 327 } 328 if (group->meth->flags & EC_FLAGS_DEFAULT_OCT) { 329 return ec_GFp_simple_point2oct(group, point, form, buf, len, ctx); 330 } 331 332 return group->meth->point2oct(group, point, form, buf, len, ctx); 333} 334 335int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, 336 EC_POINT *point, const BIGNUM *x_, 337 int y_bit, BN_CTX *ctx) { 338 BN_CTX *new_ctx = NULL; 339 BIGNUM *tmp1, *tmp2, *x, *y; 340 int ret = 0; 341 342 ERR_clear_error(); 343 344 if (ctx == NULL) { 345 ctx = new_ctx = BN_CTX_new(); 346 if (ctx == NULL) { 347 return 0; 348 } 349 } 350 351 y_bit = (y_bit != 0); 352 353 BN_CTX_start(ctx); 354 tmp1 = BN_CTX_get(ctx); 355 tmp2 = BN_CTX_get(ctx); 356 x = BN_CTX_get(ctx); 357 y = BN_CTX_get(ctx); 358 if (y == NULL) { 359 goto err; 360 } 361 362 /* Recover y. We have a Weierstrass equation 363 * y^2 = x^3 + a*x + b, 364 * so y is one of the square roots of x^3 + a*x + b. */ 365 366 /* tmp1 := x^3 */ 367 if (!BN_nnmod(x, x_, &group->field, ctx)) { 368 goto err; 369 } 370 371 if (group->meth->field_decode == 0) { 372 /* field_{sqr,mul} work on standard representation */ 373 if (!group->meth->field_sqr(group, tmp2, x_, ctx) || 374 !group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) { 375 goto err; 376 } 377 } else { 378 if (!BN_mod_sqr(tmp2, x_, &group->field, ctx) || 379 !BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) { 380 goto err; 381 } 382 } 383 384 /* tmp1 := tmp1 + a*x */ 385 if (group->a_is_minus3) { 386 if (!BN_mod_lshift1_quick(tmp2, x, &group->field) || 387 !BN_mod_add_quick(tmp2, tmp2, x, &group->field) || 388 !BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) { 389 goto err; 390 } 391 } else { 392 if (group->meth->field_decode) { 393 if (!group->meth->field_decode(group, tmp2, &group->a, ctx) || 394 !BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) { 395 goto err; 396 } 397 } else { 398 /* field_mul works on standard representation */ 399 if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) { 400 goto err; 401 } 402 } 403 404 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) { 405 goto err; 406 } 407 } 408 409 /* tmp1 := tmp1 + b */ 410 if (group->meth->field_decode) { 411 if (!group->meth->field_decode(group, tmp2, &group->b, ctx) || 412 !BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) { 413 goto err; 414 } 415 } else { 416 if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) { 417 goto err; 418 } 419 } 420 421 if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) { 422 unsigned long err = ERR_peek_last_error(); 423 424 if (ERR_GET_LIB(err) == ERR_LIB_BN && 425 ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) { 426 ERR_clear_error(); 427 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, EC_R_INVALID_COMPRESSED_POINT); 428 } else { 429 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, ERR_R_BN_LIB); 430 } 431 goto err; 432 } 433 434 if (y_bit != BN_is_odd(y)) { 435 if (BN_is_zero(y)) { 436 int kron; 437 438 kron = BN_kronecker(x, &group->field, ctx); 439 if (kron == -2) { 440 goto err; 441 } 442 443 if (kron == 1) { 444 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, 445 EC_R_INVALID_COMPRESSION_BIT); 446 } else { 447 /* BN_mod_sqrt() should have cought this error (not a square) */ 448 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, 449 EC_R_INVALID_COMPRESSED_POINT); 450 } 451 goto err; 452 } 453 if (!BN_usub(y, &group->field, y)) { 454 goto err; 455 } 456 } 457 if (y_bit != BN_is_odd(y)) { 458 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, 459 ERR_R_INTERNAL_ERROR); 460 goto err; 461 } 462 463 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) 464 goto err; 465 466 ret = 1; 467 468err: 469 BN_CTX_end(ctx); 470 if (new_ctx != NULL) 471 BN_CTX_free(new_ctx); 472 return ret; 473} 474 475int EC_POINT_set_compressed_coordinates_GFp(const EC_GROUP *group, 476 EC_POINT *point, const BIGNUM *x, 477 int y_bit, BN_CTX *ctx) { 478 if (group->meth->point_set_compressed_coordinates == 0 && 479 !(group->meth->flags & EC_FLAGS_DEFAULT_OCT)) { 480 OPENSSL_PUT_ERROR(EC, EC_POINT_set_compressed_coordinates_GFp, 481 ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); 482 return 0; 483 } 484 if (group->meth != point->meth) { 485 OPENSSL_PUT_ERROR(EC, EC_POINT_set_compressed_coordinates_GFp, 486 EC_R_INCOMPATIBLE_OBJECTS); 487 return 0; 488 } 489 if (group->meth->flags & EC_FLAGS_DEFAULT_OCT) { 490 return ec_GFp_simple_set_compressed_coordinates(group, point, x, y_bit, 491 ctx); 492 } 493 return group->meth->point_set_compressed_coordinates(group, point, x, y_bit, 494 ctx); 495} 496