1
|
|
|
<?php |
2
|
|
|
|
3
|
|
|
declare(strict_types=1); |
4
|
|
|
|
5
|
|
|
/* |
6
|
|
|
* The MIT License (MIT) |
7
|
|
|
* |
8
|
|
|
* Copyright (c) 2014-2019 Spomky-Labs |
9
|
|
|
* |
10
|
|
|
* This software may be modified and distributed under the terms |
11
|
|
|
* of the MIT license. See the LICENSE file for details. |
12
|
|
|
*/ |
13
|
|
|
|
14
|
|
|
namespace Jose\Component\Core\Util\Ecc; |
15
|
|
|
|
16
|
|
|
use GMP; |
17
|
|
|
use RuntimeException; |
18
|
|
|
|
19
|
|
|
/** |
20
|
|
|
* @internal |
21
|
|
|
*/ |
22
|
|
|
class Curve |
23
|
|
|
{ |
24
|
|
|
/** |
25
|
|
|
* Elliptic curve over the field of integers modulo a prime. |
26
|
|
|
* |
27
|
|
|
* @var GMP |
28
|
|
|
*/ |
29
|
|
|
private $a; |
30
|
|
|
|
31
|
|
|
/** |
32
|
|
|
* @var GMP |
33
|
|
|
*/ |
34
|
|
|
private $b; |
35
|
|
|
|
36
|
|
|
/** |
37
|
|
|
* @var GMP |
38
|
|
|
*/ |
39
|
|
|
private $prime; |
40
|
|
|
|
41
|
|
|
/** |
42
|
|
|
* Binary length of keys associated with these curve parameters. |
43
|
|
|
* |
44
|
|
|
* @var int |
45
|
|
|
*/ |
46
|
|
|
private $size; |
47
|
|
|
|
48
|
|
|
/** |
49
|
|
|
* @var Point |
50
|
|
|
*/ |
51
|
|
|
private $generator; |
52
|
|
|
|
53
|
|
|
public function __construct(int $size, GMP $prime, GMP $a, GMP $b, Point $generator) |
54
|
|
|
{ |
55
|
|
|
$this->size = $size; |
56
|
|
|
$this->prime = $prime; |
57
|
|
|
$this->a = $a; |
58
|
|
|
$this->b = $b; |
59
|
|
|
$this->generator = $generator; |
60
|
|
|
} |
61
|
|
|
|
62
|
|
|
public function __toString(): string |
63
|
|
|
{ |
64
|
|
|
return 'curve('.Math::toString($this->getA()).', '.Math::toString($this->getB()).', '.Math::toString($this->getPrime()).')'; |
65
|
|
|
} |
66
|
|
|
|
67
|
|
|
public function getA(): GMP |
68
|
|
|
{ |
69
|
|
|
return $this->a; |
70
|
|
|
} |
71
|
|
|
|
72
|
|
|
public function getB(): GMP |
73
|
|
|
{ |
74
|
|
|
return $this->b; |
75
|
|
|
} |
76
|
|
|
|
77
|
|
|
public function getPrime(): GMP |
78
|
|
|
{ |
79
|
|
|
return $this->prime; |
80
|
|
|
} |
81
|
|
|
|
82
|
|
|
public function getSize(): int |
83
|
|
|
{ |
84
|
|
|
return $this->size; |
85
|
|
|
} |
86
|
|
|
|
87
|
|
|
/** |
88
|
|
|
* @throws RuntimeException if the curve does not contain the point |
89
|
|
|
*/ |
90
|
|
|
public function getPoint(GMP $x, GMP $y, ?GMP $order = null): Point |
91
|
|
|
{ |
92
|
|
|
if (!$this->contains($x, $y)) { |
93
|
|
|
throw new RuntimeException('Curve '.$this->__toString().' does not contain point ('.Math::toString($x).', '.Math::toString($y).')'); |
94
|
|
|
} |
95
|
|
|
$point = Point::create($x, $y, $order); |
96
|
|
|
if (!\is_null($order)) { |
97
|
|
|
$mul = $this->mul($point, $order); |
98
|
|
|
if (!$mul->isInfinity()) { |
99
|
|
|
throw new RuntimeException('SELF * ORDER MUST EQUAL INFINITY.'); |
100
|
|
|
} |
101
|
|
|
} |
102
|
|
|
|
103
|
|
|
return $point; |
104
|
|
|
} |
105
|
|
|
|
106
|
|
|
/** |
107
|
|
|
* @throws RuntimeException if the coordinates are out of range |
108
|
|
|
*/ |
109
|
|
|
public function getPublicKeyFrom(GMP $x, GMP $y): PublicKey |
110
|
|
|
{ |
111
|
|
|
$zero = gmp_init(0, 10); |
112
|
|
|
if (Math::cmp($x, $zero) < 0 || Math::cmp($this->generator->getOrder(), $x) <= 0 || Math::cmp($y, $zero) < 0 || Math::cmp($this->generator->getOrder(), $y) <= 0) { |
113
|
|
|
throw new RuntimeException('Generator point has x and y out of range.'); |
114
|
|
|
} |
115
|
|
|
$point = $this->getPoint($x, $y); |
116
|
|
|
|
117
|
|
|
return new PublicKey($point); |
118
|
|
|
} |
119
|
|
|
|
120
|
|
|
public function contains(GMP $x, GMP $y): bool |
121
|
|
|
{ |
122
|
|
|
return Math::equals( |
123
|
|
|
ModularArithmetic::sub( |
124
|
|
|
Math::pow($y, 2), |
125
|
|
|
Math::add( |
126
|
|
|
Math::add( |
127
|
|
|
Math::pow($x, 3), |
128
|
|
|
Math::mul($this->getA(), $x) |
129
|
|
|
), |
130
|
|
|
$this->getB() |
131
|
|
|
), |
132
|
|
|
$this->getPrime() |
133
|
|
|
), |
134
|
|
|
gmp_init(0, 10) |
135
|
|
|
); |
136
|
|
|
} |
137
|
|
|
|
138
|
|
|
public function add(Point $one, Point $two): Point |
139
|
|
|
{ |
140
|
|
|
if ($two->isInfinity()) { |
141
|
|
|
return clone $one; |
142
|
|
|
} |
143
|
|
|
|
144
|
|
|
if ($one->isInfinity()) { |
145
|
|
|
return clone $two; |
146
|
|
|
} |
147
|
|
|
|
148
|
|
|
if (Math::equals($two->getX(), $one->getX())) { |
149
|
|
|
if (Math::equals($two->getY(), $one->getY())) { |
150
|
|
|
return $this->getDouble($one); |
151
|
|
|
} |
152
|
|
|
|
153
|
|
|
return Point::infinity(); |
154
|
|
|
} |
155
|
|
|
|
156
|
|
|
$slope = ModularArithmetic::div( |
157
|
|
|
Math::sub($two->getY(), $one->getY()), |
158
|
|
|
Math::sub($two->getX(), $one->getX()), |
159
|
|
|
$this->getPrime() |
160
|
|
|
); |
161
|
|
|
|
162
|
|
|
$xR = ModularArithmetic::sub( |
163
|
|
|
Math::sub(Math::pow($slope, 2), $one->getX()), |
164
|
|
|
$two->getX(), |
165
|
|
|
$this->getPrime() |
166
|
|
|
); |
167
|
|
|
|
168
|
|
|
$yR = ModularArithmetic::sub( |
169
|
|
|
Math::mul($slope, Math::sub($one->getX(), $xR)), |
170
|
|
|
$one->getY(), |
171
|
|
|
$this->getPrime() |
172
|
|
|
); |
173
|
|
|
|
174
|
|
|
return $this->getPoint($xR, $yR, $one->getOrder()); |
175
|
|
|
} |
176
|
|
|
|
177
|
|
|
public function mul(Point $one, GMP $n): Point |
178
|
|
|
{ |
179
|
|
|
if ($one->isInfinity()) { |
180
|
|
|
return Point::infinity(); |
181
|
|
|
} |
182
|
|
|
|
183
|
|
|
/** @var GMP $zero */ |
184
|
|
|
$zero = gmp_init(0, 10); |
185
|
|
|
if (Math::cmp($one->getOrder(), $zero) > 0) { |
186
|
|
|
$n = Math::mod($n, $one->getOrder()); |
187
|
|
|
} |
188
|
|
|
|
189
|
|
|
if (Math::equals($n, $zero)) { |
190
|
|
|
return Point::infinity(); |
191
|
|
|
} |
192
|
|
|
|
193
|
|
|
/** @var Point[] $r */ |
194
|
|
|
$r = [ |
195
|
|
|
Point::infinity(), |
196
|
|
|
clone $one, |
197
|
|
|
]; |
198
|
|
|
|
199
|
|
|
$k = $this->getSize(); |
200
|
|
|
$n = str_pad(Math::baseConvert(Math::toString($n), 10, 2), $k, '0', STR_PAD_LEFT); |
201
|
|
|
|
202
|
|
|
for ($i = 0; $i < $k; ++$i) { |
203
|
|
|
$j = $n[$i]; |
204
|
|
|
Point::cswap($r[0], $r[1], $j ^ 1); |
|
|
|
|
205
|
|
|
$r[0] = $this->add($r[0], $r[1]); |
206
|
|
|
$r[1] = $this->getDouble($r[1]); |
207
|
|
|
Point::cswap($r[0], $r[1], $j ^ 1); |
|
|
|
|
208
|
|
|
} |
209
|
|
|
|
210
|
|
|
$this->validate($r[0]); |
211
|
|
|
|
212
|
|
|
return $r[0]; |
213
|
|
|
} |
214
|
|
|
|
215
|
|
|
/** |
216
|
|
|
* @param Curve $other |
217
|
|
|
*/ |
218
|
|
|
public function cmp(self $other): int |
219
|
|
|
{ |
220
|
|
|
$equal = Math::equals($this->getA(), $other->getA()) && |
221
|
|
|
Math::equals($this->getB(), $other->getB()) && |
222
|
|
|
Math::equals($this->getPrime(), $other->getPrime()); |
223
|
|
|
|
224
|
|
|
return $equal ? 0 : 1; |
225
|
|
|
} |
226
|
|
|
|
227
|
|
|
/** |
228
|
|
|
* @param Curve $other |
229
|
|
|
*/ |
230
|
|
|
public function equals(self $other): bool |
231
|
|
|
{ |
232
|
|
|
return 0 === $this->cmp($other); |
233
|
|
|
} |
234
|
|
|
|
235
|
|
|
public function getDouble(Point $point): Point |
236
|
|
|
{ |
237
|
|
|
if ($point->isInfinity()) { |
238
|
|
|
return Point::infinity(); |
239
|
|
|
} |
240
|
|
|
|
241
|
|
|
$a = $this->getA(); |
242
|
|
|
$threeX2 = Math::mul(gmp_init(3, 10), Math::pow($point->getX(), 2)); |
243
|
|
|
|
244
|
|
|
$tangent = ModularArithmetic::div( |
245
|
|
|
Math::add($threeX2, $a), |
246
|
|
|
Math::mul(gmp_init(2, 10), $point->getY()), |
247
|
|
|
$this->getPrime() |
248
|
|
|
); |
249
|
|
|
|
250
|
|
|
$x3 = ModularArithmetic::sub( |
251
|
|
|
Math::pow($tangent, 2), |
252
|
|
|
Math::mul(gmp_init(2, 10), $point->getX()), |
253
|
|
|
$this->getPrime() |
254
|
|
|
); |
255
|
|
|
|
256
|
|
|
$y3 = ModularArithmetic::sub( |
257
|
|
|
Math::mul($tangent, Math::sub($point->getX(), $x3)), |
258
|
|
|
$point->getY(), |
259
|
|
|
$this->getPrime() |
260
|
|
|
); |
261
|
|
|
|
262
|
|
|
return $this->getPoint($x3, $y3, $point->getOrder()); |
263
|
|
|
} |
264
|
|
|
|
265
|
|
|
public function createPrivateKey(): PrivateKey |
266
|
|
|
{ |
267
|
|
|
return PrivateKey::create($this->generate()); |
268
|
|
|
} |
269
|
|
|
|
270
|
|
|
public function createPublicKey(PrivateKey $privateKey): PublicKey |
271
|
|
|
{ |
272
|
|
|
$point = $this->mul($this->generator, $privateKey->getSecret()); |
273
|
|
|
|
274
|
|
|
return new PublicKey($point); |
275
|
|
|
} |
276
|
|
|
|
277
|
|
|
public function getGenerator(): Point |
278
|
|
|
{ |
279
|
|
|
return $this->generator; |
280
|
|
|
} |
281
|
|
|
|
282
|
|
|
/** |
283
|
|
|
* @throws RuntimeException if the point is invalid |
284
|
|
|
*/ |
285
|
|
|
private function validate(Point $point): void |
286
|
|
|
{ |
287
|
|
|
if (!$point->isInfinity() && !$this->contains($point->getX(), $point->getY())) { |
288
|
|
|
throw new RuntimeException('Invalid point'); |
289
|
|
|
} |
290
|
|
|
} |
291
|
|
|
|
292
|
|
|
private function generate(): GMP |
293
|
|
|
{ |
294
|
|
|
$max = $this->generator->getOrder(); |
295
|
|
|
$numBits = $this->bnNumBits($max); |
296
|
|
|
$numBytes = (int) ceil($numBits / 8); |
297
|
|
|
// Generate an integer of size >= $numBits |
298
|
|
|
$bytes = random_bytes($numBytes); |
299
|
|
|
$value = Math::stringToInt($bytes); |
300
|
|
|
$mask = gmp_sub(gmp_pow(2, $numBits), 1); |
301
|
|
|
|
302
|
|
|
return gmp_and($value, $mask); |
303
|
|
|
} |
304
|
|
|
|
305
|
|
|
/** |
306
|
|
|
* Returns the number of bits used to store this number. Non-significant upper bits are not counted. |
307
|
|
|
* |
308
|
|
|
* @see https://www.openssl.org/docs/crypto/BN_num_bytes.html |
309
|
|
|
*/ |
310
|
|
|
private function bnNumBits(GMP $x): int |
311
|
|
|
{ |
312
|
|
|
$zero = gmp_init(0, 10); |
313
|
|
|
if (Math::equals($x, $zero)) { |
314
|
|
|
return 0; |
315
|
|
|
} |
316
|
|
|
$log2 = 0; |
317
|
|
|
while (false === Math::equals($x, $zero)) { |
318
|
|
|
$x = Math::rightShift($x, 1); |
319
|
|
|
++$log2; |
320
|
|
|
} |
321
|
|
|
|
322
|
|
|
return $log2; |
323
|
|
|
} |
324
|
|
|
} |
325
|
|
|
|
It seems like the type of the argument is not accepted by the function/method which you are calling.
In some cases, in particular if PHP’s automatic type-juggling kicks in this might be fine. In other cases, however this might be a bug.
We suggest to add an explicit type cast like in the following example: