[Summary view] [Print] [Text view]

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