[Summary view] [Print] [Text view]

   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  }