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