[Summary view] [Print] [Text view]

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