GitHub Access Token became invalid

It seems like the GitHub access token used for retrieving details about this repository from GitHub became invalid. This might prevent certain types of inspections from being run (in particular, everything related to pull requests).
Please ask an admin of your repository to re-new the access token on this website.
Completed
Push — master ( f95c80...e0389e )
by Rich
02:28
created

Point::calcYfromX()   A

Complexity

Conditions 3
Paths 7

Size

Total Lines 13
Code Lines 9

Duplication

Lines 0
Ratio 0 %

Importance

Changes 1
Bugs 0 Features 1
Metric Value
c 1
b 0
f 1
dl 0
loc 13
rs 9.4286
cc 3
eloc 9
nc 7
nop 2
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