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 $extended = $this->extendedGCD($n); 320 $gcd = $extended['gcd']; 321 $x = $extended['x']; 322 323 if (!$gcd->equals(static::$one[static::class])) { 324 return false; 325 } 326 327 $x = $x->compare(static::$zero[static::class]) < 0 ? $x->add($n) : $x; 328 329 return $this->compare(static::$zero[static::class]) < 0 ? $this->normalize($n->subtract($x)) : $this->normalize($x); 330 } 331 332 /** 333 * Serialize 334 * 335 * Will be called, automatically, when serialize() is called on a BigInteger object. 336 * 337 * @return array 338 */ 339 public function __sleep() 340 { 341 $this->hex = $this->toHex(true); 342 $vars = ['hex']; 343 if ($this->precision > 0) { 344 $vars[] = 'precision'; 345 } 346 return $vars; 347 } 348 349 /** 350 * Serialize 351 * 352 * Will be called, automatically, when unserialize() is called on a BigInteger object. 353 * 354 * @return void 355 */ 356 public function __wakeup() 357 { 358 $temp = new static($this->hex, -16); 359 $this->value = $temp->value; 360 $this->is_negative = $temp->is_negative; 361 if ($this->precision > 0) { 362 // recalculate $this->bitmask 363 $this->setPrecision($this->precision); 364 } 365 } 366 367 /** 368 * __serialize() magic method 369 * 370 * __sleep / __wakeup were depreciated in PHP 8.5 371 * Will be called, automatically, when serialize() is called on a Math_BigInteger object. 372 * 373 * @see self::__unserialize() 374 * @access public 375 */ 376 public function __serialize() 377 { 378 $result = ['hex' => $this->toHex(true)]; 379 if ($this->precision > 0) { 380 $result['precision'] = $this->precision; 381 } 382 return $result; 383 } 384 385 /** 386 * __unserialize() magic method 387 * 388 * __sleep / __wakeup were depreciated in PHP 8.5 389 * Will be called, automatically, when unserialize() is called on a Math_BigInteger object. 390 * 391 * @see self::__serialize() 392 * @access public 393 */ 394 public function __unserialize(array $data) 395 { 396 $temp = new static($data['hex'], -16); 397 $this->value = $temp->value; 398 $this->is_negative = $temp->is_negative; 399 if (isset($data['precision']) && $data['precision'] > 0) { 400 // recalculate $this->bitmask 401 $this->setPrecision($data['precision']); 402 } 403 } 404 405 /** 406 * JSON Serialize 407 * 408 * Will be called, automatically, when json_encode() is called on a BigInteger object. 409 * 410 * @return array{hex: string, precision?: int] 411 */ 412 #[\ReturnTypeWillChange] 413 public function jsonSerialize() 414 { 415 $result = ['hex' => $this->toHex(true)]; 416 if ($this->precision > 0) { 417 $result['precision'] = $this->precision; 418 } 419 return $result; 420 } 421 422 /** 423 * Converts a BigInteger to a base-10 number. 424 * 425 * @return string 426 */ 427 public function __toString() 428 { 429 return $this->toString(); 430 } 431 432 /** 433 * __debugInfo() magic method 434 * 435 * Will be called, automatically, when print_r() or var_dump() are called 436 * 437 * @return array 438 */ 439 public function __debugInfo() 440 { 441 $result = [ 442 'value' => '0x' . $this->toHex(true), 443 'engine' => basename(static::class) 444 ]; 445 return $this->precision > 0 ? $result + ['precision' => $this->precision] : $result; 446 } 447 448 /** 449 * Set Precision 450 * 451 * Some bitwise operations give different results depending on the precision being used. Examples include left 452 * shift, not, and rotates. 453 * 454 * @param int $bits 455 */ 456 public function setPrecision($bits) 457 { 458 if ($bits < 1) { 459 $this->precision = -1; 460 $this->bitmask = false; 461 462 return; 463 } 464 $this->precision = $bits; 465 $this->bitmask = static::setBitmask($bits); 466 467 $temp = $this->normalize($this); 468 $this->value = $temp->value; 469 } 470 471 /** 472 * Get Precision 473 * 474 * Returns the precision if it exists, -1 if it doesn't 475 * 476 * @return int 477 */ 478 public function getPrecision() 479 { 480 return $this->precision; 481 } 482 483 /** 484 * Set Bitmask 485 * @return static 486 * @param int $bits 487 * @see self::setPrecision() 488 */ 489 protected static function setBitmask($bits) 490 { 491 return new static(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256); 492 } 493 494 /** 495 * Logical Not 496 * 497 * @return Engine|string 498 */ 499 public function bitwise_not() 500 { 501 // calculuate "not" without regard to $this->precision 502 // (will always result in a smaller number. ie. ~1 isn't 1111 1110 - it's 0) 503 $temp = $this->toBytes(); 504 if ($temp == '') { 505 return $this->normalize(static::$zero[static::class]); 506 } 507 $pre_msb = decbin(ord($temp[0])); 508 $temp = ~$temp; 509 $msb = decbin(ord($temp[0])); 510 if (strlen($msb) == 8) { 511 $msb = substr($msb, strpos($msb, '0')); 512 } 513 $temp[0] = chr(bindec($msb)); 514 515 // see if we need to add extra leading 1's 516 $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8; 517 $new_bits = $this->precision - $current_bits; 518 if ($new_bits <= 0) { 519 return $this->normalize(new static($temp, 256)); 520 } 521 522 // generate as many leading 1's as we need to. 523 $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3); 524 525 self::base256_lshift($leading_ones, $current_bits); 526 527 $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT); 528 529 return $this->normalize(new static($leading_ones | $temp, 256)); 530 } 531 532 /** 533 * Logical Left Shift 534 * 535 * Shifts binary strings $shift bits, essentially multiplying by 2**$shift. 536 * 537 * @param string $x 538 * @param int $shift 539 * @return void 540 */ 541 protected static function base256_lshift(&$x, $shift) 542 { 543 if ($shift == 0) { 544 return; 545 } 546 547 $num_bytes = $shift >> 3; // eg. floor($shift/8) 548 $shift &= 7; // eg. $shift % 8 549 550 $carry = 0; 551 for ($i = strlen($x) - 1; $i >= 0; --$i) { 552 $temp = (ord($x[$i]) << $shift) | $carry; 553 $x[$i] = chr($temp & 0xFF); 554 $carry = $temp >> 8; 555 } 556 $carry = ($carry != 0) ? chr($carry) : ''; 557 $x = $carry . $x . str_repeat(chr(0), $num_bytes); 558 } 559 560 /** 561 * Logical Left Rotate 562 * 563 * Instead of the top x bits being dropped they're appended to the shifted bit string. 564 * 565 * @param int $shift 566 * @return Engine 567 */ 568 public function bitwise_leftRotate($shift) 569 { 570 $bits = $this->toBytes(); 571 572 if ($this->precision > 0) { 573 $precision = $this->precision; 574 if (static::FAST_BITWISE) { 575 $mask = $this->bitmask->toBytes(); 576 } else { 577 $mask = $this->bitmask->subtract(new static(1)); 578 $mask = $mask->toBytes(); 579 } 580 } else { 581 $temp = ord($bits[0]); 582 for ($i = 0; $temp >> $i; ++$i) { 583 } 584 $precision = 8 * strlen($bits) - 8 + $i; 585 $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3); 586 } 587 588 if ($shift < 0) { 589 $shift += $precision; 590 } 591 $shift %= $precision; 592 593 if (!$shift) { 594 return clone $this; 595 } 596 597 $left = $this->bitwise_leftShift($shift); 598 $left = $left->bitwise_and(new static($mask, 256)); 599 $right = $this->bitwise_rightShift($precision - $shift); 600 $result = static::FAST_BITWISE ? $left->bitwise_or($right) : $left->add($right); 601 return $this->normalize($result); 602 } 603 604 /** 605 * Logical Right Rotate 606 * 607 * Instead of the bottom x bits being dropped they're prepended to the shifted bit string. 608 * 609 * @param int $shift 610 * @return Engine 611 */ 612 public function bitwise_rightRotate($shift) 613 { 614 return $this->bitwise_leftRotate(-$shift); 615 } 616 617 /** 618 * Returns the smallest and largest n-bit number 619 * 620 * @param int $bits 621 * @return array{min: static, max: static} 622 */ 623 public static function minMaxBits($bits) 624 { 625 $bytes = $bits >> 3; 626 $min = str_repeat(chr(0), $bytes); 627 $max = str_repeat(chr(0xFF), $bytes); 628 $msb = $bits & 7; 629 if ($msb) { 630 $min = chr(1 << ($msb - 1)) . $min; 631 $max = chr((1 << $msb) - 1) . $max; 632 } else { 633 $min[0] = chr(0x80); 634 } 635 return [ 636 'min' => new static($min, 256), 637 'max' => new static($max, 256) 638 ]; 639 } 640 641 /** 642 * Return the size of a BigInteger in bits 643 * 644 * @return int 645 */ 646 public function getLength() 647 { 648 return strlen($this->toBits()); 649 } 650 651 /** 652 * Return the size of a BigInteger in bytes 653 * 654 * @return int 655 */ 656 public function getLengthInBytes() 657 { 658 return (int) ceil($this->getLength() / 8); 659 } 660 661 /** 662 * Performs some pre-processing for powMod 663 * 664 * @param Engine $e 665 * @param Engine $n 666 * @return static|false 667 */ 668 protected function powModOuter(Engine $e, Engine $n) 669 { 670 $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs(); 671 672 if ($e->compare(new static()) < 0) { 673 $e = $e->abs(); 674 675 $temp = $this->modInverse($n); 676 if ($temp === false) { 677 return false; 678 } 679 680 return $this->normalize($temp->powModInner($e, $n)); 681 } 682 683 if ($this->compare($n) > 0 || $this->isNegative()) { 684 list(, $temp) = $this->divide($n); 685 return $temp->powModInner($e, $n); 686 } 687 688 return $this->powModInner($e, $n); 689 } 690 691 /** 692 * Sliding Window k-ary Modular Exponentiation 693 * 694 * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} / 695 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}. In a departure from those algorithims, 696 * however, this function performs a modular reduction after every multiplication and squaring operation. 697 * As such, this function has the same preconditions that the reductions being used do. 698 * 699 * @template T of Engine 700 * @param Engine $x 701 * @param Engine $e 702 * @param Engine $n 703 * @param class-string<T> $class 704 * @return T 705 */ 706 protected static function slidingWindow(Engine $x, Engine $e, Engine $n, $class) 707 { 708 static $window_ranges = [7, 25, 81, 241, 673, 1793]; // from BigInteger.java's oddModPow function 709 //static $window_ranges = [0, 7, 36, 140, 450, 1303, 3529]; // from MPM 7.3.1 710 711 $e_bits = $e->toBits(); 712 $e_length = strlen($e_bits); 713 714 // calculate the appropriate window size. 715 // $window_size == 3 if $window_ranges is between 25 and 81, for example. 716 for ($i = 0, $window_size = 1; $i < count($window_ranges) && $e_length > $window_ranges[$i]; ++$window_size, ++$i) { 717 } 718 719 $n_value = $n->value; 720 721 if (method_exists(static::class, 'generateCustomReduction')) { 722 static::generateCustomReduction($n, $class); 723 } 724 725 // precompute $this^0 through $this^$window_size 726 $powers = []; 727 $powers[1] = static::prepareReduce($x->value, $n_value, $class); 728 $powers[2] = static::squareReduce($powers[1], $n_value, $class); 729 730 // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end 731 // in a 1. ie. it's supposed to be odd. 732 $temp = 1 << ($window_size - 1); 733 for ($i = 1; $i < $temp; ++$i) { 734 $i2 = $i << 1; 735 $powers[$i2 + 1] = static::multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $class); 736 } 737 738 $result = new $class(1); 739 $result = static::prepareReduce($result->value, $n_value, $class); 740 741 for ($i = 0; $i < $e_length;) { 742 if (!$e_bits[$i]) { 743 $result = static::squareReduce($result, $n_value, $class); 744 ++$i; 745 } else { 746 for ($j = $window_size - 1; $j > 0; --$j) { 747 if (!empty($e_bits[$i + $j])) { 748 break; 749 } 750 } 751 752 // eg. the length of substr($e_bits, $i, $j + 1) 753 for ($k = 0; $k <= $j; ++$k) { 754 $result = static::squareReduce($result, $n_value, $class); 755 } 756 757 $result = static::multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $class); 758 759 $i += $j + 1; 760 } 761 } 762 763 $temp = new $class(); 764 $temp->value = static::reduce($result, $n_value, $class); 765 766 return $temp; 767 } 768 769 /** 770 * Generates a random number of a certain size 771 * 772 * Bit length is equal to $size 773 * 774 * @param int $size 775 * @return Engine 776 */ 777 public static function random($size) 778 { 779 $minMax = static::minMaxBits($size); 780 $min = $minMax['min']; 781 $max = $minMax['max']; 782 return static::randomRange($min, $max); 783 } 784 785 /** 786 * Generates a random prime number of a certain size 787 * 788 * Bit length is equal to $size 789 * 790 * @param int $size 791 * @return Engine 792 */ 793 public static function randomPrime($size) 794 { 795 $minMax = static::minMaxBits($size); 796 $min = $minMax['min']; 797 $max = $minMax['max']; 798 return static::randomRangePrime($min, $max); 799 } 800 801 /** 802 * Performs some pre-processing for randomRangePrime 803 * 804 * @param Engine $min 805 * @param Engine $max 806 * @return static|false 807 */ 808 protected static function randomRangePrimeOuter(Engine $min, Engine $max) 809 { 810 $compare = $max->compare($min); 811 812 if (!$compare) { 813 return $min->isPrime() ? $min : false; 814 } elseif ($compare < 0) { 815 // if $min is bigger then $max, swap $min and $max 816 $temp = $max; 817 $max = $min; 818 $min = $temp; 819 } 820 821 $length = $max->getLength(); 822 if ($length > 8196) { 823 throw new \RuntimeException("Generation of random prime numbers larger than 8196 has been disabled ($length)"); 824 } 825 826 $x = static::randomRange($min, $max); 827 828 return static::randomRangePrimeInner($x, $min, $max); 829 } 830 831 /** 832 * Generate a random number between a range 833 * 834 * Returns a random number between $min and $max where $min and $max 835 * can be defined using one of the two methods: 836 * 837 * BigInteger::randomRange($min, $max) 838 * BigInteger::randomRange($max, $min) 839 * 840 * @param Engine $min 841 * @param Engine $max 842 * @return Engine 843 */ 844 protected static function randomRangeHelper(Engine $min, Engine $max) 845 { 846 $compare = $max->compare($min); 847 848 if (!$compare) { 849 return $min; 850 } elseif ($compare < 0) { 851 // if $min is bigger then $max, swap $min and $max 852 $temp = $max; 853 $max = $min; 854 $min = $temp; 855 } 856 857 if (!isset(static::$one[static::class])) { 858 static::$one[static::class] = new static(1); 859 } 860 861 $max = $max->subtract($min->subtract(static::$one[static::class])); 862 863 $size = strlen(ltrim($max->toBytes(), chr(0))); 864 865 /* 866 doing $random % $max doesn't work because some numbers will be more likely to occur than others. 867 eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145 868 would produce 5 whereas the only value of random that could produce 139 would be 139. ie. 869 not all numbers would be equally likely. some would be more likely than others. 870 871 creating a whole new random number until you find one that is within the range doesn't work 872 because, for sufficiently small ranges, the likelihood that you'd get a number within that range 873 would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability 874 would be pretty high that $random would be greater than $max. 875 876 phpseclib works around this using the technique described here: 877 878 http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string 879 */ 880 $random_max = new static(chr(1) . str_repeat("\0", $size), 256); 881 $random = new static(Random::string($size), 256); 882 883 list($max_multiple) = $random_max->divide($max); 884 $max_multiple = $max_multiple->multiply($max); 885 886 while ($random->compare($max_multiple) >= 0) { 887 $random = $random->subtract($max_multiple); 888 $random_max = $random_max->subtract($max_multiple); 889 $random = $random->bitwise_leftShift(8); 890 $random = $random->add(new static(Random::string(1), 256)); 891 $random_max = $random_max->bitwise_leftShift(8); 892 list($max_multiple) = $random_max->divide($max); 893 $max_multiple = $max_multiple->multiply($max); 894 } 895 list(, $random) = $random->divide($max); 896 897 return $random->add($min); 898 } 899 900 /** 901 * Performs some post-processing for randomRangePrime 902 * 903 * @param Engine $x 904 * @param Engine $min 905 * @param Engine $max 906 * @return static|false 907 */ 908 protected static function randomRangePrimeInner(Engine $x, Engine $min, Engine $max) 909 { 910 if (!isset(static::$two[static::class])) { 911 static::$two[static::class] = new static('2'); 912 } 913 914 $x->make_odd(); 915 if ($x->compare($max) > 0) { 916 // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range 917 if ($min->equals($max)) { 918 return false; 919 } 920 $x = clone $min; 921 $x->make_odd(); 922 } 923 924 $initial_x = clone $x; 925 926 while (true) { 927 if ($x->isPrime()) { 928 return $x; 929 } 930 931 $x = $x->add(static::$two[static::class]); 932 933 if ($x->compare($max) > 0) { 934 $x = clone $min; 935 if ($x->equals(static::$two[static::class])) { 936 return $x; 937 } 938 $x->make_odd(); 939 } 940 941 if ($x->equals($initial_x)) { 942 return false; 943 } 944 } 945 } 946 947 /** 948 * Sets the $t parameter for primality testing 949 * 950 * @return int 951 */ 952 protected function setupIsPrime() 953 { 954 $length = $this->getLengthInBytes(); 955 956 // see HAC 4.49 "Note (controlling the error probability)" 957 // @codingStandardsIgnoreStart 958 if ($length >= 163) { $t = 2; } // floor(1300 / 8) 959 else if ($length >= 106) { $t = 3; } // floor( 850 / 8) 960 else if ($length >= 81 ) { $t = 4; } // floor( 650 / 8) 961 else if ($length >= 68 ) { $t = 5; } // floor( 550 / 8) 962 else if ($length >= 56 ) { $t = 6; } // floor( 450 / 8) 963 else if ($length >= 50 ) { $t = 7; } // floor( 400 / 8) 964 else if ($length >= 43 ) { $t = 8; } // floor( 350 / 8) 965 else if ($length >= 37 ) { $t = 9; } // floor( 300 / 8) 966 else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8) 967 else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8) 968 else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8) 969 else { $t = 27; } 970 // @codingStandardsIgnoreEnd 971 972 return $t; 973 } 974 975 /** 976 * Tests Primality 977 * 978 * Uses the {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}. 979 * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24} for more info. 980 * 981 * @param int $t 982 * @return bool 983 */ 984 protected function testPrimality($t) 985 { 986 if (!$this->testSmallPrimes()) { 987 return false; 988 } 989 990 $n = clone $this; 991 $n_1 = $n->subtract(static::$one[static::class]); 992 $n_2 = $n->subtract(static::$two[static::class]); 993 994 $r = clone $n_1; 995 $s = static::scan1divide($r); 996 997 for ($i = 0; $i < $t; ++$i) { 998 $a = static::randomRange(static::$two[static::class], $n_2); 999 $y = $a->modPow($r, $n); 1000 1001 if (!$y->equals(static::$one[static::class]) && !$y->equals($n_1)) { 1002 for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) { 1003 $y = $y->modPow(static::$two[static::class], $n); 1004 if ($y->equals(static::$one[static::class])) { 1005 return false; 1006 } 1007 } 1008 1009 if (!$y->equals($n_1)) { 1010 return false; 1011 } 1012 } 1013 } 1014 1015 return true; 1016 } 1017 1018 /** 1019 * Checks a numer to see if it's prime 1020 * 1021 * Assuming the $t parameter is not set, this function has an error rate of 2**-80. The main motivation for the 1022 * $t parameter is distributability. BigInteger::randomPrime() can be distributed across multiple pageloads 1023 * on a website instead of just one. 1024 * 1025 * @param int|bool $t 1026 * @return bool 1027 */ 1028 public function isPrime($t = false) 1029 { 1030 // OpenSSL limits RSA keys to 16384 bits. The length of an RSA key is equal to the length of the modulo, which is 1031 // produced by multiplying the primes p and q by one another. The largest number two 8196 bit primes can produce is 1032 // a 16384 bit number so, basically, 8196 bit primes are the largest OpenSSL will generate and if that's the largest 1033 // that it'll generate it also stands to reason that that's the largest you'll be able to test primality on 1034 $length = $this->getLength(); 1035 if ($length > 8196) { 1036 throw new \RuntimeException("Primality testing is not supported for numbers larger than 8196 bits ($length)"); 1037 } 1038 1039 if (!$t) { 1040 $t = $this->setupIsPrime(); 1041 } 1042 return $this->testPrimality($t); 1043 } 1044 1045 /** 1046 * Performs a few preliminary checks on root 1047 * 1048 * @param int $n 1049 * @return Engine 1050 */ 1051 protected function rootHelper($n) 1052 { 1053 if ($n < 1) { 1054 return clone static::$zero[static::class]; 1055 } // we want positive exponents 1056 if ($this->compare(static::$one[static::class]) < 0) { 1057 return clone static::$zero[static::class]; 1058 } // we want positive numbers 1059 if ($this->compare(static::$two[static::class]) < 0) { 1060 return clone static::$one[static::class]; 1061 } // n-th root of 1 or 2 is 1 1062 1063 return $this->rootInner($n); 1064 } 1065 1066 /** 1067 * Calculates the nth root of a biginteger. 1068 * 1069 * Returns the nth root of a positive biginteger, where n defaults to 2 1070 * 1071 * {@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}.} 1072 * 1073 * @param int $n 1074 * @return Engine 1075 */ 1076 protected function rootInner($n) 1077 { 1078 $n = new static($n); 1079 1080 // g is our guess number 1081 $g = static::$two[static::class]; 1082 // while (g^n < num) g=g*2 1083 while ($g->pow($n)->compare($this) < 0) { 1084 $g = $g->multiply(static::$two[static::class]); 1085 } 1086 // if (g^n==num) num is a power of 2, we're lucky, end of job 1087 // == 0 bccomp(bcpow($g, $n), $n->value)==0 1088 if ($g->pow($n)->equals($this) > 0) { 1089 $root = $g; 1090 return $this->normalize($root); 1091 } 1092 1093 // if we're here num wasn't a power of 2 :( 1094 $og = $g; // og means original guess and here is our upper bound 1095 $g = $g->divide(static::$two[static::class])[0]; // g is set to be our lower bound 1096 $step = $og->subtract($g)->divide(static::$two[static::class])[0]; // step is the half of upper bound - lower bound 1097 $g = $g->add($step); // we start at lower bound + step , basically in the middle of our interval 1098 1099 // while step>1 1100 1101 while ($step->compare(static::$one[static::class]) == 1) { 1102 $guess = $g->pow($n); 1103 $step = $step->divide(static::$two[static::class])[0]; 1104 $comp = $guess->compare($this); // compare our guess with real number 1105 switch ($comp) { 1106 case -1: // if guess is lower we add the new step 1107 $g = $g->add($step); 1108 break; 1109 case 1: // if guess is higher we sub the new step 1110 $g = $g->subtract($step); 1111 break; 1112 case 0: // if guess is exactly the num we're done, we return the value 1113 $root = $g; 1114 break 2; 1115 } 1116 } 1117 1118 if ($comp == 1) { 1119 $g = $g->subtract($step); 1120 } 1121 1122 // whatever happened, g is the closest guess we can make so return it 1123 $root = $g; 1124 1125 return $this->normalize($root); 1126 } 1127 1128 /** 1129 * Calculates the nth root of a biginteger. 1130 * 1131 * @param int $n 1132 * @return Engine 1133 */ 1134 public function root($n = 2) 1135 { 1136 return $this->rootHelper($n); 1137 } 1138 1139 /** 1140 * Return the minimum BigInteger between an arbitrary number of BigIntegers. 1141 * 1142 * @param array $nums 1143 * @return Engine 1144 */ 1145 protected static function minHelper(array $nums) 1146 { 1147 if (count($nums) == 1) { 1148 return $nums[0]; 1149 } 1150 $min = $nums[0]; 1151 for ($i = 1; $i < count($nums); $i++) { 1152 $min = $min->compare($nums[$i]) > 0 ? $nums[$i] : $min; 1153 } 1154 return $min; 1155 } 1156 1157 /** 1158 * Return the minimum BigInteger between an arbitrary number of BigIntegers. 1159 * 1160 * @param array $nums 1161 * @return Engine 1162 */ 1163 protected static function maxHelper(array $nums) 1164 { 1165 if (count($nums) == 1) { 1166 return $nums[0]; 1167 } 1168 $max = $nums[0]; 1169 for ($i = 1; $i < count($nums); $i++) { 1170 $max = $max->compare($nums[$i]) < 0 ? $nums[$i] : $max; 1171 } 1172 return $max; 1173 } 1174 1175 /** 1176 * Create Recurring Modulo Function 1177 * 1178 * Sometimes it may be desirable to do repeated modulos with the same number outside of 1179 * modular exponentiation 1180 * 1181 * @return callable 1182 */ 1183 public function createRecurringModuloFunction() 1184 { 1185 $class = static::class; 1186 1187 $fqengine = !method_exists(static::$modexpEngine[static::class], 'reduce') ? 1188 '\\phpseclib3\\Math\\BigInteger\\Engines\\' . static::ENGINE_DIR . '\\DefaultEngine' : 1189 static::$modexpEngine[static::class]; 1190 if (method_exists($fqengine, 'generateCustomReduction')) { 1191 $func = $fqengine::generateCustomReduction($this, static::class); 1192 return eval('return function(' . static::class . ' $x) use ($func, $class) { 1193 $r = new $class(); 1194 $r->value = $func($x->value); 1195 return $r; 1196 };'); 1197 } 1198 $n = $this->value; 1199 return eval('return function(' . static::class . ' $x) use ($n, $fqengine, $class) { 1200 $r = new $class(); 1201 $r->value = $fqengine::reduce($x->value, $n, $class); 1202 return $r; 1203 };'); 1204 } 1205 1206 /** 1207 * Calculates the greatest common divisor and Bezout's identity. 1208 * 1209 * @param Engine $n 1210 * @return array{gcd: Engine, x: Engine, y: Engine} 1211 */ 1212 protected function extendedGCDHelper(Engine $n) 1213 { 1214 $u = clone $this; 1215 $v = clone $n; 1216 1217 $one = new static(1); 1218 $zero = new static(); 1219 1220 $a = clone $one; 1221 $b = clone $zero; 1222 $c = clone $zero; 1223 $d = clone $one; 1224 1225 while (!$v->equals($zero)) { 1226 list($q) = $u->divide($v); 1227 1228 $temp = $u; 1229 $u = $v; 1230 $v = $temp->subtract($v->multiply($q)); 1231 1232 $temp = $a; 1233 $a = $c; 1234 $c = $temp->subtract($a->multiply($q)); 1235 1236 $temp = $b; 1237 $b = $d; 1238 $d = $temp->subtract($b->multiply($q)); 1239 } 1240 1241 return [ 1242 'gcd' => $u, 1243 'x' => $a, 1244 'y' => $b 1245 ]; 1246 } 1247 1248 /** 1249 * Bitwise Split 1250 * 1251 * Splits BigInteger's into chunks of $split bits 1252 * 1253 * @param int $split 1254 * @return Engine[] 1255 */ 1256 public function bitwise_split($split) 1257 { 1258 if ($split < 1) { 1259 throw new \RuntimeException('Offset must be greater than 1'); 1260 } 1261 1262 $mask = static::$one[static::class]->bitwise_leftShift($split)->subtract(static::$one[static::class]); 1263 1264 $num = clone $this; 1265 1266 $vals = []; 1267 while (!$num->equals(static::$zero[static::class])) { 1268 $vals[] = $num->bitwise_and($mask); 1269 $num = $num->bitwise_rightShift($split); 1270 } 1271 1272 return array_reverse($vals); 1273 } 1274 1275 /** 1276 * Logical And 1277 * 1278 * @param Engine $x 1279 * @return Engine 1280 */ 1281 protected function bitwiseAndHelper(Engine $x) 1282 { 1283 $left = $this->toBytes(true); 1284 $right = $x->toBytes(true); 1285 1286 $length = max(strlen($left), strlen($right)); 1287 1288 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); 1289 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); 1290 1291 return $this->normalize(new static($left & $right, -256)); 1292 } 1293 1294 /** 1295 * Logical Or 1296 * 1297 * @param Engine $x 1298 * @return Engine 1299 */ 1300 protected function bitwiseOrHelper(Engine $x) 1301 { 1302 $left = $this->toBytes(true); 1303 $right = $x->toBytes(true); 1304 1305 $length = max(strlen($left), strlen($right)); 1306 1307 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); 1308 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); 1309 1310 return $this->normalize(new static($left | $right, -256)); 1311 } 1312 1313 /** 1314 * Logical Exclusive Or 1315 * 1316 * @param Engine $x 1317 * @return Engine 1318 */ 1319 protected function bitwiseXorHelper(Engine $x) 1320 { 1321 $left = $this->toBytes(true); 1322 $right = $x->toBytes(true); 1323 1324 $length = max(strlen($left), strlen($right)); 1325 1326 1327 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); 1328 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); 1329 return $this->normalize(new static($left ^ $right, -256)); 1330 } 1331} 1332