[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * Ed25519
   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 Ed25519 extends TwistedEdwards
  21  {
  22      const HASH = 'sha512';
  23      /*
  24        Per https://tools.ietf.org/html/rfc8032#page-6 EdDSA has several parameters, one of which is b:
  25  
  26        2.   An integer b with 2^(b-1) > p.  EdDSA public keys have exactly b
  27             bits, and EdDSA signatures have exactly 2*b bits.  b is
  28             recommended to be a multiple of 8, so public key and signature
  29             lengths are an integral number of octets.
  30  
  31        SIZE corresponds to b
  32      */
  33      const SIZE = 32;
  34  
  35      public function __construct()
  36      {
  37          // 2^255 - 19
  38          $this->setModulo(new BigInteger('7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED', 16));
  39          $this->setCoefficients(
  40              // -1
  41              new BigInteger('7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC', 16), // a
  42              // -121665/121666
  43              new BigInteger('52036CEE2B6FFE738CC740797779E89800700A4D4141D8AB75EB4DCA135978A3', 16)  // d
  44          );
  45          $this->setBasePoint(
  46              new BigInteger('216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A', 16),
  47              new BigInteger('6666666666666666666666666666666666666666666666666666666666666658', 16)
  48          );
  49          $this->setOrder(new BigInteger('1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED', 16));
  50          // algorithm 14.47 from http://cacr.uwaterloo.ca/hac/about/chap14.pdf#page=16
  51          /*
  52          $this->setReduction(function($x) {
  53              $parts = $x->bitwise_split(255);
  54              $className = $this->className;
  55  
  56              if (count($parts) > 2) {
  57                  list(, $r) = $x->divide($className::$modulo);
  58                  return $r;
  59              }
  60  
  61              $zero = new BigInteger();
  62              $c = new BigInteger(19);
  63  
  64              switch (count($parts)) {
  65                  case 2:
  66                      list($qi, $ri) = $parts;
  67                      break;
  68                  case 1:
  69                      $qi = $zero;
  70                      list($ri) = $parts;
  71                      break;
  72                  case 0:
  73                      return $zero;
  74              }
  75              $r = $ri;
  76  
  77              while ($qi->compare($zero) > 0) {
  78                  $temp = $qi->multiply($c)->bitwise_split(255);
  79                  if (count($temp) == 2) {
  80                      list($qi, $ri) = $temp;
  81                  } else {
  82                      $qi = $zero;
  83                      list($ri) = $temp;
  84                  }
  85                  $r = $r->add($ri);
  86              }
  87  
  88              while ($r->compare($className::$modulo) > 0) {
  89                  $r = $r->subtract($className::$modulo);
  90              }
  91              return $r;
  92          });
  93          */
  94      }
  95  
  96      /**
  97       * Recover X from Y
  98       *
  99       * Implements steps 2-4 at https://tools.ietf.org/html/rfc8032#section-5.1.3
 100       *
 101       * Used by EC\Keys\Common.php
 102       *
 103       * @param BigInteger $y
 104       * @param boolean $sign
 105       * @return object[]
 106       */
 107      public function recoverX(BigInteger $y, $sign)
 108      {
 109          $y = $this->factory->newInteger($y);
 110  
 111          $y2 = $y->multiply($y);
 112          $u = $y2->subtract($this->one);
 113          $v = $this->d->multiply($y2)->add($this->one);
 114          $x2 = $u->divide($v);
 115          if ($x2->equals($this->zero)) {
 116              if ($sign) {
 117                  throw new \RuntimeException('Unable to recover X coordinate (x2 = 0)');
 118              }
 119              return clone $this->zero;
 120          }
 121          // find the square root
 122          /* we don't do $x2->squareRoot() because, quoting from
 123             https://tools.ietf.org/html/rfc8032#section-5.1.1:
 124  
 125             "For point decoding or "decompression", square roots modulo p are
 126              needed.  They can be computed using the Tonelli-Shanks algorithm or
 127              the special case for p = 5 (mod 8).  To find a square root of a,
 128              first compute the candidate root x = a^((p+3)/8) (mod p)."
 129           */
 130          $exp = $this->getModulo()->add(new BigInteger(3));
 131          $exp = $exp->bitwise_rightShift(3);
 132          $x = $x2->pow($exp);
 133  
 134          // If v x^2 = -u (mod p), set x <-- x * 2^((p-1)/4), which is a square root.
 135          if (!$x->multiply($x)->subtract($x2)->equals($this->zero)) {
 136              $temp = $this->getModulo()->subtract(new BigInteger(1));
 137              $temp = $temp->bitwise_rightShift(2);
 138              $temp = $this->two->pow($temp);
 139              $x = $x->multiply($temp);
 140              if (!$x->multiply($x)->subtract($x2)->equals($this->zero)) {
 141                  throw new \RuntimeException('Unable to recover X coordinate');
 142              }
 143          }
 144          if ($x->isOdd() != $sign) {
 145              $x = $x->negate();
 146          }
 147  
 148          return [$x, $y];
 149      }
 150  
 151      /**
 152       * Extract Secret Scalar
 153       *
 154       * Implements steps 1-3 at https://tools.ietf.org/html/rfc8032#section-5.1.5
 155       *
 156       * Used by the various key handlers
 157       *
 158       * @param string $str
 159       * @return array
 160       */
 161      public function extractSecret($str)
 162      {
 163          if (strlen($str) != 32) {
 164              throw new \LengthException('Private Key should be 32-bytes long');
 165          }
 166          // 1.  Hash the 32-byte private key using SHA-512, storing the digest in
 167          //     a 64-octet large buffer, denoted h.  Only the lower 32 bytes are
 168          //     used for generating the public key.
 169          $hash = new Hash('sha512');
 170          $h = $hash->hash($str);
 171          $h = substr($h, 0, 32);
 172          // 2.  Prune the buffer: The lowest three bits of the first octet are
 173          //     cleared, the highest bit of the last octet is cleared, and the
 174          //     second highest bit of the last octet is set.
 175          $h[0] = $h[0] & chr(0xF8);
 176          $h = strrev($h);
 177          $h[0] = ($h[0] & chr(0x3F)) | chr(0x40);
 178          // 3.  Interpret the buffer as the little-endian integer, forming a
 179          //     secret scalar s.
 180          $dA = new BigInteger($h, 256);
 181  
 182          return [
 183              'dA' => $dA,
 184              'secret' => $str
 185          ];
 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))['dA'];
 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  }