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