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\Reductions; 17 18use phpseclib3\Math\BigInteger\Engines\PHP\Montgomery as Progenitor; 19 20/** 21 * PHP Montgomery Modular Exponentiation Engine 22 * 23 * @package PHP 24 * @author Jim Wigginton <terrafrost@php.net> 25 * @access public 26 */ 27abstract class Montgomery extends Progenitor 28{ 29 /** 30 * Prepare a number for use in Montgomery Modular Reductions 31 * 32 * @param array $x 33 * @param array $n 34 * @param string $class 35 * @return array 36 */ 37 protected static function prepareReduce(array $x, array $n, $class) 38 { 39 $lhs = new $class(); 40 $lhs->value = array_merge(self::array_repeat(0, count($n)), $x); 41 $rhs = new $class(); 42 $rhs->value = $n; 43 44 list(, $temp) = $lhs->divide($rhs); 45 return $temp->value; 46 } 47 48 /** 49 * Montgomery Multiply 50 * 51 * Interleaves the montgomery reduction and long multiplication algorithms together as described in 52 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36} 53 * 54 * @param array $x 55 * @param array $n 56 * @param string $class 57 * @return array 58 */ 59 protected static function reduce(array $x, array $n, $class) 60 { 61 static $cache = [ 62 self::VARIABLE => [], 63 self::DATA => [] 64 ]; 65 66 if (($key = array_search($n, $cache[self::VARIABLE])) === false) { 67 $key = count($cache[self::VARIABLE]); 68 $cache[self::VARIABLE][] = $x; 69 $cache[self::DATA][] = self::modInverse67108864($n, $class); 70 } 71 72 $k = count($n); 73 74 $result = [self::VALUE => $x]; 75 76 for ($i = 0; $i < $k; ++$i) { 77 $temp = $result[self::VALUE][$i] * $cache[self::DATA][$key]; 78 $temp = $temp - $class::BASE_FULL * ($class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31)); 79 $temp = $class::regularMultiply([$temp], $n); 80 $temp = array_merge(self::array_repeat(0, $i), $temp); 81 $result = $class::addHelper($result[self::VALUE], false, $temp, false); 82 } 83 84 $result[self::VALUE] = array_slice($result[self::VALUE], $k); 85 86 if (self::compareHelper($result, false, $n, false) >= 0) { 87 $result = $class::subtractHelper($result[self::VALUE], false, $n, false); 88 } 89 90 return $result[self::VALUE]; 91 } 92 93 /** 94 * Modular Inverse of a number mod 2**26 (eg. 67108864) 95 * 96 * Based off of the bnpInvDigit function implemented and justified in the following URL: 97 * 98 * {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js} 99 * 100 * The following URL provides more info: 101 * 102 * {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85} 103 * 104 * As for why we do all the bitmasking... strange things can happen when converting from floats to ints. For 105 * instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields 106 * int(-2147483648). To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't 107 * auto-converted to floats. The outermost bitmask is present because without it, there's no guarantee that 108 * the "residue" returned would be the so-called "common residue". We use fmod, in the last step, because the 109 * maximum possible $x is 26 bits and the maximum $result is 16 bits. Thus, we have to be able to handle up to 110 * 40 bits, which only 64-bit floating points will support. 111 * 112 * Thanks to Pedro Gimeno Fortea for input! 113 * 114 * @param array $x 115 * @param string $class 116 * @return int 117 */ 118 protected static function modInverse67108864(array $x, $class) // 2**26 == 67,108,864 119 { 120 $x = -$x[0]; 121 $result = $x & 0x3; // x**-1 mod 2**2 122 $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4 123 $result = ($result * (2 - ($x & 0xFF) * $result)) & 0xFF; // x**-1 mod 2**8 124 $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16 125 $result = $class::BASE == 26 ? 126 fmod($result * (2 - fmod($x * $result, $class::BASE_FULL)), $class::BASE_FULL) : // x**-1 mod 2**26 127 ($result * (2 - ($x * $result) % $class::BASE_FULL)) % $class::BASE_FULL; 128 return $result & $class::MAX_DIGIT; 129 } 130} 131