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