Montgomery.php — JetBackup – Backup, Restore & Migrate 3.1.22.3

backup / src / JetBackup / 3rdparty / phpseclib3 / Math / BigInteger / Engines / PHP / Reductions / Montgomery.php

backup / src / JetBackup / 3rdparty / phpseclib3 / Math / BigInteger / Engines / PHP / Reductions Last commit date

.htaccess 1 year ago Barrett.php 1 year ago Classic.php 1 year ago EvalBarrett.php 1 year ago Montgomery.php 1 year ago MontgomeryMult.php 1 year ago PowerOfTwo.php 1 year ago index.html 1 year ago web.config 1 year ago

Montgomery.php

115 lines

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