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