mirror of
https://github.com/phpseclib/phpseclib.git
synced 2024-06-03 00:50:52 +00:00
608 lines
16 KiB
PHP
608 lines
16 KiB
PHP
<?php
|
|
|
|
/**
|
|
* BCMath BigInteger Engine
|
|
*
|
|
* PHP version 5 and 7
|
|
*
|
|
* @author Jim Wigginton <terrafrost@php.net>
|
|
* @copyright 2017 Jim Wigginton
|
|
* @license http://www.opensource.org/licenses/mit-license.html MIT License
|
|
* @link http://pear.php.net/package/Math_BigInteger
|
|
*/
|
|
|
|
declare(strict_types=1);
|
|
|
|
namespace phpseclib3\Math\BigInteger\Engines;
|
|
|
|
use phpseclib3\Common\Functions\Strings;
|
|
use phpseclib3\Exception\BadConfigurationException;
|
|
|
|
/**
|
|
* BCMath Engine.
|
|
*
|
|
* @author Jim Wigginton <terrafrost@php.net>
|
|
*/
|
|
class BCMath extends Engine
|
|
{
|
|
/**
|
|
* Can Bitwise operations be done fast?
|
|
*
|
|
* @see parent::bitwise_leftRotate()
|
|
* @see parent::bitwise_rightRotate()
|
|
*/
|
|
public const FAST_BITWISE = false;
|
|
|
|
/**
|
|
* Engine Directory
|
|
*
|
|
* @see parent::setModExpEngine
|
|
*/
|
|
public const ENGINE_DIR = 'BCMath';
|
|
|
|
/**
|
|
* Test for engine validity
|
|
*
|
|
* @see parent::__construct()
|
|
*/
|
|
public static function isValidEngine(): bool
|
|
{
|
|
return extension_loaded('bcmath');
|
|
}
|
|
|
|
/**
|
|
* Default constructor
|
|
*
|
|
* @param mixed $x integer Base-10 number or base-$base number if $base set.
|
|
* @see parent::__construct()
|
|
*/
|
|
public function __construct($x = 0, int $base = 10)
|
|
{
|
|
if (!isset(static::$isValidEngine[static::class])) {
|
|
static::$isValidEngine[static::class] = self::isValidEngine();
|
|
}
|
|
if (!static::$isValidEngine[static::class]) {
|
|
throw new BadConfigurationException('BCMath is not setup correctly on this system');
|
|
}
|
|
|
|
$this->value = '0';
|
|
|
|
parent::__construct($x, $base);
|
|
}
|
|
|
|
/**
|
|
* Initialize a BCMath BigInteger Engine instance
|
|
*
|
|
* @see parent::__construct()
|
|
*/
|
|
protected function initialize(int $base): void
|
|
{
|
|
switch (abs($base)) {
|
|
case 256:
|
|
// round $len to the nearest 4
|
|
$len = (strlen($this->value) + 3) & ~3;
|
|
|
|
$x = str_pad($this->value, $len, chr(0), STR_PAD_LEFT);
|
|
|
|
$this->value = '0';
|
|
for ($i = 0; $i < $len; $i += 4) {
|
|
$this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32
|
|
$this->value = bcadd(
|
|
$this->value,
|
|
(string) (0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3]))),
|
|
0
|
|
);
|
|
}
|
|
|
|
if ($this->is_negative) {
|
|
$this->value = '-' . $this->value;
|
|
}
|
|
break;
|
|
case 16:
|
|
$x = (strlen($this->value) & 1) ? '0' . $this->value : $this->value;
|
|
$temp = new self(Strings::hex2bin($x), 256);
|
|
$this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
|
|
$this->is_negative = false;
|
|
break;
|
|
case 10:
|
|
// explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
|
|
// results then doing it on '-1' does (modInverse does $x[0])
|
|
$this->value = $this->value === '-' ? '0' : (string)$this->value;
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Converts a BigInteger to a base-10 number.
|
|
*/
|
|
public function toString(): string
|
|
{
|
|
if ($this->value === '0') {
|
|
return '0';
|
|
}
|
|
|
|
return ltrim($this->value, '0');
|
|
}
|
|
|
|
/**
|
|
* Converts a BigInteger to a byte string (eg. base-256).
|
|
*/
|
|
public function toBytes(bool $twos_compliment = false): string
|
|
{
|
|
if ($twos_compliment) {
|
|
return $this->toBytesHelper();
|
|
}
|
|
|
|
$value = '';
|
|
$current = $this->value;
|
|
|
|
if ($current[0] == '-') {
|
|
$current = substr($current, 1);
|
|
}
|
|
|
|
while (bccomp($current, '0', 0) > 0) {
|
|
$temp = bcmod($current, '16777216');
|
|
$value = chr($temp >> 16) . chr($temp >> 8) . chr((int) $temp) . $value;
|
|
$current = bcdiv($current, '16777216', 0);
|
|
}
|
|
|
|
return $this->precision > 0 ?
|
|
substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
|
|
ltrim($value, chr(0));
|
|
}
|
|
|
|
/**
|
|
* Adds two BigIntegers.
|
|
*/
|
|
public function add(BCMath $y): BCMath
|
|
{
|
|
$temp = new self();
|
|
$temp->value = bcadd($this->value, $y->value);
|
|
|
|
return $this->normalize($temp);
|
|
}
|
|
|
|
/**
|
|
* Subtracts two BigIntegers.
|
|
*/
|
|
public function subtract(BCMath $y): BCMath
|
|
{
|
|
$temp = new self();
|
|
$temp->value = bcsub($this->value, $y->value);
|
|
|
|
return $this->normalize($temp);
|
|
}
|
|
|
|
/**
|
|
* Multiplies two BigIntegers.
|
|
*/
|
|
public function multiply(BCMath $x): BCMath
|
|
{
|
|
$temp = new self();
|
|
$temp->value = bcmul($this->value, $x->value);
|
|
|
|
return $this->normalize($temp);
|
|
}
|
|
|
|
/**
|
|
* Divides two BigIntegers.
|
|
*
|
|
* Returns an array whose first element contains the quotient and whose second element contains the
|
|
* "common residue". If the remainder would be positive, the "common residue" and the remainder are the
|
|
* same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder
|
|
* and the divisor (basically, the "common residue" is the first positive modulo).
|
|
*
|
|
* @return array{static, static}
|
|
*/
|
|
public function divide(BCMath $y): array
|
|
{
|
|
$quotient = new self();
|
|
$remainder = new self();
|
|
|
|
$quotient->value = bcdiv($this->value, $y->value, 0);
|
|
$remainder->value = bcmod($this->value, $y->value);
|
|
|
|
if ($remainder->value[0] == '-') {
|
|
$remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
|
|
}
|
|
|
|
return [$this->normalize($quotient), $this->normalize($remainder)];
|
|
}
|
|
|
|
/**
|
|
* Calculates modular inverses.
|
|
*
|
|
* Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses.
|
|
*
|
|
* @return false|BCMath
|
|
*/
|
|
public function modInverse(BCMath $n)
|
|
{
|
|
return $this->modInverseHelper($n);
|
|
}
|
|
|
|
/**
|
|
* Calculates the greatest common divisor and Bezout's identity.
|
|
*
|
|
* Say you have 693 and 609. The GCD is 21. Bezout's identity states that there exist integers x and y such that
|
|
* 693*x + 609*y == 21. In point of fact, there are actually an infinite number of x and y combinations and which
|
|
* combination is returned is dependent upon which mode is in use. See
|
|
* {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information.
|
|
*
|
|
* @return array{gcd: static, x: static, y: static}
|
|
*/
|
|
public function extendedGCD(BCMath $n): array
|
|
{
|
|
// it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
|
|
// best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway. as is,
|
|
// the basic extended euclidean algorithim is what we're using.
|
|
|
|
$u = $this->value;
|
|
$v = $n->value;
|
|
|
|
$a = '1';
|
|
$b = '0';
|
|
$c = '0';
|
|
$d = '1';
|
|
|
|
while (bccomp($v, '0', 0) != 0) {
|
|
$q = bcdiv($u, $v, 0);
|
|
|
|
$temp = $u;
|
|
$u = $v;
|
|
$v = bcsub($temp, bcmul($v, $q, 0), 0);
|
|
|
|
$temp = $a;
|
|
$a = $c;
|
|
$c = bcsub($temp, bcmul($a, $q, 0), 0);
|
|
|
|
$temp = $b;
|
|
$b = $d;
|
|
$d = bcsub($temp, bcmul($b, $q, 0), 0);
|
|
}
|
|
|
|
return [
|
|
'gcd' => $this->normalize(new static($u)),
|
|
'x' => $this->normalize(new static($a)),
|
|
'y' => $this->normalize(new static($b)),
|
|
];
|
|
}
|
|
|
|
/**
|
|
* Calculates the greatest common divisor
|
|
*
|
|
* Say you have 693 and 609. The GCD is 21.
|
|
*/
|
|
public function gcd(BCMath $n): BCMath
|
|
{
|
|
extract($this->extendedGCD($n));
|
|
/** @var BCMath $gcd */
|
|
return $gcd;
|
|
}
|
|
|
|
/**
|
|
* Absolute value.
|
|
*/
|
|
public function abs(): BCMath
|
|
{
|
|
$temp = new static();
|
|
$temp->value = strlen($this->value) && $this->value[0] == '-' ?
|
|
substr($this->value, 1) :
|
|
$this->value;
|
|
|
|
return $temp;
|
|
}
|
|
|
|
/**
|
|
* Logical And
|
|
*/
|
|
public function bitwise_and(BCMath $x): BCMath
|
|
{
|
|
return $this->bitwiseAndHelper($x);
|
|
}
|
|
|
|
/**
|
|
* Logical Or
|
|
*/
|
|
public function bitwise_or(BCMath $x): BCMath
|
|
{
|
|
return $this->bitwiseXorHelper($x);
|
|
}
|
|
|
|
/**
|
|
* Logical Exclusive Or
|
|
*/
|
|
public function bitwise_xor(BCMath $x): BCMath
|
|
{
|
|
return $this->bitwiseXorHelper($x);
|
|
}
|
|
|
|
/**
|
|
* Logical Right Shift
|
|
*
|
|
* Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
|
|
*/
|
|
public function bitwise_rightShift(int $shift): BCMath
|
|
{
|
|
$temp = new static();
|
|
$temp->value = bcdiv($this->value, bcpow('2', (string)$shift, 0), 0);
|
|
|
|
return $this->normalize($temp);
|
|
}
|
|
|
|
/**
|
|
* Logical Left Shift
|
|
*
|
|
* Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
|
|
*/
|
|
public function bitwise_leftShift(int $shift): BCMath
|
|
{
|
|
$temp = new static();
|
|
$temp->value = bcmul($this->value, bcpow('2', (string) $shift, 0), 0);
|
|
|
|
return $this->normalize($temp);
|
|
}
|
|
|
|
/**
|
|
* Compares two numbers.
|
|
*
|
|
* Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this
|
|
* is demonstrated thusly:
|
|
*
|
|
* $x > $y: $x->compare($y) > 0
|
|
* $x < $y: $x->compare($y) < 0
|
|
* $x == $y: $x->compare($y) == 0
|
|
*
|
|
* Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y).
|
|
*
|
|
* {@internal Could return $this->subtract($x), but that's not as fast as what we do do.}
|
|
*
|
|
* @return int in case < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
|
|
* @see self::equals()
|
|
*/
|
|
public function compare(BCMath $y): int
|
|
{
|
|
return bccomp($this->value, $y->value, 0);
|
|
}
|
|
|
|
/**
|
|
* Tests the equality of two numbers.
|
|
*
|
|
* If you need to see if one number is greater than or less than another number, use BigInteger::compare()
|
|
*/
|
|
public function equals(BCMath $x): bool
|
|
{
|
|
return $this->value == $x->value;
|
|
}
|
|
|
|
/**
|
|
* Performs modular exponentiation.
|
|
*/
|
|
public function modPow(BCMath $e, BCMath $n): BCMath
|
|
{
|
|
return $this->powModOuter($e, $n);
|
|
}
|
|
|
|
/**
|
|
* Performs modular exponentiation.
|
|
*
|
|
* Alias for modPow().
|
|
*/
|
|
public function powMod(BCMath $e, BCMath $n): BCMath
|
|
{
|
|
return $this->powModOuter($e, $n);
|
|
}
|
|
|
|
/**
|
|
* Performs modular exponentiation.
|
|
*/
|
|
protected function powModInner(BCMath $e, BCMath $n): BCMath
|
|
{
|
|
try {
|
|
$class = static::$modexpEngine[static::class];
|
|
return $class::powModHelper($this, $e, $n, static::class);
|
|
} catch (\Exception $err) {
|
|
return BCMath\DefaultEngine::powModHelper($this, $e, $n, static::class);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Normalize
|
|
*
|
|
* Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
|
|
*/
|
|
protected function normalize(BCMath $result): BCMath
|
|
{
|
|
$result->precision = $this->precision;
|
|
$result->bitmask = $this->bitmask;
|
|
|
|
if ($result->bitmask !== false) {
|
|
$result->value = bcmod($result->value, $result->bitmask->value);
|
|
}
|
|
|
|
return $result;
|
|
}
|
|
|
|
/**
|
|
* Generate a random prime number between a range
|
|
*
|
|
* If there's not a prime within the given range, false will be returned.
|
|
*
|
|
* @return false|BCMath
|
|
*/
|
|
public static function randomRangePrime(BCMath $min, BCMath $max)
|
|
{
|
|
return self::randomRangePrimeOuter($min, $max);
|
|
}
|
|
|
|
/**
|
|
* Generate a random number between a range
|
|
*
|
|
* Returns a random number between $min and $max where $min and $max
|
|
* can be defined using one of the two methods:
|
|
*
|
|
* BigInteger::randomRange($min, $max)
|
|
* BigInteger::randomRange($max, $min)
|
|
*/
|
|
public static function randomRange(BCMath $min, BCMath $max): BCMath
|
|
{
|
|
return self::randomRangeHelper($min, $max);
|
|
}
|
|
|
|
/**
|
|
* Make the current number odd
|
|
*
|
|
* If the current number is odd it'll be unchanged. If it's even, one will be added to it.
|
|
*
|
|
* @see self::randomPrime()
|
|
*/
|
|
protected function make_odd(): void
|
|
{
|
|
if (!$this->isOdd()) {
|
|
$this->value = bcadd($this->value, '1');
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Test the number against small primes.
|
|
*
|
|
* @see self::isPrime()
|
|
*/
|
|
protected function testSmallPrimes(): bool
|
|
{
|
|
if ($this->value === '1') {
|
|
return false;
|
|
}
|
|
if ($this->value === '2') {
|
|
return true;
|
|
}
|
|
if ($this->value[-1] % 2 == 0) {
|
|
return false;
|
|
}
|
|
|
|
$value = $this->value;
|
|
|
|
foreach (self::PRIMES as $prime) {
|
|
$r = bcmod($this->value, (string)$prime);
|
|
if ($r == '0') {
|
|
return $this->value == $prime;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
/**
|
|
* Scan for 1 and right shift by that amount
|
|
*
|
|
* ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
|
|
*
|
|
* @see self::isPrime()
|
|
*/
|
|
public static function scan1divide(BCMath $r): int
|
|
{
|
|
$r_value = &$r->value;
|
|
$s = 0;
|
|
// 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
|
|
while ($r_value[-1] % 2 == 0) {
|
|
$r_value = bcdiv($r_value, '2', 0);
|
|
++$s;
|
|
}
|
|
|
|
return $s;
|
|
}
|
|
|
|
/**
|
|
* Performs exponentiation.
|
|
*/
|
|
public function pow(BCMath $n): BCMath
|
|
{
|
|
$temp = new self();
|
|
$temp->value = bcpow($this->value, $n->value);
|
|
|
|
return $this->normalize($temp);
|
|
}
|
|
|
|
/**
|
|
* Return the minimum BigInteger between an arbitrary number of BigIntegers.
|
|
*/
|
|
public static function min(BCMath ...$nums): BCMath
|
|
{
|
|
return self::minHelper($nums);
|
|
}
|
|
|
|
/**
|
|
* Return the maximum BigInteger between an arbitrary number of BigIntegers.
|
|
*/
|
|
public static function max(BCMath ...$nums): BCMath
|
|
{
|
|
return self::maxHelper($nums);
|
|
}
|
|
|
|
/**
|
|
* Tests BigInteger to see if it is between two integers, inclusive
|
|
*/
|
|
public function between(BCMath $min, BCMath $max): bool
|
|
{
|
|
return $this->compare($min) >= 0 && $this->compare($max) <= 0;
|
|
}
|
|
|
|
/**
|
|
* Set Bitmask
|
|
*
|
|
* @see self::setPrecision()
|
|
*/
|
|
protected static function setBitmask(int $bits): Engine
|
|
{
|
|
$temp = parent::setBitmask($bits);
|
|
return $temp->add(static::$one[static::class]);
|
|
}
|
|
|
|
/**
|
|
* Is Odd?
|
|
*/
|
|
public function isOdd(): bool
|
|
{
|
|
return $this->value[-1] % 2 == 1;
|
|
}
|
|
|
|
/**
|
|
* Tests if a bit is set
|
|
*/
|
|
public function testBit($x): bool
|
|
{
|
|
return bccomp(
|
|
bcmod($this->value, bcpow('2', $x + 1, 0)),
|
|
bcpow('2', $x, 0),
|
|
0
|
|
) >= 0;
|
|
}
|
|
|
|
/**
|
|
* Is Negative?
|
|
*/
|
|
public function isNegative(): bool
|
|
{
|
|
return strlen($this->value) && $this->value[0] == '-';
|
|
}
|
|
|
|
/**
|
|
* Negate
|
|
*
|
|
* Given $k, returns -$k
|
|
*/
|
|
public function negate(): BCMath
|
|
{
|
|
$temp = clone $this;
|
|
|
|
if (!strlen($temp->value)) {
|
|
return $temp;
|
|
}
|
|
|
|
$temp->value = $temp->value[0] == '-' ?
|
|
substr($this->value, 1) :
|
|
'-' . $this->value;
|
|
|
|
return $temp;
|
|
}
|
|
}
|