Subversion Repositories oidplus

Rev

Rev 846 | Go to most recent revision | 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.  * @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.  
  15. namespace phpseclib3\Crypt\EC\Curves;
  16.  
  17. use phpseclib3\Crypt\EC\BaseCurves\TwistedEdwards;
  18. use phpseclib3\Crypt\Hash;
  19. use phpseclib3\Crypt\Random;
  20. use phpseclib3\Math\BigInteger;
  21.  
  22. class 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.