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