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