|
1
|
|
|
<?php |
|
2
|
|
|
/****************************************************************************** |
|
3
|
|
|
* This file is part of the Phactor PHP project. You can always find the latest |
|
4
|
|
|
* version of this class and project at: https://github.com/ionux/phactor |
|
5
|
|
|
* |
|
6
|
|
|
* Copyright (c) 2015-2016 Rich Morgan, [email protected] |
|
7
|
|
|
* |
|
8
|
|
|
* The MIT License (MIT) |
|
9
|
|
|
* |
|
10
|
|
|
* Permission is hereby granted, free of charge, to any person obtaining a copy of |
|
11
|
|
|
* this software and associated documentation files (the "Software"), to deal in |
|
12
|
|
|
* the Software without restriction, including without limitation the rights to |
|
13
|
|
|
* use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of |
|
14
|
|
|
* the Software, and to permit persons to whom the Software is furnished to do so, |
|
15
|
|
|
* subject to the following conditions: |
|
16
|
|
|
* |
|
17
|
|
|
* The above copyright notice and this permission notice shall be included in all |
|
18
|
|
|
* copies or substantial portions of the Software. |
|
19
|
|
|
* |
|
20
|
|
|
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
|
21
|
|
|
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS |
|
22
|
|
|
* FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR |
|
23
|
|
|
* COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER |
|
24
|
|
|
* IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
|
25
|
|
|
* CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
|
26
|
|
|
******************************************************************************/ |
|
27
|
|
|
|
|
28
|
|
|
namespace Phactor; |
|
29
|
|
|
|
|
30
|
|
|
/** |
|
31
|
|
|
* This trait implements the elliptic curve math functions required to generate |
|
32
|
|
|
* new EC points based on the secp256k1 curve parameters. |
|
33
|
|
|
* |
|
34
|
|
|
* @author Rich Morgan <[email protected]> |
|
35
|
|
|
*/ |
|
36
|
|
|
trait Point |
|
37
|
|
|
{ |
|
38
|
|
|
use Math, Secp256k1; |
|
39
|
|
|
|
|
40
|
|
|
/** |
|
41
|
|
|
* EC Point addition method P + Q = R where: |
|
42
|
|
|
* s = (yP - yQ) / (xP - xQ) mod p |
|
43
|
|
|
* xR = s2 - xP - xQ mod p |
|
44
|
|
|
* yR = -yP + s(xP - xR) mod p |
|
45
|
|
|
* |
|
46
|
|
|
* @param array|string $P The first point to add. |
|
47
|
|
|
* @param array|string $Q The second point to add. |
|
48
|
|
|
* @return array $R The result of the point addition. |
|
49
|
|
|
* @throws \Exception |
|
50
|
|
|
*/ |
|
51
|
|
|
public function pointAddW($P, $Q) |
|
52
|
|
|
{ |
|
53
|
|
|
if ($this->pointType($P) == 'nul' || $this->pointType($Q) == 'nul') { |
|
54
|
|
|
throw new \Exception('You must provide valid point parameters to add.'); |
|
55
|
|
|
} |
|
56
|
|
|
|
|
57
|
|
|
$infCheck = $this->infPointCheck($P, $Q); |
|
58
|
|
|
|
|
59
|
|
|
if ($infCheck != null) { |
|
60
|
|
|
return $infCheck; |
|
61
|
|
|
} |
|
62
|
|
|
|
|
63
|
|
|
if ($P == $Q) { |
|
64
|
|
|
return $this->pointDoubleW($P); |
|
65
|
|
|
} |
|
66
|
|
|
|
|
67
|
|
|
$ss = '0'; |
|
68
|
|
|
|
|
69
|
|
|
$R = array('x' => '0', 'y' => '0'); |
|
70
|
|
|
|
|
71
|
|
|
try { |
|
72
|
|
|
$mm = $this->Subtract($P['y'], $Q['y']); |
|
73
|
|
|
$nn = $this->Subtract($P['x'], $Q['x']); |
|
74
|
|
|
$oo = $this->Invert($nn, $this->p); |
|
75
|
|
|
$st = $this->Multiply($mm, $oo); |
|
76
|
|
|
$ss = $this->Modulo($st, $this->p); |
|
77
|
|
|
|
|
78
|
|
|
$R['x'] = $this->Modulo($this->Subtract($this->Subtract($this->Multiply($ss, $ss), $P['x']), $Q['x']), $this->p); |
|
79
|
|
|
$R['y'] = $this->Modulo($this->Add($this->Subtract('0', $P['y']), $this->Multiply($ss, $this->Subtract($P['x'], $R['x']))), $this->p); |
|
80
|
|
|
|
|
81
|
|
|
return $R; |
|
82
|
|
|
|
|
83
|
|
|
} catch (\Exception $e) { |
|
84
|
|
|
throw $e; |
|
85
|
|
|
} |
|
86
|
|
|
} |
|
87
|
|
|
|
|
88
|
|
|
/** |
|
89
|
|
|
* Point multiplication method 2P = R where |
|
90
|
|
|
* s = (3xP2 + a) / (2yP) mod p |
|
91
|
|
|
* xR = s2 - 2xP mod p |
|
92
|
|
|
* yR = -yP + s(xP - xR) mod p |
|
93
|
|
|
* |
|
94
|
|
|
* @param array|string $P The point to multiply. |
|
95
|
|
|
* @return array|string $R The multiplied point. |
|
96
|
|
|
* @throws \Exception |
|
97
|
|
|
*/ |
|
98
|
|
|
public function pointDoubleW($P) |
|
99
|
|
|
{ |
|
100
|
|
|
switch ($this->pointType($P)) { |
|
101
|
|
|
case 'inf': |
|
102
|
|
|
return $this->Inf; |
|
103
|
|
|
case 'nul': |
|
104
|
|
|
throw new \Exception('You must provide a valid point parameter to double.'); |
|
105
|
|
|
} |
|
106
|
|
|
|
|
107
|
|
|
$ss = '0'; |
|
108
|
|
|
|
|
109
|
|
|
$R = array('x' => '0', 'y' => '0'); |
|
110
|
|
|
|
|
111
|
|
|
try { |
|
112
|
|
|
$mm = $this->Add($this->Multiply('3', $this->Multiply($P['x'], $P['x'])), $this->a); |
|
113
|
|
|
$oo = $this->Multiply('2', $P['y']); |
|
114
|
|
|
$nn = $this->Invert($oo, $this->p); |
|
115
|
|
|
$st = $this->Multiply($mm, $nn); |
|
116
|
|
|
$ss = $this->Modulo($st, $this->p); |
|
117
|
|
|
$xmul = $this->Multiply('2', $P['x']); |
|
118
|
|
|
$smul = $this->Multiply($ss, $ss); |
|
119
|
|
|
$xsub = $this->Subtract($smul, $xmul); |
|
120
|
|
|
$xmod = $this->Modulo($xsub, $this->p); |
|
121
|
|
|
|
|
122
|
|
|
$R['x'] = $xmod; |
|
123
|
|
|
|
|
124
|
|
|
$ysub = $this->Subtract($P['x'], $R['x']); |
|
125
|
|
|
$ymul = $this->Multiply($ss, $ysub); |
|
126
|
|
|
$ysub2 = $this->Subtract('0', $P['y']); |
|
127
|
|
|
$yadd = $this->Add($ysub2, $ymul); |
|
128
|
|
|
|
|
129
|
|
|
$R['x'] = $R['x']; |
|
130
|
|
|
$R['y'] = $this->Modulo($yadd, $this->p); |
|
131
|
|
|
|
|
132
|
|
|
return $R; |
|
133
|
|
|
|
|
134
|
|
|
} catch (\Exception $e) { |
|
135
|
|
|
throw $e; |
|
136
|
|
|
} |
|
137
|
|
|
} |
|
138
|
|
|
|
|
139
|
|
|
/** |
|
140
|
|
|
* Performs a test of an EC point by substituting the new |
|
141
|
|
|
* values into the equation for the Weierstrass form of the curve. |
|
142
|
|
|
* |
|
143
|
|
|
* @param array|string $P The generated point to test. |
|
144
|
|
|
* @return bool Whether or not the point is valid. |
|
145
|
|
|
* @throws \Exception |
|
146
|
|
|
*/ |
|
147
|
|
|
public function pointTestW($P) |
|
148
|
|
|
{ |
|
149
|
|
|
if (is_array($P) === false) { |
|
150
|
|
|
throw new \Exception('Point test failed! Cannot test a point without coordinates.'); |
|
151
|
|
|
} |
|
152
|
|
|
|
|
153
|
|
|
/* |
|
154
|
|
|
* Weierstrass form of the elliptic curve: |
|
155
|
|
|
* y^2 (mod p) = x^3 + ax + b (mod p) |
|
156
|
|
|
*/ |
|
157
|
|
|
$y2 = ''; |
|
158
|
|
|
$x3 = ''; |
|
159
|
|
|
$ax = ''; |
|
160
|
|
|
$left = ''; |
|
161
|
|
|
$right = ''; |
|
162
|
|
|
|
|
163
|
|
|
try { |
|
164
|
|
|
/* Left y^2 term */ |
|
165
|
|
|
$y2 = $this->Multiply($P['y'], $P['y']); |
|
166
|
|
|
|
|
167
|
|
|
/* Right, first x^3 term */ |
|
168
|
|
|
$x3 = $this->Multiply($this->Multiply($P['x'], $P['x']), $P['x']); |
|
169
|
|
|
|
|
170
|
|
|
/* Right, second ax term */ |
|
171
|
|
|
$ax = $this->Multiply($this->a, $P['x']); |
|
172
|
|
|
|
|
173
|
|
|
/* |
|
174
|
|
|
* If the right side of the equation equals the left, |
|
175
|
|
|
* we have a valid point, agebraically speaking. |
|
176
|
|
|
*/ |
|
177
|
|
|
$left = $this->Modulo($y2, $this->p); |
|
178
|
|
|
$right = $this->Modulo($this->Add($this->Add($x3, $ax), $this->b), $this->p); |
|
179
|
|
|
|
|
180
|
|
|
$test_point = array('x' => $right, 'y' => $left, 'y2' => $y2, 'x3' => $x3, 'ax' => $ax); |
|
181
|
|
|
|
|
182
|
|
|
if ($left == $right) { |
|
183
|
|
|
return $left == $right; |
|
184
|
|
|
} else { |
|
185
|
|
|
throw new \Exception('Point test failed! Cannot continue. I tested the point: ' . var_export($P, true) . ' but got the point: ' . var_export($test_point, true)); |
|
186
|
|
|
} |
|
187
|
|
|
|
|
188
|
|
|
} catch (\Exception $e) { |
|
189
|
|
|
throw $e; |
|
190
|
|
|
} |
|
191
|
|
|
} |
|
192
|
|
|
|
|
193
|
|
|
/** |
|
194
|
|
|
* Pure PHP implementation of the Double-And-Add algorithm, for more info see: |
|
195
|
|
|
* http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Double-and-add |
|
196
|
|
|
* |
|
197
|
|
|
* @param array $P Base EC curve point. |
|
198
|
|
|
* @param string $x Scalar value. |
|
199
|
|
|
* @return array|string $S Either 'infinity' or the new coordinates. |
|
200
|
|
|
*/ |
|
201
|
|
|
public function doubleAndAdd($P, $x = '1') |
|
202
|
|
|
{ |
|
203
|
|
|
$tmp = $this->D2B($x); |
|
204
|
|
|
$n = strlen($tmp) - 1; |
|
205
|
|
|
$S = $this->Inf; |
|
206
|
|
|
|
|
207
|
|
|
while ($n >= 0) { |
|
208
|
|
|
$S = $this->pointDoubleW($S); |
|
209
|
|
|
$S = ($tmp[$n] == '1') ? $this->pointAddW($S, $P) : $S; |
|
210
|
|
|
|
|
211
|
|
|
$n--; |
|
212
|
|
|
} |
|
213
|
|
|
|
|
214
|
|
|
return $S; |
|
215
|
|
|
} |
|
216
|
|
|
|
|
217
|
|
|
/** |
|
218
|
|
|
* Pure PHP implementation of the Montgomery Ladder algorithm which helps protect |
|
219
|
|
|
* us against side-channel attacks. This performs the same number of operations |
|
220
|
|
|
* regardless of the scalar value being used as the multiplier. It's slower than |
|
221
|
|
|
* the traditional double-and-add algorithm because of that fact but safer to use. |
|
222
|
|
|
* |
|
223
|
|
|
* @param array $P Base EC curve point. |
|
224
|
|
|
* @param string $x Scalar value. |
|
225
|
|
|
* @return array|string $S Either 'infinity' or the new coordinates. |
|
226
|
|
|
*/ |
|
227
|
|
|
public function mLadder($P, $x = '1') |
|
228
|
|
|
{ |
|
229
|
|
|
$tmp = $this->D2B($x); |
|
230
|
|
|
$n = strlen($tmp) - 1; |
|
231
|
|
|
$S0 = $this->Inf; |
|
232
|
|
|
$S1 = $P; |
|
233
|
|
|
|
|
234
|
|
|
while ($n >= 0) { |
|
235
|
|
|
switch ($tmp[$n]) { |
|
236
|
|
|
case '0': |
|
237
|
|
|
$S1 = $this->pointAddW($S0, $S1); |
|
238
|
|
|
$S0 = $this->pointDoubleW($S0); |
|
239
|
|
|
break; |
|
240
|
|
|
default: |
|
241
|
|
|
$S0 = $this->pointAddW($S0, $S1); |
|
242
|
|
|
$S1 = $this->pointDoubleW($S1); |
|
243
|
|
|
break; |
|
244
|
|
|
} |
|
245
|
|
|
|
|
246
|
|
|
$n--; |
|
247
|
|
|
} |
|
248
|
|
|
|
|
249
|
|
|
return $S0; |
|
250
|
|
|
} |
|
251
|
|
|
|
|
252
|
|
|
/** |
|
253
|
|
|
* Creates a new point on the elliptic curve. |
|
254
|
|
|
* |
|
255
|
|
|
* @param boolean $ladder Whether or not to use the mladder method. |
|
256
|
|
|
* @return array The new EC point. |
|
257
|
|
|
* @throws \Exception |
|
258
|
|
|
*/ |
|
259
|
|
|
public function GenerateNewPoint($ladder = true) |
|
260
|
|
|
{ |
|
261
|
|
|
$P = array( |
|
262
|
|
|
'x' => $this->Gx, |
|
263
|
|
|
'y' => $this->Gy |
|
264
|
|
|
); |
|
265
|
|
|
|
|
266
|
|
|
do { |
|
267
|
|
|
$random_number = $this->SecureRandomNumber(); |
|
268
|
|
|
} while ($this->randCompare($random_number)); |
|
269
|
|
|
|
|
270
|
|
|
$R = ($ladder === true) ? $this->mLadder($P, $random_number) : $this->doubleAndAdd($P, $random_number); |
|
271
|
|
|
|
|
272
|
|
|
if ($this->pointTestW($R)) { |
|
273
|
|
|
$Rx_hex = str_pad($this->encodeHex($R['x']), 64, "0", STR_PAD_LEFT); |
|
274
|
|
|
$Ry_hex = str_pad($this->encodeHex($R['y']), 64, "0", STR_PAD_LEFT); |
|
275
|
|
|
} else { |
|
276
|
|
|
throw new \Exception('Point test failed! Cannot continue. I got the point: ' . var_export($R, true)); |
|
277
|
|
|
} |
|
278
|
|
|
|
|
279
|
|
|
return array( |
|
280
|
|
|
'random_number' => $random_number, |
|
281
|
|
|
'R' => $R, |
|
282
|
|
|
'Rx_hex' => $Rx_hex, |
|
283
|
|
|
'Ry_hex' => $Ry_hex |
|
284
|
|
|
); |
|
285
|
|
|
} |
|
286
|
|
|
|
|
287
|
|
|
/** |
|
288
|
|
|
* Recalculates the y-coordinate from a compressed public key. |
|
289
|
|
|
* |
|
290
|
|
|
* @param string $x_coord The x-coordinate. |
|
291
|
|
|
* @param string $compressed_bit The hex compression value (03 or 02). |
|
292
|
|
|
* @return string $y The calculated y-coordinate. |
|
293
|
|
|
* @throws \Exception $e |
|
294
|
|
|
*/ |
|
295
|
|
|
public function calcYfromX($x_coord, $compressed_bit) |
|
296
|
|
|
{ |
|
297
|
|
|
try { |
|
298
|
|
|
$x = $this->decodeHex($this->addHexPrefix($x_coord)); |
|
299
|
|
|
$c = $this->Subtract($this->decodeHex($this->addHexPrefix($compressed_bit)), '2'); |
|
300
|
|
|
$a = $this->Modulo($this->Add($this->PowMod($x, '3', $this->p), '7'), $this->p); |
|
301
|
|
|
$y = $this->PowMod($a, $this->Divide($this->Add($this->p, '1'), '4'), $this->p); |
|
302
|
|
|
|
|
303
|
|
|
return ($this->Modulo($y, '2') != $c) ? $this->decodeHex($this->Modulo($this->Multiply('-1', $y), $this->p)) : $this->decodeHex($y); |
|
304
|
|
|
} catch (\Exception $e) { |
|
305
|
|
|
throw $e; |
|
306
|
|
|
} |
|
307
|
|
|
} |
|
308
|
|
|
|
|
309
|
|
|
/** |
|
310
|
|
|
* Basic range check. Throws exception if coordinate value is out of range. |
|
311
|
|
|
* |
|
312
|
|
|
* @param string $value The coordinate to check. |
|
313
|
|
|
* @return boolean The result of the check. |
|
314
|
|
|
*/ |
|
315
|
|
|
public function RangeCheck($value) |
|
316
|
|
|
{ |
|
317
|
|
|
$this->preOpMethodParamsCheck(array($value)); |
|
318
|
|
|
|
|
319
|
|
|
return true; |
|
320
|
|
|
} |
|
321
|
|
|
|
|
322
|
|
|
/** |
|
323
|
|
|
* Checks the basic type of the point value. |
|
324
|
|
|
* |
|
325
|
|
|
* @param mixed $value The point to check. |
|
326
|
|
|
* @return string The result of the check. |
|
327
|
|
|
* @codeCoverageIgnore |
|
328
|
|
|
*/ |
|
329
|
|
|
private function pointType($value) |
|
330
|
|
|
{ |
|
331
|
|
|
if (true === $this->arrTest($value)) { |
|
332
|
|
|
return 'arr'; |
|
333
|
|
|
} |
|
334
|
|
|
|
|
335
|
|
|
if ($this->Inf == $value) { |
|
336
|
|
|
return 'inf'; |
|
337
|
|
|
} |
|
338
|
|
|
|
|
339
|
|
|
return 'nul'; |
|
340
|
|
|
} |
|
341
|
|
|
|
|
342
|
|
|
/** |
|
343
|
|
|
* Checks the range of a pair of coordinates. |
|
344
|
|
|
* |
|
345
|
|
|
* @param string $x The key to check. |
|
346
|
|
|
* @param string $y The key to check. |
|
347
|
|
|
* @codeCoverageIgnore |
|
348
|
|
|
*/ |
|
349
|
|
|
private function coordsRangeCheck($x, $y) |
|
350
|
|
|
{ |
|
351
|
|
|
//$this->RangeCheck($x); |
|
352
|
|
|
//$this->RangeCheck($y); |
|
353
|
|
|
return true; |
|
354
|
|
|
} |
|
355
|
|
|
|
|
356
|
|
|
/** |
|
357
|
|
|
* Basic coordinate check: verifies $hex is valid |
|
358
|
|
|
* |
|
359
|
|
|
* @param string $hex The coordinate to check. |
|
360
|
|
|
* @return string $hex The checked coordinate. |
|
361
|
|
|
* @codeCoverageIgnore |
|
362
|
|
|
*/ |
|
363
|
|
|
private function CoordinateCheck($hex) |
|
364
|
|
|
{ |
|
365
|
|
|
//$hex = $this->encodeHex($hex); |
|
366
|
|
|
|
|
367
|
|
|
//$this->hexLenCheck($hex); |
|
368
|
|
|
//$this->RangeCheck($hex); |
|
369
|
|
|
|
|
370
|
|
|
return $hex; |
|
371
|
|
|
} |
|
372
|
|
|
|
|
373
|
|
|
/** |
|
374
|
|
|
* Checks if a Point is infinity or equal to another point. |
|
375
|
|
|
* |
|
376
|
|
|
* @param array|string $pointOne The first point to check. |
|
377
|
|
|
* @param array|string $pointTwo The second point to check. |
|
378
|
|
|
* @return mixed The result value to return or null. |
|
379
|
|
|
*/ |
|
380
|
|
|
private function infPointCheck($pointOne, $pointTwo) |
|
381
|
|
|
{ |
|
382
|
|
|
if ($pointOne == $this->Inf || false === $this->arrTest($pointOne)) { |
|
383
|
|
|
return $pointTwo; |
|
384
|
|
|
} |
|
385
|
|
|
|
|
386
|
|
|
if ($pointTwo == $this->Inf || false === $this->arrTest($pointTwo)) { |
|
387
|
|
|
return $pointOne; |
|
388
|
|
|
} |
|
389
|
|
|
|
|
390
|
|
|
if (($pointOne['x'] == $pointTwo['x']) && ($pointOne['y'] != $pointTwo['y'])) { |
|
391
|
|
|
return $this->Inf; |
|
392
|
|
|
} |
|
393
|
|
|
|
|
394
|
|
|
return null; |
|
395
|
|
|
} |
|
396
|
|
|
|
|
397
|
|
|
/** |
|
398
|
|
|
* Checks if a number is within a certain range: |
|
399
|
|
|
* 0x01 < number < n |
|
400
|
|
|
* |
|
401
|
|
|
* @param string $value The number to check. |
|
402
|
|
|
* @return boolean The result of the comparison. |
|
403
|
|
|
* @codeCoverageIgnore |
|
404
|
|
|
*/ |
|
405
|
|
|
private function randCompare($value) |
|
406
|
|
|
{ |
|
407
|
|
|
return ($this->Compare($value, '1') <= 0 || $this->Compare($value, $this->n) >= 0); |
|
408
|
|
|
} |
|
409
|
|
|
} |
|
410
|
|
|
|