[Summary view] [Print] [Text view]

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