[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * PHP 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;
  17  
  18  use phpseclib3\Math\BigInteger\Engines\PHP;
  19  
  20  /**
  21   * PHP Modular Exponentiation Engine
  22   *
  23   * @package PHP
  24   * @author  Jim Wigginton <[email protected]>
  25   * @access  public
  26   */
  27  abstract class Base extends PHP
  28  {
  29      /**
  30       * Cache constants
  31       *
  32       * $cache[self::VARIABLE] tells us whether or not the cached data is still valid.
  33       *
  34       * @access private
  35       */
  36      const VARIABLE = 0;
  37      /**
  38       * $cache[self::DATA] contains the cached data.
  39       *
  40       * @access private
  41       */
  42      const DATA = 1;
  43  
  44      /**
  45       * Test for engine validity
  46       *
  47       * @return bool
  48       */
  49      public static function isValidEngine()
  50      {
  51          return static::class != __CLASS__;
  52      }
  53  
  54      /**
  55       * Performs modular exponentiation.
  56       *
  57       * The most naive approach to modular exponentiation has very unreasonable requirements, and
  58       * and although the approach involving repeated squaring does vastly better, it, too, is impractical
  59       * for our purposes.  The reason being that division - by far the most complicated and time-consuming
  60       * of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
  61       *
  62       * Modular reductions resolve this issue.  Although an individual modular reduction takes more time
  63       * then an individual division, when performed in succession (with the same modulo), they're a lot faster.
  64       *
  65       * The two most commonly used modular reductions are Barrett and Montgomery reduction.  Montgomery reduction,
  66       * although faster, only works when the gcd of the modulo and of the base being used is 1.  In RSA, when the
  67       * base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because
  68       * the product of two odd numbers is odd), but what about when RSA isn't used?
  69       *
  70       * In contrast, Barrett reduction has no such constraint.  As such, some bigint implementations perform a
  71       * Barrett reduction after every operation in the modpow function.  Others perform Barrett reductions when the
  72       * modulo is even and Montgomery reductions when the modulo is odd.  BigInteger.java's modPow method, however,
  73       * uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and
  74       * the other, a power of two - and recombine them, later.  This is the method that this modPow function uses.
  75       * {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.
  76       *
  77       * @param PHP $x
  78       * @param PHP $e
  79       * @param PHP $n
  80       * @param string $class
  81       * @return PHP
  82       */
  83      protected static function powModHelper(PHP $x, PHP $e, PHP $n, $class)
  84      {
  85          if (empty($e->value)) {
  86              $temp = new $class();
  87              $temp->value = [1];
  88              return $x->normalize($temp);
  89          }
  90  
  91          if ($e->value == [1]) {
  92              list(, $temp) = $x->divide($n);
  93              return $x->normalize($temp);
  94          }
  95  
  96          if ($e->value == [2]) {
  97              $temp = new $class();
  98              $temp->value = $class::square($x->value);
  99              list(, $temp) = $temp->divide($n);
 100              return $x->normalize($temp);
 101          }
 102  
 103          return $x->normalize(static::slidingWindow($x, $e, $n, $class));
 104      }
 105  
 106      /**
 107       * Modular reduction preparation
 108       *
 109       * @param array $x
 110       * @param array $n
 111       * @param string $class
 112       * @see self::slidingWindow()
 113       * @return array
 114       */
 115      protected static function prepareReduce(array $x, array $n, $class)
 116      {
 117          return static::reduce($x, $n, $class);
 118      }
 119  
 120      /**
 121       * Modular multiply
 122       *
 123       * @param array $x
 124       * @param array $y
 125       * @param array $n
 126       * @param string $class
 127       * @see self::slidingWindow()
 128       * @return array
 129       */
 130      protected static function multiplyReduce(array $x, array $y, array $n, $class)
 131      {
 132          $temp = $class::multiplyHelper($x, false, $y, false);
 133          return static::reduce($temp[self::VALUE], $n, $class);
 134      }
 135  
 136      /**
 137       * Modular square
 138       *
 139       * @param array $x
 140       * @param array $n
 141       * @param string $class
 142       * @see self::slidingWindow()
 143       * @return array
 144       */
 145      protected static function squareReduce(array $x, array $n, $class)
 146      {
 147          return static::reduce($class::square($x), $n, $class);
 148      }
 149  }