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