1<?php
2
3/**
4 * Curves over y^2 = x^3 + a*x + x
5 *
6 * Technically, a Montgomery curve has a coefficient for y^2 but for Curve25519 and Curve448 that
7 * coefficient is 1.
8 *
9 * Curve25519 and Curve448 do not make use of the y coordinate, which makes it unsuitable for use
10 * with ECDSA / EdDSA. A few other differences between Curve25519 and Ed25519 are discussed at
11 * https://crypto.stackexchange.com/a/43058/4520
12 *
13 * More info:
14 *
15 * https://en.wikipedia.org/wiki/Montgomery_curve
16 *
17 * PHP version 5 and 7
18 *
19 * @category  Crypt
20 * @package   EC
21 * @author    Jim Wigginton <terrafrost@php.net>
22 * @copyright 2019 Jim Wigginton
23 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
24 * @link      http://pear.php.net/package/Math_BigInteger
25 */
26
27namespace phpseclib3\Crypt\EC\BaseCurves;
28
29use phpseclib3\Crypt\EC\Curves\Curve25519;
30use phpseclib3\Math\BigInteger;
31use phpseclib3\Math\PrimeField;
32use phpseclib3\Math\PrimeField\Integer as PrimeInteger;
33
34/**
35 * Curves over y^2 = x^3 + a*x + x
36 *
37 * @package EC
38 * @author  Jim Wigginton <terrafrost@php.net>
39 * @access  public
40 */
41class Montgomery extends Base
42{
43    /**
44     * Prime Field Integer factory
45     *
46     * @var \phpseclib3\Math\PrimeField
47     */
48    protected $factory;
49
50    /**
51     * Cofficient for x
52     *
53     * @var object
54     */
55    protected $a;
56
57    /**
58     * Constant used for point doubling
59     *
60     * @var object
61     */
62    protected $a24;
63
64    /**
65     * The Number Zero
66     *
67     * @var object
68     */
69    protected $zero;
70
71    /**
72     * The Number One
73     *
74     * @var object
75     */
76    protected $one;
77
78    /**
79     * Base Point
80     *
81     * @var object
82     */
83    protected $p;
84
85    /**
86     * The modulo
87     *
88     * @var BigInteger
89     */
90    protected $modulo;
91
92    /**
93     * The Order
94     *
95     * @var BigInteger
96     */
97    protected $order;
98
99    /**
100     * Sets the modulo
101     */
102    public function setModulo(BigInteger $modulo)
103    {
104        $this->modulo = $modulo;
105        $this->factory = new PrimeField($modulo);
106        $this->zero = $this->factory->newInteger(new BigInteger());
107        $this->one = $this->factory->newInteger(new BigInteger(1));
108    }
109
110    /**
111     * Set coefficients a
112     */
113    public function setCoefficients(BigInteger $a)
114    {
115        if (!isset($this->factory)) {
116            throw new \RuntimeException('setModulo needs to be called before this method');
117        }
118        $this->a = $this->factory->newInteger($a);
119        $two = $this->factory->newInteger(new BigInteger(2));
120        $four = $this->factory->newInteger(new BigInteger(4));
121        $this->a24 = $this->a->subtract($two)->divide($four);
122    }
123
124    /**
125     * Set x and y coordinates for the base point
126     *
127     * @param BigInteger|PrimeInteger $x
128     * @param BigInteger|PrimeInteger $y
129     * @return PrimeInteger[]
130     */
131    public function setBasePoint($x, $y)
132    {
133        switch (true) {
134            case !$x instanceof BigInteger && !$x instanceof PrimeInteger:
135                throw new \UnexpectedValueException('Argument 1 passed to Prime::setBasePoint() must be an instance of either BigInteger or PrimeField\Integer');
136            case !$y instanceof BigInteger && !$y instanceof PrimeInteger:
137                throw new \UnexpectedValueException('Argument 2 passed to Prime::setBasePoint() must be an instance of either BigInteger or PrimeField\Integer');
138        }
139        if (!isset($this->factory)) {
140            throw new \RuntimeException('setModulo needs to be called before this method');
141        }
142        $this->p = [
143            $x instanceof BigInteger ? $this->factory->newInteger($x) : $x,
144            $y instanceof BigInteger ? $this->factory->newInteger($y) : $y
145        ];
146    }
147
148    /**
149     * Retrieve the base point as an array
150     *
151     * @return array
152     */
153    public function getBasePoint()
154    {
155        if (!isset($this->factory)) {
156            throw new \RuntimeException('setModulo needs to be called before this method');
157        }
158        /*
159        if (!isset($this->p)) {
160            throw new \RuntimeException('setBasePoint needs to be called before this method');
161        }
162        */
163        return $this->p;
164    }
165
166    /**
167     * Doubles and adds a point on a curve
168     *
169     * See https://tools.ietf.org/html/draft-ietf-tls-curve25519-01#appendix-A.1.3
170     *
171     * @return FiniteField[][]
172     */
173    private function doubleAndAddPoint(array $p, array $q, PrimeInteger $x1)
174    {
175        if (!isset($this->factory)) {
176            throw new \RuntimeException('setModulo needs to be called before this method');
177        }
178
179        if (!count($p) || !count($q)) {
180            return [];
181        }
182
183        if (!isset($p[1])) {
184            throw new \RuntimeException('Affine coordinates need to be manually converted to XZ coordinates');
185        }
186
187        list($x2, $z2) = $p;
188        list($x3, $z3) = $q;
189
190        $a = $x2->add($z2);
191        $aa = $a->multiply($a);
192        $b = $x2->subtract($z2);
193        $bb = $b->multiply($b);
194        $e = $aa->subtract($bb);
195        $c = $x3->add($z3);
196        $d = $x3->subtract($z3);
197        $da = $d->multiply($a);
198        $cb = $c->multiply($b);
199        $temp = $da->add($cb);
200        $x5 = $temp->multiply($temp);
201        $temp = $da->subtract($cb);
202        $z5 = $x1->multiply($temp->multiply($temp));
203        $x4 = $aa->multiply($bb);
204        $temp = static::class == Curve25519::class ? $bb : $aa;
205        $z4 = $e->multiply($temp->add($this->a24->multiply($e)));
206
207        return [
208            [$x4, $z4],
209            [$x5, $z5]
210        ];
211    }
212
213    /**
214     * Multiply a point on the curve by a scalar
215     *
216     * Uses the montgomery ladder technique as described here:
217     *
218     * https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Montgomery_ladder
219     * https://github.com/phpecc/phpecc/issues/16#issuecomment-59176772
220     *
221     * @return array
222     */
223    public function multiplyPoint(array $p, BigInteger $d)
224    {
225        $p1 = [$this->one, $this->zero];
226        $alreadyInternal = isset($x[1]);
227        $p2 = $this->convertToInternal($p);
228        $x = $p[0];
229
230        $b = $d->toBits();
231        $b = str_pad($b, 256, '0', STR_PAD_LEFT);
232        for ($i = 0; $i < strlen($b); $i++) {
233            $b_i = (int) $b[$i];
234            if ($b_i) {
235                list($p2, $p1) = $this->doubleAndAddPoint($p2, $p1, $x);
236            } else {
237                list($p1, $p2) = $this->doubleAndAddPoint($p1, $p2, $x);
238            }
239        }
240
241        return $alreadyInternal ? $p1 : $this->convertToAffine($p1);
242    }
243
244    /**
245     * Converts an affine point to an XZ coordinate
246     *
247     * From https://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html
248     *
249     * XZ coordinates represent x y as X Z satsfying the following equations:
250     *
251     *   x=X/Z
252     *
253     * @return \phpseclib3\Math\PrimeField\Integer[]
254     */
255    public function convertToInternal(array $p)
256    {
257        if (empty($p)) {
258            return [clone $this->zero, clone $this->one];
259        }
260
261        if (isset($p[1])) {
262            return $p;
263        }
264
265        $p[1] = clone $this->one;
266
267        return $p;
268    }
269
270    /**
271     * Returns the affine point
272     *
273     * @return \phpseclib3\Math\PrimeField\Integer[]
274     */
275    public function convertToAffine(array $p)
276    {
277        if (!isset($p[1])) {
278            return $p;
279        }
280        list($x, $z) = $p;
281        return [$x->divide($z)];
282    }
283}
284