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