backup
/
src
/
JetBackup
/
3rdparty
/
phpseclib3
/
Math
/
BigInteger
/
Engines
/
PHP
Last commit date
Reductions
1 year ago
.htaccess
1 year ago
Base.php
1 year ago
DefaultEngine.php
1 year ago
Montgomery.php
1 year ago
OpenSSL.php
1 year ago
index.html
1 year ago
web.config
1 year ago
Base.php
123 lines
| 1 | <?php |
| 2 | |
| 3 | /** |
| 4 | * PHP 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 | declare(strict_types=1); |
| 15 | |
| 16 | namespace phpseclib3\Math\BigInteger\Engines\PHP; |
| 17 | |
| 18 | use phpseclib3\Math\BigInteger\Engines\PHP; |
| 19 | |
| 20 | /** |
| 21 | * PHP Modular Exponentiation Engine |
| 22 | * |
| 23 | * @author Jim Wigginton <terrafrost@php.net> |
| 24 | */ |
| 25 | abstract class Base extends PHP |
| 26 | { |
| 27 | /** |
| 28 | * Cache constants |
| 29 | * |
| 30 | * $cache[self::VARIABLE] tells us whether or not the cached data is still valid. |
| 31 | */ |
| 32 | public const VARIABLE = 0; |
| 33 | /** |
| 34 | * $cache[self::DATA] contains the cached data. |
| 35 | */ |
| 36 | public const DATA = 1; |
| 37 | |
| 38 | /** |
| 39 | * Test for engine validity |
| 40 | */ |
| 41 | public static function isValidEngine(): bool |
| 42 | { |
| 43 | return static::class != __CLASS__; |
| 44 | } |
| 45 | |
| 46 | /** |
| 47 | * Performs modular exponentiation. |
| 48 | * |
| 49 | * The most naive approach to modular exponentiation has very unreasonable requirements, and |
| 50 | * and although the approach involving repeated squaring does vastly better, it, too, is impractical |
| 51 | * for our purposes. The reason being that division - by far the most complicated and time-consuming |
| 52 | * of the basic operations (eg. +,-,*,/) - occurs multiple times within it. |
| 53 | * |
| 54 | * Modular reductions resolve this issue. Although an individual modular reduction takes more time |
| 55 | * then an individual division, when performed in succession (with the same modulo), they're a lot faster. |
| 56 | * |
| 57 | * The two most commonly used modular reductions are Barrett and Montgomery reduction. Montgomery reduction, |
| 58 | * although faster, only works when the gcd of the modulo and of the base being used is 1. In RSA, when the |
| 59 | * base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because |
| 60 | * the product of two odd numbers is odd), but what about when RSA isn't used? |
| 61 | * |
| 62 | * In contrast, Barrett reduction has no such constraint. As such, some bigint implementations perform a |
| 63 | * Barrett reduction after every operation in the modpow function. Others perform Barrett reductions when the |
| 64 | * modulo is even and Montgomery reductions when the modulo is odd. BigInteger.java's modPow method, however, |
| 65 | * uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and |
| 66 | * the other, a power of two - and recombine them, later. This is the method that this modPow function uses. |
| 67 | * {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates. |
| 68 | */ |
| 69 | protected static function powModHelper(PHP $x, PHP $e, PHP $n, string $class): PHP |
| 70 | { |
| 71 | if (empty($e->value)) { |
| 72 | $temp = new $class(); |
| 73 | $temp->value = [1]; |
| 74 | return $x->normalize($temp); |
| 75 | } |
| 76 | |
| 77 | if ($e->value == [1]) { |
| 78 | [, $temp] = $x->divide($n); |
| 79 | return $x->normalize($temp); |
| 80 | } |
| 81 | |
| 82 | if ($e->value == [2]) { |
| 83 | $temp = new $class(); |
| 84 | $temp->value = $class::square($x->value); |
| 85 | [, $temp] = $temp->divide($n); |
| 86 | return $x->normalize($temp); |
| 87 | } |
| 88 | |
| 89 | return $x->normalize(static::slidingWindow($x, $e, $n, $class)); |
| 90 | } |
| 91 | |
| 92 | /** |
| 93 | * Modular reduction preparation |
| 94 | * |
| 95 | * @see self::slidingWindow() |
| 96 | */ |
| 97 | protected static function prepareReduce(array $x, array $n, string $class): array |
| 98 | { |
| 99 | return static::reduce($x, $n, $class); |
| 100 | } |
| 101 | |
| 102 | /** |
| 103 | * Modular multiply |
| 104 | * |
| 105 | * @see self::slidingWindow() |
| 106 | */ |
| 107 | protected static function multiplyReduce(array $x, array $y, array $n, string $class): array |
| 108 | { |
| 109 | $temp = $class::multiplyHelper($x, false, $y, false); |
| 110 | return static::reduce($temp[self::VALUE], $n, $class); |
| 111 | } |
| 112 | |
| 113 | /** |
| 114 | * Modular square |
| 115 | * |
| 116 | * @see self::slidingWindow() |
| 117 | */ |
| 118 | protected static function squareReduce(array $x, array $n, string $class): array |
| 119 | { |
| 120 | return static::reduce($class::square($x), $n, $class); |
| 121 | } |
| 122 | } |
| 123 |