Subversion Repositories oidplus

Rev

Rev 846 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

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