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 Montgomery 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\Engine;
  19. use phpseclib3\Math\BigInteger\Engines\PHP;
  20. use phpseclib3\Math\BigInteger\Engines\PHP\Reductions\PowerOfTwo;
  21.  
  22. /**
  23.  * PHP Montgomery Modular Exponentiation Engine
  24.  *
  25.  * @package PHP
  26.  * @author  Jim Wigginton <terrafrost@php.net>
  27.  * @access  public
  28.  */
  29. abstract class Montgomery extends Base
  30. {
  31.     /**
  32.      * Test for engine validity
  33.      *
  34.      * @return bool
  35.      */
  36.     public static function isValidEngine()
  37.     {
  38.         return static::class != __CLASS__;
  39.     }
  40.  
  41.     /**
  42.      * Performs modular exponentiation.
  43.      *
  44.      * @template T of Engine
  45.      * @param Engine $x
  46.      * @param Engine $e
  47.      * @param Engine $n
  48.      * @param class-string<T> $class
  49.      * @return T
  50.      */
  51.     protected static function slidingWindow(Engine $x, Engine $e, Engine $n, $class)
  52.     {
  53.         // is the modulo odd?
  54.         if ($n->value[0] & 1) {
  55.             return parent::slidingWindow($x, $e, $n, $class);
  56.         }
  57.         // if it's not, it's even
  58.  
  59.         // find the lowest set bit (eg. the max pow of 2 that divides $n)
  60.         for ($i = 0; $i < count($n->value); ++$i) {
  61.             if ($n->value[$i]) {
  62.                 $temp = decbin($n->value[$i]);
  63.                 $j = strlen($temp) - strrpos($temp, '1') - 1;
  64.                 $j += $class::BASE * $i;
  65.                 break;
  66.             }
  67.         }
  68.         // at this point, 2^$j * $n/(2^$j) == $n
  69.  
  70.         $mod1 = clone $n;
  71.         $mod1->rshift($j);
  72.         $mod2 = new $class();
  73.         $mod2->value = [1];
  74.         $mod2->lshift($j);
  75.  
  76.         $part1 = $mod1->value != [1] ? parent::slidingWindow($x, $e, $mod1, $class) : new $class();
  77.         $part2 = PowerOfTwo::slidingWindow($x, $e, $mod2, $class);
  78.  
  79.         $y1 = $mod2->modInverse($mod1);
  80.         $y2 = $mod1->modInverse($mod2);
  81.  
  82.         $result = $part1->multiply($mod2);
  83.         $result = $result->multiply($y1);
  84.  
  85.         $temp = $part2->multiply($mod1);
  86.         $temp = $temp->multiply($y2);
  87.  
  88.         $result = $result->add($temp);
  89.         list(, $result) = $result->divide($n);
  90.  
  91.         return $result;
  92.     }
  93. }
  94.