1<?php 2 3/** 4 * Pure-PHP 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 * Pure-PHP Engine. 23 * 24 * @package PHP 25 * @author Jim Wigginton <terrafrost@php.net> 26 * @access public 27 */ 28abstract class PHP extends Engine 29{ 30 /**#@+ 31 * Array constants 32 * 33 * Rather than create a thousands and thousands of new BigInteger objects in repeated function calls to add() and 34 * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them. 35 * 36 * @access protected 37 */ 38 /** 39 * $result[self::VALUE] contains the value. 40 */ 41 const VALUE = 0; 42 /** 43 * $result[self::SIGN] contains the sign. 44 */ 45 const SIGN = 1; 46 /**#@-*/ 47 48 /** 49 * Karatsuba Cutoff 50 * 51 * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication? 52 * 53 * @access private 54 */ 55 const KARATSUBA_CUTOFF = 25; 56 57 /** 58 * Can Bitwise operations be done fast? 59 * 60 * @see parent::bitwise_leftRotate() 61 * @see parent::bitwise_rightRotate() 62 * @access protected 63 */ 64 const FAST_BITWISE = true; 65 66 /** 67 * Engine Directory 68 * 69 * @see parent::setModExpEngine 70 * @access protected 71 */ 72 const ENGINE_DIR = 'PHP'; 73 74 /** 75 * Default constructor 76 * 77 * @param mixed $x integer Base-10 number or base-$base number if $base set. 78 * @param int $base 79 * @see parent::__construct() 80 * @return \phpseclib3\Math\BigInteger\Engines\PHP 81 */ 82 public function __construct($x = 0, $base = 10) 83 { 84 if (!isset(static::$isValidEngine)) { 85 static::$isValidEngine = static::isValidEngine(); 86 } 87 if (!static::$isValidEngine) { 88 throw new BadConfigurationException(static::class . ' is not setup correctly on this system'); 89 } 90 91 $this->value = []; 92 parent::__construct($x, $base); 93 } 94 95 /** 96 * Initialize a PHP BigInteger Engine instance 97 * 98 * @param int $base 99 * @see parent::__construct() 100 */ 101 protected function initialize($base) 102 { 103 switch (abs($base)) { 104 case 16: 105 $x = (strlen($this->value) & 1) ? '0' . $this->value : $this->value; 106 $temp = new static(Hex::decode($x), 256); 107 $this->value = $temp->value; 108 break; 109 case 10: 110 $temp = new static(); 111 112 $multiplier = new static(); 113 $multiplier->value = [static::MAX10]; 114 115 $x = $this->value; 116 117 if ($x[0] == '-') { 118 $this->is_negative = true; 119 $x = substr($x, 1); 120 } 121 122 $x = str_pad($x, strlen($x) + ((static::MAX10LEN - 1) * strlen($x)) % static::MAX10LEN, 0, STR_PAD_LEFT); 123 while (strlen($x)) { 124 $temp = $temp->multiply($multiplier); 125 $temp = $temp->add(new static($this->int2bytes(substr($x, 0, static::MAX10LEN)), 256)); 126 $x = substr($x, static::MAX10LEN); 127 } 128 129 $this->value = $temp->value; 130 } 131 } 132 133 /** 134 * Pads strings so that unpack may be used on them 135 * 136 * @param string $str 137 * @return string 138 */ 139 protected function pad($str) 140 { 141 $length = strlen($str); 142 143 $pad = 4 - (strlen($str) % 4); 144 145 return str_pad($str, $length + $pad, "\0", STR_PAD_LEFT); 146 } 147 148 /** 149 * Converts a BigInteger to a base-10 number. 150 * 151 * @return string 152 */ 153 public function toString() 154 { 155 if (!count($this->value)) { 156 return '0'; 157 } 158 159 $temp = clone $this; 160 $temp->bitmask = false; 161 $temp->is_negative = false; 162 163 $divisor = new static(); 164 $divisor->value = [static::MAX10]; 165 $result = ''; 166 while (count($temp->value)) { 167 list($temp, $mod) = $temp->divide($divisor); 168 $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', static::MAX10LEN, '0', STR_PAD_LEFT) . $result; 169 } 170 $result = ltrim($result, '0'); 171 if (empty($result)) { 172 $result = '0'; 173 } 174 175 if ($this->is_negative) { 176 $result = '-' . $result; 177 } 178 179 return $result; 180 } 181 182 /** 183 * Converts a BigInteger to a byte string (eg. base-256). 184 * 185 * @param bool $twos_compliment 186 * @return string 187 */ 188 public function toBytes($twos_compliment = false) 189 { 190 if ($twos_compliment) { 191 return $this->toBytesHelper(); 192 } 193 194 if (!count($this->value)) { 195 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; 196 } 197 198 $result = $this->bitwise_small_split(8); 199 $result = implode('', array_map('chr', $result)); 200 201 return $this->precision > 0 ? 202 str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) : 203 $result; 204 } 205 206 /** 207 * Performs addition. 208 * 209 * @param array $x_value 210 * @param bool $x_negative 211 * @param array $y_value 212 * @param bool $y_negative 213 * @return array 214 */ 215 protected static function addHelper(array $x_value, $x_negative, array $y_value, $y_negative) 216 { 217 $x_size = count($x_value); 218 $y_size = count($y_value); 219 220 if ($x_size == 0) { 221 return [ 222 self::VALUE => $y_value, 223 self::SIGN => $y_negative 224 ]; 225 } elseif ($y_size == 0) { 226 return [ 227 self::VALUE => $x_value, 228 self::SIGN => $x_negative 229 ]; 230 } 231 232 // subtract, if appropriate 233 if ($x_negative != $y_negative) { 234 if ($x_value == $y_value) { 235 return [ 236 self::VALUE => [], 237 self::SIGN => false 238 ]; 239 } 240 241 $temp = self::subtractHelper($x_value, false, $y_value, false); 242 $temp[self::SIGN] = self::compareHelper($x_value, false, $y_value, false) > 0 ? 243 $x_negative : $y_negative; 244 245 return $temp; 246 } 247 248 if ($x_size < $y_size) { 249 $size = $x_size; 250 $value = $y_value; 251 } else { 252 $size = $y_size; 253 $value = $x_value; 254 } 255 256 $value[count($value)] = 0; // just in case the carry adds an extra digit 257 258 $carry = 0; 259 for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) { 260 //$sum = $x_value[$j] * static::BASE_FULL + $x_value[$i] + $y_value[$j] * static::BASE_FULL + $y_value[$i] + $carry; 261 $sum = ($x_value[$j] + $y_value[$j]) * static::BASE_FULL + $x_value[$i] + $y_value[$i] + $carry; 262 $carry = $sum >= static::MAX_DIGIT2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1 263 $sum = $carry ? $sum - static::MAX_DIGIT2 : $sum; 264 265 $temp = static::BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31); 266 267 $value[$i] = (int) ($sum - static::BASE_FULL * $temp); // eg. a faster alternative to fmod($sum, 0x4000000) 268 $value[$j] = $temp; 269 } 270 271 if ($j == $size) { // ie. if $y_size is odd 272 $sum = $x_value[$i] + $y_value[$i] + $carry; 273 $carry = $sum >= static::BASE_FULL; 274 $value[$i] = $carry ? $sum - static::BASE_FULL : $sum; 275 ++$i; // ie. let $i = $j since we've just done $value[$i] 276 } 277 278 if ($carry) { 279 for (; $value[$i] == static::MAX_DIGIT; ++$i) { 280 $value[$i] = 0; 281 } 282 ++$value[$i]; 283 } 284 285 return [ 286 self::VALUE => self::trim($value), 287 self::SIGN => $x_negative 288 ]; 289 } 290 291 /** 292 * Performs subtraction. 293 * 294 * @param array $x_value 295 * @param bool $x_negative 296 * @param array $y_value 297 * @param bool $y_negative 298 * @return array 299 */ 300 static function subtractHelper(array $x_value, $x_negative, array $y_value, $y_negative) 301 { 302 $x_size = count($x_value); 303 $y_size = count($y_value); 304 305 if ($x_size == 0) { 306 return [ 307 self::VALUE => $y_value, 308 self::SIGN => !$y_negative 309 ]; 310 } elseif ($y_size == 0) { 311 return [ 312 self::VALUE => $x_value, 313 self::SIGN => $x_negative 314 ]; 315 } 316 317 // add, if appropriate (ie. -$x - +$y or +$x - -$y) 318 if ($x_negative != $y_negative) { 319 $temp = self::addHelper($x_value, false, $y_value, false); 320 $temp[self::SIGN] = $x_negative; 321 322 return $temp; 323 } 324 325 $diff = self::compareHelper($x_value, $x_negative, $y_value, $y_negative); 326 327 if (!$diff) { 328 return [ 329 self::VALUE => [], 330 self::SIGN => false 331 ]; 332 } 333 334 // switch $x and $y around, if appropriate. 335 if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) { 336 $temp = $x_value; 337 $x_value = $y_value; 338 $y_value = $temp; 339 340 $x_negative = !$x_negative; 341 342 $x_size = count($x_value); 343 $y_size = count($y_value); 344 } 345 346 // at this point, $x_value should be at least as big as - if not bigger than - $y_value 347 348 $carry = 0; 349 for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) { 350 $sum = ($x_value[$j] - $y_value[$j]) * static::BASE_FULL + $x_value[$i] - $y_value[$i] - $carry; 351 352 $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1 353 $sum = $carry ? $sum + static::MAX_DIGIT2 : $sum; 354 355 $temp = static::BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31); 356 357 $x_value[$i] = (int) ($sum - static::BASE_FULL * $temp); 358 $x_value[$j] = $temp; 359 } 360 361 if ($j == $y_size) { // ie. if $y_size is odd 362 $sum = $x_value[$i] - $y_value[$i] - $carry; 363 $carry = $sum < 0; 364 $x_value[$i] = $carry ? $sum + static::BASE_FULL : $sum; 365 ++$i; 366 } 367 368 if ($carry) { 369 for (; !$x_value[$i]; ++$i) { 370 $x_value[$i] = static::MAX_DIGIT; 371 } 372 --$x_value[$i]; 373 } 374 375 return [ 376 self::VALUE => self::trim($x_value), 377 self::SIGN => $x_negative 378 ]; 379 } 380 381 /** 382 * Performs multiplication. 383 * 384 * @param array $x_value 385 * @param bool $x_negative 386 * @param array $y_value 387 * @param bool $y_negative 388 * @return array 389 */ 390 protected static function multiplyHelper(array $x_value, $x_negative, array $y_value, $y_negative) 391 { 392 //if ( $x_value == $y_value ) { 393 // return [ 394 // self::VALUE => self::square($x_value), 395 // self::SIGN => $x_sign != $y_value 396 // ]; 397 //} 398 399 $x_length = count($x_value); 400 $y_length = count($y_value); 401 402 if (!$x_length || !$y_length) { // a 0 is being multiplied 403 return [ 404 self::VALUE => [], 405 self::SIGN => false 406 ]; 407 } 408 409 return [ 410 self::VALUE => min($x_length, $y_length) < 2 * self::KARATSUBA_CUTOFF ? 411 self::trim(self::regularMultiply($x_value, $y_value)) : 412 self::trim(self::karatsuba($x_value, $y_value)), 413 self::SIGN => $x_negative != $y_negative 414 ]; 415 } 416 417 /** 418 * Performs Karatsuba multiplication on two BigIntegers 419 * 420 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and 421 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}. 422 * 423 * @param array $x_value 424 * @param array $y_value 425 * @return array 426 */ 427 private static function karatsuba(array $x_value, array $y_value) 428 { 429 $m = min(count($x_value) >> 1, count($y_value) >> 1); 430 431 if ($m < self::KARATSUBA_CUTOFF) { 432 return self::regularMultiply($x_value, $y_value); 433 } 434 435 $x1 = array_slice($x_value, $m); 436 $x0 = array_slice($x_value, 0, $m); 437 $y1 = array_slice($y_value, $m); 438 $y0 = array_slice($y_value, 0, $m); 439 440 $z2 = self::karatsuba($x1, $y1); 441 $z0 = self::karatsuba($x0, $y0); 442 443 $z1 = self::addHelper($x1, false, $x0, false); 444 $temp = self::addHelper($y1, false, $y0, false); 445 $z1 = self::karatsuba($z1[self::VALUE], $temp[self::VALUE]); 446 $temp = self::addHelper($z2, false, $z0, false); 447 $z1 = self::subtractHelper($z1, false, $temp[self::VALUE], false); 448 449 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2); 450 $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]); 451 452 $xy = self::addHelper($z2, false, $z1[self::VALUE], $z1[self::SIGN]); 453 $xy = self::addHelper($xy[self::VALUE], $xy[self::SIGN], $z0, false); 454 455 return $xy[self::VALUE]; 456 } 457 458 /** 459 * Performs long multiplication on two BigIntegers 460 * 461 * Modeled after 'multiply' in MutableBigInteger.java. 462 * 463 * @param array $x_value 464 * @param array $y_value 465 * @return array 466 */ 467 protected static function regularMultiply(array $x_value, array $y_value) 468 { 469 $x_length = count($x_value); 470 $y_length = count($y_value); 471 472 if (!$x_length || !$y_length) { // a 0 is being multiplied 473 return []; 474 } 475 476 $product_value = self::array_repeat(0, $x_length + $y_length); 477 478 // the following for loop could be removed if the for loop following it 479 // (the one with nested for loops) initially set $i to 0, but 480 // doing so would also make the result in one set of unnecessary adds, 481 // since on the outermost loops first pass, $product->value[$k] is going 482 // to always be 0 483 484 $carry = 0; 485 for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0 486 $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0 487 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 488 $product_value[$j] = (int) ($temp - static::BASE_FULL * $carry); 489 } 490 491 $product_value[$j] = $carry; 492 493 // the above for loop is what the previous comment was talking about. the 494 // following for loop is the "one with nested for loops" 495 for ($i = 1; $i < $y_length; ++$i) { 496 $carry = 0; 497 498 for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) { 499 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry; 500 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 501 $product_value[$k] = (int) ($temp - static::BASE_FULL * $carry); 502 } 503 504 $product_value[$k] = $carry; 505 } 506 507 return $product_value; 508 } 509 510 /** 511 * Divides two BigIntegers. 512 * 513 * Returns an array whose first element contains the quotient and whose second element contains the 514 * "common residue". If the remainder would be positive, the "common residue" and the remainder are the 515 * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder 516 * and the divisor (basically, the "common residue" is the first positive modulo). 517 * 518 * @param \phpseclib3\Math\BigInteger\engines\PHP $y 519 * @return array 520 * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}. 521 */ 522 protected function divideHelper(PHP $y) 523 { 524 if (count($y->value) == 1) { 525 list($q, $r) = $this->divide_digit($this->value, $y->value[0]); 526 $quotient = new static(); 527 $remainder = new static(); 528 $quotient->value = $q; 529 $remainder->value = [$r]; 530 $quotient->is_negative = $this->is_negative != $y->is_negative; 531 return [$this->normalize($quotient), $this->normalize($remainder)]; 532 } 533 534 $x = clone $this; 535 $y = clone $y; 536 537 $x_sign = $x->is_negative; 538 $y_sign = $y->is_negative; 539 540 $x->is_negative = $y->is_negative = false; 541 542 $diff = $x->compare($y); 543 544 if (!$diff) { 545 $temp = new static(); 546 $temp->value = [1]; 547 $temp->is_negative = $x_sign != $y_sign; 548 return [$this->normalize($temp), $this->normalize(static::$zero)]; 549 } 550 551 if ($diff < 0) { 552 // if $x is negative, "add" $y. 553 if ($x_sign) { 554 $x = $y->subtract($x); 555 } 556 return [$this->normalize(static::$zero), $this->normalize($x)]; 557 } 558 559 // normalize $x and $y as described in HAC 14.23 / 14.24 560 $msb = $y->value[count($y->value) - 1]; 561 for ($shift = 0; !($msb & static::MSB); ++$shift) { 562 $msb <<= 1; 563 } 564 $x->lshift($shift); 565 $y->lshift($shift); 566 $y_value = &$y->value; 567 568 $x_max = count($x->value) - 1; 569 $y_max = count($y->value) - 1; 570 571 $quotient = new static(); 572 $quotient_value = &$quotient->value; 573 $quotient_value = self::array_repeat(0, $x_max - $y_max + 1); 574 575 static $temp, $lhs, $rhs; 576 if (!isset($temp)) { 577 $temp = new static(); 578 $lhs = new static(); 579 $rhs = new static(); 580 } 581 $temp_value = &$temp->value; 582 $rhs_value = &$rhs->value; 583 584 // $temp = $y << ($x_max - $y_max-1) in base 2**26 585 $temp_value = array_merge(self::array_repeat(0, $x_max - $y_max), $y_value); 586 587 while ($x->compare($temp) >= 0) { 588 // calculate the "common residue" 589 ++$quotient_value[$x_max - $y_max]; 590 $x = $x->subtract($temp); 591 $x_max = count($x->value) - 1; 592 } 593 594 for ($i = $x_max; $i >= $y_max + 1; --$i) { 595 $x_value = &$x->value; 596 $x_window = [ 597 isset($x_value[$i]) ? $x_value[$i] : 0, 598 isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0, 599 isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0 600 ]; 601 $y_window = [ 602 $y_value[$y_max], 603 ($y_max > 0) ? $y_value[$y_max - 1] : 0 604 ]; 605 606 $q_index = $i - $y_max - 1; 607 if ($x_window[0] == $y_window[0]) { 608 $quotient_value[$q_index] = static::MAX_DIGIT; 609 } else { 610 $quotient_value[$q_index] = self::safe_divide( 611 $x_window[0] * static::BASE_FULL + $x_window[1], 612 $y_window[0] 613 ); 614 } 615 616 $temp_value = [$y_window[1], $y_window[0]]; 617 618 $lhs->value = [$quotient_value[$q_index]]; 619 $lhs = $lhs->multiply($temp); 620 621 $rhs_value = [$x_window[2], $x_window[1], $x_window[0]]; 622 623 while ($lhs->compare($rhs) > 0) { 624 --$quotient_value[$q_index]; 625 626 $lhs->value = [$quotient_value[$q_index]]; 627 $lhs = $lhs->multiply($temp); 628 } 629 630 $adjust = self::array_repeat(0, $q_index); 631 $temp_value = [$quotient_value[$q_index]]; 632 $temp = $temp->multiply($y); 633 $temp_value = &$temp->value; 634 if (count($temp_value)) { 635 $temp_value = array_merge($adjust, $temp_value); 636 } 637 638 $x = $x->subtract($temp); 639 640 if ($x->compare(static::$zero) < 0) { 641 $temp_value = array_merge($adjust, $y_value); 642 $x = $x->add($temp); 643 644 --$quotient_value[$q_index]; 645 } 646 647 $x_max = count($x_value) - 1; 648 } 649 650 // unnormalize the remainder 651 $x->rshift($shift); 652 653 $quotient->is_negative = $x_sign != $y_sign; 654 655 // calculate the "common residue", if appropriate 656 if ($x_sign) { 657 $y->rshift($shift); 658 $x = $y->subtract($x); 659 } 660 661 return [$this->normalize($quotient), $this->normalize($x)]; 662 } 663 664 /** 665 * Divides a BigInteger by a regular integer 666 * 667 * abc / x = a00 / x + b0 / x + c / x 668 * 669 * @param array $dividend 670 * @param int $divisor 671 * @return array 672 */ 673 private static function divide_digit(array $dividend, $divisor) 674 { 675 $carry = 0; 676 $result = []; 677 678 for ($i = count($dividend) - 1; $i >= 0; --$i) { 679 $temp = static::BASE_FULL * $carry + $dividend[$i]; 680 $result[$i] = self::safe_divide($temp, $divisor); 681 $carry = (int) ($temp - $divisor * $result[$i]); 682 } 683 684 return [$result, $carry]; 685 } 686 687 /** 688 * Single digit division 689 * 690 * Even if int64 is being used the division operator will return a float64 value 691 * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't 692 * have the precision of int64 this is a problem so, when int64 is being used, 693 * we'll guarantee that the dividend is divisible by first subtracting the remainder. 694 * 695 * @param int $x 696 * @param int $y 697 * @return int 698 */ 699 private static function safe_divide($x, $y) 700 { 701 if (static::BASE === 26) { 702 return (int) ($x / $y); 703 } 704 705 // static::BASE === 31 706 return ($x - ($x % $y)) / $y; 707 } 708 709 /* 710 * Convert an array / boolean to a PHP BigInteger object 711 * 712 * @param array $arr 713 * @return \phpseclib3\Math\BigInteger\Engines\PHP 714 */ 715 protected function convertToObj(array $arr) 716 { 717 $result = new static(); 718 $result->value = $arr[self::VALUE]; 719 $result->is_negative = $arr[self::SIGN]; 720 721 return $this->normalize($result); 722 } 723 724 /** 725 * Normalize 726 * 727 * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision 728 * 729 * @param PHP $result 730 * @return PHP 731 */ 732 protected function normalize(PHP $result) 733 { 734 unset($result->reduce); 735 736 $result->precision = $this->precision; 737 $result->bitmask = $this->bitmask; 738 739 $value = &$result->value; 740 741 if (!count($value)) { 742 $result->is_negative = false; 743 return $result; 744 } 745 746 $value = static::trim($value); 747 748 if (!empty($result->bitmask->value)) { 749 $length = min(count($value), count($result->bitmask->value)); 750 $value = array_slice($value, 0, $length); 751 752 for ($i = 0; $i < $length; ++$i) { 753 $value[$i] = $value[$i] & $result->bitmask->value[$i]; 754 } 755 } 756 757 return $result; 758 } 759 760 /* 761 * Compares two numbers. 762 * 763 * @param array $x_value 764 * @param bool $x_negative 765 * @param array $y_value 766 * @param bool $y_negative 767 * @return int 768 * @see static::compare() 769 */ 770 protected static function compareHelper(array $x_value, $x_negative, array $y_value, $y_negative) 771 { 772 if ($x_negative != $y_negative) { 773 return (!$x_negative && $y_negative) ? 1 : -1; 774 } 775 776 $result = $x_negative ? -1 : 1; 777 778 if (count($x_value) != count($y_value)) { 779 return (count($x_value) > count($y_value)) ? $result : -$result; 780 } 781 $size = max(count($x_value), count($y_value)); 782 783 $x_value = array_pad($x_value, $size, 0); 784 $y_value = array_pad($y_value, $size, 0); 785 786 for ($i = count($x_value) - 1; $i >= 0; --$i) { 787 if ($x_value[$i] != $y_value[$i]) { 788 return ($x_value[$i] > $y_value[$i]) ? $result : -$result; 789 } 790 } 791 792 return 0; 793 } 794 795 /** 796 * Absolute value. 797 * 798 * @return \phpseclib3\Math\BigInteger\Engines\PHP 799 */ 800 public function abs() 801 { 802 $temp = new static(); 803 $temp->value = $this->value; 804 805 return $temp; 806 } 807 808 /** 809 * Trim 810 * 811 * Removes leading zeros 812 * 813 * @param array $value 814 * @return PHP 815 */ 816 protected static function trim(array $value) 817 { 818 for ($i = count($value) - 1; $i >= 0; --$i) { 819 if ($value[$i]) { 820 break; 821 } 822 unset($value[$i]); 823 } 824 825 return $value; 826 } 827 828 /** 829 * Logical Right Shift 830 * 831 * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift. 832 * 833 * @param int $shift 834 * @return \phpseclib3\Math\BigInteger\Engines\PHP 835 */ 836 public function bitwise_rightShift($shift) 837 { 838 $temp = new static(); 839 840 // could just replace lshift with this, but then all lshift() calls would need to be rewritten 841 // and I don't want to do that... 842 $temp->value = $this->value; 843 $temp->rshift($shift); 844 845 return $this->normalize($temp); 846 } 847 848 /** 849 * Logical Left Shift 850 * 851 * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift. 852 * 853 * @param int $shift 854 * @return \phpseclib3\Math\BigInteger\Engines\PHP 855 */ 856 public function bitwise_leftShift($shift) 857 { 858 $temp = new static(); 859 // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten 860 // and I don't want to do that... 861 $temp->value = $this->value; 862 $temp->lshift($shift); 863 864 return $this->normalize($temp); 865 } 866 867 /** 868 * Converts 32-bit integers to bytes. 869 * 870 * @param int $x 871 * @return string 872 */ 873 private static function int2bytes($x) 874 { 875 return ltrim(pack('N', $x), chr(0)); 876 } 877 878 /** 879 * Array Repeat 880 * 881 * @param int $input 882 * @param int $multiplier 883 * @return array 884 */ 885 protected static function array_repeat($input, $multiplier) 886 { 887 return $multiplier ? array_fill(0, $multiplier, $input) : []; 888 } 889 890 /** 891 * Logical Left Shift 892 * 893 * Shifts BigInteger's by $shift bits. 894 * 895 * @param int $shift 896 */ 897 protected function lshift($shift) 898 { 899 if ($shift == 0) { 900 return; 901 } 902 903 $num_digits = (int) ($shift / static::BASE); 904 $shift %= static::BASE; 905 $shift = 1 << $shift; 906 907 $carry = 0; 908 909 for ($i = 0; $i < count($this->value); ++$i) { 910 $temp = $this->value[$i] * $shift + $carry; 911 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 912 $this->value[$i] = (int) ($temp - $carry * static::BASE_FULL); 913 } 914 915 if ($carry) { 916 $this->value[count($this->value)] = $carry; 917 } 918 919 while ($num_digits--) { 920 array_unshift($this->value, 0); 921 } 922 } 923 924 /** 925 * Logical Right Shift 926 * 927 * Shifts BigInteger's by $shift bits. 928 * 929 * @param int $shift 930 */ 931 protected function rshift($shift) 932 { 933 if ($shift == 0) { 934 return; 935 } 936 937 $num_digits = (int) ($shift / static::BASE); 938 $shift %= static::BASE; 939 $carry_shift = static::BASE - $shift; 940 $carry_mask = (1 << $shift) - 1; 941 942 if ($num_digits) { 943 $this->value = array_slice($this->value, $num_digits); 944 } 945 946 $carry = 0; 947 948 for ($i = count($this->value) - 1; $i >= 0; --$i) { 949 $temp = $this->value[$i] >> $shift | $carry; 950 $carry = ($this->value[$i] & $carry_mask) << $carry_shift; 951 $this->value[$i] = $temp; 952 } 953 954 $this->value = static::trim($this->value); 955 } 956 957 /** 958 * Performs modular exponentiation. 959 * 960 * @param PHP $e 961 * @param PHP $n 962 * @return PHP 963 */ 964 protected function powModInner(PHP $e, PHP $n) 965 { 966 try { 967 $class = static::$modexpEngine; 968 return $class::powModHelper($this, $e, $n, static::class); 969 } catch (\Exception $err) { 970 return PHP\DefaultEngine::powModHelper($this, $e, $n, static::class); 971 } 972 } 973 974 /** 975 * Performs squaring 976 * 977 * @param array $x 978 * @return array 979 */ 980 protected static function square(array $x) 981 { 982 return count($x) < 2 * self::KARATSUBA_CUTOFF ? 983 self::trim(self::baseSquare($x)) : 984 self::trim(self::karatsubaSquare($x)); 985 } 986 987 /** 988 * Performs traditional squaring on two BigIntegers 989 * 990 * Squaring can be done faster than multiplying a number by itself can be. See 991 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} / 992 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information. 993 * 994 * @param array $value 995 * @return array 996 */ 997 protected static function baseSquare(array $value) 998 { 999 if (empty($value)) { 1000 return []; 1001 } 1002 $square_value = self::array_repeat(0, 2 * count($value)); 1003 1004 for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) { 1005 $i2 = $i << 1; 1006 1007 $temp = $square_value[$i2] + $value[$i] * $value[$i]; 1008 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 1009 $square_value[$i2] = (int) ($temp - static::BASE_FULL * $carry); 1010 1011 // note how we start from $i+1 instead of 0 as we do in multiplication. 1012 for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) { 1013 $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry; 1014 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 1015 $square_value[$k] = (int) ($temp - static::BASE_FULL * $carry); 1016 } 1017 1018 // the following line can yield values larger 2**15. at this point, PHP should switch 1019 // over to floats. 1020 $square_value[$i + $max_index + 1] = $carry; 1021 } 1022 1023 return $square_value; 1024 } 1025 1026 /** 1027 * Performs Karatsuba "squaring" on two BigIntegers 1028 * 1029 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and 1030 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}. 1031 * 1032 * @param array $value 1033 * @return array 1034 */ 1035 protected static function karatsubaSquare(array $value) 1036 { 1037 $m = count($value) >> 1; 1038 1039 if ($m < self::KARATSUBA_CUTOFF) { 1040 return self::baseSquare($value); 1041 } 1042 1043 $x1 = array_slice($value, $m); 1044 $x0 = array_slice($value, 0, $m); 1045 1046 $z2 = self::karatsubaSquare($x1); 1047 $z0 = self::karatsubaSquare($x0); 1048 1049 $z1 = self::addHelper($x1, false, $x0, false); 1050 $z1 = self::karatsubaSquare($z1[self::VALUE]); 1051 $temp = self::addHelper($z2, false, $z0, false); 1052 $z1 = self::subtractHelper($z1, false, $temp[self::VALUE], false); 1053 1054 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2); 1055 $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]); 1056 1057 $xx = self::addHelper($z2, false, $z1[self::VALUE], $z1[self::SIGN]); 1058 $xx = self::addHelper($xx[self::VALUE], $xx[self::SIGN], $z0, false); 1059 1060 return $xx[self::VALUE]; 1061 } 1062 1063 /** 1064 * Make the current number odd 1065 * 1066 * If the current number is odd it'll be unchanged. If it's even, one will be added to it. 1067 * 1068 * @see self::randomPrime() 1069 */ 1070 protected function make_odd() 1071 { 1072 $this->value[0] |= 1; 1073 } 1074 1075 /** 1076 * Test the number against small primes. 1077 * 1078 * @see self::isPrime() 1079 */ 1080 protected function testSmallPrimes() 1081 { 1082 if ($this->value == [1]) { 1083 return false; 1084 } 1085 if ($this->value == [2]) { 1086 return true; 1087 } 1088 if (~$this->value[0] & 1) { 1089 return false; 1090 } 1091 1092 $value = $this->value; 1093 foreach (static::$primes as $prime) { 1094 list(, $r) = self::divide_digit($value, $prime); 1095 if (!$r) { 1096 return count($value) == 1 && $value[0] == $prime; 1097 } 1098 } 1099 1100 return true; 1101 } 1102 1103 /** 1104 * Scan for 1 and right shift by that amount 1105 * 1106 * ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s)); 1107 * 1108 * @see self::isPrime() 1109 * @param PHP $r 1110 * @return int 1111 */ 1112 public static function scan1divide(PHP $r) 1113 { 1114 $r_value = &$r->value; 1115 for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) { 1116 $temp = ~$r_value[$i] & static::MAX_DIGIT; 1117 for ($j = 1; ($temp >> $j) & 1; ++$j) { 1118 } 1119 if ($j <= static::BASE) { 1120 break; 1121 } 1122 } 1123 $s = static::BASE * $i + $j; 1124 $r->rshift($s); 1125 return $s; 1126 } 1127 1128 /** 1129 * Performs exponentiation. 1130 * 1131 * @param PHP $n 1132 * @return PHP 1133 */ 1134 protected function powHelper(PHP $n) 1135 { 1136 if ($n->compare(static::$zero) == 0) { 1137 return new static(1); 1138 } // n^0 = 1 1139 1140 $temp = clone $this; 1141 while (!$n->equals(static::$one)) { 1142 $temp = $temp->multiply($this); 1143 $n = $n->subtract(static::$one); 1144 } 1145 1146 return $temp; 1147 } 1148 1149 /** 1150 * Is Odd? 1151 * 1152 * @return boolean 1153 */ 1154 public function isOdd() 1155 { 1156 return (bool) ($this->value[0] & 1); 1157 } 1158 1159 /** 1160 * Tests if a bit is set 1161 * 1162 * @return boolean 1163 */ 1164 public function testBit($x) 1165 { 1166 $digit = floor($x / static::BASE); 1167 $bit = $x % static::BASE; 1168 1169 if (!isset($this->value[$digit])) { 1170 return false; 1171 } 1172 1173 return (bool) ($this->value[$digit] & (1 << $bit)); 1174 } 1175 1176 /** 1177 * Is Negative? 1178 * 1179 * @return boolean 1180 */ 1181 public function isNegative() 1182 { 1183 return $this->is_negative; 1184 } 1185 1186 /** 1187 * Negate 1188 * 1189 * Given $k, returns -$k 1190 * 1191 * @return BigInteger 1192 */ 1193 public function negate() 1194 { 1195 $temp = clone $this; 1196 $temp->is_negative = !$temp->is_negative; 1197 1198 return $temp; 1199 } 1200 1201 /** 1202 * Bitwise Split 1203 * 1204 * Splits BigInteger's into chunks of $split bits 1205 * 1206 * @param int $split 1207 * @return \phpseclib3\Math\BigInteger\Engines\PHP[] 1208 */ 1209 public function bitwise_split($split) 1210 { 1211 if ($split < 1) { 1212 throw new \RuntimeException('Offset must be greater than 1'); 1213 } 1214 1215 $width = (int) ($split / static::BASE); 1216 if (!$width) { 1217 $arr = $this->bitwise_small_split($split); 1218 return array_map(function ($digit) { 1219 $temp = new static(); 1220 $temp->value = $digit != 0 ? [$digit] : []; 1221 return $temp; 1222 }, $arr); 1223 } 1224 1225 $vals = []; 1226 $val = $this->value; 1227 1228 $i = $overflow = 0; 1229 $len = count($val); 1230 while ($i < $len) { 1231 $digit = []; 1232 if (!$overflow) { 1233 $digit = array_slice($val, $i, $width); 1234 $i+= $width; 1235 $overflow = $split % static::BASE; 1236 if ($overflow) { 1237 $mask = (1 << $overflow) - 1; 1238 $temp = isset($val[$i]) ? $val[$i] : 0; 1239 $digit[] = $temp & $mask; 1240 } 1241 } else { 1242 $remaining = static::BASE - $overflow; 1243 $tempsplit = $split - $remaining; 1244 $tempwidth = (int) ($tempsplit / static::BASE + 1); 1245 $digit = array_slice($val, $i, $tempwidth); 1246 $i+= $tempwidth; 1247 $tempoverflow = $tempsplit % static::BASE; 1248 if ($tempoverflow) { 1249 $tempmask = (1 << $tempoverflow) - 1; 1250 $temp = isset($val[$i]) ? $val[$i] : 0; 1251 $digit[] = $temp & $tempmask; 1252 } 1253 $newbits = 0; 1254 for ($j = count($digit) - 1; $j >= 0; $j--) { 1255 $temp = $digit[$j] & $mask; 1256 $digit[$j] = ($digit[$j] >> $overflow) | ($newbits << $remaining); 1257 $newbits = $temp; 1258 } 1259 $overflow = $tempoverflow; 1260 $mask = $tempmask; 1261 } 1262 $temp = new static(); 1263 $temp->value = static::trim($digit); 1264 $vals[] = $temp; 1265 } 1266 1267 return array_reverse($vals); 1268 } 1269 1270 /** 1271 * Bitwise Split where $split < static::BASE 1272 * 1273 * @param int $split 1274 * @return \phpseclib3\Math\BigInteger\Engines\PHP[] 1275 */ 1276 private function bitwise_small_split($split) 1277 { 1278 $vals = []; 1279 $val = $this->value; 1280 1281 $mask = (1 << $split) - 1; 1282 1283 $i = $overflow = 0; 1284 $len = count($val); 1285 $val[] = 0; 1286 $remaining = static::BASE; 1287 while ($i != $len) { 1288 $digit = $val[$i] & $mask; 1289 $val[$i]>>= $split; 1290 if (!$overflow) { 1291 $remaining-= $split; 1292 $overflow = $split <= $remaining ? 0 : $split - $remaining; 1293 1294 if (!$remaining) { 1295 $i++; 1296 $remaining = static::BASE; 1297 $overflow = 0; 1298 } 1299 } else if (++$i != $len) { 1300 $tempmask = (1 << $overflow) - 1; 1301 $digit|= ($val[$i] & $tempmask) << $remaining; 1302 $val[$i]>>= $overflow; 1303 $remaining = static::BASE - $overflow; 1304 $overflow = $split <= $remaining ? 0 : $split - $remaining; 1305 } 1306 1307 $vals[] = $digit; 1308 } 1309 1310 while ($vals[count($vals) - 1] == 0) { 1311 unset($vals[count($vals) - 1]); 1312 } 1313 1314 return array_reverse($vals); 1315 } 1316}