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