[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * Generalized Koblitz Curves over y^2 = x^3 + b.
   5   *
   6   * According to http://www.secg.org/SEC2-Ver-1.0.pdf Koblitz curves are over the GF(2**m)
   7   * finite field. Both the $a$ and $b$ coefficients are either 0 or 1. However, SEC2
   8   * generalizes the definition to include curves over GF(P) "which possess an efficiently
   9   * computable endomorphism".
  10   *
  11   * For these generalized Koblitz curves $b$ doesn't have to be 0 or 1. Whether or not $a$
  12   * has any restrictions on it is unclear, however, for all the GF(P) Koblitz curves defined
  13   * in SEC2 v1.0 $a$ is $0$ so all of the methods defined herein will assume that it is.
  14   *
  15   * I suppose we could rename the $b$ coefficient to $a$, however, the documentation refers
  16   * to $b$ so we'll just keep it.
  17   *
  18   * If a later version of SEC2 comes out wherein some $a$ values are non-zero we can create a
  19   * new method for those. eg. KoblitzA1Prime.php or something.
  20   *
  21   * PHP version 5 and 7
  22   *
  23   * @category  Crypt
  24   * @package   EC
  25   * @author    Jim Wigginton <[email protected]>
  26   * @copyright 2017 Jim Wigginton
  27   * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  28   * @link      http://pear.php.net/package/Math_BigInteger
  29   */
  30  
  31  namespace phpseclib3\Crypt\EC\BaseCurves;
  32  
  33  use phpseclib3\Math\BigInteger;
  34  use phpseclib3\Math\PrimeField;
  35  
  36  /**
  37   * Curves over y^2 = x^3 + b
  38   *
  39   * @package KoblitzPrime
  40   * @author  Jim Wigginton <[email protected]>
  41   * @access  public
  42   */
  43  class KoblitzPrime extends Prime
  44  {
  45      // don't overwrite setCoefficients() with one that only accepts one parameter so that
  46      // one might be able to switch between KoblitzPrime and Prime more easily (for benchmarking
  47      // purposes).
  48  
  49      /**
  50       * Multiply and Add Points
  51       *
  52       * Uses a efficiently computable endomorphism to achieve a slight speedup
  53       *
  54       * Adapted from https://git.io/vxbrP
  55       *
  56       * @return int[]
  57       */
  58      public function multiplyAddPoints(array $points, array $scalars)
  59      {
  60          static $zero, $one, $two;
  61          if (!isset($two)) {
  62              $two = new BigInteger(2);
  63              $one = new BigInteger(1);
  64          }
  65  
  66          if (!isset($this->beta)) {
  67              // get roots
  68              $inv = $this->one->divide($this->two)->negate();
  69              $s = $this->three->negate()->squareRoot()->multiply($inv);
  70              $betas = [
  71                  $inv->add($s),
  72                  $inv->subtract($s)
  73              ];
  74              $this->beta = $betas[0]->compare($betas[1]) < 0 ? $betas[0] : $betas[1];
  75              //echo strtoupper($this->beta->toHex(true)) . "\n"; exit;
  76          }
  77  
  78          if (!isset($this->basis)) {
  79              $factory = new PrimeField($this->order);
  80              $tempOne = $factory->newInteger($one);
  81              $tempTwo = $factory->newInteger($two);
  82              $tempThree = $factory->newInteger(new BigInteger(3));
  83  
  84              $inv = $tempOne->divide($tempTwo)->negate();
  85              $s = $tempThree->negate()->squareRoot()->multiply($inv);
  86  
  87              $lambdas = [
  88                  $inv->add($s),
  89                  $inv->subtract($s)
  90              ];
  91  
  92              $lhs = $this->multiplyPoint($this->p, $lambdas[0])[0];
  93              $rhs = $this->p[0]->multiply($this->beta);
  94              $lambda = $lhs->equals($rhs) ? $lambdas[0] : $lambdas[1];
  95  
  96              $this->basis = static::extendedGCD($lambda->toBigInteger(), $this->order);
  97              ///*
  98              foreach ($this->basis as $basis) {
  99                  echo strtoupper($basis['a']->toHex(true)) . "\n";
 100                  echo strtoupper($basis['b']->toHex(true)) . "\n\n";
 101              }
 102              exit;
 103              //*/
 104          }
 105  
 106          $npoints = $nscalars = [];
 107          for ($i = 0; $i < count($points); $i++) {
 108              $p = $points[$i];
 109              $k = $scalars[$i]->toBigInteger();
 110  
 111              // begin split
 112              list($v1, $v2) = $this->basis;
 113  
 114              $c1 = $v2['b']->multiply($k);
 115              list($c1, $r) = $c1->divide($this->order);
 116              if ($this->order->compare($r->multiply($two)) <= 0) {
 117                  $c1 = $c1->add($one);
 118              }
 119  
 120              $c2 = $v1['b']->negate()->multiply($k);
 121              list($c2, $r) = $c2->divide($this->order);
 122              if ($this->order->compare($r->multiply($two)) <= 0) {
 123                  $c2 = $c2->add($one);
 124              }
 125  
 126              $p1 = $c1->multiply($v1['a']);
 127              $p2 = $c2->multiply($v2['a']);
 128              $q1 = $c1->multiply($v1['b']);
 129              $q2 = $c2->multiply($v2['b']);
 130  
 131              $k1 = $k->subtract($p1)->subtract($p2);
 132              $k2 = $q1->add($q2)->negate();
 133              // end split
 134  
 135              $beta = [
 136                  $p[0]->multiply($this->beta),
 137                  $p[1],
 138                  clone $this->one
 139              ];
 140  
 141              if (isset($p['naf'])) {
 142                  $beta['naf'] = array_map(function ($p) {
 143                      return [
 144                          $p[0]->multiply($this->beta),
 145                          $p[1],
 146                          clone $this->one
 147                      ];
 148                  }, $p['naf']);
 149                  $beta['nafwidth'] = $p['nafwidth'];
 150              }
 151  
 152              if ($k1->isNegative()) {
 153                  $k1 = $k1->negate();
 154                  $p = $this->negatePoint($p);
 155              }
 156  
 157              if ($k2->isNegative()) {
 158                  $k2 = $k2->negate();
 159                  $beta = $this->negatePoint($beta);
 160              }
 161  
 162              $pos = 2 * $i;
 163              $npoints[$pos] = $p;
 164              $nscalars[$pos] = $this->factory->newInteger($k1);
 165  
 166              $pos++;
 167              $npoints[$pos] = $beta;
 168              $nscalars[$pos] = $this->factory->newInteger($k2);
 169          }
 170  
 171          return parent::multiplyAddPoints($npoints, $nscalars);
 172      }
 173  
 174      /**
 175       * Returns the numerator and denominator of the slope
 176       *
 177       * @return FiniteField[]
 178       */
 179      protected function doublePointHelper(array $p)
 180      {
 181          $numerator = $this->three->multiply($p[0])->multiply($p[0]);
 182          $denominator = $this->two->multiply($p[1]);
 183          return [$numerator, $denominator];
 184      }
 185  
 186      /**
 187       * Doubles a jacobian coordinate on the curve
 188       *
 189       * See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
 190       *
 191       * @return FiniteField[]
 192       */
 193      protected function jacobianDoublePoint(array $p)
 194      {
 195          list($x1, $y1, $z1) = $p;
 196          $a = $x1->multiply($x1);
 197          $b = $y1->multiply($y1);
 198          $c = $b->multiply($b);
 199          $d = $x1->add($b);
 200          $d = $d->multiply($d)->subtract($a)->subtract($c)->multiply($this->two);
 201          $e = $this->three->multiply($a);
 202          $f = $e->multiply($e);
 203          $x3 = $f->subtract($this->two->multiply($d));
 204          $y3 = $e->multiply($d->subtract($x3))->subtract(
 205              $this->eight->multiply($c)
 206          );
 207          $z3 = $this->two->multiply($y1)->multiply($z1);
 208          return [$x3, $y3, $z3];
 209      }
 210  
 211      /**
 212       * Doubles a "fresh" jacobian coordinate on the curve
 213       *
 214       * See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-mdbl-2007-bl
 215       *
 216       * @return FiniteField[]
 217       */
 218      protected function jacobianDoublePointMixed(array $p)
 219      {
 220          list($x1, $y1) = $p;
 221          $xx = $x1->multiply($x1);
 222          $yy = $y1->multiply($y1);
 223          $yyyy = $yy->multiply($yy);
 224          $s = $x1->add($yy);
 225          $s = $s->multiply($s)->subtract($xx)->subtract($yyyy)->multiply($this->two);
 226          $m = $this->three->multiply($xx);
 227          $t = $m->multiply($m)->subtract($this->two->multiply($s));
 228          $x3 = $t;
 229          $y3 = $s->subtract($t);
 230          $y3 = $m->multiply($y3)->subtract($this->eight->multiply($yyyy));
 231          $z3 = $this->two->multiply($y1);
 232          return [$x3, $y3, $z3];
 233      }
 234  
 235      /**
 236       * Tests whether or not the x / y values satisfy the equation
 237       *
 238       * @return boolean
 239       */
 240      public function verifyPoint(array $p)
 241      {
 242          list($x, $y) = $p;
 243          $lhs = $y->multiply($y);
 244          $temp = $x->multiply($x)->multiply($x);
 245          $rhs = $temp->add($this->b);
 246  
 247          return $lhs->equals($rhs);
 248      }
 249  
 250      /**
 251       * Calculates the parameters needed from the Euclidean algorithm as discussed at
 252       * http://diamond.boisestate.edu/~liljanab/MATH308/GuideToECC.pdf#page=148
 253       *
 254       * @param BigInteger $u
 255       * @param BigInteger $v
 256       * @return BigInteger[]
 257       */
 258      protected static function extendedGCD(BigInteger $u, BigInteger $v)
 259      {
 260          $one = new BigInteger(1);
 261          $zero = new BigInteger();
 262  
 263          $a = clone $one;
 264          $b = clone $zero;
 265          $c = clone $zero;
 266          $d = clone $one;
 267  
 268          $stop = $v->bitwise_rightShift($v->getLength() >> 1);
 269  
 270          $a1 = clone $zero;
 271          $b1 = clone $zero;
 272          $a2 = clone $zero;
 273          $b2 = clone $zero;
 274  
 275          $postGreatestIndex = 0;
 276  
 277          while (!$v->equals($zero)) {
 278              list($q) = $u->divide($v);
 279  
 280              $temp = $u;
 281              $u = $v;
 282              $v = $temp->subtract($v->multiply($q));
 283  
 284              $temp = $a;
 285              $a = $c;
 286              $c = $temp->subtract($a->multiply($q));
 287  
 288              $temp = $b;
 289              $b = $d;
 290              $d = $temp->subtract($b->multiply($q));
 291  
 292              if ($v->compare($stop) > 0) {
 293                  $a0 = $v;
 294                  $b0 = $c;
 295              } else {
 296                  $postGreatestIndex++;
 297              }
 298  
 299              if ($postGreatestIndex == 1) {
 300                  $a1 = $v;
 301                  $b1 = $c->negate();
 302              }
 303  
 304              if ($postGreatestIndex == 2) {
 305                  $rhs = $a0->multiply($a0)->add($b0->multiply($b0));
 306                  $lhs = $v->multiply($v)->add($b->multiply($b));
 307                  if ($lhs->compare($rhs) <= 0) {
 308                      $a2 = $a0;
 309                      $b2 = $b0->negate();
 310                  } else {
 311                      $a2 = $v;
 312                      $b2 = $c->negate();
 313                  }
 314  
 315                  break;
 316              }
 317          }
 318  
 319          return [
 320              ['a' => $a1, 'b' => $b1],
 321              ['a' => $a2, 'b' => $b2]
 322          ];
 323      }
 324  }