[Summary view] [Print] [Text view]

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