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.  * PHP Modular Exponentiation 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\PHP;
  17.  
  18. use phpseclib3\Math\BigInteger\Engines\PHP;
  19.  
  20. /**
  21.  * PHP Modular Exponentiation Engine
  22.  *
  23.  * @package PHP
  24.  * @author  Jim Wigginton <terrafrost@php.net>
  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. }
  150.