1<?php
2
3/**
4 * Ed25519
5 *
6 * PHP version 5 and 7
7 *
8 * @category  Crypt
9 * @package   EC
10 * @author    Jim Wigginton <terrafrost@php.net>
11 * @copyright 2017 Jim Wigginton
12 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
13 */
14
15namespace phpseclib3\Crypt\EC\Curves;
16
17use phpseclib3\Crypt\EC\BaseCurves\TwistedEdwards;
18use phpseclib3\Crypt\Hash;
19use phpseclib3\Crypt\Random;
20use phpseclib3\Math\BigInteger;
21
22class Ed25519 extends TwistedEdwards
23{
24    const HASH = 'sha512';
25    /*
26      Per https://tools.ietf.org/html/rfc8032#page-6 EdDSA has several parameters, one of which is b:
27
28      2.   An integer b with 2^(b-1) > p.  EdDSA public keys have exactly b
29           bits, and EdDSA signatures have exactly 2*b bits.  b is
30           recommended to be a multiple of 8, so public key and signature
31           lengths are an integral number of octets.
32
33      SIZE corresponds to b
34    */
35    const SIZE = 32;
36
37    public function __construct()
38    {
39        // 2^255 - 19
40        $this->setModulo(new BigInteger('7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED', 16));
41        $this->setCoefficients(
42            // -1
43            new BigInteger('7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC', 16), // a
44            // -121665/121666
45            new BigInteger('52036CEE2B6FFE738CC740797779E89800700A4D4141D8AB75EB4DCA135978A3', 16)  // d
46        );
47        $this->setBasePoint(
48            new BigInteger('216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A', 16),
49            new BigInteger('6666666666666666666666666666666666666666666666666666666666666658', 16)
50        );
51        $this->setOrder(new BigInteger('1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED', 16));
52        // algorithm 14.47 from http://cacr.uwaterloo.ca/hac/about/chap14.pdf#page=16
53        /*
54        $this->setReduction(function($x) {
55            $parts = $x->bitwise_split(255);
56            $className = $this->className;
57
58            if (count($parts) > 2) {
59                list(, $r) = $x->divide($className::$modulo);
60                return $r;
61            }
62
63            $zero = new BigInteger();
64            $c = new BigInteger(19);
65
66            switch (count($parts)) {
67                case 2:
68                    list($qi, $ri) = $parts;
69                    break;
70                case 1:
71                    $qi = $zero;
72                    list($ri) = $parts;
73                    break;
74                case 0:
75                    return $zero;
76            }
77            $r = $ri;
78
79            while ($qi->compare($zero) > 0) {
80                $temp = $qi->multiply($c)->bitwise_split(255);
81                if (count($temp) == 2) {
82                    list($qi, $ri) = $temp;
83                } else {
84                    $qi = $zero;
85                    list($ri) = $temp;
86                }
87                $r = $r->add($ri);
88            }
89
90            while ($r->compare($className::$modulo) > 0) {
91                $r = $r->subtract($className::$modulo);
92            }
93            return $r;
94        });
95        */
96    }
97
98    /**
99     * Recover X from Y
100     *
101     * Implements steps 2-4 at https://tools.ietf.org/html/rfc8032#section-5.1.3
102     *
103     * Used by EC\Keys\Common.php
104     *
105     * @param BigInteger $y
106     * @param boolean $sign
107     * @return object[]
108     */
109    public function recoverX(BigInteger $y, $sign)
110    {
111        $y = $this->factory->newInteger($y);
112
113        $y2 = $y->multiply($y);
114        $u = $y2->subtract($this->one);
115        $v = $this->d->multiply($y2)->add($this->one);
116        $x2 = $u->divide($v);
117        if ($x2->equals($this->zero)) {
118            if ($sign) {
119                throw new \RuntimeException('Unable to recover X coordinate (x2 = 0)');
120            }
121            return clone $this->zero;
122        }
123        // find the square root
124        /* we don't do $x2->squareRoot() because, quoting from
125           https://tools.ietf.org/html/rfc8032#section-5.1.1:
126
127           "For point decoding or "decompression", square roots modulo p are
128            needed.  They can be computed using the Tonelli-Shanks algorithm or
129            the special case for p = 5 (mod 8).  To find a square root of a,
130            first compute the candidate root x = a^((p+3)/8) (mod p)."
131         */
132        $exp = $this->getModulo()->add(new BigInteger(3));
133        $exp = $exp->bitwise_rightShift(3);
134        $x = $x2->pow($exp);
135
136        // If v x^2 = -u (mod p), set x <-- x * 2^((p-1)/4), which is a square root.
137        if (!$x->multiply($x)->subtract($x2)->equals($this->zero)) {
138            $temp = $this->getModulo()->subtract(new BigInteger(1));
139            $temp = $temp->bitwise_rightShift(2);
140            $temp = $this->two->pow($temp);
141            $x = $x->multiply($temp);
142            if (!$x->multiply($x)->subtract($x2)->equals($this->zero)) {
143                throw new \RuntimeException('Unable to recover X coordinate');
144            }
145        }
146        if ($x->isOdd() != $sign) {
147            $x = $x->negate();
148        }
149
150        return [$x, $y];
151    }
152
153    /**
154     * Extract Secret Scalar
155     *
156     * Implements steps 1-3 at https://tools.ietf.org/html/rfc8032#section-5.1.5
157     *
158     * Used by the various key handlers
159     *
160     * @param string $str
161     * @return \phpseclib3\Math\PrimeField\Integer
162     */
163    public function extractSecret($str)
164    {
165        if (strlen($str) != 32) {
166            throw new \LengthException('Private Key should be 32-bytes long');
167        }
168        // 1.  Hash the 32-byte private key using SHA-512, storing the digest in
169        //     a 64-octet large buffer, denoted h.  Only the lower 32 bytes are
170        //     used for generating the public key.
171        $hash = new Hash('sha512');
172        $h = $hash->hash($str);
173        $h = substr($h, 0, 32);
174        // 2.  Prune the buffer: The lowest three bits of the first octet are
175        //     cleared, the highest bit of the last octet is cleared, and the
176        //     second highest bit of the last octet is set.
177        $h[0] = $h[0] & chr(0xF8);
178        $h = strrev($h);
179        $h[0] = ($h[0] & chr(0x3F)) | chr(0x40);
180        // 3.  Interpret the buffer as the little-endian integer, forming a
181        //     secret scalar s.
182        $dA = new BigInteger($h, 256);
183
184        $dA->secret = $str;
185        return $dA;
186    }
187
188    /**
189     * Encode a point as a string
190     *
191     * @param array $point
192     * @return string
193     */
194    public function encodePoint($point)
195    {
196        list($x, $y) = $point;
197        $y = $y->toBytes();
198        $y[0] = $y[0] & chr(0x7F);
199        if ($x->isOdd()) {
200            $y[0] = $y[0] | chr(0x80);
201        }
202        $y = strrev($y);
203
204        return $y;
205    }
206
207    /**
208     * Creates a random scalar multiplier
209     *
210     * @return \phpseclib3\Math\PrimeField\Integer
211     */
212    public function createRandomMultiplier()
213    {
214        return $this->extractSecret(Random::string(32));
215    }
216
217    /**
218     * Converts an affine point to an extended homogeneous coordinate
219     *
220     * From https://tools.ietf.org/html/rfc8032#section-5.1.4 :
221     *
222     * A point (x,y) is represented in extended homogeneous coordinates (X, Y, Z, T),
223     * with x = X/Z, y = Y/Z, x * y = T/Z.
224     *
225     * @return \phpseclib3\Math\PrimeField\Integer[]
226     */
227    public function convertToInternal(array $p)
228    {
229        if (empty($p)) {
230            return [clone $this->zero, clone $this->one, clone $this->one, clone $this->zero];
231        }
232
233        if (isset($p[2])) {
234            return $p;
235        }
236
237        $p[2] = clone $this->one;
238        $p[3] = $p[0]->multiply($p[1]);
239
240        return $p;
241    }
242
243    /**
244     * Doubles a point on a curve
245     *
246     * @return FiniteField[]
247     */
248    public function doublePoint(array $p)
249    {
250        if (!isset($this->factory)) {
251            throw new \RuntimeException('setModulo needs to be called before this method');
252        }
253
254        if (!count($p)) {
255            return [];
256        }
257
258        if (!isset($p[2])) {
259            throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa');
260        }
261
262        // from https://tools.ietf.org/html/rfc8032#page-12
263
264        list($x1, $y1, $z1, $t1) = $p;
265
266        $a = $x1->multiply($x1);
267        $b = $y1->multiply($y1);
268        $c = $this->two->multiply($z1)->multiply($z1);
269        $h = $a->add($b);
270        $temp = $x1->add($y1);
271        $e = $h->subtract($temp->multiply($temp));
272        $g = $a->subtract($b);
273        $f = $c->add($g);
274
275        $x3 = $e->multiply($f);
276        $y3 = $g->multiply($h);
277        $t3 = $e->multiply($h);
278        $z3 = $f->multiply($g);
279
280        return [$x3, $y3, $z3, $t3];
281    }
282
283    /**
284     * Adds two points on the curve
285     *
286     * @return FiniteField[]
287     */
288    public function addPoint(array $p, array $q)
289    {
290        if (!isset($this->factory)) {
291            throw new \RuntimeException('setModulo needs to be called before this method');
292        }
293
294        if (!count($p) || !count($q)) {
295            if (count($q)) {
296                return $q;
297            }
298            if (count($p)) {
299                return $p;
300            }
301            return [];
302        }
303
304        if (!isset($p[2]) || !isset($q[2])) {
305            throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa');
306        }
307
308        if ($p[0]->equals($q[0])) {
309            return !$p[1]->equals($q[1]) ? [] : $this->doublePoint($p);
310        }
311
312        // from https://tools.ietf.org/html/rfc8032#page-12
313
314        list($x1, $y1, $z1, $t1) = $p;
315        list($x2, $y2, $z2, $t2) = $q;
316
317        $a = $y1->subtract($x1)->multiply($y2->subtract($x2));
318        $b = $y1->add($x1)->multiply($y2->add($x2));
319        $c = $t1->multiply($this->two)->multiply($this->d)->multiply($t2);
320        $d = $z1->multiply($this->two)->multiply($z2);
321        $e = $b->subtract($a);
322        $f = $d->subtract($c);
323        $g = $d->add($c);
324        $h = $b->add($a);
325
326        $x3 = $e->multiply($f);
327        $y3 = $g->multiply($h);
328        $t3 = $e->multiply($h);
329        $z3 = $f->multiply($g);
330
331        return [$x3, $y3, $z3, $t3];
332    }
333}
334