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