1 /* $OpenBSD: bn_convert.c,v 1.23 2024/11/08 14:18:44 jsing Exp $ */ 2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3 * All rights reserved. 4 * 5 * This package is an SSL implementation written 6 * by Eric Young (eay@cryptsoft.com). 7 * The implementation was written so as to conform with Netscapes SSL. 8 * 9 * This library is free for commercial and non-commercial use as long as 10 * the following conditions are aheared to. The following conditions 11 * apply to all code found in this distribution, be it the RC4, RSA, 12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13 * included with this distribution is covered by the same copyright terms 14 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15 * 16 * Copyright remains Eric Young's, and as such any Copyright notices in 17 * the code are not to be removed. 18 * If this package is used in a product, Eric Young should be given attribution 19 * as the author of the parts of the library used. 20 * This can be in the form of a textual message at program startup or 21 * in documentation (online or textual) provided with the package. 22 * 23 * Redistribution and use in source and binary forms, with or without 24 * modification, are permitted provided that the following conditions 25 * are met: 26 * 1. Redistributions of source code must retain the copyright 27 * notice, this list of conditions and the following disclaimer. 28 * 2. Redistributions in binary form must reproduce the above copyright 29 * notice, this list of conditions and the following disclaimer in the 30 * documentation and/or other materials provided with the distribution. 31 * 3. All advertising materials mentioning features or use of this software 32 * must display the following acknowledgement: 33 * "This product includes cryptographic software written by 34 * Eric Young (eay@cryptsoft.com)" 35 * The word 'cryptographic' can be left out if the rouines from the library 36 * being used are not cryptographic related :-). 37 * 4. If you include any Windows specific code (or a derivative thereof) from 38 * the apps directory (application code) you must include an acknowledgement: 39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40 * 41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51 * SUCH DAMAGE. 52 * 53 * The licence and distribution terms for any publically available version or 54 * derivative of this code cannot be changed. i.e. this code cannot simply be 55 * copied and put under another distribution licence 56 * [including the GNU Public Licence.] 57 */ 58 59 #include <ctype.h> 60 #include <limits.h> 61 #include <stdio.h> 62 #include <string.h> 63 64 #include <openssl/opensslconf.h> 65 66 #include <openssl/bio.h> 67 #include <openssl/buffer.h> 68 #include <openssl/err.h> 69 70 #include "bn_local.h" 71 #include "bytestring.h" 72 #include "crypto_internal.h" 73 74 static int bn_dec2bn_cbs(BIGNUM **bnp, CBS *cbs); 75 static int bn_hex2bn_cbs(BIGNUM **bnp, CBS *cbs); 76 77 static const char hex_digits[] = "0123456789ABCDEF"; 78 79 static int 80 bn_bn2binpad_internal(const BIGNUM *bn, uint8_t *out, int out_len, 81 int little_endian) 82 { 83 uint8_t mask, v; 84 BN_ULONG w; 85 int i, j; 86 int b, n; 87 88 n = BN_num_bytes(bn); 89 90 if (out_len == -1) 91 out_len = n; 92 if (out_len < n) 93 return -1; 94 95 if (bn->dmax == 0) { 96 explicit_bzero(out, out_len); 97 return out_len; 98 } 99 100 mask = 0; 101 b = BN_BITS2; 102 j = 0; 103 104 for (i = out_len - 1; i >= 0; i--) { 105 if (b == BN_BITS2) { 106 mask = crypto_ct_lt_mask(j, bn->top); 107 w = bn->d[j++ % bn->dmax]; 108 b = 0; 109 } 110 out[i] = (w >> b) & mask; 111 b += 8; 112 } 113 114 if (little_endian) { 115 for (i = 0, j = out_len - 1; i < out_len / 2; i++, j--) { 116 v = out[i]; 117 out[i] = out[j]; 118 out[j] = v; 119 } 120 } 121 122 return out_len; 123 } 124 125 int 126 BN_bn2bin(const BIGNUM *bn, unsigned char *to) 127 { 128 return bn_bn2binpad_internal(bn, to, -1, 0); 129 } 130 LCRYPTO_ALIAS(BN_bn2bin); 131 132 int 133 BN_bn2binpad(const BIGNUM *bn, unsigned char *to, int to_len) 134 { 135 if (to_len < 0) 136 return -1; 137 138 return bn_bn2binpad_internal(bn, to, to_len, 0); 139 } 140 LCRYPTO_ALIAS(BN_bn2binpad); 141 142 static int 143 bn_bin2bn_cbs(BIGNUM **bnp, CBS *cbs, int lebin) 144 { 145 BIGNUM *bn = NULL; 146 BN_ULONG w; 147 uint8_t v; 148 int b, i; 149 150 if ((bn = *bnp) == NULL) 151 bn = BN_new(); 152 if (bn == NULL) 153 goto err; 154 if (!bn_expand_bytes(bn, CBS_len(cbs))) 155 goto err; 156 157 b = 0; 158 i = 0; 159 w = 0; 160 161 while (CBS_len(cbs) > 0) { 162 if (lebin) { 163 if (!CBS_get_u8(cbs, &v)) 164 goto err; 165 } else { 166 if (!CBS_get_last_u8(cbs, &v)) 167 goto err; 168 } 169 170 w |= (BN_ULONG)v << b; 171 b += 8; 172 173 if (b == BN_BITS2 || CBS_len(cbs) == 0) { 174 b = 0; 175 bn->d[i++] = w; 176 w = 0; 177 } 178 } 179 180 bn->neg = 0; 181 bn->top = i; 182 183 bn_correct_top(bn); 184 185 *bnp = bn; 186 187 return 1; 188 189 err: 190 if (*bnp == NULL) 191 BN_free(bn); 192 193 return 0; 194 } 195 196 BIGNUM * 197 BN_bin2bn(const unsigned char *d, int len, BIGNUM *bn) 198 { 199 CBS cbs; 200 201 if (len < 0) 202 return NULL; 203 204 CBS_init(&cbs, d, len); 205 206 if (!bn_bin2bn_cbs(&bn, &cbs, 0)) 207 return NULL; 208 209 return bn; 210 } 211 LCRYPTO_ALIAS(BN_bin2bn); 212 213 int 214 BN_bn2lebinpad(const BIGNUM *bn, unsigned char *to, int to_len) 215 { 216 if (to_len < 0) 217 return -1; 218 219 return bn_bn2binpad_internal(bn, to, to_len, 1); 220 } 221 LCRYPTO_ALIAS(BN_bn2lebinpad); 222 223 BIGNUM * 224 BN_lebin2bn(const unsigned char *d, int len, BIGNUM *bn) 225 { 226 CBS cbs; 227 228 if (len < 0) 229 return NULL; 230 231 CBS_init(&cbs, d, len); 232 233 if (!bn_bin2bn_cbs(&bn, &cbs, 1)) 234 return NULL; 235 236 return bn; 237 } 238 LCRYPTO_ALIAS(BN_lebin2bn); 239 240 int 241 BN_asc2bn(BIGNUM **bnp, const char *s) 242 { 243 CBS cbs, cbs_hex; 244 size_t s_len; 245 uint8_t v; 246 int neg; 247 248 if (bnp != NULL && *bnp != NULL) 249 BN_zero(*bnp); 250 251 if (s == NULL) 252 return 0; 253 if ((s_len = strlen(s)) == 0) 254 return 0; 255 256 CBS_init(&cbs, s, s_len); 257 258 /* Handle negative sign. */ 259 if (!CBS_peek_u8(&cbs, &v)) 260 return 0; 261 if ((neg = (v == '-'))) { 262 if (!CBS_skip(&cbs, 1)) 263 return 0; 264 } 265 266 /* Try parsing as hexadecimal with a 0x prefix. */ 267 CBS_dup(&cbs, &cbs_hex); 268 if (!CBS_get_u8(&cbs_hex, &v)) 269 goto decimal; 270 if (v != '0') 271 goto decimal; 272 if (!CBS_get_u8(&cbs_hex, &v)) 273 goto decimal; 274 if (v != 'X' && v != 'x') 275 goto decimal; 276 if (bn_hex2bn_cbs(bnp, &cbs_hex) == 0) 277 return 0; 278 279 goto done; 280 281 decimal: 282 if (bn_dec2bn_cbs(bnp, &cbs) == 0) 283 return 0; 284 285 done: 286 if (bnp != NULL && *bnp != NULL) 287 BN_set_negative(*bnp, neg); 288 289 return 1; 290 } 291 LCRYPTO_ALIAS(BN_asc2bn); 292 293 char * 294 BN_bn2dec(const BIGNUM *bn) 295 { 296 int started = 0; 297 BIGNUM *tmp = NULL; 298 uint8_t *data = NULL; 299 size_t data_len = 0; 300 uint8_t *s = NULL; 301 size_t s_len; 302 BN_ULONG v, w; 303 uint8_t c; 304 CBB cbb; 305 CBS cbs; 306 int i; 307 308 if (!CBB_init(&cbb, 0)) 309 goto err; 310 311 if ((tmp = BN_dup(bn)) == NULL) 312 goto err; 313 314 /* 315 * Divide the BIGNUM by a large multiple of 10, then break the remainder 316 * into decimal digits. This produces a reversed string of digits, 317 * potentially with leading zeroes. 318 */ 319 while (!BN_is_zero(tmp)) { 320 if ((w = BN_div_word(tmp, BN_DEC_CONV)) == -1) 321 goto err; 322 for (i = 0; i < BN_DEC_NUM; i++) { 323 v = w % 10; 324 if (!CBB_add_u8(&cbb, '0' + v)) 325 goto err; 326 w /= 10; 327 } 328 } 329 if (!CBB_finish(&cbb, &data, &data_len)) 330 goto err; 331 332 if (data_len > SIZE_MAX - 3) 333 goto err; 334 if (!CBB_init(&cbb, data_len + 3)) 335 goto err; 336 337 if (BN_is_negative(bn)) { 338 if (!CBB_add_u8(&cbb, '-')) 339 goto err; 340 } 341 342 /* Reverse digits and trim leading zeroes. */ 343 CBS_init(&cbs, data, data_len); 344 while (CBS_len(&cbs) > 0) { 345 if (!CBS_get_last_u8(&cbs, &c)) 346 goto err; 347 if (!started && c == '0') 348 continue; 349 if (!CBB_add_u8(&cbb, c)) 350 goto err; 351 started = 1; 352 } 353 354 if (!started) { 355 if (!CBB_add_u8(&cbb, '0')) 356 goto err; 357 } 358 if (!CBB_add_u8(&cbb, '\0')) 359 goto err; 360 if (!CBB_finish(&cbb, &s, &s_len)) 361 goto err; 362 363 err: 364 BN_free(tmp); 365 CBB_cleanup(&cbb); 366 freezero(data, data_len); 367 368 return s; 369 } 370 LCRYPTO_ALIAS(BN_bn2dec); 371 372 static int 373 bn_dec2bn_cbs(BIGNUM **bnp, CBS *cbs) 374 { 375 CBS cbs_digits; 376 BIGNUM *bn = NULL; 377 int d, neg, num; 378 size_t digits = 0; 379 BN_ULONG w; 380 uint8_t v; 381 382 /* Handle negative sign. */ 383 if (!CBS_peek_u8(cbs, &v)) 384 goto err; 385 if ((neg = (v == '-'))) { 386 if (!CBS_skip(cbs, 1)) 387 goto err; 388 } 389 390 /* Scan to find last decimal digit. */ 391 CBS_dup(cbs, &cbs_digits); 392 while (CBS_len(&cbs_digits) > 0) { 393 if (!CBS_get_u8(&cbs_digits, &v)) 394 goto err; 395 if (!isdigit(v)) 396 break; 397 digits++; 398 } 399 if (digits > INT_MAX / 4) 400 goto err; 401 402 num = digits + neg; 403 404 if (bnp == NULL) 405 return num; 406 407 if ((bn = *bnp) == NULL) 408 bn = BN_new(); 409 if (bn == NULL) 410 goto err; 411 if (!bn_expand_bits(bn, digits * 4)) 412 goto err; 413 414 if ((d = digits % BN_DEC_NUM) == 0) 415 d = BN_DEC_NUM; 416 417 w = 0; 418 419 /* Work forwards from most significant digit. */ 420 while (digits-- > 0) { 421 if (!CBS_get_u8(cbs, &v)) 422 goto err; 423 424 if (v < '0' || v > '9') 425 goto err; 426 427 v -= '0'; 428 w = w * 10 + v; 429 d--; 430 431 if (d == 0) { 432 if (!BN_mul_word(bn, BN_DEC_CONV)) 433 goto err; 434 if (!BN_add_word(bn, w)) 435 goto err; 436 437 d = BN_DEC_NUM; 438 w = 0; 439 } 440 } 441 442 bn_correct_top(bn); 443 444 BN_set_negative(bn, neg); 445 446 *bnp = bn; 447 448 return num; 449 450 err: 451 if (bnp != NULL && *bnp == NULL) 452 BN_free(bn); 453 454 return 0; 455 } 456 457 int 458 BN_dec2bn(BIGNUM **bnp, const char *s) 459 { 460 size_t s_len; 461 CBS cbs; 462 463 if (bnp != NULL && *bnp != NULL) 464 BN_zero(*bnp); 465 466 if (s == NULL) 467 return 0; 468 if ((s_len = strlen(s)) == 0) 469 return 0; 470 471 CBS_init(&cbs, s, s_len); 472 473 return bn_dec2bn_cbs(bnp, &cbs); 474 } 475 LCRYPTO_ALIAS(BN_dec2bn); 476 477 static int 478 bn_bn2hex_internal(const BIGNUM *bn, int include_sign, int nibbles_only, 479 char **out, size_t *out_len) 480 { 481 int started = 0; 482 uint8_t *s = NULL; 483 size_t s_len = 0; 484 BN_ULONG v, w; 485 int i, j; 486 CBB cbb; 487 CBS cbs; 488 uint8_t nul; 489 int ret = 0; 490 491 *out = NULL; 492 *out_len = 0; 493 494 if (!CBB_init(&cbb, 0)) 495 goto err; 496 497 if (BN_is_negative(bn) && include_sign) { 498 if (!CBB_add_u8(&cbb, '-')) 499 goto err; 500 } 501 if (BN_is_zero(bn)) { 502 if (!CBB_add_u8(&cbb, '0')) 503 goto err; 504 } 505 for (i = bn->top - 1; i >= 0; i--) { 506 w = bn->d[i]; 507 for (j = BN_BITS2 - 8; j >= 0; j -= 8) { 508 v = (w >> j) & 0xff; 509 if (!started && v == 0) 510 continue; 511 if (started || !nibbles_only || (v >> 4) != 0) { 512 if (!CBB_add_u8(&cbb, hex_digits[v >> 4])) 513 goto err; 514 } 515 if (!CBB_add_u8(&cbb, hex_digits[v & 0xf])) 516 goto err; 517 started = 1; 518 } 519 } 520 if (!CBB_add_u8(&cbb, '\0')) 521 goto err; 522 if (!CBB_finish(&cbb, &s, &s_len)) 523 goto err; 524 525 /* The length of a C string does not include the terminating NUL. */ 526 CBS_init(&cbs, s, s_len); 527 if (!CBS_get_last_u8(&cbs, &nul)) 528 goto err; 529 530 *out = (char *)CBS_data(&cbs); 531 *out_len = CBS_len(&cbs); 532 s = NULL; 533 s_len = 0; 534 535 ret = 1; 536 537 err: 538 CBB_cleanup(&cbb); 539 freezero(s, s_len); 540 541 return ret; 542 } 543 544 int 545 bn_bn2hex_nosign(const BIGNUM *bn, char **out, size_t *out_len) 546 { 547 return bn_bn2hex_internal(bn, 0, 0, out, out_len); 548 } 549 550 int 551 bn_bn2hex_nibbles(const BIGNUM *bn, char **out, size_t *out_len) 552 { 553 return bn_bn2hex_internal(bn, 1, 1, out, out_len); 554 } 555 556 char * 557 BN_bn2hex(const BIGNUM *bn) 558 { 559 char *s; 560 size_t s_len; 561 562 if (!bn_bn2hex_internal(bn, 1, 0, &s, &s_len)) 563 return NULL; 564 565 return s; 566 } 567 LCRYPTO_ALIAS(BN_bn2hex); 568 569 static int 570 bn_hex2bn_cbs(BIGNUM **bnp, CBS *cbs) 571 { 572 CBS cbs_digits; 573 BIGNUM *bn = NULL; 574 int b, i, neg, num; 575 size_t digits = 0; 576 BN_ULONG w; 577 uint8_t v; 578 579 /* Handle negative sign. */ 580 if (!CBS_peek_u8(cbs, &v)) 581 goto err; 582 if ((neg = (v == '-'))) { 583 if (!CBS_skip(cbs, 1)) 584 goto err; 585 } 586 587 /* Scan to find last hexadecimal digit. */ 588 CBS_dup(cbs, &cbs_digits); 589 while (CBS_len(&cbs_digits) > 0) { 590 if (!CBS_get_u8(&cbs_digits, &v)) 591 goto err; 592 if (!isxdigit(v)) 593 break; 594 digits++; 595 } 596 if (digits > INT_MAX / 4) 597 goto err; 598 599 num = digits + neg; 600 601 if (bnp == NULL) 602 return num; 603 604 if ((bn = *bnp) == NULL) 605 bn = BN_new(); 606 if (bn == NULL) 607 goto err; 608 if (!bn_expand_bits(bn, digits * 4)) 609 goto err; 610 611 if (!CBS_get_bytes(cbs, cbs, digits)) 612 goto err; 613 614 b = 0; 615 i = 0; 616 w = 0; 617 618 /* Work backwards from least significant digit. */ 619 while (digits-- > 0) { 620 if (!CBS_get_last_u8(cbs, &v)) 621 goto err; 622 623 if (v >= '0' && v <= '9') 624 v -= '0'; 625 else if (v >= 'a' && v <= 'f') 626 v -= 'a' - 10; 627 else if (v >= 'A' && v <= 'F') 628 v -= 'A' - 10; 629 else 630 goto err; 631 632 w |= (BN_ULONG)v << b; 633 b += 4; 634 635 if (b == BN_BITS2 || digits == 0) { 636 b = 0; 637 bn->d[i++] = w; 638 w = 0; 639 } 640 } 641 642 bn->top = i; 643 bn_correct_top(bn); 644 645 BN_set_negative(bn, neg); 646 647 *bnp = bn; 648 649 return num; 650 651 err: 652 if (bnp != NULL && *bnp == NULL) 653 BN_free(bn); 654 655 return 0; 656 } 657 658 int 659 BN_hex2bn(BIGNUM **bnp, const char *s) 660 { 661 size_t s_len; 662 CBS cbs; 663 664 if (bnp != NULL && *bnp != NULL) 665 BN_zero(*bnp); 666 667 if (s == NULL) 668 return 0; 669 if ((s_len = strlen(s)) == 0) 670 return 0; 671 672 CBS_init(&cbs, s, s_len); 673 674 return bn_hex2bn_cbs(bnp, &cbs); 675 } 676 LCRYPTO_ALIAS(BN_hex2bn); 677 678 int 679 BN_bn2mpi(const BIGNUM *bn, unsigned char *d) 680 { 681 uint8_t *out_bin; 682 size_t out_len, out_bin_len; 683 int bits, bytes; 684 int extend; 685 CBB cbb, cbb_bin; 686 687 bits = BN_num_bits(bn); 688 bytes = (bits + 7) / 8; 689 extend = (bits != 0) && (bits % 8 == 0); 690 out_bin_len = extend + bytes; 691 out_len = 4 + out_bin_len; 692 693 if (d == NULL) 694 return out_len; 695 696 if (!CBB_init_fixed(&cbb, d, out_len)) 697 goto err; 698 if (!CBB_add_u32_length_prefixed(&cbb, &cbb_bin)) 699 goto err; 700 if (!CBB_add_space(&cbb_bin, &out_bin, out_bin_len)) 701 goto err; 702 if (BN_bn2binpad(bn, out_bin, out_bin_len) != out_bin_len) 703 goto err; 704 if (!CBB_finish(&cbb, NULL, NULL)) 705 goto err; 706 707 if (bn->neg) 708 d[4] |= 0x80; 709 710 return out_len; 711 712 err: 713 CBB_cleanup(&cbb); 714 715 return -1; 716 } 717 LCRYPTO_ALIAS(BN_bn2mpi); 718 719 BIGNUM * 720 BN_mpi2bn(const unsigned char *d, int n, BIGNUM *bn_in) 721 { 722 BIGNUM *bn = bn_in; 723 uint32_t mpi_len; 724 uint8_t v; 725 int neg = 0; 726 CBS cbs; 727 728 if (n < 0) 729 return NULL; 730 731 CBS_init(&cbs, d, n); 732 733 if (!CBS_get_u32(&cbs, &mpi_len)) { 734 BNerror(BN_R_INVALID_LENGTH); 735 return NULL; 736 } 737 if (CBS_len(&cbs) != mpi_len) { 738 BNerror(BN_R_ENCODING_ERROR); 739 return NULL; 740 } 741 if (CBS_len(&cbs) > 0) { 742 if (!CBS_peek_u8(&cbs, &v)) 743 return NULL; 744 neg = (v >> 7) & 1; 745 } 746 747 if (!bn_bin2bn_cbs(&bn, &cbs, 0)) 748 return NULL; 749 750 if (neg) 751 BN_clear_bit(bn, BN_num_bits(bn) - 1); 752 753 BN_set_negative(bn, neg); 754 755 return bn; 756 } 757 LCRYPTO_ALIAS(BN_mpi2bn); 758