1 /* $OpenBSD: bn_convert.c,v 1.18 2024/04/16 13:14:46 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) 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 (!CBS_get_last_u8(cbs, &v)) 177 goto err; 178 179 w |= (BN_ULONG)v << b; 180 b += 8; 181 182 if (b == BN_BITS2 || CBS_len(cbs) == 0) { 183 b = 0; 184 bn->d[i++] = w; 185 w = 0; 186 } 187 } 188 189 bn->neg = 0; 190 bn->top = i; 191 192 bn_correct_top(bn); 193 194 *bnp = bn; 195 196 return 1; 197 198 err: 199 if (*bnp == NULL) 200 BN_free(bn); 201 202 return 0; 203 } 204 205 BIGNUM * 206 BN_bin2bn(const unsigned char *d, int len, BIGNUM *bn) 207 { 208 CBS cbs; 209 210 if (len < 0) 211 return NULL; 212 213 CBS_init(&cbs, d, len); 214 215 if (!bn_bin2bn_cbs(&bn, &cbs)) 216 return NULL; 217 218 return bn; 219 } 220 LCRYPTO_ALIAS(BN_bin2bn); 221 222 int 223 BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen) 224 { 225 if (tolen < 0) 226 return -1; 227 228 return bn2binpad(a, to, tolen, little); 229 } 230 LCRYPTO_ALIAS(BN_bn2lebinpad); 231 232 BIGNUM * 233 BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret) 234 { 235 unsigned int i, m, n; 236 BN_ULONG l; 237 BIGNUM *bn = NULL; 238 239 if (ret == NULL) 240 ret = bn = BN_new(); 241 if (ret == NULL) 242 return NULL; 243 244 245 s += len; 246 /* Skip trailing zeroes. */ 247 for (; len > 0 && s[-1] == 0; s--, len--) 248 continue; 249 250 n = len; 251 if (n == 0) { 252 ret->top = 0; 253 return ret; 254 } 255 256 i = ((n - 1) / BN_BYTES) + 1; 257 m = (n - 1) % BN_BYTES; 258 if (!bn_wexpand(ret, (int)i)) { 259 BN_free(bn); 260 return NULL; 261 } 262 263 ret->top = i; 264 ret->neg = 0; 265 l = 0; 266 while (n-- > 0) { 267 s--; 268 l = (l << 8L) | *s; 269 if (m-- == 0) { 270 ret->d[--i] = l; 271 l = 0; 272 m = BN_BYTES - 1; 273 } 274 } 275 276 /* 277 * need to call this due to clear byte at top if avoiding having the 278 * top bit set (-ve number) 279 */ 280 bn_correct_top(ret); 281 282 return ret; 283 } 284 LCRYPTO_ALIAS(BN_lebin2bn); 285 286 int 287 BN_asc2bn(BIGNUM **bnp, const char *s) 288 { 289 CBS cbs, cbs_hex; 290 size_t s_len; 291 uint8_t v; 292 int neg; 293 294 if (bnp != NULL && *bnp != NULL) 295 BN_zero(*bnp); 296 297 if (s == NULL) 298 return 0; 299 if ((s_len = strlen(s)) == 0) 300 return 0; 301 302 CBS_init(&cbs, s, s_len); 303 304 /* Handle negative sign. */ 305 if (!CBS_peek_u8(&cbs, &v)) 306 return 0; 307 if ((neg = (v == '-'))) { 308 if (!CBS_skip(&cbs, 1)) 309 return 0; 310 } 311 312 /* Try parsing as hexadecimal with a 0x prefix. */ 313 CBS_dup(&cbs, &cbs_hex); 314 if (!CBS_get_u8(&cbs_hex, &v)) 315 goto decimal; 316 if (v != '0') 317 goto decimal; 318 if (!CBS_get_u8(&cbs_hex, &v)) 319 goto decimal; 320 if (v != 'X' && v != 'x') 321 goto decimal; 322 if (bn_hex2bn_cbs(bnp, &cbs_hex) == 0) 323 return 0; 324 325 goto done; 326 327 decimal: 328 if (bn_dec2bn_cbs(bnp, &cbs) == 0) 329 return 0; 330 331 done: 332 if (bnp != NULL && *bnp != NULL) 333 BN_set_negative(*bnp, neg); 334 335 return 1; 336 } 337 LCRYPTO_ALIAS(BN_asc2bn); 338 339 char * 340 BN_bn2dec(const BIGNUM *bn) 341 { 342 int started = 0; 343 BIGNUM *tmp = NULL; 344 uint8_t *data = NULL; 345 size_t data_len = 0; 346 uint8_t *s = NULL; 347 size_t s_len; 348 BN_ULONG v, w; 349 uint8_t c; 350 CBB cbb; 351 CBS cbs; 352 int i; 353 354 if (!CBB_init(&cbb, 0)) 355 goto err; 356 357 if ((tmp = BN_dup(bn)) == NULL) 358 goto err; 359 360 /* 361 * Divide the BIGNUM by a large multiple of 10, then break the remainder 362 * into decimal digits. This produces a reversed string of digits, 363 * potentially with leading zeroes. 364 */ 365 while (!BN_is_zero(tmp)) { 366 if ((w = BN_div_word(tmp, BN_DEC_CONV)) == -1) 367 goto err; 368 for (i = 0; i < BN_DEC_NUM; i++) { 369 v = w % 10; 370 if (!CBB_add_u8(&cbb, '0' + v)) 371 goto err; 372 w /= 10; 373 } 374 } 375 if (!CBB_finish(&cbb, &data, &data_len)) 376 goto err; 377 378 if (data_len > SIZE_MAX - 3) 379 goto err; 380 if (!CBB_init(&cbb, data_len + 3)) 381 goto err; 382 383 if (BN_is_negative(bn)) { 384 if (!CBB_add_u8(&cbb, '-')) 385 goto err; 386 } 387 388 /* Reverse digits and trim leading zeroes. */ 389 CBS_init(&cbs, data, data_len); 390 while (CBS_len(&cbs) > 0) { 391 if (!CBS_get_last_u8(&cbs, &c)) 392 goto err; 393 if (!started && c == '0') 394 continue; 395 if (!CBB_add_u8(&cbb, c)) 396 goto err; 397 started = 1; 398 } 399 400 if (!started) { 401 if (!CBB_add_u8(&cbb, '0')) 402 goto err; 403 } 404 if (!CBB_add_u8(&cbb, '\0')) 405 goto err; 406 if (!CBB_finish(&cbb, &s, &s_len)) 407 goto err; 408 409 err: 410 BN_free(tmp); 411 CBB_cleanup(&cbb); 412 freezero(data, data_len); 413 414 return s; 415 } 416 LCRYPTO_ALIAS(BN_bn2dec); 417 418 static int 419 bn_dec2bn_cbs(BIGNUM **bnp, CBS *cbs) 420 { 421 CBS cbs_digits; 422 BIGNUM *bn = NULL; 423 int d, neg, num; 424 size_t digits = 0; 425 BN_ULONG w; 426 uint8_t v; 427 428 /* Handle negative sign. */ 429 if (!CBS_peek_u8(cbs, &v)) 430 goto err; 431 if ((neg = (v == '-'))) { 432 if (!CBS_skip(cbs, 1)) 433 goto err; 434 } 435 436 /* Scan to find last decimal digit. */ 437 CBS_dup(cbs, &cbs_digits); 438 while (CBS_len(&cbs_digits) > 0) { 439 if (!CBS_get_u8(&cbs_digits, &v)) 440 goto err; 441 if (!isdigit(v)) 442 break; 443 digits++; 444 } 445 if (digits > INT_MAX / 4) 446 goto err; 447 448 num = digits + neg; 449 450 if (bnp == NULL) 451 return num; 452 453 if ((bn = *bnp) == NULL) 454 bn = BN_new(); 455 if (bn == NULL) 456 goto err; 457 if (!bn_expand_bits(bn, digits * 4)) 458 goto err; 459 460 if ((d = digits % BN_DEC_NUM) == 0) 461 d = BN_DEC_NUM; 462 463 w = 0; 464 465 /* Work forwards from most significant digit. */ 466 while (digits-- > 0) { 467 if (!CBS_get_u8(cbs, &v)) 468 goto err; 469 470 if (v < '0' || v > '9') 471 goto err; 472 473 v -= '0'; 474 w = w * 10 + v; 475 d--; 476 477 if (d == 0) { 478 if (!BN_mul_word(bn, BN_DEC_CONV)) 479 goto err; 480 if (!BN_add_word(bn, w)) 481 goto err; 482 483 d = BN_DEC_NUM; 484 w = 0; 485 } 486 } 487 488 bn_correct_top(bn); 489 490 BN_set_negative(bn, neg); 491 492 *bnp = bn; 493 494 return num; 495 496 err: 497 if (bnp != NULL && *bnp == NULL) 498 BN_free(bn); 499 500 return 0; 501 } 502 503 int 504 BN_dec2bn(BIGNUM **bnp, const char *s) 505 { 506 size_t s_len; 507 CBS cbs; 508 509 if (bnp != NULL && *bnp != NULL) 510 BN_zero(*bnp); 511 512 if (s == NULL) 513 return 0; 514 if ((s_len = strlen(s)) == 0) 515 return 0; 516 517 CBS_init(&cbs, s, s_len); 518 519 return bn_dec2bn_cbs(bnp, &cbs); 520 } 521 LCRYPTO_ALIAS(BN_dec2bn); 522 523 static int 524 bn_bn2hex_internal(const BIGNUM *bn, int include_sign, int nibbles_only, 525 char **out, size_t *out_len) 526 { 527 int started = 0; 528 uint8_t *s = NULL; 529 size_t s_len = 0; 530 BN_ULONG v, w; 531 int i, j; 532 CBB cbb; 533 CBS cbs; 534 uint8_t nul; 535 int ret = 0; 536 537 *out = NULL; 538 *out_len = 0; 539 540 if (!CBB_init(&cbb, 0)) 541 goto err; 542 543 if (BN_is_negative(bn) && include_sign) { 544 if (!CBB_add_u8(&cbb, '-')) 545 goto err; 546 } 547 if (BN_is_zero(bn)) { 548 if (!CBB_add_u8(&cbb, '0')) 549 goto err; 550 } 551 for (i = bn->top - 1; i >= 0; i--) { 552 w = bn->d[i]; 553 for (j = BN_BITS2 - 8; j >= 0; j -= 8) { 554 v = (w >> j) & 0xff; 555 if (!started && v == 0) 556 continue; 557 if (started || !nibbles_only || (v >> 4) != 0) { 558 if (!CBB_add_u8(&cbb, hex_digits[v >> 4])) 559 goto err; 560 } 561 if (!CBB_add_u8(&cbb, hex_digits[v & 0xf])) 562 goto err; 563 started = 1; 564 } 565 } 566 if (!CBB_add_u8(&cbb, '\0')) 567 goto err; 568 if (!CBB_finish(&cbb, &s, &s_len)) 569 goto err; 570 571 /* The length of a C string does not include the terminating NUL. */ 572 CBS_init(&cbs, s, s_len); 573 if (!CBS_get_last_u8(&cbs, &nul)) 574 goto err; 575 576 *out = (char *)CBS_data(&cbs); 577 *out_len = CBS_len(&cbs); 578 s = NULL; 579 s_len = 0; 580 581 ret = 1; 582 583 err: 584 CBB_cleanup(&cbb); 585 freezero(s, s_len); 586 587 return ret; 588 } 589 590 int 591 bn_bn2hex_nosign(const BIGNUM *bn, char **out, size_t *out_len) 592 { 593 return bn_bn2hex_internal(bn, 0, 0, out, out_len); 594 } 595 596 int 597 bn_bn2hex_nibbles(const BIGNUM *bn, char **out, size_t *out_len) 598 { 599 return bn_bn2hex_internal(bn, 1, 1, out, out_len); 600 } 601 602 char * 603 BN_bn2hex(const BIGNUM *bn) 604 { 605 char *s; 606 size_t s_len; 607 608 if (!bn_bn2hex_internal(bn, 1, 0, &s, &s_len)) 609 return NULL; 610 611 return s; 612 } 613 LCRYPTO_ALIAS(BN_bn2hex); 614 615 static int 616 bn_hex2bn_cbs(BIGNUM **bnp, CBS *cbs) 617 { 618 CBS cbs_digits; 619 BIGNUM *bn = NULL; 620 int b, i, neg, num; 621 size_t digits = 0; 622 BN_ULONG w; 623 uint8_t v; 624 625 /* Handle negative sign. */ 626 if (!CBS_peek_u8(cbs, &v)) 627 goto err; 628 if ((neg = (v == '-'))) { 629 if (!CBS_skip(cbs, 1)) 630 goto err; 631 } 632 633 /* Scan to find last hexadecimal digit. */ 634 CBS_dup(cbs, &cbs_digits); 635 while (CBS_len(&cbs_digits) > 0) { 636 if (!CBS_get_u8(&cbs_digits, &v)) 637 goto err; 638 if (!isxdigit(v)) 639 break; 640 digits++; 641 } 642 if (digits > INT_MAX / 4) 643 goto err; 644 645 num = digits + neg; 646 647 if (bnp == NULL) 648 return num; 649 650 if ((bn = *bnp) == NULL) 651 bn = BN_new(); 652 if (bn == NULL) 653 goto err; 654 if (!bn_expand_bits(bn, digits * 4)) 655 goto err; 656 657 if (!CBS_get_bytes(cbs, cbs, digits)) 658 goto err; 659 660 b = 0; 661 i = 0; 662 w = 0; 663 664 /* Work backwards from least significant digit. */ 665 while (digits-- > 0) { 666 if (!CBS_get_last_u8(cbs, &v)) 667 goto err; 668 669 if (v >= '0' && v <= '9') 670 v -= '0'; 671 else if (v >= 'a' && v <= 'f') 672 v -= 'a' - 10; 673 else if (v >= 'A' && v <= 'F') 674 v -= 'A' - 10; 675 else 676 goto err; 677 678 w |= (BN_ULONG)v << b; 679 b += 4; 680 681 if (b == BN_BITS2 || digits == 0) { 682 b = 0; 683 bn->d[i++] = w; 684 w = 0; 685 } 686 } 687 688 bn->top = i; 689 bn_correct_top(bn); 690 691 BN_set_negative(bn, neg); 692 693 *bnp = bn; 694 695 return num; 696 697 err: 698 if (bnp != NULL && *bnp == NULL) 699 BN_free(bn); 700 701 return 0; 702 } 703 704 int 705 BN_hex2bn(BIGNUM **bnp, const char *s) 706 { 707 size_t s_len; 708 CBS cbs; 709 710 if (bnp != NULL && *bnp != NULL) 711 BN_zero(*bnp); 712 713 if (s == NULL) 714 return 0; 715 if ((s_len = strlen(s)) == 0) 716 return 0; 717 718 CBS_init(&cbs, s, s_len); 719 720 return bn_hex2bn_cbs(bnp, &cbs); 721 } 722 LCRYPTO_ALIAS(BN_hex2bn); 723 724 int 725 BN_bn2mpi(const BIGNUM *a, unsigned char *d) 726 { 727 int bits; 728 int num = 0; 729 int ext = 0; 730 long l; 731 732 bits = BN_num_bits(a); 733 num = (bits + 7) / 8; 734 if (bits > 0) { 735 ext = ((bits & 0x07) == 0); 736 } 737 if (d == NULL) 738 return (num + 4 + ext); 739 740 l = num + ext; 741 d[0] = (unsigned char)(l >> 24) & 0xff; 742 d[1] = (unsigned char)(l >> 16) & 0xff; 743 d[2] = (unsigned char)(l >> 8) & 0xff; 744 d[3] = (unsigned char)(l) & 0xff; 745 if (ext) 746 d[4] = 0; 747 num = BN_bn2bin(a, &(d[4 + ext])); 748 if (a->neg) 749 d[4] |= 0x80; 750 return (num + 4 + ext); 751 } 752 LCRYPTO_ALIAS(BN_bn2mpi); 753 754 BIGNUM * 755 BN_mpi2bn(const unsigned char *d, int n, BIGNUM *ain) 756 { 757 BIGNUM *a = ain; 758 long len; 759 int neg = 0; 760 761 if (n < 4) { 762 BNerror(BN_R_INVALID_LENGTH); 763 return (NULL); 764 } 765 len = ((long)d[0] << 24) | ((long)d[1] << 16) | ((int)d[2] << 8) | 766 (int)d[3]; 767 if ((len + 4) != n) { 768 BNerror(BN_R_ENCODING_ERROR); 769 return (NULL); 770 } 771 772 if (a == NULL) 773 a = BN_new(); 774 if (a == NULL) 775 return (NULL); 776 777 if (len == 0) { 778 a->neg = 0; 779 a->top = 0; 780 return (a); 781 } 782 d += 4; 783 if ((*d) & 0x80) 784 neg = 1; 785 if (BN_bin2bn(d, (int)len, a) == NULL) { 786 if (ain == NULL) 787 BN_free(a); 788 return (NULL); 789 } 790 BN_set_negative(a, neg); 791 if (neg) { 792 BN_clear_bit(a, BN_num_bits(a) - 1); 793 } 794 return (a); 795 } 796 LCRYPTO_ALIAS(BN_mpi2bn); 797