1<?php 2 3/** 4 * Base BigInteger Engine 5 * 6 * PHP version 5 and 7 7 * 8 * @author Jim Wigginton <terrafrost@php.net> 9 * @copyright 2017 Jim Wigginton 10 * @license http://www.opensource.org/licenses/mit-license.html MIT License 11 * @link http://pear.php.net/package/Math_BigInteger 12 */ 13 14namespace phpseclib3\Math\BigInteger\Engines; 15 16use phpseclib3\Common\Functions\Strings; 17use phpseclib3\Crypt\Random; 18use phpseclib3\Exception\BadConfigurationException; 19use phpseclib3\Math\BigInteger; 20 21/** 22 * Base Engine. 23 * 24 * @author Jim Wigginton <terrafrost@php.net> 25 */ 26abstract class Engine implements \JsonSerializable 27{ 28 /* final protected */ const PRIMES = [ 29 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 30 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 31 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 32 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 33 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 34 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 35 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 36 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 37 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 38 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 39 953, 967, 971, 977, 983, 991, 997, 40 ]; 41 42 /** 43 * BigInteger(0) 44 * 45 * @var array<class-string<static>, static> 46 */ 47 protected static $zero = []; 48 49 /** 50 * BigInteger(1) 51 * 52 * @var array<class-string<static>, static> 53 */ 54 protected static $one = []; 55 56 /** 57 * BigInteger(2) 58 * 59 * @var array<class-string<static>, static> 60 */ 61 protected static $two = []; 62 63 /** 64 * Modular Exponentiation Engine 65 * 66 * @var array<class-string<static>, class-string<static>> 67 */ 68 protected static $modexpEngine; 69 70 /** 71 * Engine Validity Flag 72 * 73 * @var array<class-string<static>, bool> 74 */ 75 protected static $isValidEngine; 76 77 /** 78 * Holds the BigInteger's value 79 * 80 * @var \GMP|string|array|int 81 */ 82 protected $value; 83 84 /** 85 * Holds the BigInteger's sign 86 * 87 * @var bool 88 */ 89 protected $is_negative; 90 91 /** 92 * Precision 93 * 94 * @see static::setPrecision() 95 * @var int 96 */ 97 protected $precision = -1; 98 99 /** 100 * Precision Bitmask 101 * 102 * @see static::setPrecision() 103 * @var static|false 104 */ 105 protected $bitmask = false; 106 107 /** 108 * Recurring Modulo Function 109 * 110 * @var callable 111 */ 112 protected $reduce; 113 114 /** 115 * Mode independent value used for serialization. 116 * 117 * @see self::__sleep() 118 * @see self::__wakeup() 119 * @var string 120 */ 121 protected $hex; 122 123 /** 124 * Default constructor 125 * 126 * @param int|numeric-string $x integer Base-10 number or base-$base number if $base set. 127 * @param int $base 128 */ 129 public function __construct($x = 0, $base = 10) 130 { 131 if (!array_key_exists(static::class, static::$zero)) { 132 static::$zero[static::class] = null; // Placeholder to prevent infinite loop. 133 static::$zero[static::class] = new static(0); 134 static::$one[static::class] = new static(1); 135 static::$two[static::class] = new static(2); 136 } 137 138 // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48 139 // '0' is the only value like this per http://php.net/empty 140 if (empty($x) && (abs($base) != 256 || $x !== '0')) { 141 return; 142 } 143 144 switch ($base) { 145 case -256: 146 case 256: 147 if ($base == -256 && (ord($x[0]) & 0x80)) { 148 $this->value = ~$x; 149 $this->is_negative = true; 150 } else { 151 $this->value = $x; 152 $this->is_negative = false; 153 } 154 155 $this->initialize($base); 156 157 if ($this->is_negative) { 158 $temp = $this->add(new static('-1')); 159 $this->value = $temp->value; 160 } 161 break; 162 case -16: 163 case 16: 164 if ($base > 0 && $x[0] == '-') { 165 $this->is_negative = true; 166 $x = substr($x, 1); 167 } 168 169 $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#s', '$1', $x); 170 171 $is_negative = false; 172 if ($base < 0 && hexdec($x[0]) >= 8) { 173 $this->is_negative = $is_negative = true; 174 $x = Strings::bin2hex(~Strings::hex2bin($x)); 175 } 176 177 $this->value = $x; 178 $this->initialize($base); 179 180 if ($is_negative) { 181 $temp = $this->add(new static('-1')); 182 $this->value = $temp->value; 183 } 184 break; 185 case -10: 186 case 10: 187 // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that 188 // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals) 189 // [^-0-9].*: find any non-numeric characters and then any characters that follow that 190 $this->value = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#s', '', $x); 191 if (!strlen($this->value) || $this->value == '-') { 192 $this->value = '0'; 193 } 194 $this->initialize($base); 195 break; 196 case -2: 197 case 2: 198 if ($base > 0 && $x[0] == '-') { 199 $this->is_negative = true; 200 $x = substr($x, 1); 201 } 202 203 $x = preg_replace('#^([01]*).*#s', '$1', $x); 204 205 $temp = new static(Strings::bits2bin($x), 128 * $base); // ie. either -16 or +16 206 $this->value = $temp->value; 207 if ($temp->is_negative) { 208 $this->is_negative = true; 209 } 210 211 break; 212 default: 213 // base not supported, so we'll let $this == 0 214 } 215 } 216 217 /** 218 * Sets engine type. 219 * 220 * Throws an exception if the type is invalid 221 * 222 * @param class-string<Engine> $engine 223 */ 224 public static function setModExpEngine($engine) 225 { 226 $fqengine = '\\phpseclib3\\Math\\BigInteger\\Engines\\' . static::ENGINE_DIR . '\\' . $engine; 227 if (!class_exists($fqengine) || !method_exists($fqengine, 'isValidEngine')) { 228 throw new \InvalidArgumentException("$engine is not a valid engine"); 229 } 230 if (!$fqengine::isValidEngine()) { 231 throw new BadConfigurationException("$engine is not setup correctly on this system"); 232 } 233 static::$modexpEngine[static::class] = $fqengine; 234 } 235 236 /** 237 * Converts a BigInteger to a byte string (eg. base-256). 238 * 239 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're 240 * saved as two's compliment. 241 * @return string 242 */ 243 protected function toBytesHelper() 244 { 245 $comparison = $this->compare(new static()); 246 if ($comparison == 0) { 247 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; 248 } 249 250 $temp = $comparison < 0 ? $this->add(new static(1)) : $this; 251 $bytes = $temp->toBytes(); 252 253 if (!strlen($bytes)) { // eg. if the number we're trying to convert is -1 254 $bytes = chr(0); 255 } 256 257 if (ord($bytes[0]) & 0x80) { 258 $bytes = chr(0) . $bytes; 259 } 260 261 return $comparison < 0 ? ~$bytes : $bytes; 262 } 263 264 /** 265 * Converts a BigInteger to a hex string (eg. base-16). 266 * 267 * @param bool $twos_compliment 268 * @return string 269 */ 270 public function toHex($twos_compliment = false) 271 { 272 return Strings::bin2hex($this->toBytes($twos_compliment)); 273 } 274 275 /** 276 * Converts a BigInteger to a bit string (eg. base-2). 277 * 278 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're 279 * saved as two's compliment. 280 * 281 * @param bool $twos_compliment 282 * @return string 283 */ 284 public function toBits($twos_compliment = false) 285 { 286 $hex = $this->toBytes($twos_compliment); 287 $bits = Strings::bin2bits($hex); 288 289 $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0'); 290 291 if ($twos_compliment && $this->compare(new static()) > 0 && $this->precision <= 0) { 292 return '0' . $result; 293 } 294 295 return $result; 296 } 297 298 /** 299 * Calculates modular inverses. 300 * 301 * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses. 302 * 303 * {@internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information.} 304 * 305 * @param Engine $n 306 * @return static|false 307 */ 308 protected function modInverseHelper(Engine $n) 309 { 310 // $x mod -$n == $x mod $n. 311 $n = $n->abs(); 312 313 if ($this->compare(static::$zero[static::class]) < 0) { 314 $temp = $this->abs(); 315 $temp = $temp->modInverse($n); 316 return $this->normalize($n->subtract($temp)); 317 } 318 319 extract($this->extendedGCD($n)); 320 /** 321 * @var Engine $gcd 322 * @var Engine $x 323 */ 324 325 if (!$gcd->equals(static::$one[static::class])) { 326 return false; 327 } 328 329 $x = $x->compare(static::$zero[static::class]) < 0 ? $x->add($n) : $x; 330 331 return $this->compare(static::$zero[static::class]) < 0 ? $this->normalize($n->subtract($x)) : $this->normalize($x); 332 } 333 334 /** 335 * Serialize 336 * 337 * Will be called, automatically, when serialize() is called on a BigInteger object. 338 * 339 * @return array 340 */ 341 public function __sleep() 342 { 343 $this->hex = $this->toHex(true); 344 $vars = ['hex']; 345 if ($this->precision > 0) { 346 $vars[] = 'precision'; 347 } 348 return $vars; 349 } 350 351 /** 352 * Serialize 353 * 354 * Will be called, automatically, when unserialize() is called on a BigInteger object. 355 * 356 * @return void 357 */ 358 public function __wakeup() 359 { 360 $temp = new static($this->hex, -16); 361 $this->value = $temp->value; 362 $this->is_negative = $temp->is_negative; 363 if ($this->precision > 0) { 364 // recalculate $this->bitmask 365 $this->setPrecision($this->precision); 366 } 367 } 368 369 /** 370 * JSON Serialize 371 * 372 * Will be called, automatically, when json_encode() is called on a BigInteger object. 373 * 374 * @return array{hex: string, precision?: int] 375 */ 376 #[\ReturnTypeWillChange] 377 public function jsonSerialize() 378 { 379 $result = ['hex' => $this->toHex(true)]; 380 if ($this->precision > 0) { 381 $result['precision'] = $this->precision; 382 } 383 return $result; 384 } 385 386 /** 387 * Converts a BigInteger to a base-10 number. 388 * 389 * @return string 390 */ 391 public function __toString() 392 { 393 return $this->toString(); 394 } 395 396 /** 397 * __debugInfo() magic method 398 * 399 * Will be called, automatically, when print_r() or var_dump() are called 400 * 401 * @return array 402 */ 403 public function __debugInfo() 404 { 405 $result = [ 406 'value' => '0x' . $this->toHex(true), 407 'engine' => basename(static::class) 408 ]; 409 return $this->precision > 0 ? $result + ['precision' => $this->precision] : $result; 410 } 411 412 /** 413 * Set Precision 414 * 415 * Some bitwise operations give different results depending on the precision being used. Examples include left 416 * shift, not, and rotates. 417 * 418 * @param int $bits 419 */ 420 public function setPrecision($bits) 421 { 422 if ($bits < 1) { 423 $this->precision = -1; 424 $this->bitmask = false; 425 426 return; 427 } 428 $this->precision = $bits; 429 $this->bitmask = static::setBitmask($bits); 430 431 $temp = $this->normalize($this); 432 $this->value = $temp->value; 433 } 434 435 /** 436 * Get Precision 437 * 438 * Returns the precision if it exists, -1 if it doesn't 439 * 440 * @return int 441 */ 442 public function getPrecision() 443 { 444 return $this->precision; 445 } 446 447 /** 448 * Set Bitmask 449 * @return static 450 * @param int $bits 451 * @see self::setPrecision() 452 */ 453 protected static function setBitmask($bits) 454 { 455 return new static(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256); 456 } 457 458 /** 459 * Logical Not 460 * 461 * @return Engine|string 462 */ 463 public function bitwise_not() 464 { 465 // calculuate "not" without regard to $this->precision 466 // (will always result in a smaller number. ie. ~1 isn't 1111 1110 - it's 0) 467 $temp = $this->toBytes(); 468 if ($temp == '') { 469 return $this->normalize(static::$zero[static::class]); 470 } 471 $pre_msb = decbin(ord($temp[0])); 472 $temp = ~$temp; 473 $msb = decbin(ord($temp[0])); 474 if (strlen($msb) == 8) { 475 $msb = substr($msb, strpos($msb, '0')); 476 } 477 $temp[0] = chr(bindec($msb)); 478 479 // see if we need to add extra leading 1's 480 $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8; 481 $new_bits = $this->precision - $current_bits; 482 if ($new_bits <= 0) { 483 return $this->normalize(new static($temp, 256)); 484 } 485 486 // generate as many leading 1's as we need to. 487 $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3); 488 489 self::base256_lshift($leading_ones, $current_bits); 490 491 $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT); 492 493 return $this->normalize(new static($leading_ones | $temp, 256)); 494 } 495 496 /** 497 * Logical Left Shift 498 * 499 * Shifts binary strings $shift bits, essentially multiplying by 2**$shift. 500 * 501 * @param string $x 502 * @param int $shift 503 * @return void 504 */ 505 protected static function base256_lshift(&$x, $shift) 506 { 507 if ($shift == 0) { 508 return; 509 } 510 511 $num_bytes = $shift >> 3; // eg. floor($shift/8) 512 $shift &= 7; // eg. $shift % 8 513 514 $carry = 0; 515 for ($i = strlen($x) - 1; $i >= 0; --$i) { 516 $temp = ord($x[$i]) << $shift | $carry; 517 $x[$i] = chr($temp); 518 $carry = $temp >> 8; 519 } 520 $carry = ($carry != 0) ? chr($carry) : ''; 521 $x = $carry . $x . str_repeat(chr(0), $num_bytes); 522 } 523 524 /** 525 * Logical Left Rotate 526 * 527 * Instead of the top x bits being dropped they're appended to the shifted bit string. 528 * 529 * @param int $shift 530 * @return Engine 531 */ 532 public function bitwise_leftRotate($shift) 533 { 534 $bits = $this->toBytes(); 535 536 if ($this->precision > 0) { 537 $precision = $this->precision; 538 if (static::FAST_BITWISE) { 539 $mask = $this->bitmask->toBytes(); 540 } else { 541 $mask = $this->bitmask->subtract(new static(1)); 542 $mask = $mask->toBytes(); 543 } 544 } else { 545 $temp = ord($bits[0]); 546 for ($i = 0; $temp >> $i; ++$i) { 547 } 548 $precision = 8 * strlen($bits) - 8 + $i; 549 $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3); 550 } 551 552 if ($shift < 0) { 553 $shift += $precision; 554 } 555 $shift %= $precision; 556 557 if (!$shift) { 558 return clone $this; 559 } 560 561 $left = $this->bitwise_leftShift($shift); 562 $left = $left->bitwise_and(new static($mask, 256)); 563 $right = $this->bitwise_rightShift($precision - $shift); 564 $result = static::FAST_BITWISE ? $left->bitwise_or($right) : $left->add($right); 565 return $this->normalize($result); 566 } 567 568 /** 569 * Logical Right Rotate 570 * 571 * Instead of the bottom x bits being dropped they're prepended to the shifted bit string. 572 * 573 * @param int $shift 574 * @return Engine 575 */ 576 public function bitwise_rightRotate($shift) 577 { 578 return $this->bitwise_leftRotate(-$shift); 579 } 580 581 /** 582 * Returns the smallest and largest n-bit number 583 * 584 * @param int $bits 585 * @return array{min: static, max: static} 586 */ 587 public static function minMaxBits($bits) 588 { 589 $bytes = $bits >> 3; 590 $min = str_repeat(chr(0), $bytes); 591 $max = str_repeat(chr(0xFF), $bytes); 592 $msb = $bits & 7; 593 if ($msb) { 594 $min = chr(1 << ($msb - 1)) . $min; 595 $max = chr((1 << $msb) - 1) . $max; 596 } else { 597 $min[0] = chr(0x80); 598 } 599 return [ 600 'min' => new static($min, 256), 601 'max' => new static($max, 256) 602 ]; 603 } 604 605 /** 606 * Return the size of a BigInteger in bits 607 * 608 * @return int 609 */ 610 public function getLength() 611 { 612 return strlen($this->toBits()); 613 } 614 615 /** 616 * Return the size of a BigInteger in bytes 617 * 618 * @return int 619 */ 620 public function getLengthInBytes() 621 { 622 return (int) ceil($this->getLength() / 8); 623 } 624 625 /** 626 * Performs some pre-processing for powMod 627 * 628 * @param Engine $e 629 * @param Engine $n 630 * @return static|false 631 */ 632 protected function powModOuter(Engine $e, Engine $n) 633 { 634 $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs(); 635 636 if ($e->compare(new static()) < 0) { 637 $e = $e->abs(); 638 639 $temp = $this->modInverse($n); 640 if ($temp === false) { 641 return false; 642 } 643 644 return $this->normalize($temp->powModInner($e, $n)); 645 } 646 647 if ($this->compare($n) > 0) { 648 list(, $temp) = $this->divide($n); 649 return $temp->powModInner($e, $n); 650 } 651 652 return $this->powModInner($e, $n); 653 } 654 655 /** 656 * Sliding Window k-ary Modular Exponentiation 657 * 658 * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} / 659 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}. In a departure from those algorithims, 660 * however, this function performs a modular reduction after every multiplication and squaring operation. 661 * As such, this function has the same preconditions that the reductions being used do. 662 * 663 * @template T of Engine 664 * @param Engine $x 665 * @param Engine $e 666 * @param Engine $n 667 * @param class-string<T> $class 668 * @return T 669 */ 670 protected static function slidingWindow(Engine $x, Engine $e, Engine $n, $class) 671 { 672 static $window_ranges = [7, 25, 81, 241, 673, 1793]; // from BigInteger.java's oddModPow function 673 //static $window_ranges = [0, 7, 36, 140, 450, 1303, 3529]; // from MPM 7.3.1 674 675 $e_bits = $e->toBits(); 676 $e_length = strlen($e_bits); 677 678 // calculate the appropriate window size. 679 // $window_size == 3 if $window_ranges is between 25 and 81, for example. 680 for ($i = 0, $window_size = 1; $i < count($window_ranges) && $e_length > $window_ranges[$i]; ++$window_size, ++$i) { 681 } 682 683 $n_value = $n->value; 684 685 if (method_exists(static::class, 'generateCustomReduction')) { 686 static::generateCustomReduction($n, $class); 687 } 688 689 // precompute $this^0 through $this^$window_size 690 $powers = []; 691 $powers[1] = static::prepareReduce($x->value, $n_value, $class); 692 $powers[2] = static::squareReduce($powers[1], $n_value, $class); 693 694 // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end 695 // in a 1. ie. it's supposed to be odd. 696 $temp = 1 << ($window_size - 1); 697 for ($i = 1; $i < $temp; ++$i) { 698 $i2 = $i << 1; 699 $powers[$i2 + 1] = static::multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $class); 700 } 701 702 $result = new $class(1); 703 $result = static::prepareReduce($result->value, $n_value, $class); 704 705 for ($i = 0; $i < $e_length;) { 706 if (!$e_bits[$i]) { 707 $result = static::squareReduce($result, $n_value, $class); 708 ++$i; 709 } else { 710 for ($j = $window_size - 1; $j > 0; --$j) { 711 if (!empty($e_bits[$i + $j])) { 712 break; 713 } 714 } 715 716 // eg. the length of substr($e_bits, $i, $j + 1) 717 for ($k = 0; $k <= $j; ++$k) { 718 $result = static::squareReduce($result, $n_value, $class); 719 } 720 721 $result = static::multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $class); 722 723 $i += $j + 1; 724 } 725 } 726 727 $temp = new $class(); 728 $temp->value = static::reduce($result, $n_value, $class); 729 730 return $temp; 731 } 732 733 /** 734 * Generates a random number of a certain size 735 * 736 * Bit length is equal to $size 737 * 738 * @param int $size 739 * @return Engine 740 */ 741 public static function random($size) 742 { 743 extract(static::minMaxBits($size)); 744 /** 745 * @var BigInteger $min 746 * @var BigInteger $max 747 */ 748 return static::randomRange($min, $max); 749 } 750 751 /** 752 * Generates a random prime number of a certain size 753 * 754 * Bit length is equal to $size 755 * 756 * @param int $size 757 * @return Engine 758 */ 759 public static function randomPrime($size) 760 { 761 extract(static::minMaxBits($size)); 762 /** 763 * @var static $min 764 * @var static $max 765 */ 766 return static::randomRangePrime($min, $max); 767 } 768 769 /** 770 * Performs some pre-processing for randomRangePrime 771 * 772 * @param Engine $min 773 * @param Engine $max 774 * @return static|false 775 */ 776 protected static function randomRangePrimeOuter(Engine $min, Engine $max) 777 { 778 $compare = $max->compare($min); 779 780 if (!$compare) { 781 return $min->isPrime() ? $min : false; 782 } elseif ($compare < 0) { 783 // if $min is bigger then $max, swap $min and $max 784 $temp = $max; 785 $max = $min; 786 $min = $temp; 787 } 788 789 $length = $max->getLength(); 790 if ($length > 8196) { 791 throw new \RuntimeException("Generation of random prime numbers larger than 8196 has been disabled ($length)"); 792 } 793 794 $x = static::randomRange($min, $max); 795 796 return static::randomRangePrimeInner($x, $min, $max); 797 } 798 799 /** 800 * Generate a random number between a range 801 * 802 * Returns a random number between $min and $max where $min and $max 803 * can be defined using one of the two methods: 804 * 805 * BigInteger::randomRange($min, $max) 806 * BigInteger::randomRange($max, $min) 807 * 808 * @param Engine $min 809 * @param Engine $max 810 * @return Engine 811 */ 812 protected static function randomRangeHelper(Engine $min, Engine $max) 813 { 814 $compare = $max->compare($min); 815 816 if (!$compare) { 817 return $min; 818 } elseif ($compare < 0) { 819 // if $min is bigger then $max, swap $min and $max 820 $temp = $max; 821 $max = $min; 822 $min = $temp; 823 } 824 825 if (!isset(static::$one[static::class])) { 826 static::$one[static::class] = new static(1); 827 } 828 829 $max = $max->subtract($min->subtract(static::$one[static::class])); 830 831 $size = strlen(ltrim($max->toBytes(), chr(0))); 832 833 /* 834 doing $random % $max doesn't work because some numbers will be more likely to occur than others. 835 eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145 836 would produce 5 whereas the only value of random that could produce 139 would be 139. ie. 837 not all numbers would be equally likely. some would be more likely than others. 838 839 creating a whole new random number until you find one that is within the range doesn't work 840 because, for sufficiently small ranges, the likelihood that you'd get a number within that range 841 would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability 842 would be pretty high that $random would be greater than $max. 843 844 phpseclib works around this using the technique described here: 845 846 http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string 847 */ 848 $random_max = new static(chr(1) . str_repeat("\0", $size), 256); 849 $random = new static(Random::string($size), 256); 850 851 list($max_multiple) = $random_max->divide($max); 852 $max_multiple = $max_multiple->multiply($max); 853 854 while ($random->compare($max_multiple) >= 0) { 855 $random = $random->subtract($max_multiple); 856 $random_max = $random_max->subtract($max_multiple); 857 $random = $random->bitwise_leftShift(8); 858 $random = $random->add(new static(Random::string(1), 256)); 859 $random_max = $random_max->bitwise_leftShift(8); 860 list($max_multiple) = $random_max->divide($max); 861 $max_multiple = $max_multiple->multiply($max); 862 } 863 list(, $random) = $random->divide($max); 864 865 return $random->add($min); 866 } 867 868 /** 869 * Performs some post-processing for randomRangePrime 870 * 871 * @param Engine $x 872 * @param Engine $min 873 * @param Engine $max 874 * @return static|false 875 */ 876 protected static function randomRangePrimeInner(Engine $x, Engine $min, Engine $max) 877 { 878 if (!isset(static::$two[static::class])) { 879 static::$two[static::class] = new static('2'); 880 } 881 882 $x->make_odd(); 883 if ($x->compare($max) > 0) { 884 // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range 885 if ($min->equals($max)) { 886 return false; 887 } 888 $x = clone $min; 889 $x->make_odd(); 890 } 891 892 $initial_x = clone $x; 893 894 while (true) { 895 if ($x->isPrime()) { 896 return $x; 897 } 898 899 $x = $x->add(static::$two[static::class]); 900 901 if ($x->compare($max) > 0) { 902 $x = clone $min; 903 if ($x->equals(static::$two[static::class])) { 904 return $x; 905 } 906 $x->make_odd(); 907 } 908 909 if ($x->equals($initial_x)) { 910 return false; 911 } 912 } 913 } 914 915 /** 916 * Sets the $t parameter for primality testing 917 * 918 * @return int 919 */ 920 protected function setupIsPrime() 921 { 922 $length = $this->getLengthInBytes(); 923 924 // see HAC 4.49 "Note (controlling the error probability)" 925 // @codingStandardsIgnoreStart 926 if ($length >= 163) { $t = 2; } // floor(1300 / 8) 927 else if ($length >= 106) { $t = 3; } // floor( 850 / 8) 928 else if ($length >= 81 ) { $t = 4; } // floor( 650 / 8) 929 else if ($length >= 68 ) { $t = 5; } // floor( 550 / 8) 930 else if ($length >= 56 ) { $t = 6; } // floor( 450 / 8) 931 else if ($length >= 50 ) { $t = 7; } // floor( 400 / 8) 932 else if ($length >= 43 ) { $t = 8; } // floor( 350 / 8) 933 else if ($length >= 37 ) { $t = 9; } // floor( 300 / 8) 934 else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8) 935 else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8) 936 else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8) 937 else { $t = 27; } 938 // @codingStandardsIgnoreEnd 939 940 return $t; 941 } 942 943 /** 944 * Tests Primality 945 * 946 * Uses the {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}. 947 * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24} for more info. 948 * 949 * @param int $t 950 * @return bool 951 */ 952 protected function testPrimality($t) 953 { 954 if (!$this->testSmallPrimes()) { 955 return false; 956 } 957 958 $n = clone $this; 959 $n_1 = $n->subtract(static::$one[static::class]); 960 $n_2 = $n->subtract(static::$two[static::class]); 961 962 $r = clone $n_1; 963 $s = static::scan1divide($r); 964 965 for ($i = 0; $i < $t; ++$i) { 966 $a = static::randomRange(static::$two[static::class], $n_2); 967 $y = $a->modPow($r, $n); 968 969 if (!$y->equals(static::$one[static::class]) && !$y->equals($n_1)) { 970 for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) { 971 $y = $y->modPow(static::$two[static::class], $n); 972 if ($y->equals(static::$one[static::class])) { 973 return false; 974 } 975 } 976 977 if (!$y->equals($n_1)) { 978 return false; 979 } 980 } 981 } 982 983 return true; 984 } 985 986 /** 987 * Checks a numer to see if it's prime 988 * 989 * Assuming the $t parameter is not set, this function has an error rate of 2**-80. The main motivation for the 990 * $t parameter is distributability. BigInteger::randomPrime() can be distributed across multiple pageloads 991 * on a website instead of just one. 992 * 993 * @param int|bool $t 994 * @return bool 995 */ 996 public function isPrime($t = false) 997 { 998 // OpenSSL limits RSA keys to 16384 bits. The length of an RSA key is equal to the length of the modulo, which is 999 // produced by multiplying the primes p and q by one another. The largest number two 8196 bit primes can produce is 1000 // a 16384 bit number so, basically, 8196 bit primes are the largest OpenSSL will generate and if that's the largest 1001 // that it'll generate it also stands to reason that that's the largest you'll be able to test primality on 1002 $length = $this->getLength(); 1003 if ($length > 8196) { 1004 throw new \RuntimeException("Primality testing is not supported for numbers larger than 8196 bits ($length)"); 1005 } 1006 1007 if (!$t) { 1008 $t = $this->setupIsPrime(); 1009 } 1010 return $this->testPrimality($t); 1011 } 1012 1013 /** 1014 * Performs a few preliminary checks on root 1015 * 1016 * @param int $n 1017 * @return Engine 1018 */ 1019 protected function rootHelper($n) 1020 { 1021 if ($n < 1) { 1022 return clone static::$zero[static::class]; 1023 } // we want positive exponents 1024 if ($this->compare(static::$one[static::class]) < 0) { 1025 return clone static::$zero[static::class]; 1026 } // we want positive numbers 1027 if ($this->compare(static::$two[static::class]) < 0) { 1028 return clone static::$one[static::class]; 1029 } // n-th root of 1 or 2 is 1 1030 1031 return $this->rootInner($n); 1032 } 1033 1034 /** 1035 * Calculates the nth root of a biginteger. 1036 * 1037 * Returns the nth root of a positive biginteger, where n defaults to 2 1038 * 1039 * {@internal This function is based off of {@link http://mathforum.org/library/drmath/view/52605.html this page} and {@link http://stackoverflow.com/questions/11242920/calculating-nth-root-with-bcmath-in-php this stackoverflow question}.} 1040 * 1041 * @param int $n 1042 * @return Engine 1043 */ 1044 protected function rootInner($n) 1045 { 1046 $n = new static($n); 1047 1048 // g is our guess number 1049 $g = static::$two[static::class]; 1050 // while (g^n < num) g=g*2 1051 while ($g->pow($n)->compare($this) < 0) { 1052 $g = $g->multiply(static::$two[static::class]); 1053 } 1054 // if (g^n==num) num is a power of 2, we're lucky, end of job 1055 // == 0 bccomp(bcpow($g, $n), $n->value)==0 1056 if ($g->pow($n)->equals($this) > 0) { 1057 $root = $g; 1058 return $this->normalize($root); 1059 } 1060 1061 // if we're here num wasn't a power of 2 :( 1062 $og = $g; // og means original guess and here is our upper bound 1063 $g = $g->divide(static::$two[static::class])[0]; // g is set to be our lower bound 1064 $step = $og->subtract($g)->divide(static::$two[static::class])[0]; // step is the half of upper bound - lower bound 1065 $g = $g->add($step); // we start at lower bound + step , basically in the middle of our interval 1066 1067 // while step>1 1068 1069 while ($step->compare(static::$one[static::class]) == 1) { 1070 $guess = $g->pow($n); 1071 $step = $step->divide(static::$two[static::class])[0]; 1072 $comp = $guess->compare($this); // compare our guess with real number 1073 switch ($comp) { 1074 case -1: // if guess is lower we add the new step 1075 $g = $g->add($step); 1076 break; 1077 case 1: // if guess is higher we sub the new step 1078 $g = $g->subtract($step); 1079 break; 1080 case 0: // if guess is exactly the num we're done, we return the value 1081 $root = $g; 1082 break 2; 1083 } 1084 } 1085 1086 if ($comp == 1) { 1087 $g = $g->subtract($step); 1088 } 1089 1090 // whatever happened, g is the closest guess we can make so return it 1091 $root = $g; 1092 1093 return $this->normalize($root); 1094 } 1095 1096 /** 1097 * Calculates the nth root of a biginteger. 1098 * 1099 * @param int $n 1100 * @return Engine 1101 */ 1102 public function root($n = 2) 1103 { 1104 return $this->rootHelper($n); 1105 } 1106 1107 /** 1108 * Return the minimum BigInteger between an arbitrary number of BigIntegers. 1109 * 1110 * @param array $nums 1111 * @return Engine 1112 */ 1113 protected static function minHelper(array $nums) 1114 { 1115 if (count($nums) == 1) { 1116 return $nums[0]; 1117 } 1118 $min = $nums[0]; 1119 for ($i = 1; $i < count($nums); $i++) { 1120 $min = $min->compare($nums[$i]) > 0 ? $nums[$i] : $min; 1121 } 1122 return $min; 1123 } 1124 1125 /** 1126 * Return the minimum BigInteger between an arbitrary number of BigIntegers. 1127 * 1128 * @param array $nums 1129 * @return Engine 1130 */ 1131 protected static function maxHelper(array $nums) 1132 { 1133 if (count($nums) == 1) { 1134 return $nums[0]; 1135 } 1136 $max = $nums[0]; 1137 for ($i = 1; $i < count($nums); $i++) { 1138 $max = $max->compare($nums[$i]) < 0 ? $nums[$i] : $max; 1139 } 1140 return $max; 1141 } 1142 1143 /** 1144 * Create Recurring Modulo Function 1145 * 1146 * Sometimes it may be desirable to do repeated modulos with the same number outside of 1147 * modular exponentiation 1148 * 1149 * @return callable 1150 */ 1151 public function createRecurringModuloFunction() 1152 { 1153 $class = static::class; 1154 1155 $fqengine = !method_exists(static::$modexpEngine[static::class], 'reduce') ? 1156 '\\phpseclib3\\Math\\BigInteger\\Engines\\' . static::ENGINE_DIR . '\\DefaultEngine' : 1157 static::$modexpEngine[static::class]; 1158 if (method_exists($fqengine, 'generateCustomReduction')) { 1159 $func = $fqengine::generateCustomReduction($this, static::class); 1160 return eval('return function(' . static::class . ' $x) use ($func, $class) { 1161 $r = new $class(); 1162 $r->value = $func($x->value); 1163 return $r; 1164 };'); 1165 } 1166 $n = $this->value; 1167 return eval('return function(' . static::class . ' $x) use ($n, $fqengine, $class) { 1168 $r = new $class(); 1169 $r->value = $fqengine::reduce($x->value, $n, $class); 1170 return $r; 1171 };'); 1172 } 1173 1174 /** 1175 * Calculates the greatest common divisor and Bezout's identity. 1176 * 1177 * @param Engine $n 1178 * @return array{gcd: Engine, x: Engine, y: Engine} 1179 */ 1180 protected function extendedGCDHelper(Engine $n) 1181 { 1182 $u = clone $this; 1183 $v = clone $n; 1184 1185 $one = new static(1); 1186 $zero = new static(); 1187 1188 $a = clone $one; 1189 $b = clone $zero; 1190 $c = clone $zero; 1191 $d = clone $one; 1192 1193 while (!$v->equals($zero)) { 1194 list($q) = $u->divide($v); 1195 1196 $temp = $u; 1197 $u = $v; 1198 $v = $temp->subtract($v->multiply($q)); 1199 1200 $temp = $a; 1201 $a = $c; 1202 $c = $temp->subtract($a->multiply($q)); 1203 1204 $temp = $b; 1205 $b = $d; 1206 $d = $temp->subtract($b->multiply($q)); 1207 } 1208 1209 return [ 1210 'gcd' => $u, 1211 'x' => $a, 1212 'y' => $b 1213 ]; 1214 } 1215 1216 /** 1217 * Bitwise Split 1218 * 1219 * Splits BigInteger's into chunks of $split bits 1220 * 1221 * @param int $split 1222 * @return Engine[] 1223 */ 1224 public function bitwise_split($split) 1225 { 1226 if ($split < 1) { 1227 throw new \RuntimeException('Offset must be greater than 1'); 1228 } 1229 1230 $mask = static::$one[static::class]->bitwise_leftShift($split)->subtract(static::$one[static::class]); 1231 1232 $num = clone $this; 1233 1234 $vals = []; 1235 while (!$num->equals(static::$zero[static::class])) { 1236 $vals[] = $num->bitwise_and($mask); 1237 $num = $num->bitwise_rightShift($split); 1238 } 1239 1240 return array_reverse($vals); 1241 } 1242 1243 /** 1244 * Logical And 1245 * 1246 * @param Engine $x 1247 * @return Engine 1248 */ 1249 protected function bitwiseAndHelper(Engine $x) 1250 { 1251 $left = $this->toBytes(true); 1252 $right = $x->toBytes(true); 1253 1254 $length = max(strlen($left), strlen($right)); 1255 1256 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); 1257 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); 1258 1259 return $this->normalize(new static($left & $right, -256)); 1260 } 1261 1262 /** 1263 * Logical Or 1264 * 1265 * @param Engine $x 1266 * @return Engine 1267 */ 1268 protected function bitwiseOrHelper(Engine $x) 1269 { 1270 $left = $this->toBytes(true); 1271 $right = $x->toBytes(true); 1272 1273 $length = max(strlen($left), strlen($right)); 1274 1275 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); 1276 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); 1277 1278 return $this->normalize(new static($left | $right, -256)); 1279 } 1280 1281 /** 1282 * Logical Exclusive Or 1283 * 1284 * @param Engine $x 1285 * @return Engine 1286 */ 1287 protected function bitwiseXorHelper(Engine $x) 1288 { 1289 $left = $this->toBytes(true); 1290 $right = $x->toBytes(true); 1291 1292 $length = max(strlen($left), strlen($right)); 1293 1294 1295 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); 1296 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); 1297 return $this->normalize(new static($left ^ $right, -256)); 1298 } 1299} 1300