1 /* $OpenBSD: ec_convert.c,v 1.14 2025/01/05 16:07:08 tb Exp $ */ 2 /* 3 * Originally written by Bodo Moeller for the OpenSSL project. 4 */ 5 /* ==================================================================== 6 * Copyright (c) 1998-2003 The OpenSSL Project. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in 17 * the documentation and/or other materials provided with the 18 * distribution. 19 * 20 * 3. All advertising materials mentioning features or use of this 21 * software must display the following acknowledgment: 22 * "This product includes software developed by the OpenSSL Project 23 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 24 * 25 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 26 * endorse or promote products derived from this software without 27 * prior written permission. For written permission, please contact 28 * openssl-core@openssl.org. 29 * 30 * 5. Products derived from this software may not be called "OpenSSL" 31 * nor may "OpenSSL" appear in their names without prior written 32 * permission of the OpenSSL Project. 33 * 34 * 6. Redistributions of any form whatsoever must retain the following 35 * acknowledgment: 36 * "This product includes software developed by the OpenSSL Project 37 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 38 * 39 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 40 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 41 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 42 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 43 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 45 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 46 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 48 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 49 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 50 * OF THE POSSIBILITY OF SUCH DAMAGE. 51 * ==================================================================== 52 * 53 * This product includes cryptographic software written by Eric Young 54 * (eay@cryptsoft.com). This product includes software written by Tim 55 * Hudson (tjh@cryptsoft.com). 56 * 57 */ 58 /* ==================================================================== 59 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 60 * Binary polynomial ECC support in OpenSSL originally developed by 61 * SUN MICROSYSTEMS, INC., and contributed to the OpenSSL project. 62 */ 63 64 #include <string.h> 65 66 #include <openssl/asn1.h> 67 #include <openssl/err.h> 68 69 #include "asn1_local.h" 70 #include "ec_local.h" 71 72 /* 73 * Internal handling of the point conversion octet 74 * (see X9.62, section 4.4.2, SEC 1 section 2.3.3) 75 * 76 * Only the last three bits of the leading octet of a point should be set. 77 * Bits 3 and 2 encode the conversion form for all points except the point 78 * at infinity. In compressed and hybrid form bit 1 indicates if the even 79 * or the odd solution of the quadratic equation for y should be used. 80 * 81 * The public point_conversion_t enum lacks the point at infinity, so we 82 * ignore it except at the API boundary. 83 */ 84 85 #define EC_POINT_YBIT 0x01 86 87 #define EC_POINT_AT_INFINITY 0x00 88 #define EC_POINT_COMPRESSED 0x02 89 #define EC_POINT_UNCOMPRESSED 0x04 90 #define EC_POINT_HYBRID 0x06 91 #define EC_POINT_CONVERSION_MASK 0x06 92 93 static int 94 ec_conversion_form_is_valid(uint8_t form) 95 { 96 return (form & EC_POINT_CONVERSION_MASK) == form; 97 } 98 99 static int 100 ec_check_hybrid_ybit_is_consistent(uint8_t form, int ybit, const BIGNUM *y) 101 { 102 if (form == EC_POINT_HYBRID && ybit != BN_is_odd(y)) { 103 ECerror(EC_R_INVALID_ENCODING); 104 return 0; 105 } 106 107 return 1; 108 } 109 110 /* Nonzero y-bit only makes sense with compressed or hybrid encoding. */ 111 static int 112 ec_nonzero_ybit_allowed(uint8_t form) 113 { 114 return form == EC_POINT_COMPRESSED || form == EC_POINT_HYBRID; 115 } 116 117 static int 118 ec_add_leading_octet_cbb(CBB *cbb, uint8_t form, int ybit) 119 { 120 if (ec_nonzero_ybit_allowed(form) && ybit != 0) 121 form |= EC_POINT_YBIT; 122 123 return CBB_add_u8(cbb, form); 124 } 125 126 static int 127 ec_get_leading_octet_cbs(CBS *cbs, uint8_t *out_form, int *out_ybit) 128 { 129 uint8_t octet; 130 131 if (!CBS_get_u8(cbs, &octet)) { 132 ECerror(EC_R_BUFFER_TOO_SMALL); 133 return 0; 134 } 135 136 *out_ybit = octet & EC_POINT_YBIT; 137 *out_form = octet & ~EC_POINT_YBIT; 138 139 if (!ec_conversion_form_is_valid(*out_form)) { 140 ECerror(EC_R_INVALID_ENCODING); 141 return 0; 142 } 143 144 if (*out_ybit != 0 && !ec_nonzero_ybit_allowed(*out_form)) { 145 ECerror(EC_R_INVALID_ENCODING); 146 return 0; 147 } 148 149 return 1; 150 } 151 152 static int 153 ec_encoded_length(const EC_GROUP *group, uint8_t form, size_t *out_len) 154 { 155 switch (form) { 156 case EC_POINT_AT_INFINITY: 157 *out_len = 1; 158 return 1; 159 case EC_POINT_COMPRESSED: 160 *out_len = 1 + BN_num_bytes(group->p); 161 return 1; 162 case EC_POINT_UNCOMPRESSED: 163 case EC_POINT_HYBRID: 164 *out_len = 1 + 2 * BN_num_bytes(group->p); 165 return 1; 166 default: 167 return 0; 168 } 169 } 170 171 static int 172 ec_field_element_is_valid(const EC_GROUP *group, const BIGNUM *bn) 173 { 174 /* Ensure bn is in the range [0, p). */ 175 return !BN_is_negative(bn) && BN_cmp(group->p, bn) > 0; 176 } 177 178 static int 179 ec_add_field_element_cbb(CBB *cbb, const EC_GROUP *group, const BIGNUM *bn) 180 { 181 uint8_t *buf = NULL; 182 int buf_len = BN_num_bytes(group->p); 183 184 if (!ec_field_element_is_valid(group, bn)) { 185 ECerror(EC_R_BIGNUM_OUT_OF_RANGE); 186 return 0; 187 } 188 if (!CBB_add_space(cbb, &buf, buf_len)) { 189 ECerror(ERR_R_MALLOC_FAILURE); 190 return 0; 191 } 192 if (BN_bn2binpad(bn, buf, buf_len) != buf_len) { 193 ECerror(ERR_R_MALLOC_FAILURE); 194 return 0; 195 } 196 197 return 1; 198 } 199 200 static int 201 ec_get_field_element_cbs(CBS *cbs, const EC_GROUP *group, BIGNUM *bn) 202 { 203 CBS field_element; 204 205 if (!CBS_get_bytes(cbs, &field_element, BN_num_bytes(group->p))) { 206 ECerror(EC_R_INVALID_ENCODING); 207 return 0; 208 } 209 if (!BN_bin2bn(CBS_data(&field_element), CBS_len(&field_element), bn)) { 210 ECerror(ERR_R_MALLOC_FAILURE); 211 return 0; 212 } 213 if (!ec_field_element_is_valid(group, bn)) { 214 ECerror(EC_R_BIGNUM_OUT_OF_RANGE); 215 return 0; 216 } 217 218 return 1; 219 } 220 221 static size_t 222 ec_point2oct(const EC_GROUP *group, const EC_POINT *point, uint8_t form, 223 unsigned char *buf, size_t len, BN_CTX *ctx) 224 { 225 CBB cbb; 226 BIGNUM *x, *y; 227 size_t encoded_length; 228 size_t ret = 0; 229 230 if (EC_POINT_is_at_infinity(group, point)) 231 form = EC_POINT_AT_INFINITY; 232 233 if (!ec_encoded_length(group, form, &encoded_length)) { 234 ECerror(EC_R_INVALID_FORM); 235 return 0; 236 } 237 238 if (buf == NULL) 239 return encoded_length; 240 241 if (len < encoded_length) { 242 ECerror(EC_R_BUFFER_TOO_SMALL); 243 return 0; 244 } 245 246 BN_CTX_start(ctx); 247 if (!CBB_init_fixed(&cbb, buf, len)) 248 goto err; 249 250 if (form == EC_POINT_AT_INFINITY) { 251 if (!EC_POINT_is_at_infinity(group, point)) 252 goto err; 253 if (!ec_add_leading_octet_cbb(&cbb, form, 0)) 254 goto err; 255 256 goto done; 257 } 258 259 if ((x = BN_CTX_get(ctx)) == NULL) 260 goto err; 261 if ((y = BN_CTX_get(ctx)) == NULL) 262 goto err; 263 if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx)) 264 goto err; 265 266 if (!ec_add_leading_octet_cbb(&cbb, form, BN_is_odd(y))) 267 goto err; 268 269 if (form == EC_POINT_COMPRESSED) { 270 if (!ec_add_field_element_cbb(&cbb, group, x)) 271 goto err; 272 } else { 273 if (!ec_add_field_element_cbb(&cbb, group, x)) 274 goto err; 275 if (!ec_add_field_element_cbb(&cbb, group, y)) 276 goto err; 277 } 278 279 done: 280 if (!CBB_finish(&cbb, NULL, &ret)) 281 goto err; 282 283 if (ret != encoded_length) { 284 ret = 0; 285 goto err; 286 } 287 288 err: 289 CBB_cleanup(&cbb); 290 BN_CTX_end(ctx); 291 292 return ret; 293 } 294 295 static int 296 ec_oct2point(const EC_GROUP *group, EC_POINT *point, 297 const unsigned char *buf, size_t len, BN_CTX *ctx) 298 { 299 CBS cbs; 300 uint8_t form; 301 int ybit; 302 BIGNUM *x, *y; 303 int ret = 0; 304 305 BN_CTX_start(ctx); 306 CBS_init(&cbs, buf, len); 307 308 if (!ec_get_leading_octet_cbs(&cbs, &form, &ybit)) 309 goto err; 310 311 if (form == EC_POINT_AT_INFINITY) { 312 if (!EC_POINT_set_to_infinity(group, point)) 313 goto err; 314 315 goto done; 316 } 317 318 if ((x = BN_CTX_get(ctx)) == NULL) 319 goto err; 320 if ((y = BN_CTX_get(ctx)) == NULL) 321 goto err; 322 323 if (form == EC_POINT_COMPRESSED) { 324 if (!ec_get_field_element_cbs(&cbs, group, x)) 325 goto err; 326 if (!EC_POINT_set_compressed_coordinates(group, point, x, ybit, ctx)) 327 goto err; 328 } else { 329 if (!ec_get_field_element_cbs(&cbs, group, x)) 330 goto err; 331 if (!ec_get_field_element_cbs(&cbs, group, y)) 332 goto err; 333 if (!ec_check_hybrid_ybit_is_consistent(form, ybit, y)) 334 goto err; 335 if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx)) 336 goto err; 337 } 338 339 done: 340 if (CBS_len(&cbs) > 0) { 341 ECerror(EC_R_INVALID_ENCODING); 342 goto err; 343 } 344 345 ret = 1; 346 347 err: 348 BN_CTX_end(ctx); 349 350 return ret; 351 } 352 353 int 354 ec_point_to_octets(const EC_GROUP *group, const EC_POINT *point, int form, 355 unsigned char **out_buf, size_t *out_len, BN_CTX *ctx) 356 { 357 unsigned char *buf = NULL; 358 size_t len = 0; 359 int ret = 0; 360 361 *out_len = 0; 362 363 if (out_buf == NULL || *out_buf != NULL) 364 goto err; 365 366 if ((len = EC_POINT_point2oct(group, point, form, NULL, 0, ctx)) == 0) 367 goto err; 368 if ((buf = calloc(1, len)) == NULL) 369 goto err; 370 if (EC_POINT_point2oct(group, point, form, buf, len, ctx) != len) 371 goto err; 372 373 *out_buf = buf; 374 buf = NULL; 375 *out_len = len; 376 len = 0; 377 378 ret = 1; 379 380 err: 381 freezero(buf, len); 382 383 return ret; 384 } 385 386 int 387 ec_point_from_octets(const EC_GROUP *group, const unsigned char *buf, size_t buf_len, 388 EC_POINT **out_point, uint8_t *out_form, BN_CTX *ctx) 389 { 390 EC_POINT *point; 391 int ret = 0; 392 393 if ((point = *out_point) == NULL) 394 point = EC_POINT_new(group); 395 if (point == NULL) 396 goto err; 397 398 if (!EC_POINT_oct2point(group, point, buf, buf_len, ctx)) 399 goto err; 400 401 if (out_form != NULL) 402 *out_form = buf[0] & ~EC_POINT_YBIT; 403 404 *out_point = point; 405 point = NULL; 406 407 ret = 1; 408 409 err: 410 if (*out_point != point) 411 EC_POINT_free(point); 412 413 return ret; 414 } 415 416 static int 417 ec_normalize_form(const EC_GROUP *group, const EC_POINT *point, int form, 418 uint8_t *out_form) 419 { 420 /* 421 * Established behavior is to reject a request for the form 0 for the 422 * point at infinity even if it is valid. 423 */ 424 if (form <= 0 || form > UINT8_MAX) 425 return 0; 426 if (!ec_conversion_form_is_valid(form)) 427 return 0; 428 429 *out_form = form; 430 if (EC_POINT_is_at_infinity(group, point)) 431 *out_form = EC_POINT_AT_INFINITY; 432 433 return 1; 434 } 435 436 size_t 437 EC_POINT_point2oct(const EC_GROUP *group, const EC_POINT *point, 438 point_conversion_form_t conv_form, unsigned char *buf, size_t len, 439 BN_CTX *ctx_in) 440 { 441 BN_CTX *ctx = NULL; 442 uint8_t form; 443 size_t ret = 0; 444 445 if (!ec_normalize_form(group, point, conv_form, &form)) { 446 ECerror(EC_R_INVALID_FORM); 447 goto err; 448 } 449 450 if ((ctx = ctx_in) == NULL) 451 ctx = BN_CTX_new(); 452 if (ctx == NULL) 453 goto err; 454 455 if (group->meth != point->meth) { 456 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 457 goto err; 458 } 459 ret = ec_point2oct(group, point, form, buf, len, ctx); 460 461 err: 462 if (ctx != ctx_in) 463 BN_CTX_free(ctx); 464 465 return ret; 466 } 467 LCRYPTO_ALIAS(EC_POINT_point2oct); 468 469 int 470 EC_POINT_oct2point(const EC_GROUP *group, EC_POINT *point, 471 const unsigned char *buf, size_t len, BN_CTX *ctx_in) 472 { 473 BN_CTX *ctx; 474 int ret = 0; 475 476 if ((ctx = ctx_in) == NULL) 477 ctx = BN_CTX_new(); 478 if (ctx == NULL) 479 goto err; 480 481 if (group->meth != point->meth) { 482 ECerror(EC_R_INCOMPATIBLE_OBJECTS); 483 goto err; 484 } 485 ret = ec_oct2point(group, point, buf, len, ctx); 486 487 err: 488 if (ctx != ctx_in) 489 BN_CTX_free(ctx); 490 491 return ret; 492 } 493 LCRYPTO_ALIAS(EC_POINT_oct2point); 494 495 BIGNUM * 496 EC_POINT_point2bn(const EC_GROUP *group, const EC_POINT *point, 497 point_conversion_form_t form, BIGNUM *in_bn, BN_CTX *ctx) 498 { 499 BIGNUM *bn = NULL; 500 unsigned char *buf = NULL; 501 size_t buf_len = 0; 502 503 if (!ec_point_to_octets(group, point, form, &buf, &buf_len, ctx)) 504 goto err; 505 if ((bn = BN_bin2bn(buf, buf_len, in_bn)) == NULL) 506 goto err; 507 508 err: 509 freezero(buf, buf_len); 510 511 return bn; 512 } 513 LCRYPTO_ALIAS(EC_POINT_point2bn); 514 515 EC_POINT * 516 EC_POINT_bn2point(const EC_GROUP *group, 517 const BIGNUM *bn, EC_POINT *point, BN_CTX *ctx) 518 { 519 unsigned char *buf = NULL; 520 size_t buf_len = 0; 521 522 /* Of course BN_bn2bin() is in no way symmetric to BN_bin2bn()... */ 523 if ((buf_len = BN_num_bytes(bn)) == 0) 524 goto err; 525 if ((buf = calloc(1, buf_len)) == NULL) 526 goto err; 527 if (!BN_bn2bin(bn, buf)) 528 goto err; 529 if (!ec_point_from_octets(group, buf, buf_len, &point, NULL, ctx)) 530 goto err; 531 532 err: 533 freezero(buf, buf_len); 534 535 return point; 536 } 537 LCRYPTO_ALIAS(EC_POINT_bn2point); 538 539 char * 540 EC_POINT_point2hex(const EC_GROUP *group, const EC_POINT *point, 541 point_conversion_form_t form, BN_CTX *ctx) 542 { 543 BIGNUM *bn; 544 char *hex = NULL; 545 546 if ((bn = EC_POINT_point2bn(group, point, form, NULL, ctx)) == NULL) 547 goto err; 548 if ((hex = BN_bn2hex(bn)) == NULL) 549 goto err; 550 551 err: 552 BN_free(bn); 553 554 return hex; 555 } 556 LCRYPTO_ALIAS(EC_POINT_point2hex); 557 558 EC_POINT * 559 EC_POINT_hex2point(const EC_GROUP *group, const char *hex, 560 EC_POINT *in_point, BN_CTX *ctx) 561 { 562 EC_POINT *point = NULL; 563 BIGNUM *bn = NULL; 564 565 if (BN_hex2bn(&bn, hex) == 0) 566 goto err; 567 if ((point = EC_POINT_bn2point(group, bn, in_point, ctx)) == NULL) 568 goto err; 569 570 err: 571 BN_free(bn); 572 573 return point; 574 } 575 LCRYPTO_ALIAS(EC_POINT_hex2point); 576