Subversion Repositories oidplus

Rev

Rev 874 | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1. <?php
  2.  
  3. /**
  4.  * PHP Montgomery Modular Exponentiation Engine
  5.  *
  6.  * PHP version 5 and 7
  7.  *
  8.  * @author    Jim Wigginton <terrafrost@php.net>
  9.  * @copyright 2017 Jim Wigginton
  10.  * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  11.  * @link      http://pear.php.net/package/Math_BigInteger
  12.  */
  13.  
  14. namespace phpseclib3\Math\BigInteger\Engines\PHP\Reductions;
  15.  
  16. use phpseclib3\Math\BigInteger\Engines\PHP\Montgomery as Progenitor;
  17.  
  18. /**
  19.  * PHP Montgomery Modular Exponentiation Engine
  20.  *
  21.  * @author  Jim Wigginton <terrafrost@php.net>
  22.  */
  23. abstract class Montgomery extends Progenitor
  24. {
  25.     /**
  26.      * Prepare a number for use in Montgomery Modular Reductions
  27.      *
  28.      * @param array $x
  29.      * @param array $n
  30.      * @param string $class
  31.      * @return array
  32.      */
  33.     protected static function prepareReduce(array $x, array $n, $class)
  34.     {
  35.         $lhs = new $class();
  36.         $lhs->value = array_merge(self::array_repeat(0, count($n)), $x);
  37.         $rhs = new $class();
  38.         $rhs->value = $n;
  39.  
  40.         list(, $temp) = $lhs->divide($rhs);
  41.         return $temp->value;
  42.     }
  43.  
  44.     /**
  45.      * Montgomery Multiply
  46.      *
  47.      * Interleaves the montgomery reduction and long multiplication algorithms together as described in
  48.      * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36}
  49.      *
  50.      * @param array $x
  51.      * @param array $n
  52.      * @param string $class
  53.      * @return array
  54.      */
  55.     protected static function reduce(array $x, array $n, $class)
  56.     {
  57.         static $cache = [
  58.             self::VARIABLE => [],
  59.             self::DATA => []
  60.         ];
  61.  
  62.         if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
  63.             $key = count($cache[self::VARIABLE]);
  64.             $cache[self::VARIABLE][] = $x;
  65.             $cache[self::DATA][] = self::modInverse67108864($n, $class);
  66.         }
  67.  
  68.         $k = count($n);
  69.  
  70.         $result = [self::VALUE => $x];
  71.  
  72.         for ($i = 0; $i < $k; ++$i) {
  73.             $temp = $result[self::VALUE][$i] * $cache[self::DATA][$key];
  74.             $temp = $temp - $class::BASE_FULL * ($class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
  75.             $temp = $class::regularMultiply([$temp], $n);
  76.             $temp = array_merge(self::array_repeat(0, $i), $temp);
  77.             $result = $class::addHelper($result[self::VALUE], false, $temp, false);
  78.         }
  79.  
  80.         $result[self::VALUE] = array_slice($result[self::VALUE], $k);
  81.  
  82.         if (self::compareHelper($result, false, $n, false) >= 0) {
  83.             $result = $class::subtractHelper($result[self::VALUE], false, $n, false);
  84.         }
  85.  
  86.         return $result[self::VALUE];
  87.     }
  88.  
  89.     /**
  90.      * Modular Inverse of a number mod 2**26 (eg. 67108864)
  91.      *
  92.      * Based off of the bnpInvDigit function implemented and justified in the following URL:
  93.      *
  94.      * {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js}
  95.      *
  96.      * The following URL provides more info:
  97.      *
  98.      * {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85}
  99.      *
  100.      * As for why we do all the bitmasking...  strange things can happen when converting from floats to ints. For
  101.      * instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields
  102.      * int(-2147483648).  To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't
  103.      * auto-converted to floats.  The outermost bitmask is present because without it, there's no guarantee that
  104.      * the "residue" returned would be the so-called "common residue".  We use fmod, in the last step, because the
  105.      * maximum possible $x is 26 bits and the maximum $result is 16 bits.  Thus, we have to be able to handle up to
  106.      * 40 bits, which only 64-bit floating points will support.
  107.      *
  108.      * Thanks to Pedro Gimeno Fortea for input!
  109.      *
  110.      * @param array $x
  111.      * @param string $class
  112.      * @return int
  113.      */
  114.     protected static function modInverse67108864(array $x, $class) // 2**26 == 67,108,864
  115.     {
  116.         $x = -$x[0];
  117.         $result = $x & 0x3; // x**-1 mod 2**2
  118.         $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4
  119.         $result = ($result * (2 - ($x & 0xFF) * $result))  & 0xFF; // x**-1 mod 2**8
  120.         $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16
  121.         $result = $class::BASE == 26 ?
  122.             fmod($result * (2 - fmod($x * $result, $class::BASE_FULL)), $class::BASE_FULL) : // x**-1 mod 2**26
  123.             ($result * (2 - ($x * $result) % $class::BASE_FULL)) % $class::BASE_FULL;
  124.         return $result & $class::MAX_DIGIT;
  125.     }
  126. }
  127.