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