[Summary view] [Print] [Text view]

   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 <[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\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 <[email protected]>
  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  }