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