[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * Curve methods common to all curves
   5   *
   6   * PHP version 5 and 7
   7   *
   8   * @category  Crypt
   9   * @package   EC
  10   * @author    Jim Wigginton <[email protected]>
  11   * @copyright 2017 Jim Wigginton
  12   * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  13   * @link      http://pear.php.net/package/Math_BigInteger
  14   */
  15  
  16  namespace phpseclib3\Crypt\EC\BaseCurves;
  17  
  18  use phpseclib3\Math\BigInteger;
  19  
  20  /**
  21   * Base
  22   *
  23   * @package Prime
  24   * @author  Jim Wigginton <[email protected]>
  25   * @access  public
  26   */
  27  abstract class Base
  28  {
  29      /**
  30       * Doubles
  31       *
  32       * @var object[]
  33       */
  34      protected $doubles;
  35  
  36      /**
  37       * NAF Points
  38       *
  39       * @var int[]
  40       */
  41      private $naf;
  42  
  43      /**
  44       * The Order
  45       *
  46       * @var BigInteger
  47       */
  48      protected $order;
  49  
  50      /**
  51       * Finite Field Integer factory
  52       *
  53       * @var \phpseclib3\Math\FiniteField\Integer
  54       */
  55      protected $factory;
  56  
  57      /**
  58       * Returns a random integer
  59       *
  60       * @return object
  61       */
  62      public function randomInteger()
  63      {
  64          return $this->factory->randomInteger();
  65      }
  66  
  67      /**
  68       * Converts a BigInteger to a \phpseclib3\Math\FiniteField\Integer integer
  69       *
  70       * @return object
  71       */
  72      public function convertInteger(BigInteger $x)
  73      {
  74          return $this->factory->newInteger($x);
  75      }
  76  
  77      /**
  78       * Returns the length, in bytes, of the modulo
  79       *
  80       * @return integer
  81       */
  82      public function getLengthInBytes()
  83      {
  84          return $this->factory->getLengthInBytes();
  85      }
  86  
  87      /**
  88       * Returns the length, in bits, of the modulo
  89       *
  90       * @return integer
  91       */
  92      public function getLength()
  93      {
  94          return $this->factory->getLength();
  95      }
  96  
  97      /**
  98       * Multiply a point on the curve by a scalar
  99       *
 100       * Uses the montgomery ladder technique as described here:
 101       *
 102       * https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Montgomery_ladder
 103       * https://github.com/phpecc/phpecc/issues/16#issuecomment-59176772
 104       *
 105       * @return array
 106       */
 107      public function multiplyPoint(array $p, BigInteger $d)
 108      {
 109          $alreadyInternal = isset($p[2]);
 110          $r = $alreadyInternal ?
 111              [[], $p] :
 112              [[], $this->convertToInternal($p)];
 113  
 114          $d = $d->toBits();
 115          for ($i = 0; $i < strlen($d); $i++) {
 116              $d_i = (int) $d[$i];
 117              $r[1 - $d_i] = $this->addPoint($r[0], $r[1]);
 118              $r[$d_i] = $this->doublePoint($r[$d_i]);
 119          }
 120  
 121          return $alreadyInternal ? $r[0] : $this->convertToAffine($r[0]);
 122      }
 123  
 124      /**
 125       * Creates a random scalar multiplier
 126       *
 127       * @return BigInteger
 128       */
 129      public function createRandomMultiplier()
 130      {
 131          static $one;
 132          if (!isset($one)) {
 133              $one = new BigInteger(1);
 134          }
 135  
 136          return BigInteger::randomRange($one, $this->order->subtract($one));
 137      }
 138  
 139      /**
 140       * Performs range check
 141       */
 142      public function rangeCheck(BigInteger $x)
 143      {
 144          static $zero;
 145          if (!isset($zero)) {
 146              $zero = new BigInteger();
 147          }
 148  
 149          if (!isset($this->order)) {
 150              throw new \RuntimeException('setOrder needs to be called before this method');
 151          }
 152          if ($x->compare($this->order) > 0 || $x->compare($zero) <= 0) {
 153              throw new \RangeException('x must be between 1 and the order of the curve');
 154          }
 155      }
 156  
 157      /**
 158       * Sets the Order
 159       */
 160      public function setOrder(BigInteger $order)
 161      {
 162          $this->order = $order;
 163      }
 164  
 165      /**
 166       * Returns the Order
 167       *
 168       * @return \phpseclib3\Math\BigInteger
 169       */
 170      public function getOrder()
 171      {
 172          return $this->order;
 173      }
 174  
 175      /**
 176       * Use a custom defined modular reduction function
 177       *
 178       * @return object
 179       */
 180      public function setReduction(callable $func)
 181      {
 182          $this->factory->setReduction($func);
 183      }
 184  
 185      /**
 186       * Returns the affine point
 187       *
 188       * @return object[]
 189       */
 190      public function convertToAffine(array $p)
 191      {
 192          return $p;
 193      }
 194  
 195      /**
 196       * Converts an affine point to a jacobian coordinate
 197       *
 198       * @return object[]
 199       */
 200      public function convertToInternal(array $p)
 201      {
 202          return $p;
 203      }
 204  
 205      /**
 206       * Negates a point
 207       *
 208       * @return object[]
 209       */
 210      public function negatePoint(array $p)
 211      {
 212          $temp = [
 213              $p[0],
 214              $p[1]->negate()
 215          ];
 216          if (isset($p[2])) {
 217              $temp[] = $p[2];
 218          }
 219          return $temp;
 220      }
 221  
 222      /**
 223       * Multiply and Add Points
 224       *
 225       * @return int[]
 226       */
 227      public function multiplyAddPoints(array $points, array $scalars)
 228      {
 229          $p1 = $this->convertToInternal($points[0]);
 230          $p2 = $this->convertToInternal($points[1]);
 231          $p1 = $this->multiplyPoint($p1, $scalars[0]);
 232          $p2 = $this->multiplyPoint($p2, $scalars[1]);
 233          $r = $this->addPoint($p1, $p2);
 234          return $this->convertToAffine($r);
 235      }
 236  }