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 16namespace phpseclib3\Math\BigInteger\Engines\PHP; 17 18use phpseclib3\Math\BigInteger\Engines\Engine; 19use phpseclib3\Math\BigInteger\Engines\PHP; 20use 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 */ 29abstract 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