[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * Prime Finite Fields
   5   *
   6   * PHP version 5 and 7
   7   *
   8   * @category  Math
   9   * @package   BigInteger
  10   * @author    Jim Wigginton <[email protected]>
  11   * @copyright 2017 Jim Wigginton
  12   * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  13   */
  14  
  15  namespace phpseclib3\Math\PrimeField;
  16  
  17  use ParagonIE\ConstantTime\Hex;
  18  use phpseclib3\Math\BigInteger;
  19  use phpseclib3\Math\Common\FiniteField\Integer as Base;
  20  
  21  /**
  22   * Prime Finite Fields
  23   *
  24   * @package Math
  25   * @author  Jim Wigginton <[email protected]>
  26   * @access  public
  27   */
  28  class Integer extends Base
  29  {
  30      /**
  31       * Holds the PrimeField's value
  32       *
  33       * @var BigInteger
  34       */
  35      protected $value;
  36  
  37      /**
  38       * Keeps track of current instance
  39       *
  40       * @var int
  41       */
  42      protected $instanceID;
  43  
  44      /**
  45       * Holds the PrimeField's modulo
  46       *
  47       * @var array<int, BigInteger>
  48       */
  49      protected static $modulo;
  50  
  51      /**
  52       * Holds a pre-generated function to perform modulo reductions
  53       *
  54       * @var array<int, callable(BigInteger):BigInteger>
  55       */
  56      protected static $reduce;
  57  
  58      /**
  59       * Zero
  60       *
  61       * @var BigInteger
  62       */
  63      protected static $zero;
  64  
  65      /**
  66       * Default constructor
  67       *
  68       * @param int $instanceID
  69       */
  70      public function __construct($instanceID, BigInteger $num = null)
  71      {
  72          $this->instanceID = $instanceID;
  73          if (!isset($num)) {
  74              $this->value = clone static::$zero[static::class];
  75          } else {
  76              $reduce = static::$reduce[$instanceID];
  77              $this->value = $reduce($num);
  78          }
  79      }
  80  
  81      /**
  82       * Set the modulo for a given instance
  83       *
  84       * @param int $instanceID
  85       * @return void
  86       */
  87      public static function setModulo($instanceID, BigInteger $modulo)
  88      {
  89          static::$modulo[$instanceID] = $modulo;
  90      }
  91  
  92      /**
  93       * Set the modulo for a given instance
  94       *
  95       * @param int $instanceID
  96       * @return void
  97       */
  98      public static function setRecurringModuloFunction($instanceID, callable $function)
  99      {
 100          static::$reduce[$instanceID] = $function;
 101          if (!isset(static::$zero[static::class])) {
 102              static::$zero[static::class] = new BigInteger();
 103          }
 104      }
 105  
 106      /**
 107       * Delete the modulo for a given instance
 108       */
 109      public static function cleanupCache($instanceID)
 110      {
 111          unset(static::$modulo[$instanceID]);
 112          unset(static::$reduce[$instanceID]);
 113      }
 114  
 115      /**
 116       * Returns the modulo
 117       *
 118       * @param int $instanceID
 119       * @return BigInteger
 120       */
 121      public static function getModulo($instanceID)
 122      {
 123          return static::$modulo[$instanceID];
 124      }
 125  
 126      /**
 127       * Tests a parameter to see if it's of the right instance
 128       *
 129       * Throws an exception if the incorrect class is being utilized
 130       *
 131       * @return void
 132       */
 133      public static function checkInstance(self $x, self $y)
 134      {
 135          if ($x->instanceID != $y->instanceID) {
 136              throw new \UnexpectedValueException('The instances of the two PrimeField\Integer objects do not match');
 137          }
 138      }
 139  
 140      /**
 141       * Tests the equality of two numbers.
 142       *
 143       * @return bool
 144       */
 145      public function equals(self $x)
 146      {
 147          static::checkInstance($this, $x);
 148  
 149          return $this->value->equals($x->value);
 150      }
 151  
 152      /**
 153       * Compares two numbers.
 154       *
 155       * @return int
 156       */
 157      public function compare(self $x)
 158      {
 159          static::checkInstance($this, $x);
 160  
 161          return $this->value->compare($x->value);
 162      }
 163  
 164      /**
 165       * Adds two PrimeFieldIntegers.
 166       *
 167       * @return static
 168       */
 169      public function add(self $x)
 170      {
 171          static::checkInstance($this, $x);
 172  
 173          $temp = new static($this->instanceID);
 174          $temp->value = $this->value->add($x->value);
 175          if ($temp->value->compare(static::$modulo[$this->instanceID]) >= 0) {
 176              $temp->value = $temp->value->subtract(static::$modulo[$this->instanceID]);
 177          }
 178  
 179          return $temp;
 180      }
 181  
 182      /**
 183       * Subtracts two PrimeFieldIntegers.
 184       *
 185       * @return static
 186       */
 187      public function subtract(self $x)
 188      {
 189          static::checkInstance($this, $x);
 190  
 191          $temp = new static($this->instanceID);
 192          $temp->value = $this->value->subtract($x->value);
 193          if ($temp->value->isNegative()) {
 194              $temp->value = $temp->value->add(static::$modulo[$this->instanceID]);
 195          }
 196  
 197          return $temp;
 198      }
 199  
 200      /**
 201       * Multiplies two PrimeFieldIntegers.
 202       *
 203       * @return static
 204       */
 205      public function multiply(self $x)
 206      {
 207          static::checkInstance($this, $x);
 208  
 209          return new static($this->instanceID, $this->value->multiply($x->value));
 210      }
 211  
 212      /**
 213       * Divides two PrimeFieldIntegers.
 214       *
 215       * @return static
 216       */
 217      public function divide(self $x)
 218      {
 219          static::checkInstance($this, $x);
 220  
 221          $denominator = $x->value->modInverse(static::$modulo[$this->instanceID]);
 222          return new static($this->instanceID, $this->value->multiply($denominator));
 223      }
 224  
 225      /**
 226       * Performs power operation on a PrimeFieldInteger.
 227       *
 228       * @return static
 229       */
 230      public function pow(BigInteger $x)
 231      {
 232          $temp = new static($this->instanceID);
 233          $temp->value = $this->value->powMod($x, static::$modulo[$this->instanceID]);
 234  
 235          return $temp;
 236      }
 237  
 238      /**
 239       * Calculates the square root
 240       *
 241       * @link https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
 242       * @return static|false
 243       */
 244      public function squareRoot()
 245      {
 246          static $one, $two;
 247          if (!isset($one)) {
 248              $one = new BigInteger(1);
 249              $two = new BigInteger(2);
 250          }
 251          $reduce = static::$reduce[$this->instanceID];
 252          $p_1 = static::$modulo[$this->instanceID]->subtract($one);
 253          $q = clone $p_1;
 254          $s = BigInteger::scan1divide($q);
 255          list($pow) = $p_1->divide($two);
 256          for ($z = $one; !$z->equals(static::$modulo[$this->instanceID]); $z = $z->add($one)) {
 257              $temp = $z->powMod($pow, static::$modulo[$this->instanceID]);
 258              if ($temp->equals($p_1)) {
 259                  break;
 260              }
 261          }
 262  
 263          $m = new BigInteger($s);
 264          $c = $z->powMod($q, static::$modulo[$this->instanceID]);
 265          $t = $this->value->powMod($q, static::$modulo[$this->instanceID]);
 266          list($temp) = $q->add($one)->divide($two);
 267          $r = $this->value->powMod($temp, static::$modulo[$this->instanceID]);
 268  
 269          while (!$t->equals($one)) {
 270              $i = clone $one;
 271  
 272              while (!$t->powMod($two->pow($i), static::$modulo[$this->instanceID])->equals($one)) {
 273                  $i = $i->add($one);
 274              }
 275  
 276              if ($i->compare($m) >= 0) {
 277                  return false;
 278              }
 279              $b = $c->powMod($two->pow($m->subtract($i)->subtract($one)), static::$modulo[$this->instanceID]);
 280              $m = $i;
 281              $c = $reduce($b->multiply($b));
 282              $t = $reduce($t->multiply($c));
 283              $r = $reduce($r->multiply($b));
 284          }
 285  
 286          return new static($this->instanceID, $r);
 287      }
 288  
 289      /**
 290       * Is Odd?
 291       *
 292       * @return bool
 293       */
 294      public function isOdd()
 295      {
 296          return $this->value->isOdd();
 297      }
 298  
 299      /**
 300       * Negate
 301       *
 302       * A negative number can be written as 0-12. With modulos, 0 is the same thing as the modulo
 303       * so 0-12 is the same thing as modulo-12
 304       *
 305       * @return static
 306       */
 307      public function negate()
 308      {
 309          return new static($this->instanceID, static::$modulo[$this->instanceID]->subtract($this->value));
 310      }
 311  
 312      /**
 313       * Converts an Integer to a byte string (eg. base-256).
 314       *
 315       * @return string
 316       */
 317      public function toBytes()
 318      {
 319          $length = static::$modulo[$this->instanceID]->getLengthInBytes();
 320          return str_pad($this->value->toBytes(), $length, "\0", STR_PAD_LEFT);
 321      }
 322  
 323      /**
 324       * Converts an Integer to a hex string (eg. base-16).
 325       *
 326       * @return string
 327       */
 328      public function toHex()
 329      {
 330          return Hex::encode($this->toBytes());
 331      }
 332  
 333      /**
 334       * Converts an Integer to a bit string (eg. base-2).
 335       *
 336       * @return string
 337       */
 338      public function toBits()
 339      {
 340          // return $this->value->toBits();
 341          static $length;
 342          if (!isset($length)) {
 343              $length = static::$modulo[$this->instanceID]->getLength();
 344          }
 345  
 346          return str_pad($this->value->toBits(), $length, '0', STR_PAD_LEFT);
 347      }
 348  
 349      /**
 350       * Returns the w-ary non-adjacent form (wNAF)
 351       *
 352       * @param int $w optional
 353       * @return array<int, int>
 354       */
 355      public function getNAF($w = 1)
 356      {
 357          $w++;
 358  
 359          $mask = new BigInteger((1 << $w) - 1);
 360          $sub = new BigInteger(1 << $w);
 361          //$sub = new BigInteger(1 << ($w - 1));
 362          $d = $this->toBigInteger();
 363          $d_i = [];
 364  
 365          $i = 0;
 366          while ($d->compare(static::$zero[static::class]) > 0) {
 367              if ($d->isOdd()) {
 368                  // start mods
 369  
 370                  $bigInteger = $d->testBit($w - 1) ?
 371                      $d->bitwise_and($mask)->subtract($sub) :
 372                      //$sub->subtract($d->bitwise_and($mask)) :
 373                      $d->bitwise_and($mask);
 374                  // end mods
 375                  $d = $d->subtract($bigInteger);
 376                  $d_i[$i] = (int) $bigInteger->toString();
 377              } else {
 378                  $d_i[$i] = 0;
 379              }
 380              $shift = !$d->equals(static::$zero[static::class]) && $d->bitwise_and($mask)->equals(static::$zero[static::class]) ? $w : 1; // $w or $w + 1?
 381              $d = $d->bitwise_rightShift($shift);
 382              while (--$shift > 0) {
 383                  $d_i[++$i] = 0;
 384              }
 385              $i++;
 386          }
 387  
 388          return $d_i;
 389      }
 390  
 391      /**
 392       * Converts an Integer to a BigInteger
 393       *
 394       * @return BigInteger
 395       */
 396      public function toBigInteger()
 397      {
 398          return clone $this->value;
 399      }
 400  
 401      /**
 402       *  __toString() magic method
 403       *
 404       * @access public
 405       * @return string
 406       */
 407      public function __toString()
 408      {
 409          return (string) $this->value;
 410      }
 411  
 412      /**
 413       *  __debugInfo() magic method
 414       *
 415       * @access public
 416       * @return array
 417       */
 418      public function __debugInfo()
 419      {
 420          return ['value' => $this->toHex()];
 421      }
 422  }