1<?php 2 3/** 4 * GMP 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; 20 21/** 22 * GMP Engine. 23 * 24 * @package GMP 25 * @author Jim Wigginton <terrafrost@php.net> 26 * @access public 27 */ 28class GMP extends Engine 29{ 30 /** 31 * Can Bitwise operations be done fast? 32 * 33 * @see parent::bitwise_leftRotate() 34 * @see parent::bitwise_rightRotate() 35 * @access protected 36 */ 37 const FAST_BITWISE = true; 38 39 /** 40 * Engine Directory 41 * 42 * @see parent::setModExpEngine 43 * @access protected 44 */ 45 const ENGINE_DIR = 'GMP'; 46 47 /** 48 * Modular Exponentiation Engine 49 * 50 * @var string 51 */ 52 protected static $modexpEngine; 53 54 /** 55 * Engine Validity Flag 56 * 57 * @var bool 58 */ 59 protected static $isValidEngine; 60 61 /** 62 * BigInteger(0) 63 * 64 * @var \phpseclib3\Math\BigInteger\Engines\GMP 65 */ 66 protected static $zero; 67 68 /** 69 * BigInteger(1) 70 * 71 * @var \phpseclib3\Math\BigInteger\Engines\GMP 72 */ 73 protected static $one; 74 75 /** 76 * BigInteger(2) 77 * 78 * @var \phpseclib3\Math\BigInteger\Engines\GMP 79 */ 80 protected static $two; 81 82 /** 83 * Primes > 2 and < 1000 84 * 85 * Unused for GMP Engine 86 * 87 * @var mixed 88 */ 89 protected static $primes; 90 91 /** 92 * Test for engine validity 93 * 94 * @see parent::__construct() 95 * @return bool 96 */ 97 public static function isValidEngine() 98 { 99 return extension_loaded('gmp'); 100 } 101 102 /** 103 * Default constructor 104 * 105 * @param mixed $x integer Base-10 number or base-$base number if $base set. 106 * @param int $base 107 * @see parent::__construct() 108 * @return \phpseclib3\Math\BigInteger\Engines\GMP 109 */ 110 public function __construct($x = 0, $base = 10) 111 { 112 if (!isset(self::$isValidEngine)) { 113 self::$isValidEngine = self::isValidEngine(); 114 } 115 if (!self::$isValidEngine) { 116 throw new BadConfigurationException('GMP is not setup correctly on this system'); 117 } 118 119 if ($x instanceof \GMP) { 120 $this->value = $x; 121 return; 122 } 123 124 $this->value = gmp_init(0); 125 126 parent::__construct($x, $base); 127 } 128 129 /** 130 * Initialize a GMP BigInteger Engine instance 131 * 132 * @param int $base 133 * @see parent::__construct() 134 */ 135 protected function initialize($base) 136 { 137 switch (abs($base)) { 138 case 256: 139 $this->value = gmp_import($this->value); 140 if ($this->is_negative) { 141 $this->value = -$this->value; 142 } 143 break; 144 case 16: 145 $temp = $this->is_negative ? '-0x' . $this->value : '0x' . $this->value; 146 $this->value = gmp_init($temp); 147 break; 148 case 10: 149 $this->value = gmp_init(isset($this->value) ? $this->value : '0'); 150 } 151 } 152 153 /** 154 * Converts a BigInteger to a base-10 number. 155 * 156 * @return string 157 */ 158 public function toString() 159 { 160 return (string) $this->value; 161 } 162 163 /** 164 * Converts a BigInteger to a bit string (eg. base-2). 165 * 166 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're 167 * saved as two's compliment. 168 * 169 * @param bool $twos_compliment 170 * @return string 171 */ 172 public function toBits($twos_compliment = false) 173 { 174 $hex = $this->toHex($twos_compliment); 175 176 $bits = gmp_strval(gmp_init($hex, 16), 2); 177 178 if ($this->precision > 0) { 179 $bits = substr($bits, -$this->precision); 180 } 181 182 if ($twos_compliment && $this->compare(new static()) > 0 && $this->precision <= 0) { 183 return '0' . $bits; 184 } 185 186 return $bits; 187 } 188 189 /** 190 * Converts a BigInteger to a byte string (eg. base-256). 191 * 192 * @param bool $twos_compliment 193 * @return string 194 */ 195 function toBytes($twos_compliment = false) 196 { 197 if ($twos_compliment) { 198 return $this->toBytesHelper(); 199 } 200 201 if (gmp_cmp($this->value, gmp_init(0)) == 0) { 202 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; 203 } 204 205 $temp = gmp_export($this->value); 206 207 return $this->precision > 0 ? 208 substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) : 209 ltrim($temp, chr(0)); 210 } 211 212 /** 213 * Adds two BigIntegers. 214 * 215 * @param GMP $y 216 * @return GMP 217 */ 218 public function add(GMP $y) 219 { 220 $temp = new self(); 221 $temp->value = $this->value + $y->value; 222 223 return $this->normalize($temp); 224 } 225 226 /** 227 * Subtracts two BigIntegers. 228 * 229 * @param GMP $y 230 * @return GMP 231 */ 232 public function subtract(GMP $y) 233 { 234 $temp = new self(); 235 $temp->value = $this->value - $y->value; 236 237 return $this->normalize($temp); 238 } 239 240 /** 241 * Multiplies two BigIntegers. 242 * 243 * @param GMP $x 244 * @return GMP 245 */ 246 public function multiply(GMP $x) 247 { 248 $temp = new self(); 249 $temp->value = $this->value * $x->value; 250 251 return $this->normalize($temp); 252 } 253 254 /** 255 * Divides two BigIntegers. 256 * 257 * Returns an array whose first element contains the quotient and whose second element contains the 258 * "common residue". If the remainder would be positive, the "common residue" and the remainder are the 259 * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder 260 * and the divisor (basically, the "common residue" is the first positive modulo). 261 * 262 * @param GMP $y 263 * @return GMP 264 */ 265 public function divide(GMP $y) 266 { 267 $quotient = new self(); 268 $remainder = new self(); 269 270 list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value); 271 272 if (gmp_sign($remainder->value) < 0) { 273 $remainder->value = $remainder->value + gmp_abs($y->value); 274 } 275 276 return [$this->normalize($quotient), $this->normalize($remainder)]; 277 } 278 279 /** 280 * Compares two numbers. 281 * 282 * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this is 283 * demonstrated thusly: 284 * 285 * $x > $y: $x->compare($y) > 0 286 * $x < $y: $x->compare($y) < 0 287 * $x == $y: $x->compare($y) == 0 288 * 289 * Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y). 290 * 291 * {@internal Could return $this->subtract($x), but that's not as fast as what we do do.} 292 * 293 * @param GMP $y 294 * @return int in case < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal. 295 * @access public 296 * @see self::equals() 297 */ 298 public function compare(GMP $y) 299 { 300 $r = gmp_cmp($this->value, $y->value); 301 if ($r < -1) { 302 $r = -1; 303 } 304 if ($r > 1) { 305 $r = 1; 306 } 307 return $r; 308 } 309 310 /** 311 * Tests the equality of two numbers. 312 * 313 * If you need to see if one number is greater than or less than another number, use BigInteger::compare() 314 * 315 * @param GMP $x 316 * @return bool 317 */ 318 public function equals(GMP $x) 319 { 320 return $this->value == $x->value; 321 } 322 323 /** 324 * Calculates modular inverses. 325 * 326 * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses. 327 * 328 * @param GMP $n 329 * @return false|GMP 330 */ 331 public function modInverse(GMP $n) 332 { 333 $temp = new self(); 334 $temp->value = gmp_invert($this->value, $n->value); 335 336 return $temp->value === false ? false : $this->normalize($temp); 337 } 338 339 /** 340 * Calculates the greatest common divisor and Bezout's identity. 341 * 342 * Say you have 693 and 609. The GCD is 21. Bezout's identity states that there exist integers x and y such that 343 * 693*x + 609*y == 21. In point of fact, there are actually an infinite number of x and y combinations and which 344 * combination is returned is dependent upon which mode is in use. See 345 * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information. 346 * 347 * @param \phpseclib3\Math\BigInteger\Engines\GMP $n 348 * @return \phpseclib3\Math\BigInteger\Engines\GMP[] 349 */ 350 public function extendedGCD(GMP $n) 351 { 352 extract(gmp_gcdext($this->value, $n->value)); 353 354 return [ 355 'gcd' => $this->normalize(new self($g)), 356 'x' => $this->normalize(new self($s)), 357 'y' => $this->normalize(new self($t)) 358 ]; 359 } 360 361 /** 362 * Calculates the greatest common divisor 363 * 364 * Say you have 693 and 609. The GCD is 21. 365 * 366 * @param GMP $n 367 * @return GMP 368 */ 369 public function gcd(GMP $n) 370 { 371 $r = gmp_gcd($this->value, $n->value); 372 return $this->normalize(new self($r)); 373 } 374 375 /** 376 * Absolute value. 377 * 378 * @return \phpseclib3\Math\BigInteger\Engines\GMP 379 * @access public 380 */ 381 public function abs() 382 { 383 $temp = new self(); 384 $temp->value = gmp_abs($this->value); 385 386 return $temp; 387 } 388 389 /** 390 * Logical And 391 * 392 * @param GMP $x 393 * @return GMP 394 */ 395 public function bitwise_and(GMP $x) 396 { 397 $temp = new self(); 398 $temp->value = $this->value & $x->value; 399 400 return $this->normalize($temp); 401 } 402 403 /** 404 * Logical Or 405 * 406 * @param GMP $x 407 * @return GMP 408 */ 409 public function bitwise_or(GMP $x) 410 { 411 $temp = new self(); 412 $temp->value = $this->value | $x->value; 413 414 return $this->normalize($temp); 415 } 416 417 /** 418 * Logical Exclusive Or 419 * 420 * @param GMP $x 421 * @return GMP 422 */ 423 public function bitwise_xor(GMP $x) 424 { 425 $temp = new self(); 426 $temp->value = $this->value ^ $x->value; 427 428 return $this->normalize($temp); 429 } 430 431 /** 432 * Logical Right Shift 433 * 434 * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift. 435 * 436 * @param int $shift 437 * @return \phpseclib3\Math\BigInteger\Engines\GMP 438 */ 439 public function bitwise_rightShift($shift) 440 { 441 // 0xFFFFFFFF >> 2 == -1 (on 32-bit systems) 442 // gmp_init('0xFFFFFFFF') >> 2 == gmp_init('0x3FFFFFFF') 443 444 $temp = new self(); 445 $temp->value = $this->value >> $shift; 446 447 return $this->normalize($temp); 448 } 449 450 /** 451 * Logical Left Shift 452 * 453 * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift. 454 * 455 * @param int $shift 456 * @return \phpseclib3\Math\BigInteger\Engines\GMP 457 */ 458 public function bitwise_leftShift($shift) 459 { 460 $temp = new self(); 461 $temp->value = $this->value << $shift; 462 463 return $this->normalize($temp); 464 } 465 466 /** 467 * Performs modular exponentiation. 468 * 469 * @param GMP $e 470 * @param GMP $n 471 * @return GMP 472 */ 473 public function modPow(GMP $e, GMP $n) 474 { 475 return $this->powModOuter($e, $n); 476 } 477 478 /** 479 * Performs modular exponentiation. 480 * 481 * Alias for modPow(). 482 * 483 * @param GMP $e 484 * @param GMP $n 485 * @return GMP 486 */ 487 public function powMod(GMP $e, GMP $n) 488 { 489 return $this->powModOuter($e, $n); 490 } 491 492 /** 493 * Performs modular exponentiation. 494 * 495 * @param GMP $e 496 * @param GMP $n 497 * @return GMP 498 */ 499 protected function powModInner(GMP $e, GMP $n) 500 { 501 $class = self::$modexpEngine; 502 return $class::powModHelper($this, $e, $n); 503 } 504 505 /** 506 * Normalize 507 * 508 * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision 509 * 510 * @param GMP $result 511 * @return GMP 512 */ 513 protected function normalize(GMP $result) 514 { 515 unset($result->reduce); 516 517 $result->precision = $this->precision; 518 $result->bitmask = $this->bitmask; 519 520 if ($result->bitmask !== false) { 521 $flip = $result->value < 0; 522 if ($flip) { 523 $result->value = -$result->value; 524 } 525 $result->value = $result->value & $result->bitmask->value; 526 if ($flip) { 527 $result->value = -$result->value; 528 } 529 } 530 531 return $result; 532 } 533 534 /** 535 * Performs some post-processing for randomRangePrime 536 * 537 * @param Engine $x 538 * @param Engine $min 539 * @param Engine $max 540 * @return GMP 541 */ 542 protected static function randomRangePrimeInner(Engine $x, Engine $min, Engine $max) 543 { 544 $p = gmp_nextprime($x->value); 545 546 if ($p <= $max->value) { 547 return new self($p); 548 } 549 550 if ($min->value != $x->value) { 551 $x = new self($x->value - 1); 552 } 553 554 return self::randomRangePrime($min, $x); 555 } 556 557 /** 558 * Generate a random prime number between a range 559 * 560 * If there's not a prime within the given range, false will be returned. 561 * 562 * @param GMP $min 563 * @param GMP $max 564 * @return false|GMP 565 */ 566 public static function randomRangePrime(GMP $min, GMP $max) 567 { 568 return self::randomRangePrimeOuter($min, $max); 569 } 570 571 /** 572 * Generate a random number between a range 573 * 574 * Returns a random number between $min and $max where $min and $max 575 * can be defined using one of the two methods: 576 * 577 * BigInteger::randomRange($min, $max) 578 * BigInteger::randomRange($max, $min) 579 * 580 * @param GMP $min 581 * @param GMP $max 582 * @return GMP 583 */ 584 public static function randomRange(GMP $min, GMP $max) 585 { 586 return self::randomRangeHelper($min, $max); 587 } 588 589 /** 590 * Make the current number odd 591 * 592 * If the current number is odd it'll be unchanged. If it's even, one will be added to it. 593 * 594 * @see self::randomPrime() 595 */ 596 protected function make_odd() 597 { 598 gmp_setbit($this->value, 0); 599 } 600 601 /** 602 * Tests Primality 603 * 604 * @param int $t 605 * @return bool 606 */ 607 protected function testPrimality($t) 608 { 609 return gmp_prob_prime($this->value, $t) != 0; 610 } 611 612 /** 613 * Calculates the nth root of a biginteger. 614 * 615 * Returns the nth root of a positive biginteger, where n defaults to 2 616 * 617 * @param int $n 618 * @return GMP 619 */ 620 protected function rootInner($n) 621 { 622 $root = new self(); 623 $root->value = gmp_root($this->value, $n); 624 return $this->normalize($root); 625 } 626 627 /** 628 * Performs exponentiation. 629 * 630 * @param GMP $n 631 * @return GMP 632 */ 633 public function pow(GMP $n) 634 { 635 $temp = new self(); 636 $temp->value = $this->value ** $n->value; 637 638 return $this->normalize($temp); 639 } 640 641 /** 642 * Return the minimum BigInteger between an arbitrary number of BigIntegers. 643 * 644 * @param GMP ...$nums 645 * @return GMP 646 */ 647 public static function min(GMP ...$nums) 648 { 649 return self::minHelper($nums); 650 } 651 652 /** 653 * Return the maximum BigInteger between an arbitrary number of BigIntegers. 654 * 655 * @param GMP ...$nums 656 * @return GMP 657 */ 658 public static function max(GMP ...$nums) 659 { 660 return self::maxHelper($nums); 661 } 662 663 /** 664 * Tests BigInteger to see if it is between two integers, inclusive 665 * 666 * @param GMP $min 667 * @param GMP $max 668 * @return bool 669 */ 670 public function between(GMP $min, GMP $max) 671 { 672 return $this->compare($min) >= 0 && $this->compare($max) <= 0; 673 } 674 675 /** 676 * Create Recurring Modulo Function 677 * 678 * Sometimes it may be desirable to do repeated modulos with the same number outside of 679 * modular exponentiation 680 * 681 * @return callable 682 */ 683 public function createRecurringModuloFunction() 684 { 685 $temp = $this->value; 686 $this->reduce = function(GMP $x) use ($temp) { 687 return new GMP($x->value % $temp); 688 }; 689 return $this->reduce; 690 } 691 692 /** 693 * Scan for 1 and right shift by that amount 694 * 695 * ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s)); 696 * 697 * @param GMP $r 698 * @return int 699 */ 700 public static function scan1divide(GMP $r) 701 { 702 $s = gmp_scan1($r->value, 0); 703 $r->value >>= $s; 704 return $s; 705 } 706 707 /** 708 * Is Odd? 709 * 710 * @return boolean 711 */ 712 public function isOdd() 713 { 714 return gmp_testbit($this->value, 0); 715 } 716 717 /** 718 * Tests if a bit is set 719 * 720 * @return boolean 721 */ 722 public function testBit($x) 723 { 724 return gmp_testbit($this->value, $x); 725 } 726 727 /** 728 * Is Negative? 729 * 730 * @return boolean 731 */ 732 public function isNegative() 733 { 734 return gmp_sign($this->value) == -1; 735 } 736 737 /** 738 * Negate 739 * 740 * Given $k, returns -$k 741 * 742 * @return GMP 743 */ 744 public function negate() 745 { 746 $temp = clone $this; 747 $temp->value = -$this->value; 748 749 return $temp; 750 } 751}