Rev 846 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 827 | daniel-mar | 1 | <?php |
| 2 | |||
| 3 | /** |
||
| 4 | * PHP Montgomery Modular Exponentiation Engine |
||
| 5 | * |
||
| 6 | * PHP version 5 and 7 |
||
| 7 | * |
||
| 874 | daniel-mar | 8 | * @category Math |
| 9 | * @package BigInteger |
||
| 827 | daniel-mar | 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 | |||
| 16 | namespace phpseclib3\Math\BigInteger\Engines\PHP\Reductions; |
||
| 17 | |||
| 18 | use phpseclib3\Math\BigInteger\Engines\PHP\Montgomery as Progenitor; |
||
| 19 | |||
| 20 | /** |
||
| 21 | * PHP Montgomery Modular Exponentiation Engine |
||
| 22 | * |
||
| 874 | daniel-mar | 23 | * @package PHP |
| 827 | daniel-mar | 24 | * @author Jim Wigginton <terrafrost@php.net> |
| 874 | daniel-mar | 25 | * @access public |
| 827 | daniel-mar | 26 | */ |
| 27 | abstract 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 | } |