```/* <![CDATA[ */
function get_sym_list(){return [["Class","xc",[["KoblitzPrime",43]]],["Namespace","xn",[["phpseclib3\\\\Crypt\\\\EC\\\\BaseCurves",31]]],["Function","xf",[["doublePointHelper",179],["extendedGCD",258],["jacobianDoublePoint",193],["jacobianDoublePointMixed",218],["multiplyAddPoints",58],["verifyPoint",240]]]];} /* ]]> */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
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     *
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 = [
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 = [
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) {
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) {
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);
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
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);
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);
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);
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) {
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```