| [ Index ] |
PHP Cross Reference of DokuWiki |
[Summary view] [Print] [Text view]
1 <?php 2 3 /** 4 * Pure-PHP arbitrary precision integer arithmetic library. 5 * 6 * Supports base-2, base-10, base-16, and base-256 numbers. Uses the GMP or BCMath extensions, if available, 7 * and an internal implementation, otherwise. 8 * 9 * PHP version 5 10 * 11 * {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the 12 * {@link self::MODE_INTERNAL self::MODE_INTERNAL} mode) 13 * 14 * BigInteger uses base-2**26 to perform operations such as multiplication and division and 15 * base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction. Because the largest possible 16 * value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating 17 * point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are 18 * used. As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %, 19 * which only supports integers. Although this fact will slow this library down, the fact that such a high 20 * base is being used should more than compensate. 21 * 22 * Numbers are stored in {@link http://en.wikipedia.org/wiki/Endianness little endian} format. ie. 23 * (new \phpseclib\Math\BigInteger(pow(2, 26)))->value = array(0, 1) 24 * 25 * Useful resources are as follows: 26 * 27 * - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)} 28 * - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)} 29 * - Java's BigInteger classes. See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip 30 * 31 * Here's an example of how to use this library: 32 * <code> 33 * <?php 34 * $a = new \phpseclib\Math\BigInteger(2); 35 * $b = new \phpseclib\Math\BigInteger(3); 36 * 37 * $c = $a->add($b); 38 * 39 * echo $c->toString(); // outputs 5 40 * ?> 41 * </code> 42 * 43 * @category Math 44 * @package BigInteger 45 * @author Jim Wigginton <terrafrost@php.net> 46 * @copyright 2006 Jim Wigginton 47 * @license http://www.opensource.org/licenses/mit-license.html MIT License 48 */ 49 50 namespace phpseclib\Math; 51 52 use phpseclib\Crypt\Random; 53 54 /** 55 * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256 56 * numbers. 57 * 58 * @package BigInteger 59 * @author Jim Wigginton <terrafrost@php.net> 60 * @access public 61 */ 62 class BigInteger 63 { 64 /**#@+ 65 * Reduction constants 66 * 67 * @access private 68 * @see BigInteger::_reduce() 69 */ 70 /** 71 * @see BigInteger::_montgomery() 72 * @see BigInteger::_prepMontgomery() 73 */ 74 const MONTGOMERY = 0; 75 /** 76 * @see BigInteger::_barrett() 77 */ 78 const BARRETT = 1; 79 /** 80 * @see BigInteger::_mod2() 81 */ 82 const POWEROF2 = 2; 83 /** 84 * @see BigInteger::_remainder() 85 */ 86 const CLASSIC = 3; 87 /** 88 * @see BigInteger::__clone() 89 */ 90 const NONE = 4; 91 /**#@-*/ 92 93 /**#@+ 94 * Array constants 95 * 96 * Rather than create a thousands and thousands of new BigInteger objects in repeated function calls to add() and 97 * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them. 98 * 99 * @access private 100 */ 101 /** 102 * $result[self::VALUE] contains the value. 103 */ 104 const VALUE = 0; 105 /** 106 * $result[self::SIGN] contains the sign. 107 */ 108 const SIGN = 1; 109 /**#@-*/ 110 111 /**#@+ 112 * @access private 113 * @see BigInteger::_montgomery() 114 * @see BigInteger::_barrett() 115 */ 116 /** 117 * Cache constants 118 * 119 * $cache[self::VARIABLE] tells us whether or not the cached data is still valid. 120 */ 121 const VARIABLE = 0; 122 /** 123 * $cache[self::DATA] contains the cached data. 124 */ 125 const DATA = 1; 126 /**#@-*/ 127 128 /**#@+ 129 * Mode constants. 130 * 131 * @access private 132 * @see BigInteger::__construct() 133 */ 134 /** 135 * To use the pure-PHP implementation 136 */ 137 const MODE_INTERNAL = 1; 138 /** 139 * To use the BCMath library 140 * 141 * (if enabled; otherwise, the internal implementation will be used) 142 */ 143 const MODE_BCMATH = 2; 144 /** 145 * To use the GMP library 146 * 147 * (if present; otherwise, either the BCMath or the internal implementation will be used) 148 */ 149 const MODE_GMP = 3; 150 /**#@-*/ 151 152 /** 153 * Karatsuba Cutoff 154 * 155 * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication? 156 * 157 * @access private 158 */ 159 const KARATSUBA_CUTOFF = 25; 160 161 /**#@+ 162 * Static properties used by the pure-PHP implementation. 163 * 164 * @see __construct() 165 */ 166 protected static $base; 167 protected static $baseFull; 168 protected static $maxDigit; 169 protected static $msb; 170 171 /** 172 * $max10 in greatest $max10Len satisfying 173 * $max10 = 10**$max10Len <= 2**$base. 174 */ 175 protected static $max10; 176 177 /** 178 * $max10Len in greatest $max10Len satisfying 179 * $max10 = 10**$max10Len <= 2**$base. 180 */ 181 protected static $max10Len; 182 protected static $maxDigit2; 183 /**#@-*/ 184 185 /** 186 * Holds the BigInteger's value. 187 * 188 * @var array 189 * @access private 190 */ 191 var $value; 192 193 /** 194 * Holds the BigInteger's magnitude. 195 * 196 * @var bool 197 * @access private 198 */ 199 var $is_negative = false; 200 201 /** 202 * Precision 203 * 204 * @see self::setPrecision() 205 * @access private 206 */ 207 var $precision = -1; 208 209 /** 210 * Precision Bitmask 211 * 212 * @see self::setPrecision() 213 * @access private 214 */ 215 var $bitmask = false; 216 217 /** 218 * Mode independent value used for serialization. 219 * 220 * If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for 221 * a variable that'll be serializable regardless of whether or not extensions are being used. Unlike $this->value, 222 * however, $this->hex is only calculated when $this->__sleep() is called. 223 * 224 * @see self::__sleep() 225 * @see self::__wakeup() 226 * @var string 227 * @access private 228 */ 229 var $hex; 230 231 /** 232 * Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers. 233 * 234 * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using 235 * two's compliment. The sole exception to this is -10, which is treated the same as 10 is. 236 * 237 * Here's an example: 238 * <code> 239 * <?php 240 * $a = new \phpseclib\Math\BigInteger('0x32', 16); // 50 in base-16 241 * 242 * echo $a->toString(); // outputs 50 243 * ?> 244 * </code> 245 * 246 * @param int|string|resource $x base-10 number or base-$base number if $base set. 247 * @param int $base 248 * @return \phpseclib\Math\BigInteger 249 * @access public 250 */ 251 function __construct($x = 0, $base = 10) 252 { 253 if (!defined('MATH_BIGINTEGER_MODE')) { 254 switch (true) { 255 case extension_loaded('gmp'): 256 define('MATH_BIGINTEGER_MODE', self::MODE_GMP); 257 break; 258 case extension_loaded('bcmath'): 259 define('MATH_BIGINTEGER_MODE', self::MODE_BCMATH); 260 break; 261 default: 262 define('MATH_BIGINTEGER_MODE', self::MODE_INTERNAL); 263 } 264 } 265 266 if (extension_loaded('openssl') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) { 267 // some versions of XAMPP have mismatched versions of OpenSSL which causes it not to work 268 $versions = array(); 269 270 // avoid generating errors (even with suppression) when phpinfo() is disabled (common in production systems) 271 if (function_exists('phpinfo')) { 272 ob_start(); 273 @phpinfo(); 274 $content = ob_get_contents(); 275 ob_end_clean(); 276 277 preg_match_all('#OpenSSL (Header|Library) Version(.*)#im', $content, $matches); 278 279 if (!empty($matches[1])) { 280 for ($i = 0; $i < count($matches[1]); $i++) { 281 $fullVersion = trim(str_replace('=>', '', strip_tags($matches[2][$i]))); 282 283 // Remove letter part in OpenSSL version 284 if (!preg_match('/(\d+\.\d+\.\d+)/i', $fullVersion, $m)) { 285 $versions[$matches[1][$i]] = $fullVersion; 286 } else { 287 $versions[$matches[1][$i]] = $m[0]; 288 } 289 } 290 } 291 } 292 293 // it doesn't appear that OpenSSL versions were reported upon until PHP 5.3+ 294 switch (true) { 295 case !isset($versions['Header']): 296 case !isset($versions['Library']): 297 case $versions['Header'] == $versions['Library']: 298 case version_compare($versions['Header'], '1.0.0') >= 0 && version_compare($versions['Library'], '1.0.0') >= 0: 299 define('MATH_BIGINTEGER_OPENSSL_ENABLED', true); 300 break; 301 default: 302 define('MATH_BIGINTEGER_OPENSSL_DISABLE', true); 303 } 304 } 305 306 if (!defined('PHP_INT_SIZE')) { 307 define('PHP_INT_SIZE', 4); 308 } 309 310 if (empty(self::$base) && MATH_BIGINTEGER_MODE == self::MODE_INTERNAL) { 311 switch (PHP_INT_SIZE) { 312 case 8: // use 64-bit integers if int size is 8 bytes 313 self::$base = 31; 314 self::$baseFull = 0x80000000; 315 self::$maxDigit = 0x7FFFFFFF; 316 self::$msb = 0x40000000; 317 self::$max10 = 1000000000; 318 self::$max10Len = 9; 319 self::$maxDigit2 = pow(2, 62); 320 break; 321 //case 4: // use 64-bit floats if int size is 4 bytes 322 default: 323 self::$base = 26; 324 self::$baseFull = 0x4000000; 325 self::$maxDigit = 0x3FFFFFF; 326 self::$msb = 0x2000000; 327 self::$max10 = 10000000; 328 self::$max10Len = 7; 329 self::$maxDigit2 = pow(2, 52); // pow() prevents truncation 330 } 331 } 332 333 switch (MATH_BIGINTEGER_MODE) { 334 case self::MODE_GMP: 335 switch (true) { 336 case is_resource($x) && get_resource_type($x) == 'GMP integer': 337 // PHP 5.6 switched GMP from using resources to objects 338 case $x instanceof \GMP: 339 $this->value = $x; 340 return; 341 } 342 $this->value = gmp_init(0); 343 break; 344 case self::MODE_BCMATH: 345 $this->value = '0'; 346 break; 347 default: 348 $this->value = array(); 349 } 350 351 // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48 352 // '0' is the only value like this per http://php.net/empty 353 if (empty($x) && (abs($base) != 256 || $x !== '0')) { 354 return; 355 } 356 357 switch ($base) { 358 case -256: 359 if (ord($x[0]) & 0x80) { 360 $x = ~$x; 361 $this->is_negative = true; 362 } 363 case 256: 364 switch (MATH_BIGINTEGER_MODE) { 365 case self::MODE_GMP: 366 $this->value = function_exists('gmp_import') ? 367 gmp_import($x) : 368 gmp_init('0x' . bin2hex($x)); 369 if ($this->is_negative) { 370 $this->value = gmp_neg($this->value); 371 } 372 break; 373 case self::MODE_BCMATH: 374 // round $len to the nearest 4 (thanks, DavidMJ!) 375 $len = (strlen($x) + 3) & ~3; 376 377 $x = str_pad($x, $len, chr(0), STR_PAD_LEFT); 378 379 for ($i = 0; $i < $len; $i+= 4) { 380 $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32 381 $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])), 0); 382 } 383 384 if ($this->is_negative) { 385 $this->value = '-' . $this->value; 386 } 387 388 break; 389 // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb) 390 default: 391 while (strlen($x)) { 392 $this->value[] = $this->_bytes2int($this->_base256_rshift($x, self::$base)); 393 } 394 } 395 396 if ($this->is_negative) { 397 if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) { 398 $this->is_negative = false; 399 } 400 $temp = $this->add(new static('-1')); 401 $this->value = $temp->value; 402 } 403 break; 404 case 16: 405 case -16: 406 if ($base > 0 && $x[0] == '-') { 407 $this->is_negative = true; 408 $x = substr($x, 1); 409 } 410 411 $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#s', '$1', $x); 412 413 $is_negative = false; 414 if ($base < 0 && hexdec($x[0]) >= 8) { 415 $this->is_negative = $is_negative = true; 416 $x = bin2hex(~pack('H*', $x)); 417 } 418 419 switch (MATH_BIGINTEGER_MODE) { 420 case self::MODE_GMP: 421 $temp = $this->is_negative ? '-0x' . $x : '0x' . $x; 422 $this->value = gmp_init($temp); 423 $this->is_negative = false; 424 break; 425 case self::MODE_BCMATH: 426 $x = (strlen($x) & 1) ? '0' . $x : $x; 427 $temp = new static(pack('H*', $x), 256); 428 $this->value = $this->is_negative ? '-' . $temp->value : $temp->value; 429 $this->is_negative = false; 430 break; 431 default: 432 $x = (strlen($x) & 1) ? '0' . $x : $x; 433 $temp = new static(pack('H*', $x), 256); 434 $this->value = $temp->value; 435 } 436 437 if ($is_negative) { 438 $temp = $this->add(new static('-1')); 439 $this->value = $temp->value; 440 } 441 break; 442 case 10: 443 case -10: 444 // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that 445 // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals) 446 // [^-0-9].*: find any non-numeric characters and then any characters that follow that 447 $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#s', '', $x); 448 if (!strlen($x) || $x == '-') { 449 $x = '0'; 450 } 451 452 switch (MATH_BIGINTEGER_MODE) { 453 case self::MODE_GMP: 454 $this->value = gmp_init($x); 455 break; 456 case self::MODE_BCMATH: 457 // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different 458 // results then doing it on '-1' does (modInverse does $x[0]) 459 $this->value = $x === '-' ? '0' : (string) $x; 460 break; 461 default: 462 $temp = new static(); 463 464 $multiplier = new static(); 465 $multiplier->value = array(self::$max10); 466 467 if ($x[0] == '-') { 468 $this->is_negative = true; 469 $x = substr($x, 1); 470 } 471 472 $x = str_pad($x, strlen($x) + ((self::$max10Len - 1) * strlen($x)) % self::$max10Len, 0, STR_PAD_LEFT); 473 while (strlen($x)) { 474 $temp = $temp->multiply($multiplier); 475 $temp = $temp->add(new static($this->_int2bytes(substr($x, 0, self::$max10Len)), 256)); 476 $x = substr($x, self::$max10Len); 477 } 478 479 $this->value = $temp->value; 480 } 481 break; 482 case 2: // base-2 support originally implemented by Lluis Pamies - thanks! 483 case -2: 484 if ($base > 0 && $x[0] == '-') { 485 $this->is_negative = true; 486 $x = substr($x, 1); 487 } 488 489 $x = preg_replace('#^([01]*).*#s', '$1', $x); 490 $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT); 491 492 $str = '0x'; 493 while (strlen($x)) { 494 $part = substr($x, 0, 4); 495 $str.= dechex(bindec($part)); 496 $x = substr($x, 4); 497 } 498 499 if ($this->is_negative) { 500 $str = '-' . $str; 501 } 502 503 $temp = new static($str, 8 * $base); // ie. either -16 or +16 504 $this->value = $temp->value; 505 $this->is_negative = $temp->is_negative; 506 507 break; 508 default: 509 // base not supported, so we'll let $this == 0 510 } 511 } 512 513 /** 514 * Converts a BigInteger to a byte string (eg. base-256). 515 * 516 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're 517 * saved as two's compliment. 518 * 519 * Here's an example: 520 * <code> 521 * <?php 522 * $a = new \phpseclib\Math\BigInteger('65'); 523 * 524 * echo $a->toBytes(); // outputs chr(65) 525 * ?> 526 * </code> 527 * 528 * @param bool $twos_compliment 529 * @return string 530 * @access public 531 * @internal Converts a base-2**26 number to base-2**8 532 */ 533 function toBytes($twos_compliment = false) 534 { 535 if ($twos_compliment) { 536 $comparison = $this->compare(new static()); 537 if ($comparison == 0) { 538 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; 539 } 540 541 $temp = $comparison < 0 ? $this->add(new static(1)) : $this->copy(); 542 $bytes = $temp->toBytes(); 543 544 if (!strlen($bytes)) { // eg. if the number we're trying to convert is -1 545 $bytes = chr(0); 546 } 547 548 if ($this->precision <= 0 && (ord($bytes[0]) & 0x80)) { 549 $bytes = chr(0) . $bytes; 550 } 551 552 return $comparison < 0 ? ~$bytes : $bytes; 553 } 554 555 switch (MATH_BIGINTEGER_MODE) { 556 case self::MODE_GMP: 557 if (gmp_cmp($this->value, gmp_init(0)) == 0) { 558 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; 559 } 560 561 if (function_exists('gmp_export')) { 562 $temp = gmp_export($this->value); 563 } else { 564 $temp = gmp_strval(gmp_abs($this->value), 16); 565 $temp = (strlen($temp) & 1) ? '0' . $temp : $temp; 566 $temp = pack('H*', $temp); 567 } 568 569 return $this->precision > 0 ? 570 substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) : 571 ltrim($temp, chr(0)); 572 case self::MODE_BCMATH: 573 if ($this->value === '0') { 574 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; 575 } 576 577 $value = ''; 578 $current = $this->value; 579 580 if ($current[0] == '-') { 581 $current = substr($current, 1); 582 } 583 584 while (bccomp($current, '0', 0) > 0) { 585 $temp = bcmod($current, '16777216'); 586 $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value; 587 $current = bcdiv($current, '16777216', 0); 588 } 589 590 return $this->precision > 0 ? 591 substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) : 592 ltrim($value, chr(0)); 593 } 594 595 if (!count($this->value)) { 596 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; 597 } 598 $result = $this->_int2bytes($this->value[count($this->value) - 1]); 599 600 $temp = $this->copy(); 601 602 for ($i = count($temp->value) - 2; $i >= 0; --$i) { 603 $temp->_base256_lshift($result, self::$base); 604 $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT); 605 } 606 607 return $this->precision > 0 ? 608 str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) : 609 $result; 610 } 611 612 /** 613 * Converts a BigInteger to a hex string (eg. base-16)). 614 * 615 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're 616 * saved as two's compliment. 617 * 618 * Here's an example: 619 * <code> 620 * <?php 621 * $a = new \phpseclib\Math\BigInteger('65'); 622 * 623 * echo $a->toHex(); // outputs '41' 624 * ?> 625 * </code> 626 * 627 * @param bool $twos_compliment 628 * @return string 629 * @access public 630 * @internal Converts a base-2**26 number to base-2**8 631 */ 632 function toHex($twos_compliment = false) 633 { 634 return bin2hex($this->toBytes($twos_compliment)); 635 } 636 637 /** 638 * Converts a BigInteger to a bit string (eg. base-2). 639 * 640 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're 641 * saved as two's compliment. 642 * 643 * Here's an example: 644 * <code> 645 * <?php 646 * $a = new \phpseclib\Math\BigInteger('65'); 647 * 648 * echo $a->toBits(); // outputs '1000001' 649 * ?> 650 * </code> 651 * 652 * @param bool $twos_compliment 653 * @return string 654 * @access public 655 * @internal Converts a base-2**26 number to base-2**2 656 */ 657 function toBits($twos_compliment = false) 658 { 659 $hex = $this->toHex($twos_compliment); 660 $bits = ''; 661 for ($i = strlen($hex) - 6, $start = strlen($hex) % 6; $i >= $start; $i-=6) { 662 $bits = str_pad(decbin(hexdec(substr($hex, $i, 6))), 24, '0', STR_PAD_LEFT) . $bits; 663 } 664 if ($start) { // hexdec('') == 0 665 $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8 * $start, '0', STR_PAD_LEFT) . $bits; 666 } 667 $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0'); 668 669 if ($twos_compliment && $this->compare(new static()) > 0 && $this->precision <= 0) { 670 return '0' . $result; 671 } 672 673 return $result; 674 } 675 676 /** 677 * Converts a BigInteger to a base-10 number. 678 * 679 * Here's an example: 680 * <code> 681 * <?php 682 * $a = new \phpseclib\Math\BigInteger('50'); 683 * 684 * echo $a->toString(); // outputs 50 685 * ?> 686 * </code> 687 * 688 * @return string 689 * @access public 690 * @internal Converts a base-2**26 number to base-10**7 (which is pretty much base-10) 691 */ 692 function toString() 693 { 694 switch (MATH_BIGINTEGER_MODE) { 695 case self::MODE_GMP: 696 return gmp_strval($this->value); 697 case self::MODE_BCMATH: 698 if ($this->value === '0') { 699 return '0'; 700 } 701 702 return ltrim($this->value, '0'); 703 } 704 705 if (!count($this->value)) { 706 return '0'; 707 } 708 709 $temp = $this->copy(); 710 $temp->bitmask = false; 711 $temp->is_negative = false; 712 713 $divisor = new static(); 714 $divisor->value = array(self::$max10); 715 $result = ''; 716 while (count($temp->value)) { 717 list($temp, $mod) = $temp->divide($divisor); 718 $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', self::$max10Len, '0', STR_PAD_LEFT) . $result; 719 } 720 $result = ltrim($result, '0'); 721 if (empty($result)) { 722 $result = '0'; 723 } 724 725 if ($this->is_negative) { 726 $result = '-' . $result; 727 } 728 729 return $result; 730 } 731 732 /** 733 * Copy an object 734 * 735 * PHP5 passes objects by reference while PHP4 passes by value. As such, we need a function to guarantee 736 * that all objects are passed by value, when appropriate. More information can be found here: 737 * 738 * {@link http://php.net/language.oop5.basic#51624} 739 * 740 * @access public 741 * @see self::__clone() 742 * @return \phpseclib\Math\BigInteger 743 */ 744 function copy() 745 { 746 $temp = new static(); 747 $temp->value = $this->value; 748 $temp->is_negative = $this->is_negative; 749 $temp->precision = $this->precision; 750 $temp->bitmask = $this->bitmask; 751 return $temp; 752 } 753 754 /** 755 * __toString() magic method 756 * 757 * Will be called, automatically, if you're supporting just PHP5. If you're supporting PHP4, you'll need to call 758 * toString(). 759 * 760 * @access public 761 * @internal Implemented per a suggestion by Techie-Michael - thanks! 762 */ 763 function __toString() 764 { 765 return $this->toString(); 766 } 767 768 /** 769 * __clone() magic method 770 * 771 * Although you can call BigInteger::__toString() directly in PHP5, you cannot call BigInteger::__clone() directly 772 * in PHP5. You can in PHP4 since it's not a magic method, but in PHP5, you have to call it by using the PHP5 773 * only syntax of $y = clone $x. As such, if you're trying to write an application that works on both PHP4 and 774 * PHP5, call BigInteger::copy(), instead. 775 * 776 * @access public 777 * @see self::copy() 778 * @return \phpseclib\Math\BigInteger 779 */ 780 function __clone() 781 { 782 return $this->copy(); 783 } 784 785 /** 786 * __sleep() magic method 787 * 788 * Will be called, automatically, when serialize() is called on a BigInteger object. 789 * 790 * @see self::__wakeup() 791 * @access public 792 */ 793 function __sleep() 794 { 795 $this->hex = $this->toHex(true); 796 $vars = array('hex'); 797 if ($this->precision > 0) { 798 $vars[] = 'precision'; 799 } 800 return $vars; 801 } 802 803 /** 804 * __wakeup() magic method 805 * 806 * Will be called, automatically, when unserialize() is called on a BigInteger object. 807 * 808 * @see self::__sleep() 809 * @access public 810 */ 811 function __wakeup() 812 { 813 $temp = new static($this->hex, -16); 814 $this->value = $temp->value; 815 $this->is_negative = $temp->is_negative; 816 if ($this->precision > 0) { 817 // recalculate $this->bitmask 818 $this->setPrecision($this->precision); 819 } 820 } 821 822 /** 823 * __debugInfo() magic method 824 * 825 * Will be called, automatically, when print_r() or var_dump() are called 826 * 827 * @access public 828 */ 829 function __debugInfo() 830 { 831 $opts = array(); 832 switch (MATH_BIGINTEGER_MODE) { 833 case self::MODE_GMP: 834 $engine = 'gmp'; 835 break; 836 case self::MODE_BCMATH: 837 $engine = 'bcmath'; 838 break; 839 case self::MODE_INTERNAL: 840 $engine = 'internal'; 841 $opts[] = PHP_INT_SIZE == 8 ? '64-bit' : '32-bit'; 842 } 843 if (MATH_BIGINTEGER_MODE != self::MODE_GMP && defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) { 844 $opts[] = 'OpenSSL'; 845 } 846 if (!empty($opts)) { 847 $engine.= ' (' . implode('.', $opts) . ')'; 848 } 849 return array( 850 'value' => '0x' . $this->toHex(true), 851 'engine' => $engine 852 ); 853 } 854 855 /** 856 * Adds two BigIntegers. 857 * 858 * Here's an example: 859 * <code> 860 * <?php 861 * $a = new \phpseclib\Math\BigInteger('10'); 862 * $b = new \phpseclib\Math\BigInteger('20'); 863 * 864 * $c = $a->add($b); 865 * 866 * echo $c->toString(); // outputs 30 867 * ?> 868 * </code> 869 * 870 * @param \phpseclib\Math\BigInteger $y 871 * @return \phpseclib\Math\BigInteger 872 * @access public 873 * @internal Performs base-2**52 addition 874 */ 875 function add($y) 876 { 877 switch (MATH_BIGINTEGER_MODE) { 878 case self::MODE_GMP: 879 $temp = new static(); 880 $temp->value = gmp_add($this->value, $y->value); 881 882 return $this->_normalize($temp); 883 case self::MODE_BCMATH: 884 $temp = new static(); 885 $temp->value = bcadd($this->value, $y->value, 0); 886 887 return $this->_normalize($temp); 888 } 889 890 $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative); 891 892 $result = new static(); 893 $result->value = $temp[self::VALUE]; 894 $result->is_negative = $temp[self::SIGN]; 895 896 return $this->_normalize($result); 897 } 898 899 /** 900 * Performs addition. 901 * 902 * @param array $x_value 903 * @param bool $x_negative 904 * @param array $y_value 905 * @param bool $y_negative 906 * @return array 907 * @access private 908 */ 909 function _add($x_value, $x_negative, $y_value, $y_negative) 910 { 911 $x_size = count($x_value); 912 $y_size = count($y_value); 913 914 if ($x_size == 0) { 915 return array( 916 self::VALUE => $y_value, 917 self::SIGN => $y_negative 918 ); 919 } elseif ($y_size == 0) { 920 return array( 921 self::VALUE => $x_value, 922 self::SIGN => $x_negative 923 ); 924 } 925 926 // subtract, if appropriate 927 if ($x_negative != $y_negative) { 928 if ($x_value == $y_value) { 929 return array( 930 self::VALUE => array(), 931 self::SIGN => false 932 ); 933 } 934 935 $temp = $this->_subtract($x_value, false, $y_value, false); 936 $temp[self::SIGN] = $this->_compare($x_value, false, $y_value, false) > 0 ? 937 $x_negative : $y_negative; 938 939 return $temp; 940 } 941 942 if ($x_size < $y_size) { 943 $size = $x_size; 944 $value = $y_value; 945 } else { 946 $size = $y_size; 947 $value = $x_value; 948 } 949 950 $value[count($value)] = 0; // just in case the carry adds an extra digit 951 952 $carry = 0; 953 for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) { 954 $sum = $x_value[$j] * self::$baseFull + $x_value[$i] + $y_value[$j] * self::$baseFull + $y_value[$i] + $carry; 955 $carry = $sum >= self::$maxDigit2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1 956 $sum = $carry ? $sum - self::$maxDigit2 : $sum; 957 958 $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31); 959 960 $value[$i] = (int) ($sum - self::$baseFull * $temp); // eg. a faster alternative to fmod($sum, 0x4000000) 961 $value[$j] = $temp; 962 } 963 964 if ($j == $size) { // ie. if $y_size is odd 965 $sum = $x_value[$i] + $y_value[$i] + $carry; 966 $carry = $sum >= self::$baseFull; 967 $value[$i] = $carry ? $sum - self::$baseFull : $sum; 968 ++$i; // ie. let $i = $j since we've just done $value[$i] 969 } 970 971 if ($carry) { 972 for (; $value[$i] == self::$maxDigit; ++$i) { 973 $value[$i] = 0; 974 } 975 ++$value[$i]; 976 } 977 978 return array( 979 self::VALUE => $this->_trim($value), 980 self::SIGN => $x_negative 981 ); 982 } 983 984 /** 985 * Subtracts two BigIntegers. 986 * 987 * Here's an example: 988 * <code> 989 * <?php 990 * $a = new \phpseclib\Math\BigInteger('10'); 991 * $b = new \phpseclib\Math\BigInteger('20'); 992 * 993 * $c = $a->subtract($b); 994 * 995 * echo $c->toString(); // outputs -10 996 * ?> 997 * </code> 998 * 999 * @param \phpseclib\Math\BigInteger $y 1000 * @return \phpseclib\Math\BigInteger 1001 * @access public 1002 * @internal Performs base-2**52 subtraction 1003 */ 1004 function subtract($y) 1005 { 1006 switch (MATH_BIGINTEGER_MODE) { 1007 case self::MODE_GMP: 1008 $temp = new static(); 1009 $temp->value = gmp_sub($this->value, $y->value); 1010 1011 return $this->_normalize($temp); 1012 case self::MODE_BCMATH: 1013 $temp = new static(); 1014 $temp->value = bcsub($this->value, $y->value, 0); 1015 1016 return $this->_normalize($temp); 1017 } 1018 1019 $temp = $this->_subtract($this->value, $this->is_negative, $y->value, $y->is_negative); 1020 1021 $result = new static(); 1022 $result->value = $temp[self::VALUE]; 1023 $result->is_negative = $temp[self::SIGN]; 1024 1025 return $this->_normalize($result); 1026 } 1027 1028 /** 1029 * Performs subtraction. 1030 * 1031 * @param array $x_value 1032 * @param bool $x_negative 1033 * @param array $y_value 1034 * @param bool $y_negative 1035 * @return array 1036 * @access private 1037 */ 1038 function _subtract($x_value, $x_negative, $y_value, $y_negative) 1039 { 1040 $x_size = count($x_value); 1041 $y_size = count($y_value); 1042 1043 if ($x_size == 0) { 1044 return array( 1045 self::VALUE => $y_value, 1046 self::SIGN => !$y_negative 1047 ); 1048 } elseif ($y_size == 0) { 1049 return array( 1050 self::VALUE => $x_value, 1051 self::SIGN => $x_negative 1052 ); 1053 } 1054 1055 // add, if appropriate (ie. -$x - +$y or +$x - -$y) 1056 if ($x_negative != $y_negative) { 1057 $temp = $this->_add($x_value, false, $y_value, false); 1058 $temp[self::SIGN] = $x_negative; 1059 1060 return $temp; 1061 } 1062 1063 $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative); 1064 1065 if (!$diff) { 1066 return array( 1067 self::VALUE => array(), 1068 self::SIGN => false 1069 ); 1070 } 1071 1072 // switch $x and $y around, if appropriate. 1073 if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) { 1074 $temp = $x_value; 1075 $x_value = $y_value; 1076 $y_value = $temp; 1077 1078 $x_negative = !$x_negative; 1079 1080 $x_size = count($x_value); 1081 $y_size = count($y_value); 1082 } 1083 1084 // at this point, $x_value should be at least as big as - if not bigger than - $y_value 1085 1086 $carry = 0; 1087 for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) { 1088 $sum = $x_value[$j] * self::$baseFull + $x_value[$i] - $y_value[$j] * self::$baseFull - $y_value[$i] - $carry; 1089 $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1 1090 $sum = $carry ? $sum + self::$maxDigit2 : $sum; 1091 1092 $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31); 1093 1094 $x_value[$i] = (int) ($sum - self::$baseFull * $temp); 1095 $x_value[$j] = $temp; 1096 } 1097 1098 if ($j == $y_size) { // ie. if $y_size is odd 1099 $sum = $x_value[$i] - $y_value[$i] - $carry; 1100 $carry = $sum < 0; 1101 $x_value[$i] = $carry ? $sum + self::$baseFull : $sum; 1102 ++$i; 1103 } 1104 1105 if ($carry) { 1106 for (; !$x_value[$i]; ++$i) { 1107 $x_value[$i] = self::$maxDigit; 1108 } 1109 --$x_value[$i]; 1110 } 1111 1112 return array( 1113 self::VALUE => $this->_trim($x_value), 1114 self::SIGN => $x_negative 1115 ); 1116 } 1117 1118 /** 1119 * Multiplies two BigIntegers 1120 * 1121 * Here's an example: 1122 * <code> 1123 * <?php 1124 * $a = new \phpseclib\Math\BigInteger('10'); 1125 * $b = new \phpseclib\Math\BigInteger('20'); 1126 * 1127 * $c = $a->multiply($b); 1128 * 1129 * echo $c->toString(); // outputs 200 1130 * ?> 1131 * </code> 1132 * 1133 * @param \phpseclib\Math\BigInteger $x 1134 * @return \phpseclib\Math\BigInteger 1135 * @access public 1136 */ 1137 function multiply($x) 1138 { 1139 switch (MATH_BIGINTEGER_MODE) { 1140 case self::MODE_GMP: 1141 $temp = new static(); 1142 $temp->value = gmp_mul($this->value, $x->value); 1143 1144 return $this->_normalize($temp); 1145 case self::MODE_BCMATH: 1146 $temp = new static(); 1147 $temp->value = bcmul($this->value, $x->value, 0); 1148 1149 return $this->_normalize($temp); 1150 } 1151 1152 $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative); 1153 1154 $product = new static(); 1155 $product->value = $temp[self::VALUE]; 1156 $product->is_negative = $temp[self::SIGN]; 1157 1158 return $this->_normalize($product); 1159 } 1160 1161 /** 1162 * Performs multiplication. 1163 * 1164 * @param array $x_value 1165 * @param bool $x_negative 1166 * @param array $y_value 1167 * @param bool $y_negative 1168 * @return array 1169 * @access private 1170 */ 1171 function _multiply($x_value, $x_negative, $y_value, $y_negative) 1172 { 1173 //if ( $x_value == $y_value ) { 1174 // return array( 1175 // self::VALUE => $this->_square($x_value), 1176 // self::SIGN => $x_sign != $y_value 1177 // ); 1178 //} 1179 1180 $x_length = count($x_value); 1181 $y_length = count($y_value); 1182 1183 if (!$x_length || !$y_length) { // a 0 is being multiplied 1184 return array( 1185 self::VALUE => array(), 1186 self::SIGN => false 1187 ); 1188 } 1189 1190 return array( 1191 self::VALUE => min($x_length, $y_length) < 2 * self::KARATSUBA_CUTOFF ? 1192 $this->_trim($this->_regularMultiply($x_value, $y_value)) : 1193 $this->_trim($this->_karatsuba($x_value, $y_value)), 1194 self::SIGN => $x_negative != $y_negative 1195 ); 1196 } 1197 1198 /** 1199 * Performs long multiplication on two BigIntegers 1200 * 1201 * Modeled after 'multiply' in MutableBigInteger.java. 1202 * 1203 * @param array $x_value 1204 * @param array $y_value 1205 * @return array 1206 * @access private 1207 */ 1208 function _regularMultiply($x_value, $y_value) 1209 { 1210 $x_length = count($x_value); 1211 $y_length = count($y_value); 1212 1213 if (!$x_length || !$y_length) { // a 0 is being multiplied 1214 return array(); 1215 } 1216 1217 if ($x_length < $y_length) { 1218 $temp = $x_value; 1219 $x_value = $y_value; 1220 $y_value = $temp; 1221 1222 $x_length = count($x_value); 1223 $y_length = count($y_value); 1224 } 1225 1226 $product_value = $this->_array_repeat(0, $x_length + $y_length); 1227 1228 // the following for loop could be removed if the for loop following it 1229 // (the one with nested for loops) initially set $i to 0, but 1230 // doing so would also make the result in one set of unnecessary adds, 1231 // since on the outermost loops first pass, $product->value[$k] is going 1232 // to always be 0 1233 1234 $carry = 0; 1235 1236 for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0 1237 $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0 1238 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 1239 $product_value[$j] = (int) ($temp - self::$baseFull * $carry); 1240 } 1241 1242 $product_value[$j] = $carry; 1243 1244 // the above for loop is what the previous comment was talking about. the 1245 // following for loop is the "one with nested for loops" 1246 for ($i = 1; $i < $y_length; ++$i) { 1247 $carry = 0; 1248 1249 for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) { 1250 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry; 1251 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 1252 $product_value[$k] = (int) ($temp - self::$baseFull * $carry); 1253 } 1254 1255 $product_value[$k] = $carry; 1256 } 1257 1258 return $product_value; 1259 } 1260 1261 /** 1262 * Performs Karatsuba multiplication on two BigIntegers 1263 * 1264 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and 1265 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}. 1266 * 1267 * @param array $x_value 1268 * @param array $y_value 1269 * @return array 1270 * @access private 1271 */ 1272 function _karatsuba($x_value, $y_value) 1273 { 1274 $m = min(count($x_value) >> 1, count($y_value) >> 1); 1275 1276 if ($m < self::KARATSUBA_CUTOFF) { 1277 return $this->_regularMultiply($x_value, $y_value); 1278 } 1279 1280 $x1 = array_slice($x_value, $m); 1281 $x0 = array_slice($x_value, 0, $m); 1282 $y1 = array_slice($y_value, $m); 1283 $y0 = array_slice($y_value, 0, $m); 1284 1285 $z2 = $this->_karatsuba($x1, $y1); 1286 $z0 = $this->_karatsuba($x0, $y0); 1287 1288 $z1 = $this->_add($x1, false, $x0, false); 1289 $temp = $this->_add($y1, false, $y0, false); 1290 $z1 = $this->_karatsuba($z1[self::VALUE], $temp[self::VALUE]); 1291 $temp = $this->_add($z2, false, $z0, false); 1292 $z1 = $this->_subtract($z1, false, $temp[self::VALUE], false); 1293 1294 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2); 1295 $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]); 1296 1297 $xy = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]); 1298 $xy = $this->_add($xy[self::VALUE], $xy[self::SIGN], $z0, false); 1299 1300 return $xy[self::VALUE]; 1301 } 1302 1303 /** 1304 * Performs squaring 1305 * 1306 * @param array $x 1307 * @return array 1308 * @access private 1309 */ 1310 function _square($x = false) 1311 { 1312 return count($x) < 2 * self::KARATSUBA_CUTOFF ? 1313 $this->_trim($this->_baseSquare($x)) : 1314 $this->_trim($this->_karatsubaSquare($x)); 1315 } 1316 1317 /** 1318 * Performs traditional squaring on two BigIntegers 1319 * 1320 * Squaring can be done faster than multiplying a number by itself can be. See 1321 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} / 1322 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information. 1323 * 1324 * @param array $value 1325 * @return array 1326 * @access private 1327 */ 1328 function _baseSquare($value) 1329 { 1330 if (empty($value)) { 1331 return array(); 1332 } 1333 $square_value = $this->_array_repeat(0, 2 * count($value)); 1334 1335 for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) { 1336 $i2 = $i << 1; 1337 1338 $temp = $square_value[$i2] + $value[$i] * $value[$i]; 1339 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 1340 $square_value[$i2] = (int) ($temp - self::$baseFull * $carry); 1341 1342 // note how we start from $i+1 instead of 0 as we do in multiplication. 1343 for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) { 1344 $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry; 1345 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 1346 $square_value[$k] = (int) ($temp - self::$baseFull * $carry); 1347 } 1348 1349 // the following line can yield values larger 2**15. at this point, PHP should switch 1350 // over to floats. 1351 $square_value[$i + $max_index + 1] = $carry; 1352 } 1353 1354 return $square_value; 1355 } 1356 1357 /** 1358 * Performs Karatsuba "squaring" on two BigIntegers 1359 * 1360 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and 1361 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}. 1362 * 1363 * @param array $value 1364 * @return array 1365 * @access private 1366 */ 1367 function _karatsubaSquare($value) 1368 { 1369 $m = count($value) >> 1; 1370 1371 if ($m < self::KARATSUBA_CUTOFF) { 1372 return $this->_baseSquare($value); 1373 } 1374 1375 $x1 = array_slice($value, $m); 1376 $x0 = array_slice($value, 0, $m); 1377 1378 $z2 = $this->_karatsubaSquare($x1); 1379 $z0 = $this->_karatsubaSquare($x0); 1380 1381 $z1 = $this->_add($x1, false, $x0, false); 1382 $z1 = $this->_karatsubaSquare($z1[self::VALUE]); 1383 $temp = $this->_add($z2, false, $z0, false); 1384 $z1 = $this->_subtract($z1, false, $temp[self::VALUE], false); 1385 1386 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2); 1387 $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]); 1388 1389 $xx = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]); 1390 $xx = $this->_add($xx[self::VALUE], $xx[self::SIGN], $z0, false); 1391 1392 return $xx[self::VALUE]; 1393 } 1394 1395 /** 1396 * Divides two BigIntegers. 1397 * 1398 * Returns an array whose first element contains the quotient and whose second element contains the 1399 * "common residue". If the remainder would be positive, the "common residue" and the remainder are the 1400 * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder 1401 * and the divisor (basically, the "common residue" is the first positive modulo). 1402 * 1403 * Here's an example: 1404 * <code> 1405 * <?php 1406 * $a = new \phpseclib\Math\BigInteger('10'); 1407 * $b = new \phpseclib\Math\BigInteger('20'); 1408 * 1409 * list($quotient, $remainder) = $a->divide($b); 1410 * 1411 * echo $quotient->toString(); // outputs 0 1412 * echo "\r\n"; 1413 * echo $remainder->toString(); // outputs 10 1414 * ?> 1415 * </code> 1416 * 1417 * @param \phpseclib\Math\BigInteger $y 1418 * @return array 1419 * @access public 1420 * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}. 1421 */ 1422 function divide($y) 1423 { 1424 switch (MATH_BIGINTEGER_MODE) { 1425 case self::MODE_GMP: 1426 $quotient = new static(); 1427 $remainder = new static(); 1428 1429 list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value); 1430 1431 if (gmp_sign($remainder->value) < 0) { 1432 $remainder->value = gmp_add($remainder->value, gmp_abs($y->value)); 1433 } 1434 1435 return array($this->_normalize($quotient), $this->_normalize($remainder)); 1436 case self::MODE_BCMATH: 1437 $quotient = new static(); 1438 $remainder = new static(); 1439 1440 $quotient->value = bcdiv($this->value, $y->value, 0); 1441 $remainder->value = bcmod($this->value, $y->value); 1442 1443 if ($remainder->value[0] == '-') { 1444 $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0); 1445 } 1446 1447 return array($this->_normalize($quotient), $this->_normalize($remainder)); 1448 } 1449 1450 if (count($y->value) == 1) { 1451 list($q, $r) = $this->_divide_digit($this->value, $y->value[0]); 1452 $quotient = new static(); 1453 $remainder = new static(); 1454 $quotient->value = $q; 1455 $remainder->value = array($r); 1456 $quotient->is_negative = $this->is_negative != $y->is_negative; 1457 return array($this->_normalize($quotient), $this->_normalize($remainder)); 1458 } 1459 1460 static $zero; 1461 if (!isset($zero)) { 1462 $zero = new static(); 1463 } 1464 1465 $x = $this->copy(); 1466 $y = $y->copy(); 1467 1468 $x_sign = $x->is_negative; 1469 $y_sign = $y->is_negative; 1470 1471 $x->is_negative = $y->is_negative = false; 1472 1473 $diff = $x->compare($y); 1474 1475 if (!$diff) { 1476 $temp = new static(); 1477 $temp->value = array(1); 1478 $temp->is_negative = $x_sign != $y_sign; 1479 return array($this->_normalize($temp), $this->_normalize(new static())); 1480 } 1481 1482 if ($diff < 0) { 1483 // if $x is negative, "add" $y. 1484 if ($x_sign) { 1485 $x = $y->subtract($x); 1486 } 1487 return array($this->_normalize(new static()), $this->_normalize($x)); 1488 } 1489 1490 // normalize $x and $y as described in HAC 14.23 / 14.24 1491 $msb = $y->value[count($y->value) - 1]; 1492 for ($shift = 0; !($msb & self::$msb); ++$shift) { 1493 $msb <<= 1; 1494 } 1495 $x->_lshift($shift); 1496 $y->_lshift($shift); 1497 $y_value = &$y->value; 1498 1499 $x_max = count($x->value) - 1; 1500 $y_max = count($y->value) - 1; 1501 1502 $quotient = new static(); 1503 $quotient_value = &$quotient->value; 1504 $quotient_value = $this->_array_repeat(0, $x_max - $y_max + 1); 1505 1506 static $temp, $lhs, $rhs; 1507 if (!isset($temp)) { 1508 $temp = new static(); 1509 $lhs = new static(); 1510 $rhs = new static(); 1511 } 1512 $temp_value = &$temp->value; 1513 $rhs_value = &$rhs->value; 1514 1515 // $temp = $y << ($x_max - $y_max-1) in base 2**26 1516 $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value); 1517 1518 while ($x->compare($temp) >= 0) { 1519 // calculate the "common residue" 1520 ++$quotient_value[$x_max - $y_max]; 1521 $x = $x->subtract($temp); 1522 $x_max = count($x->value) - 1; 1523 } 1524 1525 for ($i = $x_max; $i >= $y_max + 1; --$i) { 1526 $x_value = &$x->value; 1527 $x_window = array( 1528 isset($x_value[$i]) ? $x_value[$i] : 0, 1529 isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0, 1530 isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0 1531 ); 1532 $y_window = array( 1533 $y_value[$y_max], 1534 ($y_max > 0) ? $y_value[$y_max - 1] : 0 1535 ); 1536 1537 $q_index = $i - $y_max - 1; 1538 if ($x_window[0] == $y_window[0]) { 1539 $quotient_value[$q_index] = self::$maxDigit; 1540 } else { 1541 $quotient_value[$q_index] = $this->_safe_divide( 1542 $x_window[0] * self::$baseFull + $x_window[1], 1543 $y_window[0] 1544 ); 1545 } 1546 1547 $temp_value = array($y_window[1], $y_window[0]); 1548 1549 $lhs->value = array($quotient_value[$q_index]); 1550 $lhs = $lhs->multiply($temp); 1551 1552 $rhs_value = array($x_window[2], $x_window[1], $x_window[0]); 1553 1554 while ($lhs->compare($rhs) > 0) { 1555 --$quotient_value[$q_index]; 1556 1557 $lhs->value = array($quotient_value[$q_index]); 1558 $lhs = $lhs->multiply($temp); 1559 } 1560 1561 $adjust = $this->_array_repeat(0, $q_index); 1562 $temp_value = array($quotient_value[$q_index]); 1563 $temp = $temp->multiply($y); 1564 $temp_value = &$temp->value; 1565 if (count($temp_value)) { 1566 $temp_value = array_merge($adjust, $temp_value); 1567 } 1568 1569 $x = $x->subtract($temp); 1570 1571 if ($x->compare($zero) < 0) { 1572 $temp_value = array_merge($adjust, $y_value); 1573 $x = $x->add($temp); 1574 1575 --$quotient_value[$q_index]; 1576 } 1577 1578 $x_max = count($x_value) - 1; 1579 } 1580 1581 // unnormalize the remainder 1582 $x->_rshift($shift); 1583 1584 $quotient->is_negative = $x_sign != $y_sign; 1585 1586 // calculate the "common residue", if appropriate 1587 if ($x_sign) { 1588 $y->_rshift($shift); 1589 $x = $y->subtract($x); 1590 } 1591 1592 return array($this->_normalize($quotient), $this->_normalize($x)); 1593 } 1594 1595 /** 1596 * Divides a BigInteger by a regular integer 1597 * 1598 * abc / x = a00 / x + b0 / x + c / x 1599 * 1600 * @param array $dividend 1601 * @param array $divisor 1602 * @return array 1603 * @access private 1604 */ 1605 function _divide_digit($dividend, $divisor) 1606 { 1607 $carry = 0; 1608 $result = array(); 1609 1610 for ($i = count($dividend) - 1; $i >= 0; --$i) { 1611 $temp = self::$baseFull * $carry + $dividend[$i]; 1612 $result[$i] = $this->_safe_divide($temp, $divisor); 1613 $carry = (int) ($temp - $divisor * $result[$i]); 1614 } 1615 1616 return array($result, $carry); 1617 } 1618 1619 /** 1620 * Performs modular exponentiation. 1621 * 1622 * Here's an example: 1623 * <code> 1624 * <?php 1625 * $a = new \phpseclib\Math\BigInteger('10'); 1626 * $b = new \phpseclib\Math\BigInteger('20'); 1627 * $c = new \phpseclib\Math\BigInteger('30'); 1628 * 1629 * $c = $a->modPow($b, $c); 1630 * 1631 * echo $c->toString(); // outputs 10 1632 * ?> 1633 * </code> 1634 * 1635 * @param \phpseclib\Math\BigInteger $e 1636 * @param \phpseclib\Math\BigInteger $n 1637 * @return \phpseclib\Math\BigInteger 1638 * @access public 1639 * @internal The most naive approach to modular exponentiation has very unreasonable requirements, and 1640 * and although the approach involving repeated squaring does vastly better, it, too, is impractical 1641 * for our purposes. The reason being that division - by far the most complicated and time-consuming 1642 * of the basic operations (eg. +,-,*,/) - occurs multiple times within it. 1643 * 1644 * Modular reductions resolve this issue. Although an individual modular reduction takes more time 1645 * then an individual division, when performed in succession (with the same modulo), they're a lot faster. 1646 * 1647 * The two most commonly used modular reductions are Barrett and Montgomery reduction. Montgomery reduction, 1648 * although faster, only works when the gcd of the modulo and of the base being used is 1. In RSA, when the 1649 * base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because 1650 * the product of two odd numbers is odd), but what about when RSA isn't used? 1651 * 1652 * In contrast, Barrett reduction has no such constraint. As such, some bigint implementations perform a 1653 * Barrett reduction after every operation in the modpow function. Others perform Barrett reductions when the 1654 * modulo is even and Montgomery reductions when the modulo is odd. BigInteger.java's modPow method, however, 1655 * uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and 1656 * the other, a power of two - and recombine them, later. This is the method that this modPow function uses. 1657 * {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates. 1658 */ 1659 function modPow($e, $n) 1660 { 1661 $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs(); 1662 1663 if ($e->compare(new static()) < 0) { 1664 $e = $e->abs(); 1665 1666 $temp = $this->modInverse($n); 1667 if ($temp === false) { 1668 return false; 1669 } 1670 1671 return $this->_normalize($temp->modPow($e, $n)); 1672 } 1673 1674 if (MATH_BIGINTEGER_MODE == self::MODE_GMP) { 1675 $temp = new static(); 1676 $temp->value = gmp_powm($this->value, $e->value, $n->value); 1677 1678 return $this->_normalize($temp); 1679 } 1680 1681 if ($this->compare(new static()) < 0 || $this->compare($n) > 0) { 1682 list(, $temp) = $this->divide($n); 1683 return $temp->modPow($e, $n); 1684 } 1685 1686 if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) { 1687 $components = array( 1688 'modulus' => $n->toBytes(true), 1689 'publicExponent' => $e->toBytes(true) 1690 ); 1691 1692 $components = array( 1693 'modulus' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']), 1694 'publicExponent' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent']) 1695 ); 1696 1697 $RSAPublicKey = pack( 1698 'Ca*a*a*', 1699 48, 1700 $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])), 1701 $components['modulus'], 1702 $components['publicExponent'] 1703 ); 1704 1705 $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA 1706 $RSAPublicKey = chr(0) . $RSAPublicKey; 1707 $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey; 1708 1709 $encapsulated = pack( 1710 'Ca*a*', 1711 48, 1712 $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)), 1713 $rsaOID . $RSAPublicKey 1714 ); 1715 1716 $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" . 1717 chunk_split(base64_encode($encapsulated)) . 1718 '-----END PUBLIC KEY-----'; 1719 1720 $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT); 1721 1722 if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING)) { 1723 return new static($result, 256); 1724 } 1725 } 1726 1727 if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) { 1728 $temp = new static(); 1729 $temp->value = bcpowmod($this->value, $e->value, $n->value, 0); 1730 1731 return $this->_normalize($temp); 1732 } 1733 1734 if (empty($e->value)) { 1735 $temp = new static(); 1736 $temp->value = array(1); 1737 return $this->_normalize($temp); 1738 } 1739 1740 if ($e->value == array(1)) { 1741 list(, $temp) = $this->divide($n); 1742 return $this->_normalize($temp); 1743 } 1744 1745 if ($e->value == array(2)) { 1746 $temp = new static(); 1747 $temp->value = $this->_square($this->value); 1748 list(, $temp) = $temp->divide($n); 1749 return $this->_normalize($temp); 1750 } 1751 1752 return $this->_normalize($this->_slidingWindow($e, $n, self::BARRETT)); 1753 1754 // the following code, although not callable, can be run independently of the above code 1755 // although the above code performed better in my benchmarks the following could might 1756 // perform better under different circumstances. in lieu of deleting it it's just been 1757 // made uncallable 1758 1759 // is the modulo odd? 1760 if ($n->value[0] & 1) { 1761 return $this->_normalize($this->_slidingWindow($e, $n, self::MONTGOMERY)); 1762 } 1763 // if it's not, it's even 1764 1765 // find the lowest set bit (eg. the max pow of 2 that divides $n) 1766 for ($i = 0; $i < count($n->value); ++$i) { 1767 if ($n->value[$i]) { 1768 $temp = decbin($n->value[$i]); 1769 $j = strlen($temp) - strrpos($temp, '1') - 1; 1770 $j+= 26 * $i; 1771 break; 1772 } 1773 } 1774 // at this point, 2^$j * $n/(2^$j) == $n 1775 1776 $mod1 = $n->copy(); 1777 $mod1->_rshift($j); 1778 $mod2 = new static(); 1779 $mod2->value = array(1); 1780 $mod2->_lshift($j); 1781 1782 $part1 = ($mod1->value != array(1)) ? $this->_slidingWindow($e, $mod1, self::MONTGOMERY) : new static(); 1783 $part2 = $this->_slidingWindow($e, $mod2, self::POWEROF2); 1784 1785 $y1 = $mod2->modInverse($mod1); 1786 $y2 = $mod1->modInverse($mod2); 1787 1788 $result = $part1->multiply($mod2); 1789 $result = $result->multiply($y1); 1790 1791 $temp = $part2->multiply($mod1); 1792 $temp = $temp->multiply($y2); 1793 1794 $result = $result->add($temp); 1795 list(, $result) = $result->divide($n); 1796 1797 return $this->_normalize($result); 1798 } 1799 1800 /** 1801 * Performs modular exponentiation. 1802 * 1803 * Alias for modPow(). 1804 * 1805 * @param \phpseclib\Math\BigInteger $e 1806 * @param \phpseclib\Math\BigInteger $n 1807 * @return \phpseclib\Math\BigInteger 1808 * @access public 1809 */ 1810 function powMod($e, $n) 1811 { 1812 return $this->modPow($e, $n); 1813 } 1814 1815 /** 1816 * Sliding Window k-ary Modular Exponentiation 1817 * 1818 * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} / 1819 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}. In a departure from those algorithims, 1820 * however, this function performs a modular reduction after every multiplication and squaring operation. 1821 * As such, this function has the same preconditions that the reductions being used do. 1822 * 1823 * @param \phpseclib\Math\BigInteger $e 1824 * @param \phpseclib\Math\BigInteger $n 1825 * @param int $mode 1826 * @return \phpseclib\Math\BigInteger 1827 * @access private 1828 */ 1829 function _slidingWindow($e, $n, $mode) 1830 { 1831 static $window_ranges = array(7, 25, 81, 241, 673, 1793); // from BigInteger.java's oddModPow function 1832 //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1 1833 1834 $e_value = $e->value; 1835 $e_length = count($e_value) - 1; 1836 $e_bits = decbin($e_value[$e_length]); 1837 for ($i = $e_length - 1; $i >= 0; --$i) { 1838 $e_bits.= str_pad(decbin($e_value[$i]), self::$base, '0', STR_PAD_LEFT); 1839 } 1840 1841 $e_length = strlen($e_bits); 1842 1843 // calculate the appropriate window size. 1844 // $window_size == 3 if $window_ranges is between 25 and 81, for example. 1845 for ($i = 0, $window_size = 1; $i < count($window_ranges) && $e_length > $window_ranges[$i]; ++$window_size, ++$i) { 1846 } 1847 1848 $n_value = $n->value; 1849 1850 // precompute $this^0 through $this^$window_size 1851 $powers = array(); 1852 $powers[1] = $this->_prepareReduce($this->value, $n_value, $mode); 1853 $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode); 1854 1855 // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end 1856 // in a 1. ie. it's supposed to be odd. 1857 $temp = 1 << ($window_size - 1); 1858 for ($i = 1; $i < $temp; ++$i) { 1859 $i2 = $i << 1; 1860 $powers[$i2 + 1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode); 1861 } 1862 1863 $result = array(1); 1864 $result = $this->_prepareReduce($result, $n_value, $mode); 1865 1866 for ($i = 0; $i < $e_length;) { 1867 if (!$e_bits[$i]) { 1868 $result = $this->_squareReduce($result, $n_value, $mode); 1869 ++$i; 1870 } else { 1871 for ($j = $window_size - 1; $j > 0; --$j) { 1872 if (!empty($e_bits[$i + $j])) { 1873 break; 1874 } 1875 } 1876 1877 // eg. the length of substr($e_bits, $i, $j + 1) 1878 for ($k = 0; $k <= $j; ++$k) { 1879 $result = $this->_squareReduce($result, $n_value, $mode); 1880 } 1881 1882 $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $mode); 1883 1884 $i += $j + 1; 1885 } 1886 } 1887 1888 $temp = new static(); 1889 $temp->value = $this->_reduce($result, $n_value, $mode); 1890 1891 return $temp; 1892 } 1893 1894 /** 1895 * Modular reduction 1896 * 1897 * For most $modes this will return the remainder. 1898 * 1899 * @see self::_slidingWindow() 1900 * @access private 1901 * @param array $x 1902 * @param array $n 1903 * @param int $mode 1904 * @return array 1905 */ 1906 function _reduce($x, $n, $mode) 1907 { 1908 switch ($mode) { 1909 case self::MONTGOMERY: 1910 return $this->_montgomery($x, $n); 1911 case self::BARRETT: 1912 return $this->_barrett($x, $n); 1913 case self::POWEROF2: 1914 $lhs = new static(); 1915 $lhs->value = $x; 1916 $rhs = new static(); 1917 $rhs->value = $n; 1918 return $x->_mod2($n); 1919 case self::CLASSIC: 1920 $lhs = new static(); 1921 $lhs->value = $x; 1922 $rhs = new static(); 1923 $rhs->value = $n; 1924 list(, $temp) = $lhs->divide($rhs); 1925 return $temp->value; 1926 case self::NONE: 1927 return $x; 1928 default: 1929 // an invalid $mode was provided 1930 } 1931 } 1932 1933 /** 1934 * Modular reduction preperation 1935 * 1936 * @see self::_slidingWindow() 1937 * @access private 1938 * @param array $x 1939 * @param array $n 1940 * @param int $mode 1941 * @return array 1942 */ 1943 function _prepareReduce($x, $n, $mode) 1944 { 1945 if ($mode == self::MONTGOMERY) { 1946 return $this->_prepMontgomery($x, $n); 1947 } 1948 return $this->_reduce($x, $n, $mode); 1949 } 1950 1951 /** 1952 * Modular multiply 1953 * 1954 * @see self::_slidingWindow() 1955 * @access private 1956 * @param array $x 1957 * @param array $y 1958 * @param array $n 1959 * @param int $mode 1960 * @return array 1961 */ 1962 function _multiplyReduce($x, $y, $n, $mode) 1963 { 1964 if ($mode == self::MONTGOMERY) { 1965 return $this->_montgomeryMultiply($x, $y, $n); 1966 } 1967 $temp = $this->_multiply($x, false, $y, false); 1968 return $this->_reduce($temp[self::VALUE], $n, $mode); 1969 } 1970 1971 /** 1972 * Modular square 1973 * 1974 * @see self::_slidingWindow() 1975 * @access private 1976 * @param array $x 1977 * @param array $n 1978 * @param int $mode 1979 * @return array 1980 */ 1981 function _squareReduce($x, $n, $mode) 1982 { 1983 if ($mode == self::MONTGOMERY) { 1984 return $this->_montgomeryMultiply($x, $x, $n); 1985 } 1986 return $this->_reduce($this->_square($x), $n, $mode); 1987 } 1988 1989 /** 1990 * Modulos for Powers of Two 1991 * 1992 * Calculates $x%$n, where $n = 2**$e, for some $e. Since this is basically the same as doing $x & ($n-1), 1993 * we'll just use this function as a wrapper for doing that. 1994 * 1995 * @see self::_slidingWindow() 1996 * @access private 1997 * @param \phpseclib\Math\BigInteger $n 1998 * @return \phpseclib\Math\BigInteger 1999 */ 2000 function _mod2($n) 2001 { 2002 $temp = new static(); 2003 $temp->value = array(1); 2004 return $this->bitwise_and($n->subtract($temp)); 2005 } 2006 2007 /** 2008 * Barrett Modular Reduction 2009 * 2010 * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} / 2011 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information. Modified slightly, 2012 * so as not to require negative numbers (initially, this script didn't support negative numbers). 2013 * 2014 * Employs "folding", as described at 2015 * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}. To quote from 2016 * it, "the idea [behind folding] is to find a value x' such that x (mod m) = x' (mod m), with x' being smaller than x." 2017 * 2018 * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that 2019 * usable on account of (1) its not using reasonable radix points as discussed in 2020 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable 2021 * radix points, it only works when there are an even number of digits in the denominator. The reason for (2) is that 2022 * (x >> 1) + (x >> 1) != x / 2 + x / 2. If x is even, they're the same, but if x is odd, they're not. See the in-line 2023 * comments for details. 2024 * 2025 * @see self::_slidingWindow() 2026 * @access private 2027 * @param array $n 2028 * @param array $m 2029 * @return array 2030 */ 2031 function _barrett($n, $m) 2032 { 2033 static $cache = array( 2034 self::VARIABLE => array(), 2035 self::DATA => array() 2036 ); 2037 2038 $m_length = count($m); 2039 2040 // if ($this->_compare($n, $this->_square($m)) >= 0) { 2041 if (count($n) > 2 * $m_length) { 2042 $lhs = new static(); 2043 $rhs = new static(); 2044 $lhs->value = $n; 2045 $rhs->value = $m; 2046 list(, $temp) = $lhs->divide($rhs); 2047 return $temp->value; 2048 } 2049 2050 // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced 2051 if ($m_length < 5) { 2052 return $this->_regularBarrett($n, $m); 2053 } 2054 2055 // n = 2 * m.length 2056 2057 if (($key = array_search($m, $cache[self::VARIABLE])) === false) { 2058 $key = count($cache[self::VARIABLE]); 2059 $cache[self::VARIABLE][] = $m; 2060 2061 $lhs = new static(); 2062 $lhs_value = &$lhs->value; 2063 $lhs_value = $this->_array_repeat(0, $m_length + ($m_length >> 1)); 2064 $lhs_value[] = 1; 2065 $rhs = new static(); 2066 $rhs->value = $m; 2067 2068 list($u, $m1) = $lhs->divide($rhs); 2069 $u = $u->value; 2070 $m1 = $m1->value; 2071 2072 $cache[self::DATA][] = array( 2073 'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1) 2074 'm1'=> $m1 // m.length 2075 ); 2076 } else { 2077 extract($cache[self::DATA][$key]); 2078 } 2079 2080 $cutoff = $m_length + ($m_length >> 1); 2081 $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1) 2082 $msd = array_slice($n, $cutoff); // m.length >> 1 2083 $lsd = $this->_trim($lsd); 2084 $temp = $this->_multiply($msd, false, $m1, false); 2085 $n = $this->_add($lsd, false, $temp[self::VALUE], false); // m.length + (m.length >> 1) + 1 2086 2087 if ($m_length & 1) { 2088 return $this->_regularBarrett($n[self::VALUE], $m); 2089 } 2090 2091 // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2 2092 $temp = array_slice($n[self::VALUE], $m_length - 1); 2093 // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2 2094 // if odd: ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1 2095 $temp = $this->_multiply($temp, false, $u, false); 2096 // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1 2097 // if odd: (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) 2098 $temp = array_slice($temp[self::VALUE], ($m_length >> 1) + 1); 2099 // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1 2100 // if odd: (m.length - (m.length >> 1)) + m.length = 2 * m.length - (m.length >> 1) 2101 $temp = $this->_multiply($temp, false, $m, false); 2102 2103 // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit 2104 // number from a m.length + (m.length >> 1) + 1 digit number. ie. there'd be an extra digit and the while loop 2105 // following this comment would loop a lot (hence our calling _regularBarrett() in that situation). 2106 2107 $result = $this->_subtract($n[self::VALUE], false, $temp[self::VALUE], false); 2108 2109 while ($this->_compare($result[self::VALUE], $result[self::SIGN], $m, false) >= 0) { 2110 $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $m, false); 2111 } 2112 2113 return $result[self::VALUE]; 2114 } 2115 2116 /** 2117 * (Regular) Barrett Modular Reduction 2118 * 2119 * For numbers with more than four digits BigInteger::_barrett() is faster. The difference between that and this 2120 * is that this function does not fold the denominator into a smaller form. 2121 * 2122 * @see self::_slidingWindow() 2123 * @access private 2124 * @param array $x 2125 * @param array $n 2126 * @return array 2127 */ 2128 function _regularBarrett($x, $n) 2129 { 2130 static $cache = array( 2131 self::VARIABLE => array(), 2132 self::DATA => array() 2133 ); 2134 2135 $n_length = count($n); 2136 2137 if (count($x) > 2 * $n_length) { 2138 $lhs = new static(); 2139 $rhs = new static(); 2140 $lhs->value = $x; 2141 $rhs->value = $n; 2142 list(, $temp) = $lhs->divide($rhs); 2143 return $temp->value; 2144 } 2145 2146 if (($key = array_search($n, $cache[self::VARIABLE])) === false) { 2147 $key = count($cache[self::VARIABLE]); 2148 $cache[self::VARIABLE][] = $n; 2149 $lhs = new static(); 2150 $lhs_value = &$lhs->value; 2151 $lhs_value = $this->_array_repeat(0, 2 * $n_length); 2152 $lhs_value[] = 1; 2153 $rhs = new static(); 2154 $rhs->value = $n; 2155 list($temp, ) = $lhs->divide($rhs); // m.length 2156 $cache[self::DATA][] = $temp->value; 2157 } 2158 2159 // 2 * m.length - (m.length - 1) = m.length + 1 2160 $temp = array_slice($x, $n_length - 1); 2161 // (m.length + 1) + m.length = 2 * m.length + 1 2162 $temp = $this->_multiply($temp, false, $cache[self::DATA][$key], false); 2163 // (2 * m.length + 1) - (m.length - 1) = m.length + 2 2164 $temp = array_slice($temp[self::VALUE], $n_length + 1); 2165 2166 // m.length + 1 2167 $result = array_slice($x, 0, $n_length + 1); 2168 // m.length + 1 2169 $temp = $this->_multiplyLower($temp, false, $n, false, $n_length + 1); 2170 // $temp == array_slice($temp->_multiply($temp, false, $n, false)->value, 0, $n_length + 1) 2171 2172 if ($this->_compare($result, false, $temp[self::VALUE], $temp[self::SIGN]) < 0) { 2173 $corrector_value = $this->_array_repeat(0, $n_length + 1); 2174 $corrector_value[count($corrector_value)] = 1; 2175 $result = $this->_add($result, false, $corrector_value, false); 2176 $result = $result[self::VALUE]; 2177 } 2178 2179 // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits 2180 $result = $this->_subtract($result, false, $temp[self::VALUE], $temp[self::SIGN]); 2181 while ($this->_compare($result[self::VALUE], $result[self::SIGN], $n, false) > 0) { 2182 $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $n, false); 2183 } 2184 2185 return $result[self::VALUE]; 2186 } 2187 2188 /** 2189 * Performs long multiplication up to $stop digits 2190 * 2191 * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved. 2192 * 2193 * @see self::_regularBarrett() 2194 * @param array $x_value 2195 * @param bool $x_negative 2196 * @param array $y_value 2197 * @param bool $y_negative 2198 * @param int $stop 2199 * @return array 2200 * @access private 2201 */ 2202 function _multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop) 2203 { 2204 $x_length = count($x_value); 2205 $y_length = count($y_value); 2206 2207 if (!$x_length || !$y_length) { // a 0 is being multiplied 2208 return array( 2209 self::VALUE => array(), 2210 self::SIGN => false 2211 ); 2212 } 2213 2214 if ($x_length < $y_length) { 2215 $temp = $x_value; 2216 $x_value = $y_value; 2217 $y_value = $temp; 2218 2219 $x_length = count($x_value); 2220 $y_length = count($y_value); 2221 } 2222 2223 $product_value = $this->_array_repeat(0, $x_length + $y_length); 2224 2225 // the following for loop could be removed if the for loop following it 2226 // (the one with nested for loops) initially set $i to 0, but 2227 // doing so would also make the result in one set of unnecessary adds, 2228 // since on the outermost loops first pass, $product->value[$k] is going 2229 // to always be 0 2230 2231 $carry = 0; 2232 2233 for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i 2234 $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0 2235 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 2236 $product_value[$j] = (int) ($temp - self::$baseFull * $carry); 2237 } 2238 2239 if ($j < $stop) { 2240 $product_value[$j] = $carry; 2241 } 2242 2243 // the above for loop is what the previous comment was talking about. the 2244 // following for loop is the "one with nested for loops" 2245 2246 for ($i = 1; $i < $y_length; ++$i) { 2247 $carry = 0; 2248 2249 for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) { 2250 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry; 2251 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 2252 $product_value[$k] = (int) ($temp - self::$baseFull * $carry); 2253 } 2254 2255 if ($k < $stop) { 2256 $product_value[$k] = $carry; 2257 } 2258 } 2259 2260 return array( 2261 self::VALUE => $this->_trim($product_value), 2262 self::SIGN => $x_negative != $y_negative 2263 ); 2264 } 2265 2266 /** 2267 * Montgomery Modular Reduction 2268 * 2269 * ($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n. 2270 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=170 MPM 6.3} provides insights on how this can be 2271 * improved upon (basically, by using the comba method). gcd($n, 2) must be equal to one for this function 2272 * to work correctly. 2273 * 2274 * @see self::_prepMontgomery() 2275 * @see self::_slidingWindow() 2276 * @access private 2277 * @param array $x 2278 * @param array $n 2279 * @return array 2280 */ 2281 function _montgomery($x, $n) 2282 { 2283 static $cache = array( 2284 self::VARIABLE => array(), 2285 self::DATA => array() 2286 ); 2287 2288 if (($key = array_search($n, $cache[self::VARIABLE])) === false) { 2289 $key = count($cache[self::VARIABLE]); 2290 $cache[self::VARIABLE][] = $x; 2291 $cache[self::DATA][] = $this->_modInverse67108864($n); 2292 } 2293 2294 $k = count($n); 2295 2296 $result = array(self::VALUE => $x); 2297 2298 for ($i = 0; $i < $k; ++$i) { 2299 $temp = $result[self::VALUE][$i] * $cache[self::DATA][$key]; 2300 $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31)); 2301 $temp = $this->_regularMultiply(array($temp), $n); 2302 $temp = array_merge($this->_array_repeat(0, $i), $temp); 2303 $result = $this->_add($result[self::VALUE], false, $temp, false); 2304 } 2305 2306 $result[self::VALUE] = array_slice($result[self::VALUE], $k); 2307 2308 if ($this->_compare($result, false, $n, false) >= 0) { 2309 $result = $this->_subtract($result[self::VALUE], false, $n, false); 2310 } 2311 2312 return $result[self::VALUE]; 2313 } 2314 2315 /** 2316 * Montgomery Multiply 2317 * 2318 * Interleaves the montgomery reduction and long multiplication algorithms together as described in 2319 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36} 2320 * 2321 * @see self::_prepMontgomery() 2322 * @see self::_montgomery() 2323 * @access private 2324 * @param array $x 2325 * @param array $y 2326 * @param array $m 2327 * @return array 2328 */ 2329 function _montgomeryMultiply($x, $y, $m) 2330 { 2331 $temp = $this->_multiply($x, false, $y, false); 2332 return $this->_montgomery($temp[self::VALUE], $m); 2333 2334 // the following code, although not callable, can be run independently of the above code 2335 // although the above code performed better in my benchmarks the following could might 2336 // perform better under different circumstances. in lieu of deleting it it's just been 2337 // made uncallable 2338 2339 static $cache = array( 2340 self::VARIABLE => array(), 2341 self::DATA => array() 2342 ); 2343 2344 if (($key = array_search($m, $cache[self::VARIABLE])) === false) { 2345 $key = count($cache[self::VARIABLE]); 2346 $cache[self::VARIABLE][] = $m; 2347 $cache[self::DATA][] = $this->_modInverse67108864($m); 2348 } 2349 2350 $n = max(count($x), count($y), count($m)); 2351 $x = array_pad($x, $n, 0); 2352 $y = array_pad($y, $n, 0); 2353 $m = array_pad($m, $n, 0); 2354 $a = array(self::VALUE => $this->_array_repeat(0, $n + 1)); 2355 for ($i = 0; $i < $n; ++$i) { 2356 $temp = $a[self::VALUE][0] + $x[$i] * $y[0]; 2357 $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31)); 2358 $temp = $temp * $cache[self::DATA][$key]; 2359 $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31)); 2360 $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false); 2361 $a = $this->_add($a[self::VALUE], false, $temp[self::VALUE], false); 2362 $a[self::VALUE] = array_slice($a[self::VALUE], 1); 2363 } 2364 if ($this->_compare($a[self::VALUE], false, $m, false) >= 0) { 2365 $a = $this->_subtract($a[self::VALUE], false, $m, false); 2366 } 2367 return $a[self::VALUE]; 2368 } 2369 2370 /** 2371 * Prepare a number for use in Montgomery Modular Reductions 2372 * 2373 * @see self::_montgomery() 2374 * @see self::_slidingWindow() 2375 * @access private 2376 * @param array $x 2377 * @param array $n 2378 * @return array 2379 */ 2380 function _prepMontgomery($x, $n) 2381 { 2382 $lhs = new static(); 2383 $lhs->value = array_merge($this->_array_repeat(0, count($n)), $x); 2384 $rhs = new static(); 2385 $rhs->value = $n; 2386 2387 list(, $temp) = $lhs->divide($rhs); 2388 return $temp->value; 2389 } 2390 2391 /** 2392 * Modular Inverse of a number mod 2**26 (eg. 67108864) 2393 * 2394 * Based off of the bnpInvDigit function implemented and justified in the following URL: 2395 * 2396 * {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js} 2397 * 2398 * The following URL provides more info: 2399 * 2400 * {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85} 2401 * 2402 * As for why we do all the bitmasking... strange things can happen when converting from floats to ints. For 2403 * instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields 2404 * int(-2147483648). To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't 2405 * auto-converted to floats. The outermost bitmask is present because without it, there's no guarantee that 2406 * the "residue" returned would be the so-called "common residue". We use fmod, in the last step, because the 2407 * maximum possible $x is 26 bits and the maximum $result is 16 bits. Thus, we have to be able to handle up to 2408 * 40 bits, which only 64-bit floating points will support. 2409 * 2410 * Thanks to Pedro Gimeno Fortea for input! 2411 * 2412 * @see self::_montgomery() 2413 * @access private 2414 * @param array $x 2415 * @return int 2416 */ 2417 function _modInverse67108864($x) // 2**26 == 67,108,864 2418 { 2419 $x = -$x[0]; 2420 $result = $x & 0x3; // x**-1 mod 2**2 2421 $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4 2422 $result = ($result * (2 - ($x & 0xFF) * $result)) & 0xFF; // x**-1 mod 2**8 2423 $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16 2424 $result = fmod($result * (2 - fmod($x * $result, self::$baseFull)), self::$baseFull); // x**-1 mod 2**26 2425 return $result & self::$maxDigit; 2426 } 2427 2428 /** 2429 * Calculates modular inverses. 2430 * 2431 * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses. 2432 * 2433 * Here's an example: 2434 * <code> 2435 * <?php 2436 * $a = new \phpseclib\Math\BigInteger(30); 2437 * $b = new \phpseclib\Math\BigInteger(17); 2438 * 2439 * $c = $a->modInverse($b); 2440 * echo $c->toString(); // outputs 4 2441 * 2442 * echo "\r\n"; 2443 * 2444 * $d = $a->multiply($c); 2445 * list(, $d) = $d->divide($b); 2446 * echo $d; // outputs 1 (as per the definition of modular inverse) 2447 * ?> 2448 * </code> 2449 * 2450 * @param \phpseclib\Math\BigInteger $n 2451 * @return \phpseclib\Math\BigInteger|false 2452 * @access public 2453 * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information. 2454 */ 2455 function modInverse($n) 2456 { 2457 switch (MATH_BIGINTEGER_MODE) { 2458 case self::MODE_GMP: 2459 $temp = new static(); 2460 $temp->value = gmp_invert($this->value, $n->value); 2461 2462 return ($temp->value === false) ? false : $this->_normalize($temp); 2463 } 2464 2465 static $zero, $one; 2466 if (!isset($zero)) { 2467 $zero = new static(); 2468 $one = new static(1); 2469 } 2470 2471 // $x mod -$n == $x mod $n. 2472 $n = $n->abs(); 2473 2474 if ($this->compare($zero) < 0) { 2475 $temp = $this->abs(); 2476 $temp = $temp->modInverse($n); 2477 return $this->_normalize($n->subtract($temp)); 2478 } 2479 2480 extract($this->extendedGCD($n)); 2481 2482 if (!$gcd->equals($one)) { 2483 return false; 2484 } 2485 2486 $x = $x->compare($zero) < 0 ? $x->add($n) : $x; 2487 2488 return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x); 2489 } 2490 2491 /** 2492 * Calculates the greatest common divisor and Bezout's identity. 2493 * 2494 * Say you have 693 and 609. The GCD is 21. Bezout's identity states that there exist integers x and y such that 2495 * 693*x + 609*y == 21. In point of fact, there are actually an infinite number of x and y combinations and which 2496 * combination is returned is dependent upon which mode is in use. See 2497 * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information. 2498 * 2499 * Here's an example: 2500 * <code> 2501 * <?php 2502 * $a = new \phpseclib\Math\BigInteger(693); 2503 * $b = new \phpseclib\Math\BigInteger(609); 2504 * 2505 * extract($a->extendedGCD($b)); 2506 * 2507 * echo $gcd->toString() . "\r\n"; // outputs 21 2508 * echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21 2509 * ?> 2510 * </code> 2511 * 2512 * @param \phpseclib\Math\BigInteger $n 2513 * @return \phpseclib\Math\BigInteger 2514 * @access public 2515 * @internal Calculates the GCD using the binary xGCD algorithim described in 2516 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=19 HAC 14.61}. As the text above 14.61 notes, 2517 * the more traditional algorithim requires "relatively costly multiple-precision divisions". 2518 */ 2519 function extendedGCD($n) 2520 { 2521 switch (MATH_BIGINTEGER_MODE) { 2522 case self::MODE_GMP: 2523 extract(gmp_gcdext($this->value, $n->value)); 2524 2525 return array( 2526 'gcd' => $this->_normalize(new static($g)), 2527 'x' => $this->_normalize(new static($s)), 2528 'y' => $this->_normalize(new static($t)) 2529 ); 2530 case self::MODE_BCMATH: 2531 // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works 2532 // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway. as is, 2533 // the basic extended euclidean algorithim is what we're using. 2534 2535 $u = $this->value; 2536 $v = $n->value; 2537 2538 $a = '1'; 2539 $b = '0'; 2540 $c = '0'; 2541 $d = '1'; 2542 2543 while (bccomp($v, '0', 0) != 0) { 2544 $q = bcdiv($u, $v, 0); 2545 2546 $temp = $u; 2547 $u = $v; 2548 $v = bcsub($temp, bcmul($v, $q, 0), 0); 2549 2550 $temp = $a; 2551 $a = $c; 2552 $c = bcsub($temp, bcmul($a, $q, 0), 0); 2553 2554 $temp = $b; 2555 $b = $d; 2556 $d = bcsub($temp, bcmul($b, $q, 0), 0); 2557 } 2558 2559 return array( 2560 'gcd' => $this->_normalize(new static($u)), 2561 'x' => $this->_normalize(new static($a)), 2562 'y' => $this->_normalize(new static($b)) 2563 ); 2564 } 2565 2566 $y = $n->copy(); 2567 $x = $this->copy(); 2568 $g = new static(); 2569 $g->value = array(1); 2570 2571 while (!(($x->value[0] & 1)|| ($y->value[0] & 1))) { 2572 $x->_rshift(1); 2573 $y->_rshift(1); 2574 $g->_lshift(1); 2575 } 2576 2577 $u = $x->copy(); 2578 $v = $y->copy(); 2579 2580 $a = new static(); 2581 $b = new static(); 2582 $c = new static(); 2583 $d = new static(); 2584 2585 $a->value = $d->value = $g->value = array(1); 2586 $b->value = $c->value = array(); 2587 2588 while (!empty($u->value)) { 2589 while (!($u->value[0] & 1)) { 2590 $u->_rshift(1); 2591 if ((!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1))) { 2592 $a = $a->add($y); 2593 $b = $b->subtract($x); 2594 } 2595 $a->_rshift(1); 2596 $b->_rshift(1); 2597 } 2598 2599 while (!($v->value[0] & 1)) { 2600 $v->_rshift(1); 2601 if ((!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1))) { 2602 $c = $c->add($y); 2603 $d = $d->subtract($x); 2604 } 2605 $c->_rshift(1); 2606 $d->_rshift(1); 2607 } 2608 2609 if ($u->compare($v) >= 0) { 2610 $u = $u->subtract($v); 2611 $a = $a->subtract($c); 2612 $b = $b->subtract($d); 2613 } else { 2614 $v = $v->subtract($u); 2615 $c = $c->subtract($a); 2616 $d = $d->subtract($b); 2617 } 2618 } 2619 2620 return array( 2621 'gcd' => $this->_normalize($g->multiply($v)), 2622 'x' => $this->_normalize($c), 2623 'y' => $this->_normalize($d) 2624 ); 2625 } 2626 2627 /** 2628 * Calculates the greatest common divisor 2629 * 2630 * Say you have 693 and 609. The GCD is 21. 2631 * 2632 * Here's an example: 2633 * <code> 2634 * <?php 2635 * $a = new \phpseclib\Math\BigInteger(693); 2636 * $b = new \phpseclib\Math\BigInteger(609); 2637 * 2638 * $gcd = a->extendedGCD($b); 2639 * 2640 * echo $gcd->toString() . "\r\n"; // outputs 21 2641 * ?> 2642 * </code> 2643 * 2644 * @param \phpseclib\Math\BigInteger $n 2645 * @return \phpseclib\Math\BigInteger 2646 * @access public 2647 */ 2648 function gcd($n) 2649 { 2650 extract($this->extendedGCD($n)); 2651 return $gcd; 2652 } 2653 2654 /** 2655 * Absolute value. 2656 * 2657 * @return \phpseclib\Math\BigInteger 2658 * @access public 2659 */ 2660 function abs() 2661 { 2662 $temp = new static(); 2663 2664 switch (MATH_BIGINTEGER_MODE) { 2665 case self::MODE_GMP: 2666 $temp->value = gmp_abs($this->value); 2667 break; 2668 case self::MODE_BCMATH: 2669 $temp->value = (bccomp($this->value, '0', 0) < 0) ? substr($this->value, 1) : $this->value; 2670 break; 2671 default: 2672 $temp->value = $this->value; 2673 } 2674 2675 return $temp; 2676 } 2677 2678 /** 2679 * Compares two numbers. 2680 * 2681 * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this is 2682 * demonstrated thusly: 2683 * 2684 * $x > $y: $x->compare($y) > 0 2685 * $x < $y: $x->compare($y) < 0 2686 * $x == $y: $x->compare($y) == 0 2687 * 2688 * Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y). 2689 * 2690 * @param \phpseclib\Math\BigInteger $y 2691 * @return int that is < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal. 2692 * @access public 2693 * @see self::equals() 2694 * @internal Could return $this->subtract($x), but that's not as fast as what we do do. 2695 */ 2696 function compare($y) 2697 { 2698 switch (MATH_BIGINTEGER_MODE) { 2699 case self::MODE_GMP: 2700 $r = gmp_cmp($this->value, $y->value); 2701 if ($r < -1) { 2702 $r = -1; 2703 } 2704 if ($r > 1) { 2705 $r = 1; 2706 } 2707 return $r; 2708 case self::MODE_BCMATH: 2709 return bccomp($this->value, $y->value, 0); 2710 } 2711 2712 return $this->_compare($this->value, $this->is_negative, $y->value, $y->is_negative); 2713 } 2714 2715 /** 2716 * Compares two numbers. 2717 * 2718 * @param array $x_value 2719 * @param bool $x_negative 2720 * @param array $y_value 2721 * @param bool $y_negative 2722 * @return int 2723 * @see self::compare() 2724 * @access private 2725 */ 2726 function _compare($x_value, $x_negative, $y_value, $y_negative) 2727 { 2728 if ($x_negative != $y_negative) { 2729 return (!$x_negative && $y_negative) ? 1 : -1; 2730 } 2731 2732 $result = $x_negative ? -1 : 1; 2733 2734 if (count($x_value) != count($y_value)) { 2735 return (count($x_value) > count($y_value)) ? $result : -$result; 2736 } 2737 $size = max(count($x_value), count($y_value)); 2738 2739 $x_value = array_pad($x_value, $size, 0); 2740 $y_value = array_pad($y_value, $size, 0); 2741 2742 for ($i = count($x_value) - 1; $i >= 0; --$i) { 2743 if ($x_value[$i] != $y_value[$i]) { 2744 return ($x_value[$i] > $y_value[$i]) ? $result : -$result; 2745 } 2746 } 2747 2748 return 0; 2749 } 2750 2751 /** 2752 * Tests the equality of two numbers. 2753 * 2754 * If you need to see if one number is greater than or less than another number, use BigInteger::compare() 2755 * 2756 * @param \phpseclib\Math\BigInteger $x 2757 * @return bool 2758 * @access public 2759 * @see self::compare() 2760 */ 2761 function equals($x) 2762 { 2763 switch (MATH_BIGINTEGER_MODE) { 2764 case self::MODE_GMP: 2765 return gmp_cmp($this->value, $x->value) == 0; 2766 default: 2767 return $this->value === $x->value && $this->is_negative == $x->is_negative; 2768 } 2769 } 2770 2771 /** 2772 * Set Precision 2773 * 2774 * Some bitwise operations give different results depending on the precision being used. Examples include left 2775 * shift, not, and rotates. 2776 * 2777 * @param int $bits 2778 * @access public 2779 */ 2780 function setPrecision($bits) 2781 { 2782 $this->precision = $bits; 2783 if (MATH_BIGINTEGER_MODE != self::MODE_BCMATH) { 2784 $this->bitmask = new static(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256); 2785 } else { 2786 $this->bitmask = new static(bcpow('2', $bits, 0)); 2787 } 2788 2789 $temp = $this->_normalize($this); 2790 $this->value = $temp->value; 2791 } 2792 2793 /** 2794 * Logical And 2795 * 2796 * @param \phpseclib\Math\BigInteger $x 2797 * @access public 2798 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat> 2799 * @return \phpseclib\Math\BigInteger 2800 */ 2801 function bitwise_and($x) 2802 { 2803 switch (MATH_BIGINTEGER_MODE) { 2804 case self::MODE_GMP: 2805 $temp = new static(); 2806 $temp->value = gmp_and($this->value, $x->value); 2807 2808 return $this->_normalize($temp); 2809 case self::MODE_BCMATH: 2810 $left = $this->toBytes(); 2811 $right = $x->toBytes(); 2812 2813 $length = max(strlen($left), strlen($right)); 2814 2815 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); 2816 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); 2817 2818 return $this->_normalize(new static($left & $right, 256)); 2819 } 2820 2821 $result = $this->copy(); 2822 2823 $length = min(count($x->value), count($this->value)); 2824 2825 $result->value = array_slice($result->value, 0, $length); 2826 2827 for ($i = 0; $i < $length; ++$i) { 2828 $result->value[$i]&= $x->value[$i]; 2829 } 2830 2831 return $this->_normalize($result); 2832 } 2833 2834 /** 2835 * Logical Or 2836 * 2837 * @param \phpseclib\Math\BigInteger $x 2838 * @access public 2839 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat> 2840 * @return \phpseclib\Math\BigInteger 2841 */ 2842 function bitwise_or($x) 2843 { 2844 switch (MATH_BIGINTEGER_MODE) { 2845 case self::MODE_GMP: 2846 $temp = new static(); 2847 $temp->value = gmp_or($this->value, $x->value); 2848 2849 return $this->_normalize($temp); 2850 case self::MODE_BCMATH: 2851 $left = $this->toBytes(); 2852 $right = $x->toBytes(); 2853 2854 $length = max(strlen($left), strlen($right)); 2855 2856 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); 2857 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); 2858 2859 return $this->_normalize(new static($left | $right, 256)); 2860 } 2861 2862 $length = max(count($this->value), count($x->value)); 2863 $result = $this->copy(); 2864 $result->value = array_pad($result->value, $length, 0); 2865 $x->value = array_pad($x->value, $length, 0); 2866 2867 for ($i = 0; $i < $length; ++$i) { 2868 $result->value[$i]|= $x->value[$i]; 2869 } 2870 2871 return $this->_normalize($result); 2872 } 2873 2874 /** 2875 * Logical Exclusive-Or 2876 * 2877 * @param \phpseclib\Math\BigInteger $x 2878 * @access public 2879 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat> 2880 * @return \phpseclib\Math\BigInteger 2881 */ 2882 function bitwise_xor($x) 2883 { 2884 switch (MATH_BIGINTEGER_MODE) { 2885 case self::MODE_GMP: 2886 $temp = new static(); 2887 $temp->value = gmp_xor(gmp_abs($this->value), gmp_abs($x->value)); 2888 return $this->_normalize($temp); 2889 case self::MODE_BCMATH: 2890 $left = $this->toBytes(); 2891 $right = $x->toBytes(); 2892 2893 $length = max(strlen($left), strlen($right)); 2894 2895 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); 2896 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); 2897 2898 return $this->_normalize(new static($left ^ $right, 256)); 2899 } 2900 2901 $length = max(count($this->value), count($x->value)); 2902 $result = $this->copy(); 2903 $result->is_negative = false; 2904 $result->value = array_pad($result->value, $length, 0); 2905 $x->value = array_pad($x->value, $length, 0); 2906 2907 for ($i = 0; $i < $length; ++$i) { 2908 $result->value[$i]^= $x->value[$i]; 2909 } 2910 2911 return $this->_normalize($result); 2912 } 2913 2914 /** 2915 * Logical Not 2916 * 2917 * @access public 2918 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat> 2919 * @return \phpseclib\Math\BigInteger 2920 */ 2921 function bitwise_not() 2922 { 2923 // calculuate "not" without regard to $this->precision 2924 // (will always result in a smaller number. ie. ~1 isn't 1111 1110 - it's 0) 2925 $temp = $this->toBytes(); 2926 if ($temp == '') { 2927 return $this->_normalize(new static()); 2928 } 2929 $pre_msb = decbin(ord($temp[0])); 2930 $temp = ~$temp; 2931 $msb = decbin(ord($temp[0])); 2932 if (strlen($msb) == 8) { 2933 $msb = substr($msb, strpos($msb, '0')); 2934 } 2935 $temp[0] = chr(bindec($msb)); 2936 2937 // see if we need to add extra leading 1's 2938 $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8; 2939 $new_bits = $this->precision - $current_bits; 2940 if ($new_bits <= 0) { 2941 return $this->_normalize(new static($temp, 256)); 2942 } 2943 2944 // generate as many leading 1's as we need to. 2945 $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3); 2946 $this->_base256_lshift($leading_ones, $current_bits); 2947 2948 $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT); 2949 2950 return $this->_normalize(new static($leading_ones | $temp, 256)); 2951 } 2952 2953 /** 2954 * Logical Right Shift 2955 * 2956 * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift. 2957 * 2958 * @param int $shift 2959 * @return \phpseclib\Math\BigInteger 2960 * @access public 2961 * @internal The only version that yields any speed increases is the internal version. 2962 */ 2963 function bitwise_rightShift($shift) 2964 { 2965 $temp = new static(); 2966 2967 switch (MATH_BIGINTEGER_MODE) { 2968 case self::MODE_GMP: 2969 static $two; 2970 2971 if (!isset($two)) { 2972 $two = gmp_init('2'); 2973 } 2974 2975 $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift)); 2976 2977 break; 2978 case self::MODE_BCMATH: 2979 $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0); 2980 2981 break; 2982 default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten 2983 // and I don't want to do that... 2984 $temp->value = $this->value; 2985 $temp->_rshift($shift); 2986 } 2987 2988 return $this->_normalize($temp); 2989 } 2990 2991 /** 2992 * Logical Left Shift 2993 * 2994 * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift. 2995 * 2996 * @param int $shift 2997 * @return \phpseclib\Math\BigInteger 2998 * @access public 2999 * @internal The only version that yields any speed increases is the internal version. 3000 */ 3001 function bitwise_leftShift($shift) 3002 { 3003 $temp = new static(); 3004 3005 switch (MATH_BIGINTEGER_MODE) { 3006 case self::MODE_GMP: 3007 static $two; 3008 3009 if (!isset($two)) { 3010 $two = gmp_init('2'); 3011 } 3012 3013 $temp->value = gmp_mul($this->value, gmp_pow($two, $shift)); 3014 3015 break; 3016 case self::MODE_BCMATH: 3017 $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0); 3018 3019 break; 3020 default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten 3021 // and I don't want to do that... 3022 $temp->value = $this->value; 3023 $temp->_lshift($shift); 3024 } 3025 3026 return $this->_normalize($temp); 3027 } 3028 3029 /** 3030 * Logical Left Rotate 3031 * 3032 * Instead of the top x bits being dropped they're appended to the shifted bit string. 3033 * 3034 * @param int $shift 3035 * @return \phpseclib\Math\BigInteger 3036 * @access public 3037 */ 3038 function bitwise_leftRotate($shift) 3039 { 3040 $bits = $this->toBytes(); 3041 3042 if ($this->precision > 0) { 3043 $precision = $this->precision; 3044 if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) { 3045 $mask = $this->bitmask->subtract(new static(1)); 3046 $mask = $mask->toBytes(); 3047 } else { 3048 $mask = $this->bitmask->toBytes(); 3049 } 3050 } else { 3051 $temp = ord($bits[0]); 3052 for ($i = 0; $temp >> $i; ++$i) { 3053 } 3054 $precision = 8 * strlen($bits) - 8 + $i; 3055 $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3); 3056 } 3057 3058 if ($shift < 0) { 3059 $shift+= $precision; 3060 } 3061 $shift%= $precision; 3062 3063 if (!$shift) { 3064 return $this->copy(); 3065 } 3066 3067 $left = $this->bitwise_leftShift($shift); 3068 $left = $left->bitwise_and(new static($mask, 256)); 3069 $right = $this->bitwise_rightShift($precision - $shift); 3070 $result = MATH_BIGINTEGER_MODE != self::MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right); 3071 return $this->_normalize($result); 3072 } 3073 3074 /** 3075 * Logical Right Rotate 3076 * 3077 * Instead of the bottom x bits being dropped they're prepended to the shifted bit string. 3078 * 3079 * @param int $shift 3080 * @return \phpseclib\Math\BigInteger 3081 * @access public 3082 */ 3083 function bitwise_rightRotate($shift) 3084 { 3085 return $this->bitwise_leftRotate(-$shift); 3086 } 3087 3088 /** 3089 * Generates a random BigInteger 3090 * 3091 * Byte length is equal to $length. Uses \phpseclib\Crypt\Random if it's loaded and mt_rand if it's not. 3092 * 3093 * @param int $size 3094 * @return \phpseclib\Math\BigInteger 3095 * @access private 3096 */ 3097 function _random_number_helper($size) 3098 { 3099 if (class_exists('\phpseclib\Crypt\Random')) { 3100 $random = Random::string($size); 3101 } else { 3102 $random = ''; 3103 3104 if ($size & 1) { 3105 $random.= chr(mt_rand(0, 255)); 3106 } 3107 3108 $blocks = $size >> 1; 3109 for ($i = 0; $i < $blocks; ++$i) { 3110 // mt_rand(-2147483648, 0x7FFFFFFF) always produces -2147483648 on some systems 3111 $random.= pack('n', mt_rand(0, 0xFFFF)); 3112 } 3113 } 3114 3115 return new static($random, 256); 3116 } 3117 3118 /** 3119 * Generate a random number 3120 * 3121 * Returns a random number between $min and $max where $min and $max 3122 * can be defined using one of the two methods: 3123 * 3124 * $min->random($max) 3125 * $max->random($min) 3126 * 3127 * @param \phpseclib\Math\BigInteger $arg1 3128 * @param \phpseclib\Math\BigInteger $arg2 3129 * @return \phpseclib\Math\BigInteger 3130 * @access public 3131 * @internal The API for creating random numbers used to be $a->random($min, $max), where $a was a BigInteger object. 3132 * That method is still supported for BC purposes. 3133 */ 3134 function random($arg1, $arg2 = false) 3135 { 3136 if ($arg1 === false) { 3137 return false; 3138 } 3139 3140 if ($arg2 === false) { 3141 $max = $arg1; 3142 $min = $this; 3143 } else { 3144 $min = $arg1; 3145 $max = $arg2; 3146 } 3147 3148 $compare = $max->compare($min); 3149 3150 if (!$compare) { 3151 return $this->_normalize($min); 3152 } elseif ($compare < 0) { 3153 // if $min is bigger then $max, swap $min and $max 3154 $temp = $max; 3155 $max = $min; 3156 $min = $temp; 3157 } 3158 3159 static $one; 3160 if (!isset($one)) { 3161 $one = new static(1); 3162 } 3163 3164 $max = $max->subtract($min->subtract($one)); 3165 $size = strlen(ltrim($max->toBytes(), chr(0))); 3166 3167 /* 3168 doing $random % $max doesn't work because some numbers will be more likely to occur than others. 3169 eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145 3170 would produce 5 whereas the only value of random that could produce 139 would be 139. ie. 3171 not all numbers would be equally likely. some would be more likely than others. 3172 3173 creating a whole new random number until you find one that is within the range doesn't work 3174 because, for sufficiently small ranges, the likelihood that you'd get a number within that range 3175 would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability 3176 would be pretty high that $random would be greater than $max. 3177 3178 phpseclib works around this using the technique described here: 3179 3180 http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string 3181 */ 3182 $random_max = new static(chr(1) . str_repeat("\0", $size), 256); 3183 $random = $this->_random_number_helper($size); 3184 3185 list($max_multiple) = $random_max->divide($max); 3186 $max_multiple = $max_multiple->multiply($max); 3187 3188 while ($random->compare($max_multiple) >= 0) { 3189 $random = $random->subtract($max_multiple); 3190 $random_max = $random_max->subtract($max_multiple); 3191 $random = $random->bitwise_leftShift(8); 3192 $random = $random->add($this->_random_number_helper(1)); 3193 $random_max = $random_max->bitwise_leftShift(8); 3194 list($max_multiple) = $random_max->divide($max); 3195 $max_multiple = $max_multiple->multiply($max); 3196 } 3197 list(, $random) = $random->divide($max); 3198 3199 return $this->_normalize($random->add($min)); 3200 } 3201 3202 /** 3203 * Generate a random prime number. 3204 * 3205 * If there's not a prime within the given range, false will be returned. 3206 * If more than $timeout seconds have elapsed, give up and return false. 3207 * 3208 * @param \phpseclib\Math\BigInteger $arg1 3209 * @param \phpseclib\Math\BigInteger $arg2 3210 * @param int $timeout 3211 * @return Math_BigInteger|false 3212 * @access public 3213 * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=15 HAC 4.44}. 3214 */ 3215 function randomPrime($arg1, $arg2 = false, $timeout = false) 3216 { 3217 if ($arg1 === false) { 3218 return false; 3219 } 3220 3221 if ($arg2 === false) { 3222 $max = $arg1; 3223 $min = $this; 3224 } else { 3225 $min = $arg1; 3226 $max = $arg2; 3227 } 3228 3229 $compare = $max->compare($min); 3230 3231 if (!$compare) { 3232 return $min->isPrime() ? $min : false; 3233 } elseif ($compare < 0) { 3234 // if $min is bigger then $max, swap $min and $max 3235 $temp = $max; 3236 $max = $min; 3237 $min = $temp; 3238 } 3239 3240 static $one, $two; 3241 if (!isset($one)) { 3242 $one = new static(1); 3243 $two = new static(2); 3244 } 3245 3246 $start = time(); 3247 3248 $x = $this->random($min, $max); 3249 3250 // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>. 3251 if (MATH_BIGINTEGER_MODE == self::MODE_GMP && extension_loaded('gmp')) { 3252 $p = new static(); 3253 $p->value = gmp_nextprime($x->value); 3254 3255 if ($p->compare($max) <= 0) { 3256 return $p; 3257 } 3258 3259 if (!$min->equals($x)) { 3260 $x = $x->subtract($one); 3261 } 3262 3263 return $x->randomPrime($min, $x); 3264 } 3265 3266 if ($x->equals($two)) { 3267 return $x; 3268 } 3269 3270 $x->_make_odd(); 3271 if ($x->compare($max) > 0) { 3272 // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range 3273 if ($min->equals($max)) { 3274 return false; 3275 } 3276 $x = $min->copy(); 3277 $x->_make_odd(); 3278 } 3279 3280 $initial_x = $x->copy(); 3281 3282 while (true) { 3283 if ($timeout !== false && time() - $start > $timeout) { 3284 return false; 3285 } 3286 3287 if ($x->isPrime()) { 3288 return $x; 3289 } 3290 3291 $x = $x->add($two); 3292 3293 if ($x->compare($max) > 0) { 3294 $x = $min->copy(); 3295 if ($x->equals($two)) { 3296 return $x; 3297 } 3298 $x->_make_odd(); 3299 } 3300 3301 if ($x->equals($initial_x)) { 3302 return false; 3303 } 3304 } 3305 } 3306 3307 /** 3308 * Make the current number odd 3309 * 3310 * If the current number is odd it'll be unchanged. If it's even, one will be added to it. 3311 * 3312 * @see self::randomPrime() 3313 * @access private 3314 */ 3315 function _make_odd() 3316 { 3317 switch (MATH_BIGINTEGER_MODE) { 3318 case self::MODE_GMP: 3319 gmp_setbit($this->value, 0); 3320 break; 3321 case self::MODE_BCMATH: 3322 if ($this->value[strlen($this->value) - 1] % 2 == 0) { 3323 $this->value = bcadd($this->value, '1'); 3324 } 3325 break; 3326 default: 3327 $this->value[0] |= 1; 3328 } 3329 } 3330 3331 /** 3332 * Checks a numer to see if it's prime 3333 * 3334 * Assuming the $t parameter is not set, this function has an error rate of 2**-80. The main motivation for the 3335 * $t parameter is distributability. BigInteger::randomPrime() can be distributed across multiple pageloads 3336 * on a website instead of just one. 3337 * 3338 * @param \phpseclib\Math\BigInteger $t 3339 * @return bool 3340 * @access public 3341 * @internal Uses the 3342 * {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}. See 3343 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24}. 3344 */ 3345 function isPrime($t = false) 3346 { 3347 $length = strlen($this->toBytes()); 3348 3349 if (!$t) { 3350 // see HAC 4.49 "Note (controlling the error probability)" 3351 // @codingStandardsIgnoreStart 3352 if ($length >= 163) { $t = 2; } // floor(1300 / 8) 3353 else if ($length >= 106) { $t = 3; } // floor( 850 / 8) 3354 else if ($length >= 81 ) { $t = 4; } // floor( 650 / 8) 3355 else if ($length >= 68 ) { $t = 5; } // floor( 550 / 8) 3356 else if ($length >= 56 ) { $t = 6; } // floor( 450 / 8) 3357 else if ($length >= 50 ) { $t = 7; } // floor( 400 / 8) 3358 else if ($length >= 43 ) { $t = 8; } // floor( 350 / 8) 3359 else if ($length >= 37 ) { $t = 9; } // floor( 300 / 8) 3360 else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8) 3361 else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8) 3362 else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8) 3363 else { $t = 27; } 3364 // @codingStandardsIgnoreEnd 3365 } 3366 3367 // ie. gmp_testbit($this, 0) 3368 // ie. isEven() or !isOdd() 3369 switch (MATH_BIGINTEGER_MODE) { 3370 case self::MODE_GMP: 3371 return gmp_prob_prime($this->value, $t) != 0; 3372 case self::MODE_BCMATH: 3373 if ($this->value === '2') { 3374 return true; 3375 } 3376 if ($this->value[strlen($this->value) - 1] % 2 == 0) { 3377 return false; 3378 } 3379 break; 3380 default: 3381 if ($this->value == array(2)) { 3382 return true; 3383 } 3384 if (~$this->value[0] & 1) { 3385 return false; 3386 } 3387 } 3388 3389 static $primes, $zero, $one, $two; 3390 3391 if (!isset($primes)) { 3392 $primes = array( 3393 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 3394 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 3395 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 3396 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 3397 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 3398 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 3399 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 3400 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 3401 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 3402 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 3403 953, 967, 971, 977, 983, 991, 997 3404 ); 3405 3406 if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) { 3407 for ($i = 0; $i < count($primes); ++$i) { 3408 $primes[$i] = new static($primes[$i]); 3409 } 3410 } 3411 3412 $zero = new static(); 3413 $one = new static(1); 3414 $two = new static(2); 3415 } 3416 3417 if ($this->equals($one)) { 3418 return false; 3419 } 3420 3421 // see HAC 4.4.1 "Random search for probable primes" 3422 if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) { 3423 foreach ($primes as $prime) { 3424 list(, $r) = $this->divide($prime); 3425 if ($r->equals($zero)) { 3426 return $this->equals($prime); 3427 } 3428 } 3429 } else { 3430 $value = $this->value; 3431 foreach ($primes as $prime) { 3432 list(, $r) = $this->_divide_digit($value, $prime); 3433 if (!$r) { 3434 return count($value) == 1 && $value[0] == $prime; 3435 } 3436 } 3437 } 3438 3439 $n = $this->copy(); 3440 $n_1 = $n->subtract($one); 3441 $n_2 = $n->subtract($two); 3442 3443 $r = $n_1->copy(); 3444 $r_value = $r->value; 3445 // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s)); 3446 if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) { 3447 $s = 0; 3448 // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals($one) check earlier 3449 while ($r->value[strlen($r->value) - 1] % 2 == 0) { 3450 $r->value = bcdiv($r->value, '2', 0); 3451 ++$s; 3452 } 3453 } else { 3454 for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) { 3455 $temp = ~$r_value[$i] & 0xFFFFFF; 3456 for ($j = 1; ($temp >> $j) & 1; ++$j) { 3457 } 3458 if ($j != 25) { 3459 break; 3460 } 3461 } 3462 $s = 26 * $i + $j; 3463 $r->_rshift($s); 3464 } 3465 3466 for ($i = 0; $i < $t; ++$i) { 3467 $a = $this->random($two, $n_2); 3468 $y = $a->modPow($r, $n); 3469 3470 if (!$y->equals($one) && !$y->equals($n_1)) { 3471 for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) { 3472 $y = $y->modPow($two, $n); 3473 if ($y->equals($one)) { 3474 return false; 3475 } 3476 } 3477 3478 if (!$y->equals($n_1)) { 3479 return false; 3480 } 3481 } 3482 } 3483 return true; 3484 } 3485 3486 /** 3487 * Logical Left Shift 3488 * 3489 * Shifts BigInteger's by $shift bits. 3490 * 3491 * @param int $shift 3492 * @access private 3493 */ 3494 function _lshift($shift) 3495 { 3496 if ($shift == 0) { 3497 return; 3498 } 3499 3500 $num_digits = (int) ($shift / self::$base); 3501 $shift %= self::$base; 3502 $shift = 1 << $shift; 3503 3504 $carry = 0; 3505 3506 for ($i = 0; $i < count($this->value); ++$i) { 3507 $temp = $this->value[$i] * $shift + $carry; 3508 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 3509 $this->value[$i] = (int) ($temp - $carry * self::$baseFull); 3510 } 3511 3512 if ($carry) { 3513 $this->value[count($this->value)] = $carry; 3514 } 3515 3516 while ($num_digits--) { 3517 array_unshift($this->value, 0); 3518 } 3519 } 3520 3521 /** 3522 * Logical Right Shift 3523 * 3524 * Shifts BigInteger's by $shift bits. 3525 * 3526 * @param int $shift 3527 * @access private 3528 */ 3529 function _rshift($shift) 3530 { 3531 if ($shift == 0) { 3532 return; 3533 } 3534 3535 $num_digits = (int) ($shift / self::$base); 3536 $shift %= self::$base; 3537 $carry_shift = self::$base - $shift; 3538 $carry_mask = (1 << $shift) - 1; 3539 3540 if ($num_digits) { 3541 $this->value = array_slice($this->value, $num_digits); 3542 } 3543 3544 $carry = 0; 3545 3546 for ($i = count($this->value) - 1; $i >= 0; --$i) { 3547 $temp = $this->value[$i] >> $shift | $carry; 3548 $carry = ($this->value[$i] & $carry_mask) << $carry_shift; 3549 $this->value[$i] = $temp; 3550 } 3551 3552 $this->value = $this->_trim($this->value); 3553 } 3554 3555 /** 3556 * Normalize 3557 * 3558 * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision 3559 * 3560 * @param \phpseclib\Math\BigInteger $result 3561 * @return \phpseclib\Math\BigInteger 3562 * @see self::_trim() 3563 * @access private 3564 */ 3565 function _normalize($result) 3566 { 3567 $result->precision = $this->precision; 3568 $result->bitmask = $this->bitmask; 3569 3570 switch (MATH_BIGINTEGER_MODE) { 3571 case self::MODE_GMP: 3572 if ($this->bitmask !== false) { 3573 $flip = gmp_cmp($result->value, gmp_init(0)) < 0; 3574 if ($flip) { 3575 $result->value = gmp_neg($result->value); 3576 } 3577 $result->value = gmp_and($result->value, $result->bitmask->value); 3578 if ($flip) { 3579 $result->value = gmp_neg($result->value); 3580 } 3581 } 3582 3583 return $result; 3584 case self::MODE_BCMATH: 3585 if (!empty($result->bitmask->value)) { 3586 $result->value = bcmod($result->value, $result->bitmask->value); 3587 } 3588 3589 return $result; 3590 } 3591 3592 $value = &$result->value; 3593 3594 if (!count($value)) { 3595 $result->is_negative = false; 3596 return $result; 3597 } 3598 3599 $value = $this->_trim($value); 3600 3601 if (!empty($result->bitmask->value)) { 3602 $length = min(count($value), count($this->bitmask->value)); 3603 $value = array_slice($value, 0, $length); 3604 3605 for ($i = 0; $i < $length; ++$i) { 3606 $value[$i] = $value[$i] & $this->bitmask->value[$i]; 3607 } 3608 } 3609 3610 return $result; 3611 } 3612 3613 /** 3614 * Trim 3615 * 3616 * Removes leading zeros 3617 * 3618 * @param array $value 3619 * @return \phpseclib\Math\BigInteger 3620 * @access private 3621 */ 3622 function _trim($value) 3623 { 3624 for ($i = count($value) - 1; $i >= 0; --$i) { 3625 if ($value[$i]) { 3626 break; 3627 } 3628 unset($value[$i]); 3629 } 3630 3631 return $value; 3632 } 3633 3634 /** 3635 * Array Repeat 3636 * 3637 * @param array $input 3638 * @param mixed $multiplier 3639 * @return array 3640 * @access private 3641 */ 3642 function _array_repeat($input, $multiplier) 3643 { 3644 return ($multiplier) ? array_fill(0, $multiplier, $input) : array(); 3645 } 3646 3647 /** 3648 * Logical Left Shift 3649 * 3650 * Shifts binary strings $shift bits, essentially multiplying by 2**$shift. 3651 * 3652 * @param string $x (by reference) 3653 * @param int $shift 3654 * @return string 3655 * @access private 3656 */ 3657 function _base256_lshift(&$x, $shift) 3658 { 3659 if ($shift == 0) { 3660 return; 3661 } 3662 3663 $num_bytes = $shift >> 3; // eg. floor($shift/8) 3664 $shift &= 7; // eg. $shift % 8 3665 3666 $carry = 0; 3667 for ($i = strlen($x) - 1; $i >= 0; --$i) { 3668 $temp = ord($x[$i]) << $shift | $carry; 3669 $x[$i] = chr($temp); 3670 $carry = $temp >> 8; 3671 } 3672 $carry = ($carry != 0) ? chr($carry) : ''; 3673 $x = $carry . $x . str_repeat(chr(0), $num_bytes); 3674 } 3675 3676 /** 3677 * Logical Right Shift 3678 * 3679 * Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder. 3680 * 3681 * @param string $x (by referenc) 3682 * @param int $shift 3683 * @return string 3684 * @access private 3685 */ 3686 function _base256_rshift(&$x, $shift) 3687 { 3688 if ($shift == 0) { 3689 $x = ltrim($x, chr(0)); 3690 return ''; 3691 } 3692 3693 $num_bytes = $shift >> 3; // eg. floor($shift/8) 3694 $shift &= 7; // eg. $shift % 8 3695 3696 $remainder = ''; 3697 if ($num_bytes) { 3698 $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes; 3699 $remainder = substr($x, $start); 3700 $x = substr($x, 0, -$num_bytes); 3701 } 3702 3703 $carry = 0; 3704 $carry_shift = 8 - $shift; 3705 for ($i = 0; $i < strlen($x); ++$i) { 3706 $temp = (ord($x[$i]) >> $shift) | $carry; 3707 $carry = (ord($x[$i]) << $carry_shift) & 0xFF; 3708 $x[$i] = chr($temp); 3709 } 3710 $x = ltrim($x, chr(0)); 3711 3712 $remainder = chr($carry >> $carry_shift) . $remainder; 3713 3714 return ltrim($remainder, chr(0)); 3715 } 3716 3717 // one quirk about how the following functions are implemented is that PHP defines N to be an unsigned long 3718 // at 32-bits, while java's longs are 64-bits. 3719 3720 /** 3721 * Converts 32-bit integers to bytes. 3722 * 3723 * @param int $x 3724 * @return string 3725 * @access private 3726 */ 3727 function _int2bytes($x) 3728 { 3729 return ltrim(pack('N', $x), chr(0)); 3730 } 3731 3732 /** 3733 * Converts bytes to 32-bit integers 3734 * 3735 * @param string $x 3736 * @return int 3737 * @access private 3738 */ 3739 function _bytes2int($x) 3740 { 3741 $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT)); 3742 return $temp['int']; 3743 } 3744 3745 /** 3746 * DER-encode an integer 3747 * 3748 * The ability to DER-encode integers is needed to create RSA public keys for use with OpenSSL 3749 * 3750 * @see self::modPow() 3751 * @access private 3752 * @param int $length 3753 * @return string 3754 */ 3755 function _encodeASN1Length($length) 3756 { 3757 if ($length <= 0x7F) { 3758 return chr($length); 3759 } 3760 3761 $temp = ltrim(pack('N', $length), chr(0)); 3762 return pack('Ca*', 0x80 | strlen($temp), $temp); 3763 } 3764 3765 /** 3766 * Single digit division 3767 * 3768 * Even if int64 is being used the division operator will return a float64 value 3769 * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't 3770 * have the precision of int64 this is a problem so, when int64 is being used, 3771 * we'll guarantee that the dividend is divisible by first subtracting the remainder. 3772 * 3773 * @access private 3774 * @param int $x 3775 * @param int $y 3776 * @return int 3777 */ 3778 function _safe_divide($x, $y) 3779 { 3780 if (self::$base === 26) { 3781 return (int) ($x / $y); 3782 } 3783 3784 // self::$base === 31 3785 return ($x - (