1<?php
2
3/**
4 * Generalized Koblitz Curves over y^2 = x^3 + b.
5 *
6 * According to http://www.secg.org/SEC2-Ver-1.0.pdf Koblitz curves are over the GF(2**m)
7 * finite field. Both the $a$ and $b$ coefficients are either 0 or 1. However, SEC2
8 * generalizes the definition to include curves over GF(P) "which possess an efficiently
9 * computable endomorphism".
10 *
11 * For these generalized Koblitz curves $b$ doesn't have to be 0 or 1. Whether or not $a$
12 * has any restrictions on it is unclear, however, for all the GF(P) Koblitz curves defined
13 * in SEC2 v1.0 $a$ is $0$ so all of the methods defined herein will assume that it is.
14 *
15 * I suppose we could rename the $b$ coefficient to $a$, however, the documentation refers
16 * to $b$ so we'll just keep it.
17 *
18 * If a later version of SEC2 comes out wherein some $a$ values are non-zero we can create a
19 * new method for those. eg. KoblitzA1Prime.php or something.
20 *
21 * PHP version 5 and 7
22 *
23 * @category  Crypt
24 * @package   EC
25 * @author    Jim Wigginton <terrafrost@php.net>
26 * @copyright 2017 Jim Wigginton
27 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
28 * @link      http://pear.php.net/package/Math_BigInteger
29 */
30
31namespace phpseclib3\Crypt\EC\BaseCurves;
32
33use phpseclib3\Math\BigInteger;
34use phpseclib3\Math\PrimeField;
35
36/**
37 * Curves over y^2 = x^3 + b
38 *
39 * @package KoblitzPrime
40 * @author  Jim Wigginton <terrafrost@php.net>
41 * @access  public
42 */
43class KoblitzPrime extends Prime
44{
45    // don't overwrite setCoefficients() with one that only accepts one parameter so that
46    // one might be able to switch between KoblitzPrime and Prime more easily (for benchmarking
47    // purposes).
48
49    /**
50     * Multiply and Add Points
51     *
52     * Uses a efficiently computable endomorphism to achieve a slight speedup
53     *
54     * Adapted from https://git.io/vxbrP
55     *
56     * @return int[]
57     */
58    public function multiplyAddPoints(array $points, array $scalars)
59    {
60        static $zero, $one, $two;
61        if (!isset($two)) {
62            $two = new BigInteger(2);
63            $one = new BigInteger(1);
64        }
65
66        if (!isset($this->beta)) {
67            // get roots
68            $inv = $this->one->divide($this->two)->negate();
69            $s = $this->three->negate()->squareRoot()->multiply($inv);
70            $betas = [
71                $inv->add($s),
72                $inv->subtract($s)
73            ];
74            $this->beta = $betas[0]->compare($betas[1]) < 0 ? $betas[0] : $betas[1];
75            //echo strtoupper($this->beta->toHex(true)) . "\n"; exit;
76        }
77
78        if (!isset($this->basis)) {
79            $factory = new PrimeField($this->order);
80            $tempOne = $factory->newInteger($one);
81            $tempTwo = $factory->newInteger($two);
82            $tempThree = $factory->newInteger(new BigInteger(3));
83
84            $inv = $tempOne->divide($tempTwo)->negate();
85            $s = $tempThree->negate()->squareRoot()->multiply($inv);
86
87            $lambdas = [
88                $inv->add($s),
89                $inv->subtract($s)
90            ];
91
92            $lhs = $this->multiplyPoint($this->p, $lambdas[0])[0];
93            $rhs = $this->p[0]->multiply($this->beta);
94            $lambda = $lhs->equals($rhs) ? $lambdas[0] : $lambdas[1];
95
96            $this->basis = static::extendedGCD($lambda->toBigInteger(), $this->order);
97            ///*
98            foreach ($this->basis as $basis) {
99                echo strtoupper($basis['a']->toHex(true)) . "\n";
100                echo strtoupper($basis['b']->toHex(true)) . "\n\n";
101            }
102            exit;
103            //*/
104        }
105
106        $npoints = $nscalars = [];
107        for ($i = 0; $i < count($points); $i++) {
108            $p = $points[$i];
109            $k = $scalars[$i]->toBigInteger();
110
111            // begin split
112            list($v1, $v2) = $this->basis;
113
114            $c1 = $v2['b']->multiply($k);
115            list($c1, $r) = $c1->divide($this->order);
116            if ($this->order->compare($r->multiply($two)) <= 0) {
117                $c1 = $c1->add($one);
118            }
119
120            $c2 = $v1['b']->negate()->multiply($k);
121            list($c2, $r) = $c2->divide($this->order);
122            if ($this->order->compare($r->multiply($two)) <= 0) {
123                $c2 = $c2->add($one);
124            }
125
126            $p1 = $c1->multiply($v1['a']);
127            $p2 = $c2->multiply($v2['a']);
128            $q1 = $c1->multiply($v1['b']);
129            $q2 = $c2->multiply($v2['b']);
130
131            $k1 = $k->subtract($p1)->subtract($p2);
132            $k2 = $q1->add($q2)->negate();
133            // end split
134
135            $beta = [
136                $p[0]->multiply($this->beta),
137                $p[1],
138                clone $this->one
139            ];
140
141            if (isset($p['naf'])) {
142                $beta['naf'] = array_map(function ($p) {
143                    return [
144                        $p[0]->multiply($this->beta),
145                        $p[1],
146                        clone $this->one
147                    ];
148                }, $p['naf']);
149                $beta['nafwidth'] = $p['nafwidth'];
150            }
151
152            if ($k1->isNegative()) {
153                $k1 = $k1->negate();
154                $p = $this->negatePoint($p);
155            }
156
157            if ($k2->isNegative()) {
158                $k2 = $k2->negate();
159                $beta = $this->negatePoint($beta);
160            }
161
162            $pos = 2 * $i;
163            $npoints[$pos] = $p;
164            $nscalars[$pos] = $this->factory->newInteger($k1);
165
166            $pos++;
167            $npoints[$pos] = $beta;
168            $nscalars[$pos] = $this->factory->newInteger($k2);
169        }
170
171        return parent::multiplyAddPoints($npoints, $nscalars);
172    }
173
174    /**
175     * Returns the numerator and denominator of the slope
176     *
177     * @return FiniteField[]
178     */
179    protected function doublePointHelper(array $p)
180    {
181        $numerator = $this->three->multiply($p[0])->multiply($p[0]);
182        $denominator = $this->two->multiply($p[1]);
183        return [$numerator, $denominator];
184    }
185
186    /**
187     * Doubles a jacobian coordinate on the curve
188     *
189     * See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
190     *
191     * @return FiniteField[]
192     */
193    protected function jacobianDoublePoint(array $p)
194    {
195        list($x1, $y1, $z1) = $p;
196        $a = $x1->multiply($x1);
197        $b = $y1->multiply($y1);
198        $c = $b->multiply($b);
199        $d = $x1->add($b);
200        $d = $d->multiply($d)->subtract($a)->subtract($c)->multiply($this->two);
201        $e = $this->three->multiply($a);
202        $f = $e->multiply($e);
203        $x3 = $f->subtract($this->two->multiply($d));
204        $y3 = $e->multiply($d->subtract($x3))->subtract(
205            $this->eight->multiply($c)
206        );
207        $z3 = $this->two->multiply($y1)->multiply($z1);
208        return [$x3, $y3, $z3];
209    }
210
211    /**
212     * Doubles a "fresh" jacobian coordinate on the curve
213     *
214     * See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-mdbl-2007-bl
215     *
216     * @return FiniteField[]
217     */
218    protected function jacobianDoublePointMixed(array $p)
219    {
220        list($x1, $y1) = $p;
221        $xx = $x1->multiply($x1);
222        $yy = $y1->multiply($y1);
223        $yyyy = $yy->multiply($yy);
224        $s = $x1->add($yy);
225        $s = $s->multiply($s)->subtract($xx)->subtract($yyyy)->multiply($this->two);
226        $m = $this->three->multiply($xx);
227        $t = $m->multiply($m)->subtract($this->two->multiply($s));
228        $x3 = $t;
229        $y3 = $s->subtract($t);
230        $y3 = $m->multiply($y3)->subtract($this->eight->multiply($yyyy));
231        $z3 = $this->two->multiply($y1);
232        return [$x3, $y3, $z3];
233    }
234
235    /**
236     * Tests whether or not the x / y values satisfy the equation
237     *
238     * @return boolean
239     */
240    public function verifyPoint(array $p)
241    {
242        list($x, $y) = $p;
243        $lhs = $y->multiply($y);
244        $temp = $x->multiply($x)->multiply($x);
245        $rhs = $temp->add($this->b);
246
247        return $lhs->equals($rhs);
248    }
249
250    /**
251     * Calculates the parameters needed from the Euclidean algorithm as discussed at
252     * http://diamond.boisestate.edu/~liljanab/MATH308/GuideToECC.pdf#page=148
253     *
254     * @param BigInteger $u
255     * @param BigInteger $v
256     * @return BigInteger[]
257     */
258    protected static function extendedGCD(BigInteger $u, BigInteger $v)
259    {
260        $one = new BigInteger(1);
261        $zero = new BigInteger();
262
263        $a = clone $one;
264        $b = clone $zero;
265        $c = clone $zero;
266        $d = clone $one;
267
268        $stop = $v->bitwise_rightShift($v->getLength() >> 1);
269
270        $a1 = clone $zero;
271        $b1 = clone $zero;
272        $a2 = clone $zero;
273        $b2 = clone $zero;
274
275        $postGreatestIndex = 0;
276
277        while (!$v->equals($zero)) {
278            list($q) = $u->divide($v);
279
280            $temp = $u;
281            $u = $v;
282            $v = $temp->subtract($v->multiply($q));
283
284            $temp = $a;
285            $a = $c;
286            $c = $temp->subtract($a->multiply($q));
287
288            $temp = $b;
289            $b = $d;
290            $d = $temp->subtract($b->multiply($q));
291
292            if ($v->compare($stop) > 0) {
293                $a0 = $v;
294                $b0 = $c;
295            } else {
296                $postGreatestIndex++;
297            }
298
299            if ($postGreatestIndex == 1) {
300                $a1 = $v;
301                $b1 = $c->negate();
302            }
303
304            if ($postGreatestIndex == 2) {
305                $rhs = $a0->multiply($a0)->add($b0->multiply($b0));
306                $lhs = $v->multiply($v)->add($b->multiply($b));
307                if ($lhs->compare($rhs) <= 0) {
308                    $a2 = $a0;
309                    $b2 = $b0->negate();
310                } else {
311                    $a2 = $v;
312                    $b2 = $c->negate();
313                }
314
315                break;
316            }
317        }
318
319        return [
320            ['a' => $a1, 'b' => $b1],
321            ['a' => $a2, 'b' => $b2]
322        ];
323    }
324}
325