[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * Curves over y^2 + x*y = x^3 + a*x^2 + b
   5   *
   6   * These are curves used in SEC 2 over prime fields: http://www.secg.org/SEC2-Ver-1.0.pdf
   7   * The curve is a weierstrass curve with a[3] and a[2] set to 0.
   8   *
   9   * Uses Jacobian Coordinates for speed if able:
  10   *
  11   * https://en.wikipedia.org/wiki/Jacobian_curve
  12   * https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates
  13   *
  14   * PHP version 5 and 7
  15   *
  16   * @category  Crypt
  17   * @package   EC
  18   * @author    Jim Wigginton <[email protected]>
  19   * @copyright 2017 Jim Wigginton
  20   * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  21   * @link      http://pear.php.net/package/Math_BigInteger
  22   */
  23  
  24  namespace phpseclib3\Crypt\EC\BaseCurves;
  25  
  26  use phpseclib3\Math\BigInteger;
  27  use phpseclib3\Math\BinaryField;
  28  use phpseclib3\Math\BinaryField\Integer as BinaryInteger;
  29  
  30  /**
  31   * Curves over y^2 + x*y = x^3 + a*x^2 + b
  32   *
  33   * @package Binary
  34   * @author  Jim Wigginton <[email protected]>
  35   * @access  public
  36   */
  37  class Binary extends Base
  38  {
  39      /**
  40       * Binary Field Integer factory
  41       *
  42       * @var \phpseclib3\Math\BinaryField
  43       */
  44      protected $factory;
  45  
  46      /**
  47       * Cofficient for x^1
  48       *
  49       * @var object
  50       */
  51      protected $a;
  52  
  53      /**
  54       * Cofficient for x^0
  55       *
  56       * @var object
  57       */
  58      protected $b;
  59  
  60      /**
  61       * Base Point
  62       *
  63       * @var object
  64       */
  65      protected $p;
  66  
  67      /**
  68       * The number one over the specified finite field
  69       *
  70       * @var object
  71       */
  72      protected $one;
  73  
  74      /**
  75       * The modulo
  76       *
  77       * @var BigInteger
  78       */
  79      protected $modulo;
  80  
  81      /**
  82       * The Order
  83       *
  84       * @var BigInteger
  85       */
  86      protected $order;
  87  
  88      /**
  89       * Sets the modulo
  90       */
  91      public function setModulo(...$modulo)
  92      {
  93          $this->modulo = $modulo;
  94          $this->factory = new BinaryField(...$modulo);
  95  
  96          $this->one = $this->factory->newInteger("\1");
  97      }
  98  
  99      /**
 100       * Set coefficients a and b
 101       *
 102       * @param string $a
 103       * @param string $b
 104       */
 105      public function setCoefficients($a, $b)
 106      {
 107          if (!isset($this->factory)) {
 108              throw new \RuntimeException('setModulo needs to be called before this method');
 109          }
 110          $this->a = $this->factory->newInteger(pack('H*', $a));
 111          $this->b = $this->factory->newInteger(pack('H*', $b));
 112      }
 113  
 114      /**
 115       * Set x and y coordinates for the base point
 116       *
 117       * @param string|BinaryInteger $x
 118       * @param string|BinaryInteger $y
 119       */
 120      public function setBasePoint($x, $y)
 121      {
 122          switch (true) {
 123              case !is_string($x) && !$x instanceof BinaryInteger:
 124                  throw new \UnexpectedValueException('Argument 1 passed to Binary::setBasePoint() must be a string or an instance of BinaryField\Integer');
 125              case !is_string($y) && !$y instanceof BinaryInteger:
 126                  throw new \UnexpectedValueException('Argument 2 passed to Binary::setBasePoint() must be a string or an instance of BinaryField\Integer');
 127          }
 128          if (!isset($this->factory)) {
 129              throw new \RuntimeException('setModulo needs to be called before this method');
 130          }
 131          $this->p = [
 132              is_string($x) ? $this->factory->newInteger(pack('H*', $x)) : $x,
 133              is_string($y) ? $this->factory->newInteger(pack('H*', $y)) : $y
 134          ];
 135      }
 136  
 137      /**
 138       * Retrieve the base point as an array
 139       *
 140       * @return array
 141       */
 142      public function getBasePoint()
 143      {
 144          if (!isset($this->factory)) {
 145              throw new \RuntimeException('setModulo needs to be called before this method');
 146          }
 147          /*
 148          if (!isset($this->p)) {
 149              throw new \RuntimeException('setBasePoint needs to be called before this method');
 150          }
 151          */
 152          return $this->p;
 153      }
 154  
 155      /**
 156       * Adds two points on the curve
 157       *
 158       * @return FiniteField[]
 159       */
 160      public function addPoint(array $p, array $q)
 161      {
 162          if (!isset($this->factory)) {
 163              throw new \RuntimeException('setModulo needs to be called before this method');
 164          }
 165  
 166          if (!count($p) || !count($q)) {
 167              if (count($q)) {
 168                  return $q;
 169              }
 170              if (count($p)) {
 171                  return $p;
 172              }
 173              return [];
 174          }
 175  
 176          if (!isset($p[2]) || !isset($q[2])) {
 177              throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa');
 178          }
 179  
 180          if ($p[0]->equals($q[0])) {
 181              return !$p[1]->equals($q[1]) ? [] : $this->doublePoint($p);
 182          }
 183  
 184          // formulas from http://hyperelliptic.org/EFD/g12o/auto-shortw-jacobian.html
 185  
 186          list($x1, $y1, $z1) = $p;
 187          list($x2, $y2, $z2) = $q;
 188  
 189          $o1 = $z1->multiply($z1);
 190          $b = $x2->multiply($o1);
 191  
 192          if ($z2->equals($this->one)) {
 193              $d = $y2->multiply($o1)->multiply($z1);
 194              $e = $x1->add($b);
 195              $f = $y1->add($d);
 196              $z3 = $e->multiply($z1);
 197              $h = $f->multiply($x2)->add($z3->multiply($y2));
 198              $i = $f->add($z3);
 199              $g = $z3->multiply($z3);
 200              $p1 = $this->a->multiply($g);
 201              $p2 = $f->multiply($i);
 202              $p3 = $e->multiply($e)->multiply($e);
 203              $x3 = $p1->add($p2)->add($p3);
 204              $y3 = $i->multiply($x3)->add($g->multiply($h));
 205  
 206              return [$x3, $y3, $z3];
 207          }
 208  
 209          $o2 = $z2->multiply($z2);
 210          $a = $x1->multiply($o2);
 211          $c = $y1->multiply($o2)->multiply($z2);
 212          $d = $y2->multiply($o1)->multiply($z1);
 213          $e = $a->add($b);
 214          $f = $c->add($d);
 215          $g = $e->multiply($z1);
 216          $h = $f->multiply($x2)->add($g->multiply($y2));
 217          $z3 = $g->multiply($z2);
 218          $i = $f->add($z3);
 219          $p1 = $this->a->multiply($z3->multiply($z3));
 220          $p2 = $f->multiply($i);
 221          $p3 = $e->multiply($e)->multiply($e);
 222          $x3 = $p1->add($p2)->add($p3);
 223          $y3 = $i->multiply($x3)->add($g->multiply($g)->multiply($h));
 224  
 225          return [$x3, $y3, $z3];
 226      }
 227  
 228      /**
 229       * Doubles a point on a curve
 230       *
 231       * @return FiniteField[]
 232       */
 233      public function doublePoint(array $p)
 234      {
 235          if (!isset($this->factory)) {
 236              throw new \RuntimeException('setModulo needs to be called before this method');
 237          }
 238  
 239          if (!count($p)) {
 240              return [];
 241          }
 242  
 243          if (!isset($p[2])) {
 244              throw new \RuntimeException('Affine coordinates need to be manually converted to "Jacobi" coordinates or vice versa');
 245          }
 246  
 247          // formulas from http://hyperelliptic.org/EFD/g12o/auto-shortw-jacobian.html
 248  
 249          list($x1, $y1, $z1) = $p;
 250  
 251          $a = $x1->multiply($x1);
 252          $b = $a->multiply($a);
 253  
 254          if ($z1->equals($this->one)) {
 255              $x3 = $b->add($this->b);
 256              $z3 = clone $x1;
 257              $p1 = $a->add($y1)->add($z3)->multiply($this->b);
 258              $p2 = $a->add($y1)->multiply($b);
 259              $y3 = $p1->add($p2);
 260  
 261              return [$x3, $y3, $z3];
 262          }
 263  
 264          $c = $z1->multiply($z1);
 265          $d = $c->multiply($c);
 266          $x3 = $b->add($this->b->multiply($d->multiply($d)));
 267          $z3 = $x1->multiply($c);
 268          $p1 = $b->multiply($z3);
 269          $p2 = $a->add($y1->multiply($z1))->add($z3)->multiply($x3);
 270          $y3 = $p1->add($p2);
 271  
 272          return [$x3, $y3, $z3];
 273      }
 274  
 275      /**
 276       * Returns the X coordinate and the derived Y coordinate
 277       *
 278       * Not supported because it is covered by patents.
 279       * Quoting https://www.openssl.org/docs/man1.1.0/apps/ecparam.html ,
 280       *
 281       * "Due to patent issues the compressed option is disabled by default for binary curves
 282       *  and can be enabled by defining the preprocessor macro OPENSSL_EC_BIN_PT_COMP at
 283       *  compile time."
 284       *
 285       * @return array
 286       */
 287      public function derivePoint($m)
 288      {
 289          throw new \RuntimeException('Point compression on binary finite field elliptic curves is not supported');
 290      }
 291  
 292      /**
 293       * Tests whether or not the x / y values satisfy the equation
 294       *
 295       * @return boolean
 296       */
 297      public function verifyPoint(array $p)
 298      {
 299          list($x, $y) = $p;
 300          $lhs = $y->multiply($y);
 301          $lhs = $lhs->add($x->multiply($y));
 302          $x2 = $x->multiply($x);
 303          $x3 = $x2->multiply($x);
 304          $rhs = $x3->add($this->a->multiply($x2))->add($this->b);
 305  
 306          return $lhs->equals($rhs);
 307      }
 308  
 309      /**
 310       * Returns the modulo
 311       *
 312       * @return \phpseclib3\Math\BigInteger
 313       */
 314      public function getModulo()
 315      {
 316          return $this->modulo;
 317      }
 318  
 319      /**
 320       * Returns the a coefficient
 321       *
 322       * @return \phpseclib3\Math\PrimeField\Integer
 323       */
 324      public function getA()
 325      {
 326          return $this->a;
 327      }
 328  
 329      /**
 330       * Returns the a coefficient
 331       *
 332       * @return \phpseclib3\Math\PrimeField\Integer
 333       */
 334      public function getB()
 335      {
 336          return $this->b;
 337      }
 338  
 339      /**
 340       * Returns the affine point
 341       *
 342       * A Jacobian Coordinate is of the form (x, y, z).
 343       * To convert a Jacobian Coordinate to an Affine Point
 344       * you do (x / z^2, y / z^3)
 345       *
 346       * @return \phpseclib3\Math\PrimeField\Integer[]
 347       */
 348      public function convertToAffine(array $p)
 349      {
 350          if (!isset($p[2])) {
 351              return $p;
 352          }
 353          list($x, $y, $z) = $p;
 354          $z = $this->one->divide($z);
 355          $z2 = $z->multiply($z);
 356          return [
 357              $x->multiply($z2),
 358              $y->multiply($z2)->multiply($z)
 359          ];
 360      }
 361  
 362      /**
 363       * Converts an affine point to a jacobian coordinate
 364       *
 365       * @return \phpseclib3\Math\PrimeField\Integer[]
 366       */
 367      public function convertToInternal(array $p)
 368      {
 369          if (isset($p[2])) {
 370              return $p;
 371          }
 372  
 373          $p[2] = clone $this->one;
 374          $p['fresh'] = true;
 375          return $p;
 376      }
 377  }