1 /** 2 * BigInt 3 * 4 * Copyright: 5 * (C) 1999-2008,2012 Jack Lloyd 6 * (C) 2014-2015 Etienne Cimon 7 * 2007 FlexSecure 8 * 9 * License: 10 * Botan is released under the Simplified BSD License (see LICENSE.md) 11 */ 12 module botan.math.bigint.bigint; 13 14 import botan.constants; 15 public import botan.math.mp.mp_types; 16 public import botan.utils.types; 17 import botan.constants; 18 import botan.rng.rng; 19 import memutils.vector; 20 import botan.utils.charset; 21 import botan.codec.hex; 22 import botan.math.bigint.divide; 23 import botan.math.mp.mp_core; 24 import botan.utils.get_byte; 25 import botan.utils.parsing; 26 import botan.utils.rounding; 27 import botan.utils.parsing; 28 import botan.utils.bit_ops; 29 import std.algorithm; 30 import std.traits : isNumeric; 31 32 /** 33 * Arbitrary precision integer 34 */ 35 struct BigInt 36 { 37 public: 38 /* 39 * Write the BigInt into a vector 40 */ 41 Vector!char toVector(Base base = Decimal) const 42 { 43 Vector!ubyte buffer = BigInt.encode(this, base); 44 Vector!char ret; 45 size_t skip = 0; 46 while(skip < buffer.length && buffer[skip] == '0') 47 ++skip; 48 ret[] = cast(char[])(buffer.ptr + skip)[0 .. buffer.length - skip]; 49 return ret.move(); 50 } 51 52 /* 53 * Write the BigInt into a string 54 */ 55 string toString(Base base = Decimal) const 56 { 57 auto vec = toVector(base); 58 //logTrace("toString: ", vec[]); 59 return (vec[]).idup; 60 } 61 alias Base = int; 62 /** 63 * Base enumerator for encoding and decoding 64 */ 65 enum : Base { Decimal = 10, Hexadecimal = 16, Binary = 256 } 66 67 alias Sign = bool; 68 /** 69 * Sign symbol definitions for positive and negative numbers 70 */ 71 enum : Sign { Negative = 0, Positive = 1 } 72 73 /** 74 * DivideByZero Exception 75 */ 76 class DivideByZero : Exception 77 { 78 this() { 79 super("BigInt divide by zero"); 80 } 81 } 82 83 /** 84 * Create BigInt from any integer 85 * Params: 86 * n = initial value of this BigInt 87 */ 88 this(T)(T n) 89 if (isNumeric!T) 90 { 91 import std.algorithm : max; 92 if (n == 0) 93 return; 94 const size_t limbs_needed = std.algorithm.max(1, T.sizeof / word.sizeof); 95 m_reg.resize(4*limbs_needed); 96 foreach (size_t i; 0 .. limbs_needed) 97 m_reg[i] = ((n >> (i*MP_WORD_BITS)) & MP_WORD_MASK); 98 } 99 100 @disable this(this); 101 102 /// Move constructor 103 ref BigInt opAssign(size_t other) 104 { 105 BigInt bigInt = BigInt(other); 106 this.swap(bigInt); 107 108 return this; 109 } 110 111 /// Copy constructor 112 void load()(auto ref BigInt other) { 113 m_reg[] = other.m_reg[]; 114 m_signedness = other.m_signedness; 115 m_sig_words = other.m_sig_words; 116 } 117 118 /** 119 * Create BigInt from a string. If the string starts with 0x the 120 * rest of the string will be interpreted as hexadecimal digits. 121 * Otherwise, it will be interpreted as a decimal number. 122 * 123 * Params: 124 * str = the string to parse for an integer value 125 */ 126 this(in string str) 127 { 128 Base base = Decimal; 129 size_t markers = 0; 130 bool negative = false; 131 132 if (str.length > 0 && str[0] == '-') 133 { 134 markers += 1; 135 negative = true; 136 } 137 138 if (str.length > markers + 2 && str[markers ] == '0' && 139 str[markers + 1] == 'x') 140 { 141 markers += 2; 142 base = Hexadecimal; 143 } 144 auto contents = decode(cast(const(ubyte)*)(str.ptr) + markers, str.length - markers, base); 145 this.swap( contents ); 146 147 if (negative) setSign(Negative); 148 else setSign(Positive); 149 } 150 151 /** 152 * Create a BigInt from an integer in a ubyte array 153 * Params: 154 * input = the ubyte array holding the value 155 * length = size of buf 156 * base = is the number base of the integer in buf 157 */ 158 this(const(ubyte)* input, size_t length, Base base = Binary) 159 { 160 auto contents = decode(input, length, base); 161 this.swap( contents ); 162 } 163 164 /** 165 * Create a random BigInt of the specified size 166 * Params: 167 * rng = random number generator 168 * bits = size in bits 169 * set_high_bit = if true, the highest bit is always set 170 */ 171 this(RandomNumberGenerator rng, size_t bits, bool set_high_bit = true) 172 { 173 randomize(rng, bits, set_high_bit); 174 } 175 /** 176 * Create BigInt of specified size, all zeros 177 * Params: 178 * s = the sign 179 * size = of the internal register in words 180 */ 181 this(Sign s, size_t size) 182 { 183 m_reg.resize(roundUp!size_t(size, 8)); 184 m_signedness = s; 185 } 186 187 /** 188 * Move constructor 189 */ 190 this()(auto ref BigInt other) 191 { 192 this.swap(other); 193 } 194 195 this(ALLOC)(auto const ref Vector!(ubyte, ALLOC) payload, in Sign sign, in size_t sig_words = size_t.max) { 196 this(payload.ptr, payload.length, sig_words); 197 } 198 199 this(ALLOC)(auto const ref RefCounted!(Vector!(ubyte, ALLOC), ALLOC) payload, in Sign sign, in size_t sig_words = size_t.max) { 200 this(payload.ptr, payload.length, sig_words); 201 } 202 203 this()(auto ref SecureVector!word reg, Sign sign, in size_t sig_words = size_t.max) { 204 import std.algorithm : swap; 205 m_reg.swap(reg); 206 swap(m_signedness, sign); 207 m_sig_words = sig_words; 208 } 209 210 void reserve(size_t n) { 211 m_reg.reserve(n); 212 } 213 214 /** 215 * Move assignment 216 */ 217 void opAssign()(auto ref BigInt other) 218 { 219 this.swap(other); 220 } 221 222 /** 223 * Copy assignment 224 */ 225 // BigInt operator=(const ref BigInt) = default; 226 227 /** 228 * Swap this value with another 229 * Params: 230 * other = BigInt to swap values with 231 */ 232 void swap()(auto ref BigInt other) 233 { 234 m_reg.swap(other.m_reg); 235 236 .swap(m_signedness, other.m_signedness); 237 .swap(m_sig_words, other.m_sig_words); 238 } 239 240 void swapReg(ref SecureVector!word reg) 241 { 242 m_reg.swap(reg); 243 m_sig_words = size_t.max; 244 } 245 246 /** 247 * += operator 248 * Params: 249 * y = the BigInt to add to this 250 */ 251 void opOpAssign(string op)(auto const ref BigInt y) 252 if (op == "+") 253 { 254 const size_t x_sw = sigWords(), y_sw = y.sigWords(); 255 256 const size_t reg_size = std.algorithm.max(x_sw, y_sw) + 1; 257 growTo(reg_size); 258 259 if (sign() == y.sign()) 260 bigint_add2(mutablePtr(), reg_size - 1, y.ptr, y_sw); 261 else 262 { 263 int relative_size = bigint_cmp(mutablePtr(), x_sw, y.ptr, y_sw); 264 265 if (relative_size < 0) 266 { 267 SecureVector!word z = SecureVector!word(reg_size - 1); 268 bigint_sub3(z.ptr, y.ptr, reg_size - 1, mutablePtr(), x_sw); 269 m_reg[] = z; 270 m_sig_words = z.length; 271 setSign(y.sign()); 272 } 273 else if (relative_size == 0) 274 { 275 zeroise(m_reg); 276 setSign(Positive); 277 } 278 else if (relative_size > 0) 279 bigint_sub2(mutablePtr(), x_sw, y.ptr, y_sw); 280 } 281 282 } 283 284 void opOpAssign(string op)(in word y) 285 if (op == "+") 286 { 287 this += BigInt(y); 288 } 289 290 /** 291 * -= operator 292 * Params: 293 * y = the BigInt to subtract from this 294 */ 295 void opOpAssign(string op)(auto const ref BigInt y) 296 if (op == "-") 297 { 298 const size_t x_sw = sigWords(), y_sw = y.sigWords(); 299 300 int relative_size = bigint_cmp(mutablePtr(), x_sw, y.ptr, y_sw); 301 302 const size_t reg_size = std.algorithm.max(x_sw, y_sw) + 1; 303 growTo(reg_size); 304 305 if (relative_size < 0) 306 { 307 if (sign() == y.sign()) 308 bigint_sub2_rev(mutablePtr(), y.ptr, y_sw); 309 else 310 bigint_add2(mutablePtr(), reg_size - 1, y.ptr, y_sw); 311 312 setSign(y.reverseSign()); 313 } 314 else if (relative_size == 0) 315 { 316 if (sign() == y.sign()) 317 { 318 clear(); 319 setSign(Positive); 320 } 321 else 322 bigint_shl1(mutablePtr(), x_sw, 0, 1); 323 } 324 else if (relative_size > 0) 325 { 326 if (sign() == y.sign()) 327 bigint_sub2(mutablePtr(), x_sw, y.ptr, y_sw); 328 else 329 bigint_add2(mutablePtr(), reg_size - 1, y.ptr, y_sw); 330 } 331 } 332 333 334 void opOpAssign(string op)(in word y) 335 if (op == "-") 336 { 337 this -= BigInt(y); 338 } 339 340 341 /** 342 * *= operator 343 * Params: 344 * y = the BigInt to multiply with this 345 */ 346 void opOpAssign(string op)(const ref BigInt y) 347 if (op == "*") 348 { 349 const size_t x_sw = sigWords(), y_sw = y.sigWords(); 350 setSign((sign() == y.sign()) ? Positive : Negative); 351 352 if (x_sw == 0 || y_sw == 0) 353 { 354 clear(); 355 setSign(Positive); 356 } 357 else if (x_sw == 1 && y_sw) 358 { 359 growTo(y_sw + 2); 360 bigint_linmul3(mutablePtr(), y.ptr, y_sw, wordAt(0)); 361 } 362 else if (y_sw == 1 && x_sw) 363 { 364 growTo(x_sw + 2); 365 bigint_linmul2(mutablePtr(), x_sw, y.wordAt(0)); 366 } 367 else 368 { 369 growTo(size() + y.length); 370 371 SecureVector!word z = SecureVector!word(mutablePtr()[0 .. x_sw]); 372 SecureVector!word workspace = SecureVector!word(size()); 373 374 bigint_mul(mutablePtr(), size(), workspace.ptr, z.ptr, z.length, x_sw, y.ptr, y.length, y_sw); 375 } 376 } 377 378 379 void opOpAssign(string op)(in word y) 380 if (op == "*") 381 { 382 const BigInt b_y = BigInt(y); 383 this *= b_y; 384 } 385 386 /** 387 * /= operator 388 * Params: 389 * y = the BigInt to divide this by 390 */ 391 void opOpAssign(string op)(auto const ref BigInt y) 392 if (op == "/") 393 { 394 if (y.sigWords() == 1 && isPowerOf2(y.wordAt(0))) 395 this >>= (y.bits() - 1); 396 else 397 this = this / y; 398 } 399 400 401 void opOpAssign(string op)(in word y) 402 if (op == "/") 403 { 404 this /= BigInt(y); 405 } 406 407 408 /** 409 * Modulo operator 410 * Params: 411 * mod = the modulus to reduce this by 412 */ 413 void opOpAssign(string op)(auto const ref BigInt mod) 414 if (op == "%") 415 { 416 this = this % mod; 417 } 418 419 /** 420 * Modulo operator 421 * Params: 422 * mod = the modulus (word) to reduce this by 423 */ 424 void opOpAssign(string op)(word mod) 425 if (op == "%") 426 { 427 if (mod == 0) 428 throw new DivideByZero(); 429 430 if (isPowerOf2(mod)) 431 { 432 word result = (wordAt(0) & (mod - 1)); 433 clear(); 434 growTo(2); 435 m_reg[0] = result; 436 return; 437 } 438 439 word remainder = 0; 440 441 for (size_t j = sigWords(); j > 0; --j) 442 remainder = bigint_modop(remainder, wordAt(j-1), mod); 443 clear(); 444 growTo(2); 445 446 if (remainder && sign() == Negative) 447 m_reg[0] = mod - remainder; 448 else 449 m_reg[0] = remainder; 450 451 setSign(Positive); 452 } 453 454 455 /** 456 * Left shift operator 457 * Params: 458 * shift = the number of bits to shift this left by 459 */ 460 void opOpAssign(string op)(size_t shift) 461 if (op == "<<") 462 { 463 if (shift) 464 { 465 const size_t shift_words = shift / MP_WORD_BITS; 466 const size_t shift_bits = shift % MP_WORD_BITS; 467 const size_t words = sigWords(); 468 469 growTo(words + shift_words + (shift_bits ? 1 : 0)); 470 bigint_shl1(mutablePtr(), words, shift_words, shift_bits); 471 } 472 473 } 474 475 /** 476 * Right shift operator 477 * Params: 478 * shift = the number of bits to shift this right by 479 */ 480 void opOpAssign(string op)(size_t shift) 481 if (op == ">>") 482 { 483 if (shift) 484 { 485 const size_t shift_words = shift / MP_WORD_BITS; 486 const size_t shift_bits = shift % MP_WORD_BITS; 487 488 bigint_shr1(mutablePtr(), sigWords(), shift_words, shift_bits); 489 m_sig_words = size_t.max; 490 if (isZero()) 491 setSign(Positive); 492 } 493 } 494 495 /** 496 * Increment operator 497 */ 498 ref BigInt opUnary(string op)() if (op == "++") { this += BigInt(1); return this; } 499 500 /** 501 * Decrement operator 502 */ 503 ref BigInt opUnary(string op)() if (op == "--") { this -= BigInt(1); return this; } 504 505 /** 506 * Unary negation operator 507 * Returns: negative this 508 */ 509 BigInt opUnary(string op)() const 510 if (op == "-") 511 { 512 BigInt ret = this.dup; 513 ret.flipSign(); 514 return ret; 515 } 516 517 /** 518 * bool cast 519 * Returns: true iff this is not zero, otherwise false 520 */ 521 T opCast(T : bool)() const { return isNonzero(); } 522 523 T opCast(T : BigInt)() const { return *cast(BigInt*)&this; } 524 525 /** 526 * Zeroize the BigInt. The size of the underlying register is not 527 * modified. 528 */ 529 void clear() 530 { 531 import core.stdc..string : memset; 532 if (!m_reg.empty){ 533 memset(mutablePtr(), 0, word.sizeof*m_reg.length); 534 } 535 } 536 537 /** 538 * Compare this to another BigInt 539 * Params: 540 * other = the BigInt value to compare with 541 * check_signs = include sign in comparison? 542 * Returns: if (this<n) return -1, if (this>n) return 1, if both 543 * values are identical return 0 [like Perl's <=> operator] 544 */ 545 int cmp(const ref BigInt other, bool check_signs = true) const 546 { 547 if (check_signs) 548 { 549 if (other.isPositive() && this.isNegative()) 550 return -1; 551 552 if (other.isNegative() && this.isPositive()) 553 return 1; 554 555 if (other.isNegative() && this.isNegative()) 556 return (-bigint_cmp(m_reg.ptr, this.sigWords(), other.ptr, other.sigWords())); 557 } 558 559 return bigint_cmp(m_reg.ptr, this.sigWords(), other.ptr, other.sigWords()); 560 } 561 /* 562 * Comparison Operators 563 */ 564 bool opEquals()(auto const ref BigInt b) const 565 { return (cmp(b) == 0); } 566 567 bool opEquals(in size_t n) const 568 { 569 BigInt b = n; 570 return (cmp(b) == 0); 571 } 572 573 574 int opCmp()(auto const ref BigInt b) const 575 { 576 return cmp(b); 577 } 578 579 int opCmp(in size_t n) const 580 { 581 BigInt b = n; 582 return cmp(b); 583 } 584 585 /** 586 * Test if the integer has an even value 587 * Returns: true if the integer is even, false otherwise 588 */ 589 bool isEven() const { return (getBit(0) == 0); } 590 591 /** 592 * Test if the integer has an odd value 593 * Returns: true if the integer is odd, false otherwise 594 */ 595 bool isOdd() const { return (getBit(0) == 1); } 596 597 /** 598 * Test if the integer is not zero 599 * Returns: true if the integer is non-zero, false otherwise 600 */ 601 bool isNonzero() const { return (!isZero()); } 602 603 /** 604 * Test if the integer is zero 605 * Returns: true if the integer is zero, false otherwise 606 */ 607 bool isZero() const 608 { 609 const size_t sw = sigWords(); 610 foreach (size_t i; 0 .. sw) 611 if (m_reg[i] > 0) 612 return false; 613 return true; 614 } 615 616 /** 617 * Set bit at specified position 618 * Params: 619 * n = bit position to set 620 */ 621 void setBit(size_t n) 622 { 623 const size_t which = n / MP_WORD_BITS; 624 const word mask = cast(word)(1) << (n % MP_WORD_BITS); 625 if (which >= size()) growTo(which + 1); 626 m_reg[which] |= mask; 627 m_sig_words = size_t.max; 628 } 629 630 /** 631 * Clear bit at specified position 632 * Params: 633 * n = bit position to clear 634 */ 635 void clearBit(size_t n) 636 { 637 const size_t which = n / MP_WORD_BITS; 638 const word mask = cast(word)(1) << (n % MP_WORD_BITS); 639 if (which < size()) 640 m_reg[which] &= ~mask; 641 m_sig_words = size_t.max; 642 } 643 644 /** 645 * Clear all but the lowest n bits 646 * Params: 647 * n = amount of bits to keep 648 */ 649 void maskBits(size_t n) 650 { 651 if (n == 0) { clear(); return; } 652 if (n >= bits()) return; 653 654 const size_t top_word = n / MP_WORD_BITS; 655 const word mask = ((cast(word)1) << (n % MP_WORD_BITS)) - 1; 656 657 if (top_word < size()) 658 clearMem(&m_reg[top_word+1], size() - (top_word + 1)); 659 660 m_reg[top_word] &= mask; 661 m_sig_words = size_t.max; 662 } 663 664 /** 665 * Return bit value at specified position 666 * Params: 667 * n = the bit offset to test 668 * Returns: true, if the bit at position n is set, false otherwise 669 */ 670 bool getBit(size_t n) const 671 { 672 return ((wordAt(n / MP_WORD_BITS) >> (n % MP_WORD_BITS)) & 1); 673 } 674 675 /** 676 * Return (a maximum of) 32 bits of the complete value 677 * Params: 678 * offset = the offset to start extracting 679 * length = amount of bits to extract (starting at offset) 680 * Returns: the integer extracted from the register starting at 681 * offset with specified length 682 */ 683 uint getSubstring(size_t offset, size_t length) const 684 { 685 if (length > 32) 686 throw new InvalidArgument("BigInt.getSubstring: Substring size too big"); 687 688 ulong piece = 0; 689 foreach (size_t i; 0 .. 8) 690 { 691 const ubyte part = byteAt((offset / 8) + (7-i)); 692 piece = (piece << 8) | part; 693 } 694 695 const ulong mask = (cast(ulong)(1) << length) - 1; 696 const size_t shift = (offset % 8); 697 698 return cast(uint)((piece >> shift) & mask); 699 } 700 701 /** 702 * Convert this value into a uint, if it is in the range 703 * [0 ... 2**32-1], or otherwise throw new an exception. 704 * Returns: the value as a uint if conversion is possible 705 */ 706 uint toUint() const 707 { 708 if (isNegative()) 709 throw new EncodingError("BigInt.to_uint: Number is negative"); 710 if (bits() >= 32) 711 throw new EncodingError("BigInt.to_uint: Number is too big to convert"); 712 713 uint output = 0; 714 for (uint j = 0; j != 4; ++j) 715 output = (output << 8) | byteAt(3-j); 716 return output; 717 } 718 719 /** 720 * Params: 721 * n = the offset to get a ubyte from 722 * Returns: ubyte at offset n 723 */ 724 ubyte byteAt(size_t n) const 725 { 726 const size_t WORD_BYTES = (word).sizeof; 727 size_t word_num = n / WORD_BYTES; 728 size_t byte_num = n % WORD_BYTES; 729 if (word_num >= size()) 730 return 0; 731 else 732 return get_byte(WORD_BYTES - byte_num - 1, m_reg[word_num]); 733 } 734 735 /** 736 * Return the word at a specified position of the internal register 737 * Params: 738 * n = position in the register 739 * Returns: value at position n 740 */ 741 word wordAt(size_t n) const 742 { return ((n < size()) ? m_reg[n] : 0); } 743 744 /** 745 * Tests if the sign of the integer is negative 746 * Returns: true, iff the integer has a negative sign 747 */ 748 bool isNegative() const { return (sign() == Negative); } 749 750 /** 751 * Tests if the sign of the integer is positive 752 * Returns: true, iff the integer has a positive sign 753 */ 754 bool isPositive() const { return (sign() == Positive); } 755 756 /** 757 * Return the sign of the integer 758 * Returns: the sign of the integer 759 */ 760 Sign sign() const { return (m_signedness); } 761 762 /** 763 * Returns: the opposite sign of the represented integer value 764 */ 765 Sign reverseSign() const 766 { 767 if (sign() == Positive) 768 return Negative; 769 return Positive; 770 } 771 772 /** 773 * Flip the sign of this BigInt 774 */ 775 void flipSign() 776 { 777 setSign(reverseSign()); 778 } 779 780 /** 781 * Set sign of the integer 782 * Params: 783 * s = new Sign to set 784 */ 785 void setSign(Sign s) 786 { 787 if (isZero()) 788 m_signedness = Positive; 789 else 790 m_signedness = s; 791 } 792 793 /** 794 * Returns: absolute (positive) value of this 795 */ 796 BigInt abs() const 797 { 798 BigInt ret = this.dup; 799 ret.setSign(Positive); 800 return ret; 801 } 802 803 /** 804 * Give size of internal register 805 * Returns: size of internal register in words 806 */ 807 size_t size() const { return m_reg.length; } 808 809 // ditto 810 size_t length() const { return size(); } 811 812 /** 813 * Return how many words we need to hold this value 814 * Returns: significant words of the represented integer value 815 */ 816 size_t sigWords() const 817 { 818 if (m_sig_words != size_t.max) return m_sig_words; 819 const word* x = m_reg.ptr; 820 size_t sig = m_reg.length; 821 822 while (sig && (x[sig-1] == 0)) 823 sig--; 824 (cast()this).m_sig_words = sig; 825 return sig; 826 } 827 828 /** 829 * Give ubyte length of the integer 830 * Returns: ubyte length of the represented integer value 831 */ 832 size_t bytes() const 833 { 834 return (bits() + 7) / 8; 835 } 836 837 /** 838 * Get the bit length of the integer 839 * Returns: bit length of the represented integer value 840 */ 841 size_t bits() const 842 { 843 const size_t words = sigWords(); 844 if (words == 0) 845 return 0; 846 847 const size_t full_words = words - 1; 848 return (full_words * MP_WORD_BITS + highBit(wordAt(full_words))); 849 } 850 851 /** 852 * Return a mutable pointer to the register 853 * Returns: a pointer to the start of the internal register 854 */ 855 word* mutablePtr() { m_sig_words = size_t.max; return m_reg.ptr; } 856 857 /** 858 * Return a const pointer to the register 859 * Returns: a pointer to the start of the internal register 860 */ 861 @property const(word*) ptr() const { return m_reg.ptr; } 862 863 /** 864 * Increase internal register buffer to at least n words 865 * Params: 866 * n = new size of register 867 */ 868 void growTo(size_t n) 869 { 870 if (n >= size()) 871 m_reg.resize(roundUp!size_t(n, 8)); 872 } 873 874 /** 875 * Fill BigInt with a random number with size of bitsize 876 * If set_high_bit is true, the highest bit will be set, which causes 877 * the entropy to be bits-1. Otherwise the highest bit is randomly choosen 878 * by the rng, causing the entropy to be bits. 879 * 880 * Params: 881 * rng = the random number generator to use 882 * bitsize = number of bits the created random value should have 883 * set_high_bit = if true, the highest bit is always set 884 */ 885 void randomize(RandomNumberGenerator rng, size_t bitsize = 0, bool set_high_bit = true) 886 { 887 setSign(Positive); 888 889 if (bitsize == 0) 890 clear(); 891 else 892 { 893 SecureVector!ubyte array = rng.randomVec((bitsize + 7) / 8); 894 // Always cut unwanted bits 895 if (bitsize % 8) 896 array[0] &= 0xFF >> (8 - (bitsize % 8)); 897 // Set the highest bit if wanted 898 if (set_high_bit) 899 array[0] |= 0x80 >> ((bitsize % 8) ? (8 - bitsize % 8) : 0); 900 binaryDecode(array.ptr, array.length); 901 } 902 } 903 904 /** 905 * Store BigInt-value in a given ubyte array 906 * Params: 907 * output = destination ubyte array for the integer value 908 */ 909 void binaryEncode(ubyte* output) const 910 { 911 const size_t sig_bytes = bytes(); 912 foreach (size_t i; 0 .. sig_bytes) { 913 output[sig_bytes-i-1] = byteAt(i); 914 } 915 } 916 917 /** 918 * Read integer value from a ubyte array with given size 919 * Params: 920 * buf = ubyte array buffer containing the integer 921 * length = size of buf 922 */ 923 void binaryDecode(const(ubyte)* buf, size_t length) 924 { 925 const size_t WORD_BYTES = (word).sizeof; 926 927 clear(); 928 m_reg.resize(roundUp!size_t((length / WORD_BYTES) + 1, 8)); 929 foreach (size_t i; 0 .. (length / WORD_BYTES)) 930 { 931 const size_t top = length - WORD_BYTES*i; 932 for (size_t j = WORD_BYTES; j > 0; --j) 933 m_reg[i] = (m_reg[i] << 8) | buf[top - j]; 934 } 935 936 foreach (size_t i; 0 .. (length % WORD_BYTES)) 937 m_reg[length / WORD_BYTES] = (m_reg[length / WORD_BYTES] << 8) | buf[i]; 938 m_sig_words = size_t.max; 939 } 940 941 /** 942 * Read integer value from a ubyte array (SecureVector!ubyte) 943 * Params: 944 * buf = the array to load from 945 */ 946 void binaryDecode(ALLOC)(auto const ref Vector!(ubyte, ALLOC) buf) 947 { 948 binaryDecode(buf.ptr, buf.length); 949 } 950 951 /// ditto 952 void binaryDecode(ALLOC)(auto const ref RefCounted!(Vector!(ubyte, ALLOC), ALLOC) buf) 953 { 954 binaryDecode(buf.ptr, buf.length); 955 } 956 957 /** 958 * Params: 959 * base = the base to measure the size for 960 * Returns: size of this integer in base base 961 */ 962 size_t encodedSize(Base base = Binary) const 963 { 964 static const double LOG_2_BASE_10 = 0.30102999566; 965 966 if (base == Binary) 967 return bytes(); 968 else if (base == Hexadecimal) 969 return 2*bytes(); 970 else if (base == Decimal) 971 return cast(size_t)((bits() * LOG_2_BASE_10) + 1); 972 else 973 throw new InvalidArgument("Unknown base for BigInt encoding"); 974 } 975 976 /** 977 * Params: 978 * rng = a random number generator 979 * min = the minimum value 980 * max = the maximum value 981 * Returns: random integer in [min,max$(RPAREN) 982 */ 983 static BigInt randomInteger()(RandomNumberGenerator rng, auto const ref BigInt min, auto const ref BigInt max) 984 { 985 BigInt delta_upper_bound = max - min - 1; 986 987 if (delta_upper_bound <= 0) 988 throw new InvalidArgument("randomInteger: invalid min/max values"); 989 // Choose x in [0, delta_upper_bound] 990 BigInt x; 991 do { 992 auto bitsize = delta_upper_bound.bits(); 993 x.randomize(rng, bitsize, false); 994 } while (x > delta_upper_bound); 995 996 return min + x; 997 } 998 999 /** 1000 * Create a power of two 1001 * Params: 1002 * n = the power of two to create 1003 * Returns: bigint representing 2^n 1004 */ 1005 static BigInt powerOf2(size_t n) 1006 { 1007 BigInt b; 1008 b.setBit(n); 1009 return b; 1010 } 1011 1012 /** 1013 * Encode the integer value from a BigInt to an Array of bytes 1014 * Params: 1015 * n = the BigInt to use as integer source 1016 * base = number-base of resulting ubyte array representation 1017 * Returns: SecureVector of bytes containing the integer with given base 1018 */ 1019 static Vector!ubyte encode()(auto const ref BigInt n, Base base = Binary) 1020 { 1021 Vector!ubyte output = Vector!ubyte(n.encodedSize(base)); 1022 encode(output.ptr, n, base); 1023 if (base != Binary) 1024 for (size_t j = 0; j != output.length; ++j) 1025 if (output[j] == 0) 1026 output[j] = '0'; 1027 return output.move(); 1028 } 1029 1030 /** 1031 * Encode the integer value from a BigInt to a Secure Array of bytes 1032 * Params: 1033 * n = the BigInt to use as integer source 1034 * base = number-base of resulting ubyte array representation 1035 * Returns: SecureVector of bytes containing the integer with given base 1036 */ 1037 static SecureVector!ubyte encodeLocked()(auto const ref BigInt n, Base base = Binary) 1038 { 1039 SecureVector!ubyte output = SecureVector!ubyte(n.encodedSize(base)); 1040 encode(output.ptr, n, base); 1041 if (base != Binary) 1042 for (size_t j = 0; j != output.length; ++j) 1043 if (output[j] == 0) 1044 output[j] = '0'; 1045 return output.move(); 1046 } 1047 1048 /** 1049 * Encode the integer value from a BigInt to a ubyte array 1050 * Params: 1051 * output = destination ubyte array for the encoded integer 1052 * value with given base 1053 * n = the BigInt to use as integer source 1054 * base = number-base of resulting ubyte array representation 1055 */ 1056 static void encode()(ubyte* output, auto const ref BigInt n, Base base = Binary) 1057 { 1058 if (base == Binary) 1059 { 1060 n.binaryEncode(output); 1061 } 1062 else if (base == Hexadecimal) 1063 { 1064 SecureVector!ubyte binary = SecureVector!ubyte(n.encodedSize(Binary)); 1065 n.binaryEncode(binary.ptr); 1066 1067 hexEncode(cast(char*)(output), binary.ptr, binary.length); 1068 } 1069 else if (base == Decimal) 1070 { 1071 BigInt copy = n.dup(); 1072 BigInt remainder; 1073 copy.setSign(Positive); 1074 const size_t output_size = n.encodedSize(Decimal); 1075 foreach (size_t j; 0 .. output_size) 1076 { 1077 auto bi = BigInt(10); 1078 divide(copy, bi, copy, remainder); 1079 output[output_size - 1 - j] = digit2char(cast(ubyte)(remainder.wordAt(0))); 1080 if (copy.isZero()) 1081 break; 1082 } 1083 } 1084 else 1085 throw new InvalidArgument("Unknown BigInt encoding method"); 1086 } 1087 1088 /** 1089 * Create a BigInt from an integer in a ubyte array 1090 * Params: 1091 * buf = the binary value to load 1092 * length = size of buf 1093 * base = number-base of the integer in buf 1094 * Returns: BigInt representing the integer in the ubyte array 1095 */ 1096 static BigInt decode(const(ubyte)* buf, size_t length, Base base = Binary) 1097 { 1098 BigInt r; 1099 if (base == Binary) 1100 r.binaryDecode(buf, length); 1101 else if (base == Hexadecimal) 1102 { 1103 SecureVector!ubyte binary; 1104 if (length % 2) 1105 { 1106 // Handle lack of leading 0 1107 const char[2] buf0_with_leading_0 = [ '0', cast(char)(buf[0]) ]; 1108 1109 binary = hexDecodeLocked(buf0_with_leading_0.ptr, 2); 1110 binary.reserve(length); 1111 binary ~= hexDecodeLocked(cast(const(char)*)&buf[1], length - 1, false); 1112 } 1113 else { 1114 binary = hexDecodeLocked(cast(const(char)*)buf, length, false); 1115 } 1116 r.binaryDecode(binary.ptr, binary.length); 1117 } 1118 else if (base == Decimal) 1119 { 1120 foreach (size_t i; 0 .. length) 1121 { 1122 if (isSpace(buf[i])) 1123 continue; 1124 1125 if (!isDigit(buf[i])) 1126 throw new InvalidArgument("BigInt.decode: " ~ "Invalid character in decimal input"); 1127 1128 const ubyte x = char2digit(buf[i]); 1129 1130 if (x >= 10) 1131 throw new InvalidArgument("BigInt: Invalid decimal string"); 1132 1133 r *= 10; 1134 r += x; 1135 } 1136 } 1137 else 1138 throw new InvalidArgument("Unknown BigInt decoding method"); 1139 return r.move; 1140 } 1141 1142 1143 /** 1144 * Create a BigInt from an integer in a ubyte array 1145 * Params: 1146 * buf = the binary value to load 1147 * base = number-base of the integer in buf 1148 * Returns: BigInt representing the integer in the ubyte array 1149 */ 1150 static BigInt decode(ALLOC)(auto const ref RefCounted!(Vector!(ubyte, ALLOC), ALLOC) buf, Base base = Binary) 1151 { 1152 return BigInt.decode(buf.ptr, buf.length, base); 1153 } 1154 1155 /** 1156 * Create a BigInt from an integer in a ubyte array 1157 * Params: 1158 * buf = the binary value to load 1159 * base = number-base of the integer in buf 1160 * Returns: BigInt representing the integer in the ubyte array 1161 */ 1162 static BigInt decode(ALLOC)(auto const ref Vector!(ubyte, ALLOC) buf, Base base = Binary) 1163 { 1164 return BigInt.decode(buf.ptr, buf.length, base); 1165 } 1166 1167 /** 1168 * Encode a BigInt to a ubyte array according to IEEE 1363 1169 * Params: 1170 * n = the BigInt to encode 1171 * bytes = the length of the resulting SecureVector!ubyte 1172 * Returns: a SecureVector!ubyte containing the encoded BigInt 1173 */ 1174 static SecureVector!ubyte encode1363()(auto const ref BigInt n, size_t bytes) 1175 { 1176 const size_t n_bytes = n.bytes(); 1177 if (n_bytes > bytes) 1178 throw new EncodingError("encode1363: n is too large to encode properly"); 1179 1180 const size_t leading_0s = bytes - n_bytes; 1181 1182 SecureVector!ubyte output = SecureVector!ubyte(bytes); 1183 encode(&output[leading_0s], n, Binary); 1184 return output; 1185 } 1186 1187 /* 1188 * Addition Operator 1189 */ 1190 BigInt opBinary(string op)(auto const ref BigInt y) const 1191 if (op == "+") 1192 { 1193 const BigInt* x = &this; 1194 const size_t x_sw = x.sigWords(), y_sw = y.sigWords(); 1195 1196 BigInt z = BigInt(x.sign(), std.algorithm.max(x_sw, y_sw) + 1); 1197 1198 if ((x.sign() == y.sign())) 1199 bigint_add3(z.mutablePtr(), x.ptr, x_sw, y.ptr, y_sw); 1200 else 1201 { 1202 int relative_size = bigint_cmp(x.ptr, x_sw, y.ptr, y_sw); 1203 1204 if (relative_size < 0) 1205 { 1206 bigint_sub3(z.mutablePtr(), y.ptr, y_sw, x.ptr, x_sw); 1207 z.setSign(y.sign()); 1208 } 1209 else if (relative_size == 0) 1210 z.setSign(BigInt.Positive); 1211 else if (relative_size > 0) 1212 bigint_sub3(z.mutablePtr(), x.ptr, x_sw, y.ptr, y_sw); 1213 } 1214 return z.move(); 1215 } 1216 1217 BigInt opBinary(string op)(in word y) const 1218 if (op == "+") 1219 { 1220 return this + BigInt(y); 1221 } 1222 1223 /* 1224 * Subtraction Operator 1225 */ 1226 BigInt opBinary(string op)(auto const ref BigInt y) const 1227 if (op == "-") 1228 { 1229 const BigInt* x = &this; 1230 const size_t x_sw = x.sigWords(), y_sw = y.sigWords(); 1231 1232 int relative_size = bigint_cmp(x.ptr, x_sw, y.ptr, y_sw); 1233 1234 BigInt z = BigInt(BigInt.Positive, std.algorithm.max(x_sw, y_sw) + 1); 1235 1236 if (relative_size < 0) 1237 { 1238 if (x.sign() == y.sign()) 1239 bigint_sub3(z.mutablePtr(), y.ptr, y_sw, x.ptr, x_sw); 1240 else 1241 bigint_add3(z.mutablePtr(), x.ptr, x_sw, y.ptr, y_sw); 1242 z.setSign(y.reverseSign()); 1243 } 1244 else if (relative_size == 0) 1245 { 1246 if (x.sign() != y.sign()) 1247 bigint_shl2(z.mutablePtr(), x.ptr, x_sw, 0, 1); 1248 } 1249 else if (relative_size > 0) 1250 { 1251 if (x.sign() == y.sign()) 1252 bigint_sub3(z.mutablePtr(), x.ptr, x_sw, y.ptr, y_sw); 1253 else 1254 bigint_add3(z.mutablePtr(), x.ptr, x_sw, y.ptr, y_sw); 1255 z.setSign(x.sign()); 1256 } 1257 return z.move(); 1258 } 1259 1260 1261 BigInt opBinary(string op)(in word y) const 1262 if (op == "-") 1263 { 1264 return this - BigInt(y); 1265 } 1266 1267 /* 1268 * Multiplication Operator 1269 */ 1270 BigInt opBinary(string op)(auto const ref BigInt y) const 1271 if (op == "*") 1272 { 1273 const BigInt* x = &this; 1274 const size_t x_sw = x.sigWords(), y_sw = y.sigWords(); 1275 1276 BigInt z = BigInt(BigInt.Positive, x.length + y.length); 1277 1278 if (x_sw == 1 && y_sw) 1279 bigint_linmul3(z.mutablePtr(), y.ptr, y_sw, x.wordAt(0)); 1280 else if (y_sw == 1 && x_sw) 1281 bigint_linmul3(z.mutablePtr(), x.ptr, x_sw, y.wordAt(0)); 1282 else if (x_sw && y_sw) 1283 { 1284 SecureVector!word workspace = SecureVector!word(z.length); 1285 bigint_mul(z.mutablePtr(), z.length, workspace.ptr, 1286 x.ptr, x.length, x_sw, 1287 y.ptr, y.length, y_sw); 1288 } 1289 1290 if (x_sw && y_sw && x.sign() != y.sign()) 1291 z.flipSign(); 1292 return z.move(); 1293 } 1294 1295 1296 BigInt opBinary(string op)(in word y) const 1297 if (op == "*") 1298 { 1299 return this * BigInt(y); 1300 } 1301 1302 /* 1303 * Division Operator 1304 */ 1305 BigInt opBinary(string op)(auto const ref BigInt y) const 1306 if (op == "/") 1307 { 1308 const BigInt* x = &this; 1309 BigInt q, r; 1310 divide(*x, y, q, r); 1311 return q.move(); 1312 } 1313 1314 1315 BigInt opBinary(string op)(in word y) const 1316 if (op == "/") 1317 { 1318 return this / BigInt(y); 1319 } 1320 1321 /* 1322 * Modulo Operator 1323 */ 1324 BigInt opBinary(string op)(auto const ref BigInt mod) const 1325 if (op == "%") 1326 { 1327 const BigInt* n = &this; 1328 if (mod.isZero()) 1329 throw new BigInt.DivideByZero(); 1330 if (mod.isNegative()) 1331 throw new InvalidArgument("BigInt.operator%: modulus must be > 0"); 1332 if (n.isPositive() && mod.isPositive() && *n < mod) 1333 return n.dup; 1334 1335 BigInt q, r; 1336 divide(*n, mod, q, r); 1337 return r.move(); 1338 } 1339 1340 /* 1341 * Modulo Operator 1342 */ 1343 word opBinary(string op)(word mod) const 1344 if (op == "%") 1345 { 1346 const BigInt* n = &this; 1347 if (mod == 0) 1348 throw new BigInt.DivideByZero(); 1349 1350 if (isPowerOf2(mod)) 1351 return (n.wordAt(0) & (mod - 1)); 1352 1353 word remainder = 0; 1354 1355 for (size_t j = n.sigWords(); j > 0; --j) 1356 remainder = bigint_modop(remainder, n.wordAt(j-1), mod); 1357 1358 if (remainder && n.sign() == BigInt.Negative) 1359 return mod - remainder; 1360 return remainder; 1361 } 1362 1363 /* 1364 * Left Shift Operator 1365 */ 1366 BigInt opBinary(string op)(size_t shift) const 1367 if (op == "<<") 1368 { 1369 const BigInt* x = &this; 1370 if (shift == 0) 1371 return x.dup(); 1372 1373 const size_t shift_words = shift / MP_WORD_BITS, 1374 shift_bits = shift % MP_WORD_BITS; 1375 1376 const size_t x_sw = x.sigWords(); 1377 1378 BigInt y = BigInt(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0)); 1379 bigint_shl2(y.mutablePtr(), x.ptr, x_sw, shift_words, shift_bits); 1380 return y.move(); 1381 } 1382 1383 /* 1384 * Right Shift Operator 1385 */ 1386 BigInt opBinary(string op)(size_t shift) const 1387 if (op == ">>") 1388 { 1389 if (shift == 0) 1390 return this.dup; 1391 if (bits() <= shift) 1392 return BigInt(0); 1393 1394 const size_t shift_words = shift / MP_WORD_BITS, 1395 shift_bits = shift % MP_WORD_BITS, 1396 x_sw = sigWords(); 1397 1398 BigInt y = BigInt(sign(), x_sw - shift_words); 1399 bigint_shr2(y.mutablePtr(), ptr, x_sw, shift_words, shift_bits); 1400 return y.move(); 1401 } 1402 1403 @property BigInt move() { 1404 return BigInt(m_reg, m_signedness, m_sig_words); 1405 } 1406 1407 @property BigInt dup() const { 1408 return BigInt(m_reg.dup(), m_signedness, m_sig_words); 1409 } 1410 private: 1411 1412 SecureVector!word m_reg; 1413 Sign m_signedness = Positive; 1414 size_t m_sig_words = size_t.max; 1415 1416 }