Subversion Repositories oidplus

Rev

Rev 874 | Blame | Compare with Previous | Last modification | View Log | RSS feed

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