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
|
|
|
|