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.  * Ed25519
  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 Ed25519 extends TwistedEdwards
  23. {
  24.     const HASH = 'sha512';
  25.     /*
  26.       Per https://tools.ietf.org/html/rfc8032#page-6 EdDSA has several parameters, one of which is b:
  27.  
  28.       2.   An integer b with 2^(b-1) > p.  EdDSA public keys have exactly b
  29.            bits, and EdDSA signatures have exactly 2*b bits.  b is
  30.            recommended to be a multiple of 8, so public key and signature
  31.            lengths are an integral number of octets.
  32.  
  33.       SIZE corresponds to b
  34.     */
  35.     const SIZE = 32;
  36.  
  37.     public function __construct()
  38.     {
  39.         // 2^255 - 19
  40.         $this->setModulo(new BigInteger('7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED', 16));
  41.         $this->setCoefficients(
  42.             // -1
  43.             new BigInteger('7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC', 16), // a
  44.             // -121665/121666
  45.             new BigInteger('52036CEE2B6FFE738CC740797779E89800700A4D4141D8AB75EB4DCA135978A3', 16)  // d
  46.         );
  47.         $this->setBasePoint(
  48.             new BigInteger('216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A', 16),
  49.             new BigInteger('6666666666666666666666666666666666666666666666666666666666666658', 16)
  50.         );
  51.         $this->setOrder(new BigInteger('1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED', 16));
  52.         // algorithm 14.47 from http://cacr.uwaterloo.ca/hac/about/chap14.pdf#page=16
  53.         /*
  54.         $this->setReduction(function($x) {
  55.             $parts = $x->bitwise_split(255);
  56.             $className = $this->className;
  57.  
  58.             if (count($parts) > 2) {
  59.                 list(, $r) = $x->divide($className::$modulo);
  60.                 return $r;
  61.             }
  62.  
  63.             $zero = new BigInteger();
  64.             $c = new BigInteger(19);
  65.  
  66.             switch (count($parts)) {
  67.                 case 2:
  68.                     list($qi, $ri) = $parts;
  69.                     break;
  70.                 case 1:
  71.                     $qi = $zero;
  72.                     list($ri) = $parts;
  73.                     break;
  74.                 case 0:
  75.                     return $zero;
  76.             }
  77.             $r = $ri;
  78.  
  79.             while ($qi->compare($zero) > 0) {
  80.                 $temp = $qi->multiply($c)->bitwise_split(255);
  81.                 if (count($temp) == 2) {
  82.                     list($qi, $ri) = $temp;
  83.                 } else {
  84.                     $qi = $zero;
  85.                     list($ri) = $temp;
  86.                 }
  87.                 $r = $r->add($ri);
  88.             }
  89.  
  90.             while ($r->compare($className::$modulo) > 0) {
  91.                 $r = $r->subtract($className::$modulo);
  92.             }
  93.             return $r;
  94.         });
  95.         */
  96.     }
  97.  
  98.     /**
  99.      * Recover X from Y
  100.      *
  101.      * Implements steps 2-4 at https://tools.ietf.org/html/rfc8032#section-5.1.3
  102.      *
  103.      * Used by EC\Keys\Common.php
  104.      *
  105.      * @param BigInteger $y
  106.      * @param boolean $sign
  107.      * @return object[]
  108.      */
  109.     public function recoverX(BigInteger $y, $sign)
  110.     {
  111.         $y = $this->factory->newInteger($y);
  112.  
  113.         $y2 = $y->multiply($y);
  114.         $u = $y2->subtract($this->one);
  115.         $v = $this->d->multiply($y2)->add($this->one);
  116.         $x2 = $u->divide($v);
  117.         if ($x2->equals($this->zero)) {
  118.             if ($sign) {
  119.                 throw new \RuntimeException('Unable to recover X coordinate (x2 = 0)');
  120.             }
  121.             return clone $this->zero;
  122.         }
  123.         // find the square root
  124.         /* we don't do $x2->squareRoot() because, quoting from
  125.            https://tools.ietf.org/html/rfc8032#section-5.1.1:
  126.  
  127.            "For point decoding or "decompression", square roots modulo p are
  128.             needed.  They can be computed using the Tonelli-Shanks algorithm or
  129.             the special case for p = 5 (mod 8).  To find a square root of a,
  130.             first compute the candidate root x = a^((p+3)/8) (mod p)."
  131.          */
  132.         $exp = $this->getModulo()->add(new BigInteger(3));
  133.         $exp = $exp->bitwise_rightShift(3);
  134.         $x = $x2->pow($exp);
  135.  
  136.         // If v x^2 = -u (mod p), set x <-- x * 2^((p-1)/4), which is a square root.
  137.         if (!$x->multiply($x)->subtract($x2)->equals($this->zero)) {
  138.             $temp = $this->getModulo()->subtract(new BigInteger(1));
  139.             $temp = $temp->bitwise_rightShift(2);
  140.             $temp = $this->two->pow($temp);
  141.             $x = $x->multiply($temp);
  142.             if (!$x->multiply($x)->subtract($x2)->equals($this->zero)) {
  143.                 throw new \RuntimeException('Unable to recover X coordinate');
  144.             }
  145.         }
  146.         if ($x->isOdd() != $sign) {
  147.             $x = $x->negate();
  148.         }
  149.  
  150.         return [$x, $y];
  151.     }
  152.  
  153.     /**
  154.      * Extract Secret Scalar
  155.      *
  156.      * Implements steps 1-3 at https://tools.ietf.org/html/rfc8032#section-5.1.5
  157.      *
  158.      * Used by the various key handlers
  159.      *
  160.      * @param string $str
  161.      * @return \phpseclib3\Math\PrimeField\Integer
  162.      */
  163.     public function extractSecret($str)
  164.     {
  165.         if (strlen($str) != 32) {
  166.             throw new \LengthException('Private Key should be 32-bytes long');
  167.         }
  168.         // 1.  Hash the 32-byte private key using SHA-512, storing the digest in
  169.         //     a 64-octet large buffer, denoted h.  Only the lower 32 bytes are
  170.         //     used for generating the public key.
  171.         $hash = new Hash('sha512');
  172.         $h = $hash->hash($str);
  173.         $h = substr($h, 0, 32);
  174.         // 2.  Prune the buffer: The lowest three bits of the first octet are
  175.         //     cleared, the highest bit of the last octet is cleared, and the
  176.         //     second highest bit of the last octet is set.
  177.         $h[0] = $h[0] & chr(0xF8);
  178.         $h = strrev($h);
  179.         $h[0] = ($h[0] & chr(0x3F)) | chr(0x40);
  180.         // 3.  Interpret the buffer as the little-endian integer, forming a
  181.         //     secret scalar s.
  182.         $dA = new BigInteger($h, 256);
  183.  
  184.         $dA->secret = $str;
  185.         return $dA;
  186.     }
  187.  
  188.     /**
  189.      * Encode a point as a string
  190.      *
  191.      * @param array $point
  192.      * @return string
  193.      */
  194.     public function encodePoint($point)
  195.     {
  196.         list($x, $y) = $point;
  197.         $y = $y->toBytes();
  198.         $y[0] = $y[0] & chr(0x7F);
  199.         if ($x->isOdd()) {
  200.             $y[0] = $y[0] | chr(0x80);
  201.         }
  202.         $y = strrev($y);
  203.  
  204.         return $y;
  205.     }
  206.  
  207.     /**
  208.      * Creates a random scalar multiplier
  209.      *
  210.      * @return \phpseclib3\Math\PrimeField\Integer
  211.      */
  212.     public function createRandomMultiplier()
  213.     {
  214.         return $this->extractSecret(Random::string(32));
  215.     }
  216.  
  217.     /**
  218.      * Converts an affine point to an extended homogeneous coordinate
  219.      *
  220.      * From https://tools.ietf.org/html/rfc8032#section-5.1.4 :
  221.      *
  222.      * A point (x,y) is represented in extended homogeneous coordinates (X, Y, Z, T),
  223.      * with x = X/Z, y = Y/Z, x * y = T/Z.
  224.      *
  225.      * @return \phpseclib3\Math\PrimeField\Integer[]
  226.      */
  227.     public function convertToInternal(array $p)
  228.     {
  229.         if (empty($p)) {
  230.             return [clone $this->zero, clone $this->one, clone $this->one, clone $this->zero];
  231.         }
  232.  
  233.         if (isset($p[2])) {
  234.             return $p;
  235.         }
  236.  
  237.         $p[2] = clone $this->one;
  238.         $p[3] = $p[0]->multiply($p[1]);
  239.  
  240.         return $p;
  241.     }
  242.  
  243.     /**
  244.      * Doubles a point on a curve
  245.      *
  246.      * @return FiniteField[]
  247.      */
  248.     public function doublePoint(array $p)
  249.     {
  250.         if (!isset($this->factory)) {
  251.             throw new \RuntimeException('setModulo needs to be called before this method');
  252.         }
  253.  
  254.         if (!count($p)) {
  255.             return [];
  256.         }
  257.  
  258.         if (!isset($p[2])) {
  259.             throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa');
  260.         }
  261.  
  262.         // from https://tools.ietf.org/html/rfc8032#page-12
  263.  
  264.         list($x1, $y1, $z1, $t1) = $p;
  265.  
  266.         $a = $x1->multiply($x1);
  267.         $b = $y1->multiply($y1);
  268.         $c = $this->two->multiply($z1)->multiply($z1);
  269.         $h = $a->add($b);
  270.         $temp = $x1->add($y1);
  271.         $e = $h->subtract($temp->multiply($temp));
  272.         $g = $a->subtract($b);
  273.         $f = $c->add($g);
  274.  
  275.         $x3 = $e->multiply($f);
  276.         $y3 = $g->multiply($h);
  277.         $t3 = $e->multiply($h);
  278.         $z3 = $f->multiply($g);
  279.  
  280.         return [$x3, $y3, $z3, $t3];
  281.     }
  282.  
  283.     /**
  284.      * Adds two points on the curve
  285.      *
  286.      * @return FiniteField[]
  287.      */
  288.     public function addPoint(array $p, array $q)
  289.     {
  290.         if (!isset($this->factory)) {
  291.             throw new \RuntimeException('setModulo needs to be called before this method');
  292.         }
  293.  
  294.         if (!count($p) || !count($q)) {
  295.             if (count($q)) {
  296.                 return $q;
  297.             }
  298.             if (count($p)) {
  299.                 return $p;
  300.             }
  301.             return [];
  302.         }
  303.  
  304.         if (!isset($p[2]) || !isset($q[2])) {
  305.             throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa');
  306.         }
  307.  
  308.         if ($p[0]->equals($q[0])) {
  309.             return !$p[1]->equals($q[1]) ? [] : $this->doublePoint($p);
  310.         }
  311.  
  312.         // from https://tools.ietf.org/html/rfc8032#page-12
  313.  
  314.         list($x1, $y1, $z1, $t1) = $p;
  315.         list($x2, $y2, $z2, $t2) = $q;
  316.  
  317.         $a = $y1->subtract($x1)->multiply($y2->subtract($x2));
  318.         $b = $y1->add($x1)->multiply($y2->add($x2));
  319.         $c = $t1->multiply($this->two)->multiply($this->d)->multiply($t2);
  320.         $d = $z1->multiply($this->two)->multiply($z2);
  321.         $e = $b->subtract($a);
  322.         $f = $d->subtract($c);
  323.         $g = $d->add($c);
  324.         $h = $b->add($a);
  325.  
  326.         $x3 = $e->multiply($f);
  327.         $y3 = $g->multiply($h);
  328.         $t3 = $e->multiply($h);
  329.         $z3 = $f->multiply($g);
  330.  
  331.         return [$x3, $y3, $z3, $t3];
  332.     }
  333. }
  334.