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