1 /* $OpenBSD: bn_convert.c,v 1.22 2024/06/22 16:33:00 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 73 static int bn_dec2bn_cbs(BIGNUM **bnp, CBS *cbs); 74 static int bn_hex2bn_cbs(BIGNUM **bnp, CBS *cbs); 75 76 static const char hex_digits[] = "0123456789ABCDEF"; 77 78 typedef enum { 79 big, 80 little, 81 } endianness_t; 82 83 /* ignore negative */ 84 static int 85 bn2binpad(const BIGNUM *a, unsigned char *to, int tolen, endianness_t endianness) 86 { 87 int n; 88 size_t i, lasti, j, atop, mask; 89 BN_ULONG l; 90 91 /* 92 * In case |a| is fixed-top, BN_num_bytes can return bogus length, 93 * but it's assumed that fixed-top inputs ought to be "nominated" 94 * even for padded output, so it works out... 95 */ 96 n = BN_num_bytes(a); 97 if (tolen == -1) 98 tolen = n; 99 else if (tolen < n) { /* uncommon/unlike case */ 100 BIGNUM temp = *a; 101 102 bn_correct_top(&temp); 103 104 n = BN_num_bytes(&temp); 105 if (tolen < n) 106 return -1; 107 } 108 109 /* Swipe through whole available data and don't give away padded zero. */ 110 atop = a->dmax * BN_BYTES; 111 if (atop == 0) { 112 explicit_bzero(to, tolen); 113 return tolen; 114 } 115 116 lasti = atop - 1; 117 atop = a->top * BN_BYTES; 118 119 if (endianness == big) 120 to += tolen; /* start from the end of the buffer */ 121 122 for (i = 0, j = 0; j < (size_t)tolen; j++) { 123 unsigned char val; 124 125 l = a->d[i / BN_BYTES]; 126 mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1)); 127 val = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask); 128 129 if (endianness == big) 130 *--to = val; 131 else 132 *to++ = val; 133 134 i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */ 135 } 136 137 return tolen; 138 } 139 140 int 141 BN_bn2bin(const BIGNUM *a, unsigned char *to) 142 { 143 return bn2binpad(a, to, -1, big); 144 } 145 LCRYPTO_ALIAS(BN_bn2bin); 146 147 int 148 BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) 149 { 150 if (tolen < 0) 151 return -1; 152 return bn2binpad(a, to, tolen, big); 153 } 154 LCRYPTO_ALIAS(BN_bn2binpad); 155 156 static int 157 bn_bin2bn_cbs(BIGNUM **bnp, CBS *cbs, int lebin) 158 { 159 BIGNUM *bn = NULL; 160 BN_ULONG w; 161 uint8_t v; 162 int b, i; 163 164 if ((bn = *bnp) == NULL) 165 bn = BN_new(); 166 if (bn == NULL) 167 goto err; 168 if (!bn_expand_bytes(bn, CBS_len(cbs))) 169 goto err; 170 171 b = 0; 172 i = 0; 173 w = 0; 174 175 while (CBS_len(cbs) > 0) { 176 if (lebin) { 177 if (!CBS_get_u8(cbs, &v)) 178 goto err; 179 } else { 180 if (!CBS_get_last_u8(cbs, &v)) 181 goto err; 182 } 183 184 w |= (BN_ULONG)v << b; 185 b += 8; 186 187 if (b == BN_BITS2 || CBS_len(cbs) == 0) { 188 b = 0; 189 bn->d[i++] = w; 190 w = 0; 191 } 192 } 193 194 bn->neg = 0; 195 bn->top = i; 196 197 bn_correct_top(bn); 198 199 *bnp = bn; 200 201 return 1; 202 203 err: 204 if (*bnp == NULL) 205 BN_free(bn); 206 207 return 0; 208 } 209 210 BIGNUM * 211 BN_bin2bn(const unsigned char *d, int len, BIGNUM *bn) 212 { 213 CBS cbs; 214 215 if (len < 0) 216 return NULL; 217 218 CBS_init(&cbs, d, len); 219 220 if (!bn_bin2bn_cbs(&bn, &cbs, 0)) 221 return NULL; 222 223 return bn; 224 } 225 LCRYPTO_ALIAS(BN_bin2bn); 226 227 int 228 BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen) 229 { 230 if (tolen < 0) 231 return -1; 232 233 return bn2binpad(a, to, tolen, little); 234 } 235 LCRYPTO_ALIAS(BN_bn2lebinpad); 236 237 BIGNUM * 238 BN_lebin2bn(const unsigned char *d, int len, BIGNUM *bn) 239 { 240 CBS cbs; 241 242 if (len < 0) 243 return NULL; 244 245 CBS_init(&cbs, d, len); 246 247 if (!bn_bin2bn_cbs(&bn, &cbs, 1)) 248 return NULL; 249 250 return bn; 251 } 252 LCRYPTO_ALIAS(BN_lebin2bn); 253 254 int 255 BN_asc2bn(BIGNUM **bnp, const char *s) 256 { 257 CBS cbs, cbs_hex; 258 size_t s_len; 259 uint8_t v; 260 int neg; 261 262 if (bnp != NULL && *bnp != NULL) 263 BN_zero(*bnp); 264 265 if (s == NULL) 266 return 0; 267 if ((s_len = strlen(s)) == 0) 268 return 0; 269 270 CBS_init(&cbs, s, s_len); 271 272 /* Handle negative sign. */ 273 if (!CBS_peek_u8(&cbs, &v)) 274 return 0; 275 if ((neg = (v == '-'))) { 276 if (!CBS_skip(&cbs, 1)) 277 return 0; 278 } 279 280 /* Try parsing as hexadecimal with a 0x prefix. */ 281 CBS_dup(&cbs, &cbs_hex); 282 if (!CBS_get_u8(&cbs_hex, &v)) 283 goto decimal; 284 if (v != '0') 285 goto decimal; 286 if (!CBS_get_u8(&cbs_hex, &v)) 287 goto decimal; 288 if (v != 'X' && v != 'x') 289 goto decimal; 290 if (bn_hex2bn_cbs(bnp, &cbs_hex) == 0) 291 return 0; 292 293 goto done; 294 295 decimal: 296 if (bn_dec2bn_cbs(bnp, &cbs) == 0) 297 return 0; 298 299 done: 300 if (bnp != NULL && *bnp != NULL) 301 BN_set_negative(*bnp, neg); 302 303 return 1; 304 } 305 LCRYPTO_ALIAS(BN_asc2bn); 306 307 char * 308 BN_bn2dec(const BIGNUM *bn) 309 { 310 int started = 0; 311 BIGNUM *tmp = NULL; 312 uint8_t *data = NULL; 313 size_t data_len = 0; 314 uint8_t *s = NULL; 315 size_t s_len; 316 BN_ULONG v, w; 317 uint8_t c; 318 CBB cbb; 319 CBS cbs; 320 int i; 321 322 if (!CBB_init(&cbb, 0)) 323 goto err; 324 325 if ((tmp = BN_dup(bn)) == NULL) 326 goto err; 327 328 /* 329 * Divide the BIGNUM by a large multiple of 10, then break the remainder 330 * into decimal digits. This produces a reversed string of digits, 331 * potentially with leading zeroes. 332 */ 333 while (!BN_is_zero(tmp)) { 334 if ((w = BN_div_word(tmp, BN_DEC_CONV)) == -1) 335 goto err; 336 for (i = 0; i < BN_DEC_NUM; i++) { 337 v = w % 10; 338 if (!CBB_add_u8(&cbb, '0' + v)) 339 goto err; 340 w /= 10; 341 } 342 } 343 if (!CBB_finish(&cbb, &data, &data_len)) 344 goto err; 345 346 if (data_len > SIZE_MAX - 3) 347 goto err; 348 if (!CBB_init(&cbb, data_len + 3)) 349 goto err; 350 351 if (BN_is_negative(bn)) { 352 if (!CBB_add_u8(&cbb, '-')) 353 goto err; 354 } 355 356 /* Reverse digits and trim leading zeroes. */ 357 CBS_init(&cbs, data, data_len); 358 while (CBS_len(&cbs) > 0) { 359 if (!CBS_get_last_u8(&cbs, &c)) 360 goto err; 361 if (!started && c == '0') 362 continue; 363 if (!CBB_add_u8(&cbb, c)) 364 goto err; 365 started = 1; 366 } 367 368 if (!started) { 369 if (!CBB_add_u8(&cbb, '0')) 370 goto err; 371 } 372 if (!CBB_add_u8(&cbb, '\0')) 373 goto err; 374 if (!CBB_finish(&cbb, &s, &s_len)) 375 goto err; 376 377 err: 378 BN_free(tmp); 379 CBB_cleanup(&cbb); 380 freezero(data, data_len); 381 382 return s; 383 } 384 LCRYPTO_ALIAS(BN_bn2dec); 385 386 static int 387 bn_dec2bn_cbs(BIGNUM **bnp, CBS *cbs) 388 { 389 CBS cbs_digits; 390 BIGNUM *bn = NULL; 391 int d, neg, num; 392 size_t digits = 0; 393 BN_ULONG w; 394 uint8_t v; 395 396 /* Handle negative sign. */ 397 if (!CBS_peek_u8(cbs, &v)) 398 goto err; 399 if ((neg = (v == '-'))) { 400 if (!CBS_skip(cbs, 1)) 401 goto err; 402 } 403 404 /* Scan to find last decimal digit. */ 405 CBS_dup(cbs, &cbs_digits); 406 while (CBS_len(&cbs_digits) > 0) { 407 if (!CBS_get_u8(&cbs_digits, &v)) 408 goto err; 409 if (!isdigit(v)) 410 break; 411 digits++; 412 } 413 if (digits > INT_MAX / 4) 414 goto err; 415 416 num = digits + neg; 417 418 if (bnp == NULL) 419 return num; 420 421 if ((bn = *bnp) == NULL) 422 bn = BN_new(); 423 if (bn == NULL) 424 goto err; 425 if (!bn_expand_bits(bn, digits * 4)) 426 goto err; 427 428 if ((d = digits % BN_DEC_NUM) == 0) 429 d = BN_DEC_NUM; 430 431 w = 0; 432 433 /* Work forwards from most significant digit. */ 434 while (digits-- > 0) { 435 if (!CBS_get_u8(cbs, &v)) 436 goto err; 437 438 if (v < '0' || v > '9') 439 goto err; 440 441 v -= '0'; 442 w = w * 10 + v; 443 d--; 444 445 if (d == 0) { 446 if (!BN_mul_word(bn, BN_DEC_CONV)) 447 goto err; 448 if (!BN_add_word(bn, w)) 449 goto err; 450 451 d = BN_DEC_NUM; 452 w = 0; 453 } 454 } 455 456 bn_correct_top(bn); 457 458 BN_set_negative(bn, neg); 459 460 *bnp = bn; 461 462 return num; 463 464 err: 465 if (bnp != NULL && *bnp == NULL) 466 BN_free(bn); 467 468 return 0; 469 } 470 471 int 472 BN_dec2bn(BIGNUM **bnp, const char *s) 473 { 474 size_t s_len; 475 CBS cbs; 476 477 if (bnp != NULL && *bnp != NULL) 478 BN_zero(*bnp); 479 480 if (s == NULL) 481 return 0; 482 if ((s_len = strlen(s)) == 0) 483 return 0; 484 485 CBS_init(&cbs, s, s_len); 486 487 return bn_dec2bn_cbs(bnp, &cbs); 488 } 489 LCRYPTO_ALIAS(BN_dec2bn); 490 491 static int 492 bn_bn2hex_internal(const BIGNUM *bn, int include_sign, int nibbles_only, 493 char **out, size_t *out_len) 494 { 495 int started = 0; 496 uint8_t *s = NULL; 497 size_t s_len = 0; 498 BN_ULONG v, w; 499 int i, j; 500 CBB cbb; 501 CBS cbs; 502 uint8_t nul; 503 int ret = 0; 504 505 *out = NULL; 506 *out_len = 0; 507 508 if (!CBB_init(&cbb, 0)) 509 goto err; 510 511 if (BN_is_negative(bn) && include_sign) { 512 if (!CBB_add_u8(&cbb, '-')) 513 goto err; 514 } 515 if (BN_is_zero(bn)) { 516 if (!CBB_add_u8(&cbb, '0')) 517 goto err; 518 } 519 for (i = bn->top - 1; i >= 0; i--) { 520 w = bn->d[i]; 521 for (j = BN_BITS2 - 8; j >= 0; j -= 8) { 522 v = (w >> j) & 0xff; 523 if (!started && v == 0) 524 continue; 525 if (started || !nibbles_only || (v >> 4) != 0) { 526 if (!CBB_add_u8(&cbb, hex_digits[v >> 4])) 527 goto err; 528 } 529 if (!CBB_add_u8(&cbb, hex_digits[v & 0xf])) 530 goto err; 531 started = 1; 532 } 533 } 534 if (!CBB_add_u8(&cbb, '\0')) 535 goto err; 536 if (!CBB_finish(&cbb, &s, &s_len)) 537 goto err; 538 539 /* The length of a C string does not include the terminating NUL. */ 540 CBS_init(&cbs, s, s_len); 541 if (!CBS_get_last_u8(&cbs, &nul)) 542 goto err; 543 544 *out = (char *)CBS_data(&cbs); 545 *out_len = CBS_len(&cbs); 546 s = NULL; 547 s_len = 0; 548 549 ret = 1; 550 551 err: 552 CBB_cleanup(&cbb); 553 freezero(s, s_len); 554 555 return ret; 556 } 557 558 int 559 bn_bn2hex_nosign(const BIGNUM *bn, char **out, size_t *out_len) 560 { 561 return bn_bn2hex_internal(bn, 0, 0, out, out_len); 562 } 563 564 int 565 bn_bn2hex_nibbles(const BIGNUM *bn, char **out, size_t *out_len) 566 { 567 return bn_bn2hex_internal(bn, 1, 1, out, out_len); 568 } 569 570 char * 571 BN_bn2hex(const BIGNUM *bn) 572 { 573 char *s; 574 size_t s_len; 575 576 if (!bn_bn2hex_internal(bn, 1, 0, &s, &s_len)) 577 return NULL; 578 579 return s; 580 } 581 LCRYPTO_ALIAS(BN_bn2hex); 582 583 static int 584 bn_hex2bn_cbs(BIGNUM **bnp, CBS *cbs) 585 { 586 CBS cbs_digits; 587 BIGNUM *bn = NULL; 588 int b, i, neg, num; 589 size_t digits = 0; 590 BN_ULONG w; 591 uint8_t v; 592 593 /* Handle negative sign. */ 594 if (!CBS_peek_u8(cbs, &v)) 595 goto err; 596 if ((neg = (v == '-'))) { 597 if (!CBS_skip(cbs, 1)) 598 goto err; 599 } 600 601 /* Scan to find last hexadecimal digit. */ 602 CBS_dup(cbs, &cbs_digits); 603 while (CBS_len(&cbs_digits) > 0) { 604 if (!CBS_get_u8(&cbs_digits, &v)) 605 goto err; 606 if (!isxdigit(v)) 607 break; 608 digits++; 609 } 610 if (digits > INT_MAX / 4) 611 goto err; 612 613 num = digits + neg; 614 615 if (bnp == NULL) 616 return num; 617 618 if ((bn = *bnp) == NULL) 619 bn = BN_new(); 620 if (bn == NULL) 621 goto err; 622 if (!bn_expand_bits(bn, digits * 4)) 623 goto err; 624 625 if (!CBS_get_bytes(cbs, cbs, digits)) 626 goto err; 627 628 b = 0; 629 i = 0; 630 w = 0; 631 632 /* Work backwards from least significant digit. */ 633 while (digits-- > 0) { 634 if (!CBS_get_last_u8(cbs, &v)) 635 goto err; 636 637 if (v >= '0' && v <= '9') 638 v -= '0'; 639 else if (v >= 'a' && v <= 'f') 640 v -= 'a' - 10; 641 else if (v >= 'A' && v <= 'F') 642 v -= 'A' - 10; 643 else 644 goto err; 645 646 w |= (BN_ULONG)v << b; 647 b += 4; 648 649 if (b == BN_BITS2 || digits == 0) { 650 b = 0; 651 bn->d[i++] = w; 652 w = 0; 653 } 654 } 655 656 bn->top = i; 657 bn_correct_top(bn); 658 659 BN_set_negative(bn, neg); 660 661 *bnp = bn; 662 663 return num; 664 665 err: 666 if (bnp != NULL && *bnp == NULL) 667 BN_free(bn); 668 669 return 0; 670 } 671 672 int 673 BN_hex2bn(BIGNUM **bnp, const char *s) 674 { 675 size_t s_len; 676 CBS cbs; 677 678 if (bnp != NULL && *bnp != NULL) 679 BN_zero(*bnp); 680 681 if (s == NULL) 682 return 0; 683 if ((s_len = strlen(s)) == 0) 684 return 0; 685 686 CBS_init(&cbs, s, s_len); 687 688 return bn_hex2bn_cbs(bnp, &cbs); 689 } 690 LCRYPTO_ALIAS(BN_hex2bn); 691 692 int 693 BN_bn2mpi(const BIGNUM *bn, unsigned char *d) 694 { 695 uint8_t *out_bin; 696 size_t out_len, out_bin_len; 697 int bits, bytes; 698 int extend; 699 CBB cbb, cbb_bin; 700 701 bits = BN_num_bits(bn); 702 bytes = (bits + 7) / 8; 703 extend = (bits != 0) && (bits % 8 == 0); 704 out_bin_len = extend + bytes; 705 out_len = 4 + out_bin_len; 706 707 if (d == NULL) 708 return out_len; 709 710 if (!CBB_init_fixed(&cbb, d, out_len)) 711 goto err; 712 if (!CBB_add_u32_length_prefixed(&cbb, &cbb_bin)) 713 goto err; 714 if (!CBB_add_space(&cbb_bin, &out_bin, out_bin_len)) 715 goto err; 716 if (BN_bn2binpad(bn, out_bin, out_bin_len) != out_bin_len) 717 goto err; 718 if (!CBB_finish(&cbb, NULL, NULL)) 719 goto err; 720 721 if (bn->neg) 722 d[4] |= 0x80; 723 724 return out_len; 725 726 err: 727 CBB_cleanup(&cbb); 728 729 return -1; 730 } 731 LCRYPTO_ALIAS(BN_bn2mpi); 732 733 BIGNUM * 734 BN_mpi2bn(const unsigned char *d, int n, BIGNUM *bn_in) 735 { 736 BIGNUM *bn = bn_in; 737 uint32_t mpi_len; 738 uint8_t v; 739 int neg = 0; 740 CBS cbs; 741 742 if (n < 0) 743 return NULL; 744 745 CBS_init(&cbs, d, n); 746 747 if (!CBS_get_u32(&cbs, &mpi_len)) { 748 BNerror(BN_R_INVALID_LENGTH); 749 return NULL; 750 } 751 if (CBS_len(&cbs) != mpi_len) { 752 BNerror(BN_R_ENCODING_ERROR); 753 return NULL; 754 } 755 if (CBS_len(&cbs) > 0) { 756 if (!CBS_peek_u8(&cbs, &v)) 757 return NULL; 758 neg = (v >> 7) & 1; 759 } 760 761 if (!bn_bin2bn_cbs(&bn, &cbs, 0)) 762 return NULL; 763 764 if (neg) 765 BN_clear_bit(bn, BN_num_bits(bn) - 1); 766 767 BN_set_negative(bn, neg); 768 769 return bn; 770 } 771 LCRYPTO_ALIAS(BN_mpi2bn); 772