1<?php
2
3/**
4 * Generic EC Key Parsing Helper functions
5 *
6 * PHP version 5
7 *
8 * @category  Crypt
9 * @package   EC
10 * @author    Jim Wigginton <terrafrost@php.net>
11 * @copyright 2015 Jim Wigginton
12 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
13 * @link      http://phpseclib.sourceforge.net
14 */
15
16namespace phpseclib3\Crypt\EC\Formats\Keys;
17
18use ParagonIE\ConstantTime\Hex;
19use phpseclib3\Common\Functions\Strings;
20use phpseclib3\Crypt\EC\BaseCurves\Base as BaseCurve;
21use phpseclib3\Crypt\EC\BaseCurves\Binary as BinaryCurve;
22use phpseclib3\Crypt\EC\BaseCurves\Prime as PrimeCurve;
23use phpseclib3\Crypt\EC\BaseCurves\TwistedEdwards as TwistedEdwardsCurve;
24use phpseclib3\Exception\UnsupportedCurveException;
25use phpseclib3\File\ASN1;
26use phpseclib3\File\ASN1\Maps;
27use phpseclib3\Math\BigInteger;
28
29/**
30 * Generic EC Key Parsing Helper functions
31 *
32 * @package EC
33 * @author  Jim Wigginton <terrafrost@php.net>
34 * @access  public
35 */
36trait Common
37{
38    /**
39     * Curve OIDs
40     *
41     * @var array
42     */
43    private static $curveOIDs = [];
44
45    /**
46     * Child OIDs loaded
47     *
48     * @var bool
49     */
50    protected static $childOIDsLoaded = false;
51
52    /**
53     * Use Named Curves
54     *
55     * @var bool
56     */
57    private static $useNamedCurves = true;
58
59    /**
60     * Initialize static variables
61     */
62    private static function initialize_static_variables()
63    {
64        if (empty(self::$curveOIDs)) {
65            // the sec* curves are from the standards for efficient cryptography group
66            // sect* curves are curves over binary finite fields
67            // secp* curves are curves over prime finite fields
68            // sec*r* curves are regular curves; sec*k* curves are koblitz curves
69            // brainpool*r* curves are regular prime finite field curves
70            // brainpool*t* curves are twisted versions of the brainpool*r* curves
71            self::$curveOIDs = [
72                'prime192v1' => '1.2.840.10045.3.1.1', // J.5.1, example 1 (aka secp192r1)
73                'prime192v2' => '1.2.840.10045.3.1.2', // J.5.1, example 2
74                'prime192v3' => '1.2.840.10045.3.1.3', // J.5.1, example 3
75                'prime239v1' => '1.2.840.10045.3.1.4', // J.5.2, example 1
76                'prime239v2' => '1.2.840.10045.3.1.5', // J.5.2, example 2
77                'prime239v3' => '1.2.840.10045.3.1.6', // J.5.2, example 3
78                'prime256v1' => '1.2.840.10045.3.1.7', // J.5.3, example 1 (aka secp256r1)
79
80                // https://tools.ietf.org/html/rfc5656#section-10
81                'nistp256' => '1.2.840.10045.3.1.7', // aka secp256r1
82                'nistp384' => '1.3.132.0.34', // aka secp384r1
83                'nistp521' => '1.3.132.0.35', // aka secp521r1
84
85                'nistk163' => '1.3.132.0.1', // aka sect163k1
86                'nistp192' => '1.2.840.10045.3.1.1', // aka secp192r1
87                'nistp224' => '1.3.132.0.33', // aka secp224r1
88                'nistk233' => '1.3.132.0.26', // aka sect233k1
89                'nistb233' => '1.3.132.0.27', // aka sect233r1
90                'nistk283' => '1.3.132.0.16', // aka sect283k1
91                'nistk409' => '1.3.132.0.36', // aka sect409k1
92                'nistb409' => '1.3.132.0.37', // aka sect409r1
93                'nistt571' => '1.3.132.0.38', // aka sect571k1
94
95                // from https://tools.ietf.org/html/rfc5915
96                'secp192r1' => '1.2.840.10045.3.1.1', // aka prime192v1
97                'sect163k1' => '1.3.132.0.1',
98                'sect163r2' => '1.3.132.0.15',
99                'secp224r1' => '1.3.132.0.33',
100                'sect233k1' => '1.3.132.0.26',
101                'sect233r1' => '1.3.132.0.27',
102                'secp256r1' => '1.2.840.10045.3.1.7', // aka prime256v1
103                'sect283k1' => '1.3.132.0.16',
104                'sect283r1' => '1.3.132.0.17',
105                'secp384r1' => '1.3.132.0.34',
106                'sect409k1' => '1.3.132.0.36',
107                'sect409r1' => '1.3.132.0.37',
108                'secp521r1' => '1.3.132.0.35',
109                'sect571k1' => '1.3.132.0.38',
110                'sect571r1' => '1.3.132.0.39',
111                // from http://www.secg.org/SEC2-Ver-1.0.pdf
112                'secp112r1' => '1.3.132.0.6',
113                'secp112r2' => '1.3.132.0.7',
114                'secp128r1' => '1.3.132.0.28',
115                'secp128r2' => '1.3.132.0.29',
116                'secp160k1' => '1.3.132.0.9',
117                'secp160r1' => '1.3.132.0.8',
118                'secp160r2' => '1.3.132.0.30',
119                'secp192k1' => '1.3.132.0.31',
120                'secp224k1' => '1.3.132.0.32',
121                'secp256k1' => '1.3.132.0.10',
122
123                'sect113r1' => '1.3.132.0.4',
124                'sect113r2' => '1.3.132.0.5',
125                'sect131r1' => '1.3.132.0.22',
126                'sect131r2' => '1.3.132.0.23',
127                'sect163r1' => '1.3.132.0.2',
128                'sect193r1' => '1.3.132.0.24',
129                'sect193r2' => '1.3.132.0.25',
130                'sect239k1' => '1.3.132.0.3',
131
132                // from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.202.2977&rep=rep1&type=pdf#page=36
133                /*
134                'c2pnb163v1' => '1.2.840.10045.3.0.1', // J.4.1, example 1
135                'c2pnb163v2' => '1.2.840.10045.3.0.2', // J.4.1, example 2
136                'c2pnb163v3' => '1.2.840.10045.3.0.3', // J.4.1, example 3
137                'c2pnb172w1' => '1.2.840.10045.3.0.4', // J.4.2, example 1
138                'c2tnb191v1' => '1.2.840.10045.3.0.5', // J.4.3, example 1
139                'c2tnb191v2' => '1.2.840.10045.3.0.6', // J.4.3, example 2
140                'c2tnb191v3' => '1.2.840.10045.3.0.7', // J.4.3, example 3
141                'c2onb191v4' => '1.2.840.10045.3.0.8', // J.4.3, example 4
142                'c2onb191v5' => '1.2.840.10045.3.0.9', // J.4.3, example 5
143                'c2pnb208w1' => '1.2.840.10045.3.0.10', // J.4.4, example 1
144                'c2tnb239v1' => '1.2.840.10045.3.0.11', // J.4.5, example 1
145                'c2tnb239v2' => '1.2.840.10045.3.0.12', // J.4.5, example 2
146                'c2tnb239v3' => '1.2.840.10045.3.0.13', // J.4.5, example 3
147                'c2onb239v4' => '1.2.840.10045.3.0.14', // J.4.5, example 4
148                'c2onb239v5' => '1.2.840.10045.3.0.15', // J.4.5, example 5
149                'c2pnb272w1' => '1.2.840.10045.3.0.16', // J.4.6, example 1
150                'c2pnb304w1' => '1.2.840.10045.3.0.17', // J.4.7, example 1
151                'c2tnb359v1' => '1.2.840.10045.3.0.18', // J.4.8, example 1
152                'c2pnb368w1' => '1.2.840.10045.3.0.19', // J.4.9, example 1
153                'c2tnb431r1' => '1.2.840.10045.3.0.20', // J.4.10, example 1
154                */
155
156                // http://www.ecc-brainpool.org/download/Domain-parameters.pdf
157                // https://tools.ietf.org/html/rfc5639
158                'brainpoolP160r1' => '1.3.36.3.3.2.8.1.1.1',
159                'brainpoolP160t1' => '1.3.36.3.3.2.8.1.1.2',
160                'brainpoolP192r1' => '1.3.36.3.3.2.8.1.1.3',
161                'brainpoolP192t1' => '1.3.36.3.3.2.8.1.1.4',
162                'brainpoolP224r1' => '1.3.36.3.3.2.8.1.1.5',
163                'brainpoolP224t1' => '1.3.36.3.3.2.8.1.1.6',
164                'brainpoolP256r1' => '1.3.36.3.3.2.8.1.1.7',
165                'brainpoolP256t1' => '1.3.36.3.3.2.8.1.1.8',
166                'brainpoolP320r1' => '1.3.36.3.3.2.8.1.1.9',
167                'brainpoolP320t1' => '1.3.36.3.3.2.8.1.1.10',
168                'brainpoolP384r1' => '1.3.36.3.3.2.8.1.1.11',
169                'brainpoolP384t1' => '1.3.36.3.3.2.8.1.1.12',
170                'brainpoolP512r1' => '1.3.36.3.3.2.8.1.1.13',
171                'brainpoolP512t1' => '1.3.36.3.3.2.8.1.1.14'
172            ];
173            ASN1::loadOIDs([
174                'prime-field' => '1.2.840.10045.1.1',
175                'characteristic-two-field' => '1.2.840.10045.1.2',
176                'characteristic-two-basis' => '1.2.840.10045.1.2.3',
177                // per http://www.secg.org/SEC1-Ver-1.0.pdf#page=84, gnBasis "not used here"
178                'gnBasis' => '1.2.840.10045.1.2.3.1', // NULL
179                'tpBasis' => '1.2.840.10045.1.2.3.2', // Trinomial
180                'ppBasis' => '1.2.840.10045.1.2.3.3'  // Pentanomial
181            ] + self::$curveOIDs);
182        }
183    }
184
185    /**
186     * Explicitly set the curve
187     *
188     * If the key contains an implicit curve phpseclib needs the curve
189     * to be explicitly provided
190     *
191     * @param \phpseclib3\Crypt\EC\BaseCurves\Base $curve
192     */
193    public static function setImplicitCurve(BaseCurve $curve)
194    {
195        self::$implicitCurve = $curve;
196    }
197
198    /**
199     * Returns an instance of \phpseclib3\Crypt\EC\BaseCurves\Base based
200     * on the curve parameters
201     *
202     * @param array $params
203     * @return \phpseclib3\Crypt\EC\BaseCurves\Base|false
204     */
205    protected static function loadCurveByParam(array $params)
206    {
207        if (count($params) > 1) {
208            throw new \RuntimeException('No parameters are present');
209        }
210        if (isset($params['namedCurve'])) {
211            $curve = '\phpseclib3\Crypt\EC\Curves\\' . $params['namedCurve'];
212            if (!class_exists($curve)) {
213                throw new UnsupportedCurveException('Named Curve of ' . $params['namedCurve'] . ' is not supported');
214            }
215            return new $curve();
216        }
217        if (isset($params['implicitCurve'])) {
218            if (!isset(self::$implicitCurve)) {
219                throw new \RuntimeException('Implicit curves can be provided by calling setImplicitCurve');
220            }
221            return self::$implicitCurve;
222        }
223        if (isset($params['specifiedCurve'])) {
224            $data = $params['specifiedCurve'];
225            switch ($data['fieldID']['fieldType']) {
226                case 'prime-field':
227                    $curve = new PrimeCurve();
228                    $curve->setModulo($data['fieldID']['parameters']);
229                    $curve->setCoefficients(
230                        new BigInteger($data['curve']['a'], 256),
231                        new BigInteger($data['curve']['b'], 256)
232                    );
233                    $point = self::extractPoint("\0" . $data['base'], $curve);
234                    $curve->setBasePoint(...$point);
235                    $curve->setOrder($data['order']);
236                    return $curve;
237                case 'characteristic-two-field':
238                    $curve = new BinaryCurve();
239                    $params = ASN1::decodeBER($data['fieldID']['parameters']);
240                    $params = ASN1::asn1map($params[0], Maps\Characteristic_two::MAP);
241                    $modulo = [(int) $params['m']->toString()];
242                    switch ($params['basis']) {
243                        case 'tpBasis':
244                            $modulo[] = (int) $params['parameters']->toString();
245                            break;
246                        case 'ppBasis':
247                            $temp = ASN1::decodeBER($params['parameters']);
248                            $temp = ASN1::asn1map($temp[0], Maps\Pentanomial::MAP);
249                            $modulo[] = (int) $temp['k3']->toString();
250                            $modulo[] = (int) $temp['k2']->toString();
251                            $modulo[] = (int) $temp['k1']->toString();
252                    }
253                    $modulo[] = 0;
254                    $curve->setModulo(...$modulo);
255                    $len = ceil($modulo[0] / 8);
256                    $curve->setCoefficients(
257                        Hex::encode($data['curve']['a']),
258                        Hex::encode($data['curve']['b'])
259                    );
260                    $point = self::extractPoint("\0" . $data['base'], $curve);
261                    $curve->setBasePoint(...$point);
262                    $curve->setOrder($data['order']);
263                    return $curve;
264                default:
265                    throw new UnsupportedCurveException('Field Type of ' . $data['fieldID']['fieldType'] . ' is not supported');
266            }
267        }
268        throw new \RuntimeException('No valid parameters are present');
269    }
270
271    /**
272     * Extract points from a string
273     *
274     * Supports both compressed and uncompressed points
275     *
276     * @param string $str
277     * @param \phpseclib3\Crypt\EC\BaseCurves\Base $curve
278     * @return object[]
279     */
280    public static function extractPoint($str, BaseCurve $curve)
281    {
282        if ($curve instanceof TwistedEdwardsCurve) {
283            // first step of point deciding as discussed at the following URL's:
284            // https://tools.ietf.org/html/rfc8032#section-5.1.3
285            // https://tools.ietf.org/html/rfc8032#section-5.2.3
286            $y = $str;
287            $y = strrev($y);
288            $sign = (bool) (ord($y[0]) & 0x80);
289            $y[0] = $y[0] & chr(0x7F);
290            $y = new BigInteger($y, 256);
291            if ($y->compare($curve->getModulo()) >= 0) {
292                throw new \RuntimeException('The Y coordinate should not be >= the modulo');
293            }
294            $point = $curve->recoverX($y, $sign);
295            if (!$curve->verifyPoint($point)) {
296                throw new \RuntimeException('Unable to verify that point exists on curve');
297            }
298            return $point;
299        }
300
301        // the first byte of a bit string represents the number of bits in the last byte that are to be ignored but,
302        // currently, bit strings wanting a non-zero amount of bits trimmed are not supported
303        if (($val = Strings::shift($str)) != "\0") {
304            throw new \UnexpectedValueException('extractPoint expects the first byte to be null - not ' . Hex::encode($val));
305        }
306        if ($str == "\0") {
307            return [];
308        }
309
310        $keylen = strlen($str);
311        $order = $curve->getLengthInBytes();
312        // point compression is being used
313        if ($keylen == $order + 1) {
314            return $curve->derivePoint($str);
315        }
316
317        // point compression is not being used
318        if ($keylen == 2 * $order + 1) {
319            preg_match("#(.)(.{{$order}})(.{{$order}})#s", $str, $matches);
320            list(, $w, $x, $y) = $matches;
321            if ($w != "\4") {
322                throw new \UnexpectedValueException('The first byte of an uncompressed point should be 04 - not ' . Hex::encode($val));
323            }
324            $point = [
325                $curve->convertInteger(new BigInteger($x, 256)),
326                $curve->convertInteger(new BigInteger($y, 256))
327            ];
328
329            if (!$curve->verifyPoint($point)) {
330                throw new \RuntimeException('Unable to verify that point exists on curve');
331            }
332
333            return $point;
334        }
335
336        throw new \UnexpectedValueException('The string representation of the points is not of an appropriate length');
337    }
338
339    /**
340     * Encode Parameters
341     *
342     * @todo Maybe at some point this could be moved to __toString() for each of the curves?
343     * @param \phpseclib3\Crypt\EC\BaseCurves\Base $curve
344     * @param bool $returnArray optional
345     * @param array $options optional
346     * @return string|false
347     */
348    private static function encodeParameters(BaseCurve $curve, $returnArray = false, array $options = [])
349    {
350        $useNamedCurves = isset($options['namedCurve']) ? $options['namedCurve'] : self::$useNamedCurves;
351
352        $reflect = new \ReflectionClass($curve);
353        $name = $reflect->getShortName();
354        if ($useNamedCurves) {
355            if (isset(self::$curveOIDs[$name])) {
356                if ($reflect->isFinal()) {
357                    $reflect = $reflect->getParentClass();
358                    $name = $reflect->getShortName();
359                }
360                return $returnArray ?
361                    ['namedCurve' => $name] :
362                    ASN1::encodeDER(['namedCurve' => $name], Maps\ECParameters::MAP);
363            }
364            foreach (new \DirectoryIterator(__DIR__ . '/../../Curves/') as $file) {
365                if ($file->getExtension() != 'php') {
366                    continue;
367                }
368                $testName = $file->getBasename('.php');
369                $class = 'phpseclib3\Crypt\EC\Curves\\' . $testName;
370                $reflect = new \ReflectionClass($class);
371                if ($reflect->isFinal()) {
372                    continue;
373                }
374                $candidate = new $class();
375                switch ($name) {
376                    case 'Prime':
377                        if (!$candidate instanceof PrimeCurve) {
378                            break;
379                        }
380                        if (!$candidate->getModulo()->equals($curve->getModulo())) {
381                            break;
382                        }
383                        if ($candidate->getA()->toBytes() != $curve->getA()->toBytes()) {
384                            break;
385                        }
386                        if ($candidate->getB()->toBytes() != $curve->getB()->toBytes()) {
387                            break;
388                        }
389
390                        list($candidateX, $candidateY) = $candidate->getBasePoint();
391                        list($curveX, $curveY) = $curve->getBasePoint();
392                        if ($candidateX->toBytes() != $curveX->toBytes()) {
393                            break;
394                        }
395                        if ($candidateY->toBytes() != $curveY->toBytes()) {
396                            break;
397                        }
398
399                        return $returnArray ?
400                            ['namedCurve' => $testName] :
401                            ASN1::encodeDER(['namedCurve' => $testName], Maps\ECParameters::MAP);
402                    case 'Binary':
403                        if (!$candidate instanceof BinaryCurve) {
404                            break;
405                        }
406                        if ($candidate->getModulo() != $curve->getModulo()) {
407                            break;
408                        }
409                        if ($candidate->getA()->toBytes() != $curve->getA()->toBytes()) {
410                            break;
411                        }
412                        if ($candidate->getB()->toBytes() != $curve->getB()->toBytes()) {
413                            break;
414                        }
415
416                        list($candidateX, $candidateY) = $candidate->getBasePoint();
417                        list($curveX, $curveY) = $curve->getBasePoint();
418                        if ($candidateX->toBytes() != $curveX->toBytes()) {
419                            break;
420                        }
421                        if ($candidateY->toBytes() != $curveY->toBytes()) {
422                            break;
423                        }
424
425                        return $returnArray ?
426                            ['namedCurve' => $testName] :
427                            ASN1::encodeDER(['namedCurve' => $testName], Maps\ECParameters::MAP);
428                }
429            }
430        }
431
432        $order = $curve->getOrder();
433        // we could try to calculate the order thusly:
434        // https://crypto.stackexchange.com/a/27914/4520
435        // https://en.wikipedia.org/wiki/Schoof%E2%80%93Elkies%E2%80%93Atkin_algorithm
436        if (!$order) {
437            throw new \RuntimeException('Specified Curves need the order to be specified');
438        }
439        $point = $curve->getBasePoint();
440        $x = $point[0]->toBytes();
441        $y = $point[1]->toBytes();
442
443        if ($curve instanceof PrimeCurve) {
444            /*
445             * valid versions are:
446             *
447             * ecdpVer1:
448             *   - neither the curve or the base point are generated verifiably randomly.
449             * ecdpVer2:
450             *   - curve and base point are generated verifiably at random and curve.seed is present
451             * ecdpVer3:
452             *   - base point is generated verifiably at random but curve is not. curve.seed is present
453             */
454            // other (optional) parameters can be calculated using the methods discused at
455            // https://crypto.stackexchange.com/q/28947/4520
456            $data = [
457                'version' => 'ecdpVer1',
458                'fieldID' => [
459                    'fieldType' => 'prime-field',
460                    'parameters' => $curve->getModulo()
461                ],
462                'curve' => [
463                    'a' => $curve->getA()->toBytes(),
464                    'b' => $curve->getB()->toBytes()
465                ],
466                'base' => "\4" . $x . $y,
467                'order' => $order
468            ];
469
470            return $returnArray ?
471                ['specifiedCurve' => $data] :
472                ASN1::encodeDER(['specifiedCurve' => $data], Maps\ECParameters::MAP);
473        }
474        if ($curve instanceof BinaryCurve) {
475            $modulo = $curve->getModulo();
476            $basis = count($modulo);
477            $m = array_shift($modulo);
478            array_pop($modulo); // the last parameter should always be 0
479            //rsort($modulo);
480            switch ($basis) {
481                case 3:
482                    $basis = 'tpBasis';
483                    $modulo = new BigInteger($modulo[0]);
484                    break;
485                case 5:
486                    $basis = 'ppBasis';
487                    // these should be in strictly ascending order (hence the commented out rsort above)
488                    $modulo = [
489                        'k1' => new BigInteger($modulo[2]),
490                        'k2' => new BigInteger($modulo[1]),
491                        'k3' => new BigInteger($modulo[0])
492                    ];
493                    $modulo = ASN1::encodeDER($modulo, Maps\Pentanomial::MAP);
494                    $modulo = new ASN1\Element($modulo);
495            }
496            $params = ASN1::encodeDER([
497                'm' => new BigInteger($m),
498                'basis' => $basis,
499                'parameters' => $modulo
500            ], Maps\Characteristic_two::MAP);
501            $params = new ASN1\Element($params);
502            $a = ltrim($curve->getA()->toBytes(), "\0");
503            if (!strlen($a)) {
504                $a = "\0";
505            }
506            $b = ltrim($curve->getB()->toBytes(), "\0");
507            if (!strlen($b)) {
508                $b = "\0";
509            }
510            $data = [
511                'version' => 'ecdpVer1',
512                'fieldID' => [
513                    'fieldType' => 'characteristic-two-field',
514                    'parameters' => $params
515                ],
516                'curve' => [
517                    'a' => $a,
518                    'b' => $b
519                ],
520                'base' => "\4" . $x . $y,
521                'order' => $order
522            ];
523
524            return $returnArray ?
525                ['specifiedCurve' => $data] :
526                ASN1::encodeDER(['specifiedCurve' => $data], Maps\ECParameters::MAP);
527        }
528
529        throw new UnsupportedCurveException('Curve cannot be serialized');
530    }
531
532    /**
533     * Use Specified Curve
534     *
535     * A specified curve has all the coefficients, the base points, etc, explicitely included.
536     * A specified curve is a more verbose way of representing a curve
537     */
538    public static function useSpecifiedCurve()
539    {
540        self::$useNamedCurves = false;
541    }
542
543    /**
544     * Use Named Curve
545     *
546     * A named curve does not include any parameters. It is up to the EC parameters to
547     * know what the coefficients, the base points, etc, are from the name of the curve.
548     * A named curve is a more concise way of representing a curve
549     */
550    public static function useNamedCurve()
551    {
552        self::$useNamedCurves = true;
553    }
554}
555