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