|
1
|
|
|
<?php |
|
2
|
|
|
|
|
3
|
|
|
namespace Mdanter\Ecc\Math; |
|
4
|
|
|
|
|
5
|
|
|
/*********************************************************************** |
|
6
|
|
|
* Copyright (C) 2012 Matyas Danter |
|
7
|
|
|
* |
|
8
|
|
|
* Permission is hereby granted, free of charge, to any person obtaining |
|
9
|
|
|
* a copy of this software and associated documentation files (the "Software"), |
|
10
|
|
|
* to deal in the Software without restriction, including without limitation |
|
11
|
|
|
* the rights to use, copy, modify, merge, publish, distribute, sublicense, |
|
12
|
|
|
* and/or sell copies of the Software, and to permit persons to whom the |
|
13
|
|
|
* Software is furnished to do so, subject to the following conditions: |
|
14
|
|
|
* |
|
15
|
|
|
* The above copyright notice and this permission notice shall be included |
|
16
|
|
|
* in all copies or substantial portions of the Software. |
|
17
|
|
|
* |
|
18
|
|
|
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS |
|
19
|
|
|
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
|
20
|
|
|
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
|
21
|
|
|
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES |
|
22
|
|
|
* OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, |
|
23
|
|
|
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
|
24
|
|
|
* OTHER DEALINGS IN THE SOFTWARE. |
|
25
|
|
|
************************************************************************/ |
|
26
|
|
|
|
|
27
|
|
|
/** |
|
28
|
|
|
* Implementation of some number theoretic algorithms |
|
29
|
|
|
* |
|
30
|
|
|
* @author Matyas Danter |
|
31
|
|
|
*/ |
|
32
|
|
|
|
|
33
|
|
|
use Mdanter\Ecc\Exception\NumberTheoryException; |
|
34
|
|
|
use Mdanter\Ecc\Exception\SquareRootException; |
|
35
|
|
|
|
|
36
|
|
|
/** |
|
37
|
|
|
* Rewritten to take a MathAdaptor to handle different environments. Has |
|
38
|
|
|
* some desireable functions for public key compression/recovery. |
|
39
|
|
|
*/ |
|
40
|
|
|
class NumberTheory |
|
41
|
|
|
{ |
|
42
|
|
|
/** |
|
43
|
|
|
* @var GmpMathInterface |
|
44
|
|
|
*/ |
|
45
|
|
|
private $adapter; |
|
46
|
|
|
|
|
47
|
|
|
/** |
|
48
|
|
|
* @var GMP |
|
49
|
|
|
*/ |
|
50
|
|
|
private $zero; |
|
51
|
|
|
|
|
52
|
|
|
/** |
|
53
|
|
|
* @var GMP |
|
54
|
|
|
*/ |
|
55
|
|
|
private $one; |
|
56
|
|
|
|
|
57
|
|
|
/** |
|
58
|
|
|
* @var GMP |
|
59
|
|
|
*/ |
|
60
|
|
|
private $two; |
|
61
|
|
|
|
|
62
|
|
|
|
|
63
|
|
|
/** |
|
64
|
|
|
* @param GmpMathInterface $adapter |
|
65
|
|
|
*/ |
|
66
|
|
|
public function __construct(GmpMathInterface $adapter) |
|
67
|
|
|
{ |
|
68
|
|
|
$this->adapter = $adapter; |
|
69
|
|
|
$this->zero = gmp_init(0, 10); |
|
|
|
|
|
|
70
|
|
|
$this->one = gmp_init(1, 10); |
|
|
|
|
|
|
71
|
|
|
$this->two = gmp_init(2, 10); |
|
|
|
|
|
|
72
|
|
|
} |
|
73
|
|
|
|
|
74
|
|
|
/** |
|
75
|
|
|
* @param \GMP[] $poly |
|
76
|
|
|
* @param \GMP[] $polymod |
|
77
|
|
|
* @param \GMP $p |
|
78
|
|
|
* @return \GMP[] |
|
79
|
|
|
*/ |
|
80
|
|
|
public function polynomialReduceMod(array $poly, array $polymod, \GMP $p): array |
|
81
|
|
|
{ |
|
82
|
|
|
$adapter = $this->adapter; |
|
83
|
|
|
|
|
84
|
|
|
// Only enter if last value is set, implying count > 0 |
|
85
|
|
|
if ((($last = end($polymod)) instanceof \GMP) && $adapter->equals($last, $this->one)) { |
|
86
|
|
|
$count_polymod = count($polymod); |
|
87
|
|
|
while (count($poly) >= $count_polymod) { |
|
88
|
|
|
if (!$adapter->equals(end($poly), $this->zero)) { |
|
89
|
|
|
for ($i = 2; $i < $count_polymod + 1; $i++) { |
|
90
|
|
|
$poly[count($poly) - $i] = |
|
91
|
|
|
$adapter->mod( |
|
92
|
|
|
$adapter->sub( |
|
93
|
|
|
$poly[count($poly) - $i], |
|
94
|
|
|
$adapter->mul( |
|
95
|
|
|
end($poly), |
|
96
|
|
|
$polymod[$count_polymod - $i] |
|
97
|
|
|
) |
|
98
|
|
|
), |
|
99
|
|
|
$p |
|
100
|
|
|
); |
|
101
|
|
|
} |
|
102
|
|
|
} |
|
103
|
|
|
|
|
104
|
|
|
$poly = array_slice($poly, 0, count($poly) - 1); |
|
105
|
|
|
} |
|
106
|
|
|
|
|
107
|
|
|
return $poly; |
|
108
|
|
|
} |
|
109
|
|
|
|
|
110
|
|
|
throw new NumberTheoryException('Unable to calculate polynomialReduceMod'); |
|
111
|
|
|
} |
|
112
|
|
|
|
|
113
|
|
|
/** |
|
114
|
|
|
* @param \GMP[] $m1 |
|
115
|
|
|
* @param \GMP[] $m2 |
|
116
|
|
|
* @param \GMP[] $polymod |
|
117
|
|
|
* @param \GMP $p |
|
118
|
|
|
* @return \GMP[] |
|
119
|
|
|
*/ |
|
120
|
|
|
public function polynomialMultiplyMod(array $m1, array $m2, array $polymod, \GMP $p): array |
|
121
|
|
|
{ |
|
122
|
|
|
$prod = array(); |
|
123
|
|
|
$cm1 = count($m1); |
|
124
|
|
|
$cm2 = count($m2); |
|
125
|
|
|
|
|
126
|
|
|
for ($i = 0; $i < $cm1; $i++) { |
|
127
|
|
|
for ($j = 0; $j < $cm2; $j++) { |
|
128
|
|
|
$index = $i + $j; |
|
129
|
|
|
if (!isset($prod[$index])) { |
|
130
|
|
|
$prod[$index] = $this->zero; |
|
131
|
|
|
} |
|
132
|
|
|
$prod[$index] = |
|
133
|
|
|
$this->adapter->mod( |
|
134
|
|
|
$this->adapter->add( |
|
135
|
|
|
$prod[$index], |
|
136
|
|
|
$this->adapter->mul( |
|
137
|
|
|
$m1[$i], |
|
138
|
|
|
$m2[$j] |
|
139
|
|
|
) |
|
140
|
|
|
), |
|
141
|
|
|
$p |
|
142
|
|
|
); |
|
143
|
|
|
} |
|
144
|
|
|
} |
|
145
|
|
|
|
|
146
|
|
|
return $this->polynomialReduceMod($prod, $polymod, $p); |
|
147
|
|
|
} |
|
148
|
|
|
|
|
149
|
|
|
/** |
|
150
|
|
|
* @param \GMP[] $base |
|
151
|
|
|
* @param \GMP $exponent |
|
152
|
|
|
* @param \GMP[] $polymod |
|
153
|
|
|
* @param \GMP $p |
|
154
|
|
|
* @return \GMP[] |
|
155
|
|
|
*/ |
|
156
|
|
|
public function polynomialPowMod(array $base, \GMP $exponent, array $polymod, \GMP $p): array |
|
157
|
|
|
{ |
|
158
|
|
|
$adapter = $this->adapter; |
|
159
|
|
|
|
|
160
|
|
|
if ($adapter->cmp($exponent, $p) < 0) { |
|
161
|
|
|
if ($adapter->equals($exponent, $this->zero)) { |
|
162
|
|
|
return $this->one; |
|
|
|
|
|
|
163
|
|
|
} |
|
164
|
|
|
|
|
165
|
|
|
$G = $base; |
|
166
|
|
|
$k = $exponent; |
|
167
|
|
|
|
|
168
|
|
|
if ($adapter->equals($adapter->mod($k, $this->two), $this->one)) { |
|
169
|
|
|
$s = $G; |
|
170
|
|
|
} else { |
|
171
|
|
|
$s = array($this->one); |
|
172
|
|
|
} |
|
173
|
|
|
|
|
174
|
|
|
while ($adapter->cmp($k, $this->one) > 0) { |
|
175
|
|
|
$k = $adapter->div($k, $this->two); |
|
176
|
|
|
|
|
177
|
|
|
$G = $this->polynomialMultiplyMod($G, $G, $polymod, $p); |
|
178
|
|
|
if ($adapter->equals($adapter->mod($k, $this->two), $this->one)) { |
|
179
|
|
|
$s = $this->polynomialMultiplyMod($G, $s, $polymod, $p); |
|
180
|
|
|
} |
|
181
|
|
|
} |
|
182
|
|
|
|
|
183
|
|
|
return $s; |
|
184
|
|
|
} |
|
185
|
|
|
|
|
186
|
|
|
throw new NumberTheoryException('Unable to calculate polynomialPowMod'); |
|
187
|
|
|
} |
|
188
|
|
|
|
|
189
|
|
|
/** |
|
190
|
|
|
* @param \GMP $a |
|
191
|
|
|
* @param \GMP $p |
|
192
|
|
|
* @return \GMP |
|
193
|
|
|
*/ |
|
194
|
|
|
public function squareRootModP(\GMP $a, \GMP $p): \GMP |
|
195
|
|
|
{ |
|
196
|
|
|
$math = $this->adapter; |
|
197
|
|
|
$four = gmp_init(4, 10); |
|
198
|
|
|
$eight = gmp_init(8, 10); |
|
199
|
|
|
|
|
200
|
|
|
$modMath = $math->getModularArithmetic($p); |
|
201
|
|
|
if ($math->cmp($this->one, $p) < 0) { |
|
202
|
|
|
if ($math->equals($a, $this->zero)) { |
|
203
|
|
|
return $this->zero; |
|
204
|
|
|
} |
|
205
|
|
|
|
|
206
|
|
|
if ($math->equals($p, $this->two)) { |
|
207
|
|
|
return $a; |
|
208
|
|
|
} |
|
209
|
|
|
|
|
210
|
|
|
$jac = $math->jacobi($a, $p); |
|
211
|
|
|
if ($jac === -1) { |
|
212
|
|
|
throw new SquareRootException("{$math->toString($a)} has no square root modulo {$math->toString($p)}"); |
|
213
|
|
|
} |
|
214
|
|
|
|
|
215
|
|
|
if ($math->equals($math->mod($p, $four), gmp_init(3, 10))) { |
|
|
|
|
|
|
216
|
|
|
return $modMath->pow($a, $math->div($math->add($p, $this->one), $four)); |
|
|
|
|
|
|
217
|
|
|
} |
|
218
|
|
|
|
|
219
|
|
|
if ($math->equals($math->mod($p, $eight), gmp_init(5, 10))) { |
|
220
|
|
|
$d = $modMath->pow($a, $math->div($math->sub($p, $this->one), $four)); |
|
221
|
|
|
if ($math->equals($d, $this->one)) { |
|
222
|
|
|
return $modMath->pow($a, $math->div($math->add($p, gmp_init(3, 10)), $eight)); |
|
|
|
|
|
|
223
|
|
|
} |
|
224
|
|
|
|
|
225
|
|
|
if ($math->equals($d, $math->sub($p, $this->one))) { |
|
226
|
|
|
return $modMath->mul( |
|
227
|
|
|
$math->mul( |
|
228
|
|
|
$this->two, |
|
229
|
|
|
$a |
|
230
|
|
|
), |
|
231
|
|
|
$modMath->pow( |
|
232
|
|
|
$math->mul( |
|
233
|
|
|
$four, |
|
|
|
|
|
|
234
|
|
|
$a |
|
235
|
|
|
), |
|
236
|
|
|
$math->div( |
|
237
|
|
|
$math->sub( |
|
238
|
|
|
$p, |
|
239
|
|
|
gmp_init(5, 10) |
|
|
|
|
|
|
240
|
|
|
), |
|
241
|
|
|
$eight |
|
242
|
|
|
) |
|
243
|
|
|
) |
|
244
|
|
|
); |
|
245
|
|
|
} |
|
246
|
|
|
//shouldn't get here |
|
247
|
|
|
} |
|
248
|
|
|
|
|
249
|
|
|
for ($b = $this->two; $math->cmp($b, $p) < 0; $b = gmp_add($b, $this->one)) { |
|
250
|
|
|
if ($math->jacobi( |
|
251
|
|
|
$math->sub( |
|
252
|
|
|
$math->mul($b, $b), |
|
253
|
|
|
$math->mul($four, $a) |
|
254
|
|
|
), |
|
255
|
|
|
$p |
|
256
|
|
|
) == -1 |
|
257
|
|
|
) { |
|
258
|
|
|
$f = array($a, $math->sub($this->zero, $b), $this->one); |
|
259
|
|
|
|
|
260
|
|
|
$ff = $this->polynomialPowMod( |
|
261
|
|
|
array($this->zero, $this->one), |
|
262
|
|
|
$math->div( |
|
263
|
|
|
$math->add( |
|
264
|
|
|
$p, |
|
265
|
|
|
$this->one |
|
266
|
|
|
), |
|
267
|
|
|
$this->two |
|
268
|
|
|
), |
|
269
|
|
|
$f, |
|
270
|
|
|
$p |
|
271
|
|
|
); |
|
272
|
|
|
|
|
273
|
|
|
if ($math->equals($ff[1], $this->zero)) { |
|
274
|
|
|
return $ff[0]; |
|
275
|
|
|
} |
|
276
|
|
|
// if we got here no b was found |
|
277
|
|
|
} |
|
278
|
|
|
} |
|
279
|
|
|
} |
|
280
|
|
|
|
|
281
|
|
|
throw new SquareRootException('Unable to calculate square root mod p!'); |
|
282
|
|
|
} |
|
283
|
|
|
} |
|
284
|
|
|
|
shanecurran /
phpecc
Loading history...
Our type inference engine has found an assignment to a property that is incompatible with the declared type of that property.
Either this assignment is in error or the assigned type should be added to the documentation/type hint for that property..