1<?php
2
3/**
4 * Ed448
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 Ed448 extends TwistedEdwards
23{
24    const HASH = 'shake256-912';
25    const SIZE = 57;
26
27    public function __construct()
28    {
29        // 2^448 - 2^224 - 1
30        $this->setModulo(new BigInteger(
31            'FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE' .
32            'FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF',
33            16
34        ));
35        $this->setCoefficients(
36            new BigInteger(1),
37            // -39081
38            new BigInteger('FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE' .
39                           'FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6756', 16)
40        );
41        $this->setBasePoint(
42            new BigInteger('4F1970C66BED0DED221D15A622BF36DA9E146570470F1767EA6DE324' .
43                           'A3D3A46412AE1AF72AB66511433B80E18B00938E2626A82BC70CC05E', 16),
44            new BigInteger('693F46716EB6BC248876203756C9C7624BEA73736CA3984087789C1E' .
45                           '05A0C2D73AD3FF1CE67C39C4FDBD132C4ED7C8AD9808795BF230FA14', 16)
46        );
47        $this->setOrder(new BigInteger(
48            '3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF' .
49            '7CCA23E9C44EDB49AED63690216CC2728DC58F552378C292AB5844F3',
50            16
51        ));
52    }
53
54    /**
55     * Recover X from Y
56     *
57     * Implements steps 2-4 at https://tools.ietf.org/html/rfc8032#section-5.2.3
58     *
59     * Used by EC\Keys\Common.php
60     *
61     * @param BigInteger $y
62     * @param boolean $sign
63     * @return object[]
64     */
65    public function recoverX(BigInteger $y, $sign)
66    {
67        $y = $this->factory->newInteger($y);
68
69        $y2 = $y->multiply($y);
70        $u = $y2->subtract($this->one);
71        $v = $this->d->multiply($y2)->subtract($this->one);
72        $x2 = $u->divide($v);
73        if ($x2->equals($this->zero)) {
74            if ($sign) {
75                throw new \RuntimeException('Unable to recover X coordinate (x2 = 0)');
76            }
77            return clone $this->zero;
78        }
79        // find the square root
80        $exp = $this->getModulo()->add(new BigInteger(1));
81        $exp = $exp->bitwise_rightShift(2);
82        $x = $x2->pow($exp);
83
84        if (!$x->multiply($x)->subtract($x2)->equals($this->zero)) {
85            throw new \RuntimeException('Unable to recover X coordinate');
86        }
87        if ($x->isOdd() != $sign) {
88            $x = $x->negate();
89        }
90
91        return [$x, $y];
92    }
93
94    /**
95     * Extract Secret Scalar
96     *
97     * Implements steps 1-3 at https://tools.ietf.org/html/rfc8032#section-5.2.5
98     *
99     * Used by the various key handlers
100     *
101     * @param string $str
102     * @return \phpseclib3\Math\PrimeField\Integer
103     */
104    public function extractSecret($str)
105    {
106        if (strlen($str) != 57) {
107            throw new \LengthException('Private Key should be 57-bytes long');
108        }
109        // 1.  Hash the 57-byte private key using SHAKE256(x, 114), storing the
110        //     digest in a 114-octet large buffer, denoted h.  Only the lower 57
111        //     bytes are used for generating the public key.
112        $hash = new Hash('shake256-912');
113        $h = $hash->hash($str);
114        $h = substr($h, 0, 57);
115        // 2.  Prune the buffer: The two least significant bits of the first
116        //     octet are cleared, all eight bits the last octet are cleared, and
117        //     the highest bit of the second to last octet is set.
118        $h[0] = $h[0] & chr(0xFC);
119        $h = strrev($h);
120        $h[0] = "\0";
121        $h[1] = $h[1] | chr(0x80);
122        // 3.  Interpret the buffer as the little-endian integer, forming a
123        //     secret scalar s.
124        $dA = new BigInteger($h, 256);
125
126        $dA->secret = $str;
127        return $dA;
128    }
129
130    /**
131     * Encode a point as a string
132     *
133     * @param array $point
134     * @return string
135     */
136    public function encodePoint($point)
137    {
138        list($x, $y) = $point;
139        $y = "\0" . $y->toBytes();
140        if ($x->isOdd()) {
141            $y[0] = $y[0] | chr(0x80);
142        }
143        $y = strrev($y);
144
145        return $y;
146    }
147
148    /**
149     * Creates a random scalar multiplier
150     *
151     * @return \phpseclib3\Math\PrimeField\Integer
152     */
153    public function createRandomMultiplier()
154    {
155        return $this->extractSecret(Random::string(57));
156    }
157
158    /**
159     * Converts an affine point to an extended homogeneous coordinate
160     *
161     * From https://tools.ietf.org/html/rfc8032#section-5.2.4 :
162     *
163     * A point (x,y) is represented in extended homogeneous coordinates (X, Y, Z, T),
164     * with x = X/Z, y = Y/Z, x * y = T/Z.
165     *
166     * @return \phpseclib3\Math\PrimeField\Integer[]
167     */
168    public function convertToInternal(array $p)
169    {
170        if (empty($p)) {
171            return [clone $this->zero, clone $this->one, clone $this->one];
172        }
173
174        if (isset($p[2])) {
175            return $p;
176        }
177
178        $p[2] = clone $this->one;
179
180        return $p;
181    }
182
183    /**
184     * Doubles a point on a curve
185     *
186     * @return FiniteField[]
187     */
188    public function doublePoint(array $p)
189    {
190        if (!isset($this->factory)) {
191            throw new \RuntimeException('setModulo needs to be called before this method');
192        }
193
194        if (!count($p)) {
195            return [];
196        }
197
198        if (!isset($p[2])) {
199            throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa');
200        }
201
202        // from https://tools.ietf.org/html/rfc8032#page-18
203
204        list($x1, $y1, $z1) = $p;
205
206        $b = $x1->add($y1);
207        $b = $b->multiply($b);
208        $c = $x1->multiply($x1);
209        $d = $y1->multiply($y1);
210        $e = $c->add($d);
211        $h = $z1->multiply($z1);
212        $j = $e->subtract($this->two->multiply($h));
213
214        $x3 = $b->subtract($e)->multiply($j);
215        $y3 = $c->subtract($d)->multiply($e);
216        $z3 = $e->multiply($j);
217
218        return [$x3, $y3, $z3];
219    }
220
221    /**
222     * Adds two points on the curve
223     *
224     * @return FiniteField[]
225     */
226    public function addPoint(array $p, array $q)
227    {
228        if (!isset($this->factory)) {
229            throw new \RuntimeException('setModulo needs to be called before this method');
230        }
231
232        if (!count($p) || !count($q)) {
233            if (count($q)) {
234                return $q;
235            }
236            if (count($p)) {
237                return $p;
238            }
239            return [];
240        }
241
242        if (!isset($p[2]) || !isset($q[2])) {
243            throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa');
244        }
245
246        if ($p[0]->equals($q[0])) {
247            return !$p[1]->equals($q[1]) ? [] : $this->doublePoint($p);
248        }
249
250        // from https://tools.ietf.org/html/rfc8032#page-17
251
252        list($x1, $y1, $z1) = $p;
253        list($x2, $y2, $z2) = $q;
254
255        $a = $z1->multiply($z2);
256        $b = $a->multiply($a);
257        $c = $x1->multiply($x2);
258        $d = $y1->multiply($y2);
259        $e = $this->d->multiply($c)->multiply($d);
260        $f = $b->subtract($e);
261        $g = $b->add($e);
262        $h = $x1->add($y1)->multiply($x2->add($y2));
263
264        $x3 = $a->multiply($f)->multiply($h->subtract($c)->subtract($d));
265        $y3 = $a->multiply($g)->multiply($d->subtract($c));
266        $z3 = $f->multiply($g);
267
268        return [$x3, $y3, $z3];
269    }
270}
271