[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * Curves over y^2 = x^3 + a*x + x
   5   *
   6   * Technically, a Montgomery curve has a coefficient for y^2 but for Curve25519 and Curve448 that
   7   * coefficient is 1.
   8   *
   9   * Curve25519 and Curve448 do not make use of the y coordinate, which makes it unsuitable for use
  10   * with ECDSA / EdDSA. A few other differences between Curve25519 and Ed25519 are discussed at
  11   * https://crypto.stackexchange.com/a/43058/4520
  12   *
  13   * More info:
  14   *
  15   * https://en.wikipedia.org/wiki/Montgomery_curve
  16   *
  17   * PHP version 5 and 7
  18   *
  19   * @category  Crypt
  20   * @package   EC
  21   * @author    Jim Wigginton <[email protected]>
  22   * @copyright 2019 Jim Wigginton
  23   * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  24   * @link      http://pear.php.net/package/Math_BigInteger
  25   */
  26  
  27  namespace phpseclib3\Crypt\EC\BaseCurves;
  28  
  29  use phpseclib3\Crypt\EC\Curves\Curve25519;
  30  use phpseclib3\Math\BigInteger;
  31  use phpseclib3\Math\PrimeField;
  32  use phpseclib3\Math\PrimeField\Integer as PrimeInteger;
  33  
  34  /**
  35   * Curves over y^2 = x^3 + a*x + x
  36   *
  37   * @package EC
  38   * @author  Jim Wigginton <[email protected]>
  39   * @access  public
  40   */
  41  class Montgomery extends Base
  42  {
  43      /**
  44       * Prime Field Integer factory
  45       *
  46       * @var \phpseclib3\Math\PrimeField
  47       */
  48      protected $factory;
  49  
  50      /**
  51       * Cofficient for x
  52       *
  53       * @var object
  54       */
  55      protected $a;
  56  
  57      /**
  58       * Constant used for point doubling
  59       *
  60       * @var object
  61       */
  62      protected $a24;
  63  
  64      /**
  65       * The Number Zero
  66       *
  67       * @var object
  68       */
  69      protected $zero;
  70  
  71      /**
  72       * The Number One
  73       *
  74       * @var object
  75       */
  76      protected $one;
  77  
  78      /**
  79       * Base Point
  80       *
  81       * @var object
  82       */
  83      protected $p;
  84  
  85      /**
  86       * The modulo
  87       *
  88       * @var BigInteger
  89       */
  90      protected $modulo;
  91  
  92      /**
  93       * The Order
  94       *
  95       * @var BigInteger
  96       */
  97      protected $order;
  98  
  99      /**
 100       * Sets the modulo
 101       */
 102      public function setModulo(BigInteger $modulo)
 103      {
 104          $this->modulo = $modulo;
 105          $this->factory = new PrimeField($modulo);
 106          $this->zero = $this->factory->newInteger(new BigInteger());
 107          $this->one = $this->factory->newInteger(new BigInteger(1));
 108      }
 109  
 110      /**
 111       * Set coefficients a
 112       */
 113      public function setCoefficients(BigInteger $a)
 114      {
 115          if (!isset($this->factory)) {
 116              throw new \RuntimeException('setModulo needs to be called before this method');
 117          }
 118          $this->a = $this->factory->newInteger($a);
 119          $two = $this->factory->newInteger(new BigInteger(2));
 120          $four = $this->factory->newInteger(new BigInteger(4));
 121          $this->a24 = $this->a->subtract($two)->divide($four);
 122      }
 123  
 124      /**
 125       * Set x and y coordinates for the base point
 126       *
 127       * @param BigInteger|PrimeInteger $x
 128       * @param BigInteger|PrimeInteger $y
 129       * @return PrimeInteger[]
 130       */
 131      public function setBasePoint($x, $y)
 132      {
 133          switch (true) {
 134              case !$x instanceof BigInteger && !$x instanceof PrimeInteger:
 135                  throw new \UnexpectedValueException('Argument 1 passed to Prime::setBasePoint() must be an instance of either BigInteger or PrimeField\Integer');
 136              case !$y instanceof BigInteger && !$y instanceof PrimeInteger:
 137                  throw new \UnexpectedValueException('Argument 2 passed to Prime::setBasePoint() must be an instance of either BigInteger or PrimeField\Integer');
 138          }
 139          if (!isset($this->factory)) {
 140              throw new \RuntimeException('setModulo needs to be called before this method');
 141          }
 142          $this->p = [
 143              $x instanceof BigInteger ? $this->factory->newInteger($x) : $x,
 144              $y instanceof BigInteger ? $this->factory->newInteger($y) : $y
 145          ];
 146      }
 147  
 148      /**
 149       * Retrieve the base point as an array
 150       *
 151       * @return array
 152       */
 153      public function getBasePoint()
 154      {
 155          if (!isset($this->factory)) {
 156              throw new \RuntimeException('setModulo needs to be called before this method');
 157          }
 158          /*
 159          if (!isset($this->p)) {
 160              throw new \RuntimeException('setBasePoint needs to be called before this method');
 161          }
 162          */
 163          return $this->p;
 164      }
 165  
 166      /**
 167       * Doubles and adds a point on a curve
 168       *
 169       * See https://tools.ietf.org/html/draft-ietf-tls-curve25519-01#appendix-A.1.3
 170       *
 171       * @return FiniteField[][]
 172       */
 173      private function doubleAndAddPoint(array $p, array $q, PrimeInteger $x1)
 174      {
 175          if (!isset($this->factory)) {
 176              throw new \RuntimeException('setModulo needs to be called before this method');
 177          }
 178  
 179          if (!count($p) || !count($q)) {
 180              return [];
 181          }
 182  
 183          if (!isset($p[1])) {
 184              throw new \RuntimeException('Affine coordinates need to be manually converted to XZ coordinates');
 185          }
 186  
 187          list($x2, $z2) = $p;
 188          list($x3, $z3) = $q;
 189  
 190          $a = $x2->add($z2);
 191          $aa = $a->multiply($a);
 192          $b = $x2->subtract($z2);
 193          $bb = $b->multiply($b);
 194          $e = $aa->subtract($bb);
 195          $c = $x3->add($z3);
 196          $d = $x3->subtract($z3);
 197          $da = $d->multiply($a);
 198          $cb = $c->multiply($b);
 199          $temp = $da->add($cb);
 200          $x5 = $temp->multiply($temp);
 201          $temp = $da->subtract($cb);
 202          $z5 = $x1->multiply($temp->multiply($temp));
 203          $x4 = $aa->multiply($bb);
 204          $temp = static::class == Curve25519::class ? $bb : $aa;
 205          $z4 = $e->multiply($temp->add($this->a24->multiply($e)));
 206  
 207          return [
 208              [$x4, $z4],
 209              [$x5, $z5]
 210          ];
 211      }
 212  
 213      /**
 214       * Multiply a point on the curve by a scalar
 215       *
 216       * Uses the montgomery ladder technique as described here:
 217       *
 218       * https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Montgomery_ladder
 219       * https://github.com/phpecc/phpecc/issues/16#issuecomment-59176772
 220       *
 221       * @return array
 222       */
 223      public function multiplyPoint(array $p, BigInteger $d)
 224      {
 225          $p1 = [$this->one, $this->zero];
 226          $alreadyInternal = isset($x[1]);
 227          $p2 = $this->convertToInternal($p);
 228          $x = $p[0];
 229  
 230          $b = $d->toBits();
 231          $b = str_pad($b, 256, '0', STR_PAD_LEFT);
 232          for ($i = 0; $i < strlen($b); $i++) {
 233              $b_i = (int) $b[$i];
 234              if ($b_i) {
 235                  list($p2, $p1) = $this->doubleAndAddPoint($p2, $p1, $x);
 236              } else {
 237                  list($p1, $p2) = $this->doubleAndAddPoint($p1, $p2, $x);
 238              }
 239          }
 240  
 241          return $alreadyInternal ? $p1 : $this->convertToAffine($p1);
 242      }
 243  
 244      /**
 245       * Converts an affine point to an XZ coordinate
 246       *
 247       * From https://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html
 248       *
 249       * XZ coordinates represent x y as X Z satsfying the following equations:
 250       *
 251       *   x=X/Z
 252       *
 253       * @return \phpseclib3\Math\PrimeField\Integer[]
 254       */
 255      public function convertToInternal(array $p)
 256      {
 257          if (empty($p)) {
 258              return [clone $this->zero, clone $this->one];
 259          }
 260  
 261          if (isset($p[1])) {
 262              return $p;
 263          }
 264  
 265          $p[1] = clone $this->one;
 266  
 267          return $p;
 268      }
 269  
 270      /**
 271       * Returns the affine point
 272       *
 273       * @return \phpseclib3\Math\PrimeField\Integer[]
 274       */
 275      public function convertToAffine(array $p)
 276      {
 277          if (!isset($p[1])) {
 278              return $p;
 279          }
 280          list($x, $z) = $p;
 281          return [$x->divide($z)];
 282      }
 283  }