[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * Ed448
   5   *
   6   * PHP version 5 and 7
   7   *
   8   * @category  Crypt
   9   * @package   EC
  10   * @author    Jim Wigginton <[email protected]>
  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  }