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