1<?php
2
3/**
4 * Curves over y^2 + x*y = x^3 + a*x^2 + b
5 *
6 * These are curves used in SEC 2 over prime fields: http://www.secg.org/SEC2-Ver-1.0.pdf
7 * The curve is a weierstrass curve with a[3] and a[2] set to 0.
8 *
9 * Uses Jacobian Coordinates for speed if able:
10 *
11 * https://en.wikipedia.org/wiki/Jacobian_curve
12 * https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates
13 *
14 * PHP version 5 and 7
15 *
16 * @category  Crypt
17 * @package   EC
18 * @author    Jim Wigginton <terrafrost@php.net>
19 * @copyright 2017 Jim Wigginton
20 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
21 * @link      http://pear.php.net/package/Math_BigInteger
22 */
23
24namespace phpseclib3\Crypt\EC\BaseCurves;
25
26use phpseclib3\Math\BigInteger;
27use phpseclib3\Math\BinaryField;
28use phpseclib3\Math\BinaryField\Integer as BinaryInteger;
29
30/**
31 * Curves over y^2 + x*y = x^3 + a*x^2 + b
32 *
33 * @package Binary
34 * @author  Jim Wigginton <terrafrost@php.net>
35 * @access  public
36 */
37class Binary extends Base
38{
39    /**
40     * Binary Field Integer factory
41     *
42     * @var \phpseclib3\Math\BinaryField
43     */
44    protected $factory;
45
46    /**
47     * Cofficient for x^1
48     *
49     * @var object
50     */
51    protected $a;
52
53    /**
54     * Cofficient for x^0
55     *
56     * @var object
57     */
58    protected $b;
59
60    /**
61     * Base Point
62     *
63     * @var object
64     */
65    protected $p;
66
67    /**
68     * The number one over the specified finite field
69     *
70     * @var object
71     */
72    protected $one;
73
74    /**
75     * The modulo
76     *
77     * @var BigInteger
78     */
79    protected $modulo;
80
81    /**
82     * The Order
83     *
84     * @var BigInteger
85     */
86    protected $order;
87
88    /**
89     * Sets the modulo
90     */
91    public function setModulo(...$modulo)
92    {
93        $this->modulo = $modulo;
94        $this->factory = new BinaryField(...$modulo);
95
96        $this->one = $this->factory->newInteger("\1");
97    }
98
99    /**
100     * Set coefficients a and b
101     *
102     * @param string $a
103     * @param string $b
104     */
105    public function setCoefficients($a, $b)
106    {
107        if (!isset($this->factory)) {
108            throw new \RuntimeException('setModulo needs to be called before this method');
109        }
110        $this->a = $this->factory->newInteger(pack('H*', $a));
111        $this->b = $this->factory->newInteger(pack('H*', $b));
112    }
113
114    /**
115     * Set x and y coordinates for the base point
116     *
117     * @param string|BinaryInteger $x
118     * @param string|BinaryInteger $y
119     */
120    public function setBasePoint($x, $y)
121    {
122        switch (true) {
123            case !is_string($x) && !$x instanceof BinaryInteger:
124                throw new \UnexpectedValueException('Argument 1 passed to Binary::setBasePoint() must be a string or an instance of BinaryField\Integer');
125            case !is_string($y) && !$y instanceof BinaryInteger:
126                throw new \UnexpectedValueException('Argument 2 passed to Binary::setBasePoint() must be a string or an instance of BinaryField\Integer');
127        }
128        if (!isset($this->factory)) {
129            throw new \RuntimeException('setModulo needs to be called before this method');
130        }
131        $this->p = [
132            is_string($x) ? $this->factory->newInteger(pack('H*', $x)) : $x,
133            is_string($y) ? $this->factory->newInteger(pack('H*', $y)) : $y
134        ];
135    }
136
137    /**
138     * Retrieve the base point as an array
139     *
140     * @return array
141     */
142    public function getBasePoint()
143    {
144        if (!isset($this->factory)) {
145            throw new \RuntimeException('setModulo needs to be called before this method');
146        }
147        /*
148        if (!isset($this->p)) {
149            throw new \RuntimeException('setBasePoint needs to be called before this method');
150        }
151        */
152        return $this->p;
153    }
154
155    /**
156     * Adds two points on the curve
157     *
158     * @return FiniteField[]
159     */
160    public function addPoint(array $p, array $q)
161    {
162        if (!isset($this->factory)) {
163            throw new \RuntimeException('setModulo needs to be called before this method');
164        }
165
166        if (!count($p) || !count($q)) {
167            if (count($q)) {
168                return $q;
169            }
170            if (count($p)) {
171                return $p;
172            }
173            return [];
174        }
175
176        if (!isset($p[2]) || !isset($q[2])) {
177            throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa');
178        }
179
180        if ($p[0]->equals($q[0])) {
181            return !$p[1]->equals($q[1]) ? [] : $this->doublePoint($p);
182        }
183
184        // formulas from http://hyperelliptic.org/EFD/g12o/auto-shortw-jacobian.html
185
186        list($x1, $y1, $z1) = $p;
187        list($x2, $y2, $z2) = $q;
188
189        $o1 = $z1->multiply($z1);
190        $b = $x2->multiply($o1);
191
192        if ($z2->equals($this->one)) {
193            $d = $y2->multiply($o1)->multiply($z1);
194            $e = $x1->add($b);
195            $f = $y1->add($d);
196            $z3 = $e->multiply($z1);
197            $h = $f->multiply($x2)->add($z3->multiply($y2));
198            $i = $f->add($z3);
199            $g = $z3->multiply($z3);
200            $p1 = $this->a->multiply($g);
201            $p2 = $f->multiply($i);
202            $p3 = $e->multiply($e)->multiply($e);
203            $x3 = $p1->add($p2)->add($p3);
204            $y3 = $i->multiply($x3)->add($g->multiply($h));
205
206            return [$x3, $y3, $z3];
207        }
208
209        $o2 = $z2->multiply($z2);
210        $a = $x1->multiply($o2);
211        $c = $y1->multiply($o2)->multiply($z2);
212        $d = $y2->multiply($o1)->multiply($z1);
213        $e = $a->add($b);
214        $f = $c->add($d);
215        $g = $e->multiply($z1);
216        $h = $f->multiply($x2)->add($g->multiply($y2));
217        $z3 = $g->multiply($z2);
218        $i = $f->add($z3);
219        $p1 = $this->a->multiply($z3->multiply($z3));
220        $p2 = $f->multiply($i);
221        $p3 = $e->multiply($e)->multiply($e);
222        $x3 = $p1->add($p2)->add($p3);
223        $y3 = $i->multiply($x3)->add($g->multiply($g)->multiply($h));
224
225        return [$x3, $y3, $z3];
226    }
227
228    /**
229     * Doubles a point on a curve
230     *
231     * @return FiniteField[]
232     */
233    public function doublePoint(array $p)
234    {
235        if (!isset($this->factory)) {
236            throw new \RuntimeException('setModulo needs to be called before this method');
237        }
238
239        if (!count($p)) {
240            return [];
241        }
242
243        if (!isset($p[2])) {
244            throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa');
245        }
246
247        // formulas from http://hyperelliptic.org/EFD/g12o/auto-shortw-jacobian.html
248
249        list($x1, $y1, $z1) = $p;
250
251        $a = $x1->multiply($x1);
252        $b = $a->multiply($a);
253
254        if ($z1->equals($this->one)) {
255            $x3 = $b->add($this->b);
256            $z3 = clone $x1;
257            $p1 = $a->add($y1)->add($z3)->multiply($this->b);
258            $p2 = $a->add($y1)->multiply($b);
259            $y3 = $p1->add($p2);
260
261            return [$x3, $y3, $z3];
262        }
263
264        $c = $z1->multiply($z1);
265        $d = $c->multiply($c);
266        $x3 = $b->add($this->b->multiply($d->multiply($d)));
267        $z3 = $x1->multiply($c);
268        $p1 = $b->multiply($z3);
269        $p2 = $a->add($y1->multiply($z1))->add($z3)->multiply($x3);
270        $y3 = $p1->add($p2);
271
272        return [$x3, $y3, $z3];
273    }
274
275    /**
276     * Returns the X coordinate and the derived Y coordinate
277     *
278     * Not supported because it is covered by patents.
279     * Quoting https://www.openssl.org/docs/man1.1.0/apps/ecparam.html ,
280     *
281     * "Due to patent issues the compressed option is disabled by default for binary curves
282     *  and can be enabled by defining the preprocessor macro OPENSSL_EC_BIN_PT_COMP at
283     *  compile time."
284     *
285     * @return array
286     */
287    public function derivePoint($m)
288    {
289        throw new \RuntimeException('Point compression on binary finite field elliptic curves is not supported');
290    }
291
292    /**
293     * Tests whether or not the x / y values satisfy the equation
294     *
295     * @return boolean
296     */
297    public function verifyPoint(array $p)
298    {
299        list($x, $y) = $p;
300        $lhs = $y->multiply($y);
301        $lhs = $lhs->add($x->multiply($y));
302        $x2 = $x->multiply($x);
303        $x3 = $x2->multiply($x);
304        $rhs = $x3->add($this->a->multiply($x2))->add($this->b);
305
306        return $lhs->equals($rhs);
307    }
308
309    /**
310     * Returns the modulo
311     *
312     * @return \phpseclib3\Math\BigInteger
313     */
314    public function getModulo()
315    {
316        return $this->modulo;
317    }
318
319    /**
320     * Returns the a coefficient
321     *
322     * @return \phpseclib3\Math\PrimeField\Integer
323     */
324    public function getA()
325    {
326        return $this->a;
327    }
328
329    /**
330     * Returns the a coefficient
331     *
332     * @return \phpseclib3\Math\PrimeField\Integer
333     */
334    public function getB()
335    {
336        return $this->b;
337    }
338
339    /**
340     * Returns the affine point
341     *
342     * A Jacobian Coordinate is of the form (x, y, z).
343     * To convert a Jacobian Coordinate to an Affine Point
344     * you do (x / z^2, y / z^3)
345     *
346     * @return \phpseclib3\Math\PrimeField\Integer[]
347     */
348    public function convertToAffine(array $p)
349    {
350        if (!isset($p[2])) {
351            return $p;
352        }
353        list($x, $y, $z) = $p;
354        $z = $this->one->divide($z);
355        $z2 = $z->multiply($z);
356        return [
357            $x->multiply($z2),
358            $y->multiply($z2)->multiply($z)
359        ];
360    }
361
362    /**
363     * Converts an affine point to a jacobian coordinate
364     *
365     * @return \phpseclib3\Math\PrimeField\Integer[]
366     */
367    public function convertToInternal(array $p)
368    {
369        if (isset($p[2])) {
370            return $p;
371        }
372
373        $p[2] = clone $this->one;
374        $p['fresh'] = true;
375        return $p;
376    }
377}
378