[Summary view] [Print] [Text view]

   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 <[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\Exception\BadConfigurationException;
  20  
  21  /**
  22   * BCMath Engine.
  23   *
  24   * @package BCMath
  25   * @author  Jim Wigginton <[email protected]>
  26   * @access  public
  27   */
  28  class 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  }