[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * Binary Finite Fields
   5   *
   6   * In a binary finite field numbers are actually polynomial equations. If you
   7   * represent the number as a sequence of bits you get a sequence of 1's or 0's.
   8   * These 1's or 0's represent the coefficients of the x**n, where n is the
   9   * location of the given bit. When you add numbers over a binary finite field
  10   * the result should have a coefficient of 1 or 0 as well. Hence addition
  11   * and subtraction become the same operation as XOR.
  12   * eg. 1 + 1 + 1 == 3 % 2 == 1 or 0 - 1 == -1 % 2 == 1
  13   *
  14   * PHP version 5 and 7
  15   *
  16   * @author    Jim Wigginton <terrafrost@php.net>
  17   * @copyright 2017 Jim Wigginton
  18   * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  19   */
  20  
  21  namespace phpseclib3\Math\BinaryField;
  22  
  23  use phpseclib3\Common\Functions\Strings;
  24  use phpseclib3\Math\BigInteger;
  25  use phpseclib3\Math\BinaryField;
  26  use phpseclib3\Math\Common\FiniteField\Integer as Base;
  27  
  28  /**
  29   * Binary Finite Fields
  30   *
  31   * @author  Jim Wigginton <terrafrost@php.net>
  32   */
  33  class Integer extends Base
  34  {
  35      /**
  36       * Holds the BinaryField's value
  37       *
  38       * @var string
  39       */
  40      protected $value;
  41  
  42      /**
  43       * Keeps track of current instance
  44       *
  45       * @var int
  46       */
  47      protected $instanceID;
  48  
  49      /**
  50       * Holds the PrimeField's modulo
  51       *
  52       * @var array<int, string>
  53       */
  54      protected static $modulo;
  55  
  56      /**
  57       * Holds a pre-generated function to perform modulo reductions
  58       *
  59       * @var callable[]
  60       */
  61      protected static $reduce;
  62  
  63      /**
  64       * Default constructor
  65       */
  66      public function __construct($instanceID, $num = '')
  67      {
  68          $this->instanceID = $instanceID;
  69          if (!strlen($num)) {
  70              $this->value = '';
  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       * @param int $instanceID
  80       * @param string $modulo
  81       */
  82      public static function setModulo($instanceID, $modulo)
  83      {
  84          static::$modulo[$instanceID] = $modulo;
  85      }
  86  
  87      /**
  88       * Set the modulo for a given instance
  89       */
  90      public static function setRecurringModuloFunction($instanceID, callable $function)
  91      {
  92          static::$reduce[$instanceID] = $function;
  93      }
  94  
  95      /**
  96       * Tests a parameter to see if it's of the right instance
  97       *
  98       * Throws an exception if the incorrect class is being utilized
  99       */
 100      private static function checkInstance(self $x, self $y)
 101      {
 102          if ($x->instanceID != $y->instanceID) {
 103              throw new \UnexpectedValueException('The instances of the two BinaryField\Integer objects do not match');
 104          }
 105      }
 106  
 107      /**
 108       * Tests the equality of two numbers.
 109       *
 110       * @return bool
 111       */
 112      public function equals(self $x)
 113      {
 114          static::checkInstance($this, $x);
 115  
 116          return $this->value == $x->value;
 117      }
 118  
 119      /**
 120       * Compares two numbers.
 121       *
 122       * @return int
 123       */
 124      public function compare(self $x)
 125      {
 126          static::checkInstance($this, $x);
 127  
 128          $a = $this->value;
 129          $b = $x->value;
 130  
 131          $length = max(strlen($a), strlen($b));
 132  
 133          $a = str_pad($a, $length, "\0", STR_PAD_LEFT);
 134          $b = str_pad($b, $length, "\0", STR_PAD_LEFT);
 135  
 136          return strcmp($a, $b);
 137      }
 138  
 139      /**
 140       * Returns the degree of the polynomial
 141       *
 142       * @param string $x
 143       * @return int
 144       */
 145      private static function deg($x)
 146      {
 147          $x = ltrim($x, "\0");
 148          $xbit = decbin(ord($x[0]));
 149          $xlen = $xbit == '0' ? 0 : strlen($xbit);
 150          $len = strlen($x);
 151          if (!$len) {
 152              return -1;
 153          }
 154          return 8 * strlen($x) - 9 + $xlen;
 155      }
 156  
 157      /**
 158       * Perform polynomial division
 159       *
 160       * @return string[]
 161       * @link https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclidean_division
 162       */
 163      private static function polynomialDivide($x, $y)
 164      {
 165          // in wikipedia's description of the algorithm, lc() is the leading coefficient. over a binary field that's
 166          // always going to be 1.
 167  
 168          $q = chr(0);
 169          $d = static::deg($y);
 170          $r = $x;
 171          while (($degr = static::deg($r)) >= $d) {
 172              $s = '1' . str_repeat('0', $degr - $d);
 173              $s = BinaryField::base2ToBase256($s);
 174              $length = max(strlen($s), strlen($q));
 175              $q = !isset($q) ? $s :
 176                  str_pad($q, $length, "\0", STR_PAD_LEFT) ^
 177                  str_pad($s, $length, "\0", STR_PAD_LEFT);
 178              $s = static::polynomialMultiply($s, $y);
 179              $length = max(strlen($r), strlen($s));
 180              $r = str_pad($r, $length, "\0", STR_PAD_LEFT) ^
 181                   str_pad($s, $length, "\0", STR_PAD_LEFT);
 182          }
 183  
 184          return [ltrim($q, "\0"), ltrim($r, "\0")];
 185      }
 186  
 187      /**
 188       * Perform polynomial multiplation in the traditional way
 189       *
 190       * @return string
 191       * @link https://en.wikipedia.org/wiki/Finite_field_arithmetic#Multiplication
 192       */
 193      private static function regularPolynomialMultiply($x, $y)
 194      {
 195          $precomputed = [ltrim($x, "\0")];
 196          $x = strrev(BinaryField::base256ToBase2($x));
 197          $y = strrev(BinaryField::base256ToBase2($y));
 198          if (strlen($x) == strlen($y)) {
 199              $length = strlen($x);
 200          } else {
 201              $length = max(strlen($x), strlen($y));
 202              $x = str_pad($x, $length, '0');
 203              $y = str_pad($y, $length, '0');
 204          }
 205          $result = str_repeat('0', 2 * $length - 1);
 206          $result = BinaryField::base2ToBase256($result);
 207          $size = strlen($result);
 208          $x = strrev($x);
 209  
 210          // precompute left shift 1 through 7
 211          for ($i = 1; $i < 8; $i++) {
 212              $precomputed[$i] = BinaryField::base2ToBase256($x . str_repeat('0', $i));
 213          }
 214          for ($i = 0; $i < strlen($y); $i++) {
 215              if ($y[$i] == '1') {
 216                  $temp = $precomputed[$i & 7] . str_repeat("\0", $i >> 3);
 217                  $result ^= str_pad($temp, $size, "\0", STR_PAD_LEFT);
 218              }
 219          }
 220  
 221          return $result;
 222      }
 223  
 224      /**
 225       * Perform polynomial multiplation
 226       *
 227       * Uses karatsuba multiplication to reduce x-bit multiplications to a series of 32-bit multiplications
 228       *
 229       * @return string
 230       * @link https://en.wikipedia.org/wiki/Karatsuba_algorithm
 231       */
 232      private static function polynomialMultiply($x, $y)
 233      {
 234          if (strlen($x) == strlen($y)) {
 235              $length = strlen($x);
 236          } else {
 237              $length = max(strlen($x), strlen($y));
 238              $x = str_pad($x, $length, "\0", STR_PAD_LEFT);
 239              $y = str_pad($y, $length, "\0", STR_PAD_LEFT);
 240          }
 241  
 242          switch (true) {
 243              case PHP_INT_SIZE == 8 && $length <= 4:
 244                  return $length != 4 ?
 245                      self::subMultiply(str_pad($x, 4, "\0", STR_PAD_LEFT), str_pad($y, 4, "\0", STR_PAD_LEFT)) :
 246                      self::subMultiply($x, $y);
 247              case PHP_INT_SIZE == 4 || $length > 32:
 248                  return self::regularPolynomialMultiply($x, $y);
 249          }
 250  
 251          $m = $length >> 1;
 252  
 253          $x1 = substr($x, 0, -$m);
 254          $x0 = substr($x, -$m);
 255          $y1 = substr($y, 0, -$m);
 256          $y0 = substr($y, -$m);
 257  
 258          $z2 = self::polynomialMultiply($x1, $y1);
 259          $z0 = self::polynomialMultiply($x0, $y0);
 260          $z1 = self::polynomialMultiply(
 261              self::subAdd2($x1, $x0),
 262              self::subAdd2($y1, $y0)
 263          );
 264  
 265          $z1 = self::subAdd3($z1, $z2, $z0);
 266  
 267          $xy = self::subAdd3(
 268              $z2 . str_repeat("\0", 2 * $m),
 269              $z1 . str_repeat("\0", $m),
 270              $z0
 271          );
 272  
 273          return ltrim($xy, "\0");
 274      }
 275  
 276      /**
 277       * Perform polynomial multiplication on 2x 32-bit numbers, returning
 278       * a 64-bit number
 279       *
 280       * @param string $x
 281       * @param string $y
 282       * @return string
 283       * @link https://www.bearssl.org/constanttime.html#ghash-for-gcm
 284       */
 285      private static function subMultiply($x, $y)
 286      {
 287          $x = unpack('N', $x)[1];
 288          $y = unpack('N', $y)[1];
 289  
 290          $x0 = $x & 0x11111111;
 291          $x1 = $x & 0x22222222;
 292          $x2 = $x & 0x44444444;
 293          $x3 = $x & 0x88888888;
 294  
 295          $y0 = $y & 0x11111111;
 296          $y1 = $y & 0x22222222;
 297          $y2 = $y & 0x44444444;
 298          $y3 = $y & 0x88888888;
 299  
 300          $z0 = ($x0 * $y0) ^ ($x1 * $y3) ^ ($x2 * $y2) ^ ($x3 * $y1);
 301          $z1 = ($x0 * $y1) ^ ($x1 * $y0) ^ ($x2 * $y3) ^ ($x3 * $y2);
 302          $z2 = ($x0 * $y2) ^ ($x1 * $y1) ^ ($x2 * $y0) ^ ($x3 * $y3);
 303          $z3 = ($x0 * $y3) ^ ($x1 * $y2) ^ ($x2 * $y1) ^ ($x3 * $y0);
 304  
 305          $z0 &= 0x1111111111111111;
 306          $z1 &= 0x2222222222222222;
 307          $z2 &= 0x4444444444444444;
 308          $z3 &= -8608480567731124088; // 0x8888888888888888 gets interpreted as a float
 309  
 310          $z = $z0 | $z1 | $z2 | $z3;
 311  
 312          return pack('J', $z);
 313      }
 314  
 315      /**
 316       * Adds two numbers
 317       *
 318       * @param string $x
 319       * @param string $y
 320       * @return string
 321       */
 322      private static function subAdd2($x, $y)
 323      {
 324          $length = max(strlen($x), strlen($y));
 325          $x = str_pad($x, $length, "\0", STR_PAD_LEFT);
 326          $y = str_pad($y, $length, "\0", STR_PAD_LEFT);
 327          return $x ^ $y;
 328      }
 329  
 330      /**
 331       * Adds three numbers
 332       *
 333       * @param string $x
 334       * @param string $y
 335       * @return string
 336       */
 337      private static function subAdd3($x, $y, $z)
 338      {
 339          $length = max(strlen($x), strlen($y), strlen($z));
 340          $x = str_pad($x, $length, "\0", STR_PAD_LEFT);
 341          $y = str_pad($y, $length, "\0", STR_PAD_LEFT);
 342          $z = str_pad($z, $length, "\0", STR_PAD_LEFT);
 343          return $x ^ $y ^ $z;
 344      }
 345  
 346      /**
 347       * Adds two BinaryFieldIntegers.
 348       *
 349       * @return static
 350       */
 351      public function add(self $y)
 352      {
 353          static::checkInstance($this, $y);
 354  
 355          $length = strlen(static::$modulo[$this->instanceID]);
 356  
 357          $x = str_pad($this->value, $length, "\0", STR_PAD_LEFT);
 358          $y = str_pad($y->value, $length, "\0", STR_PAD_LEFT);
 359  
 360          return new static($this->instanceID, $x ^ $y);
 361      }
 362  
 363      /**
 364       * Subtracts two BinaryFieldIntegers.
 365       *
 366       * @return static
 367       */
 368      public function subtract(self $x)
 369      {
 370          return $this->add($x);
 371      }
 372  
 373      /**
 374       * Multiplies two BinaryFieldIntegers.
 375       *
 376       * @return static
 377       */
 378      public function multiply(self $y)
 379      {
 380          static::checkInstance($this, $y);
 381  
 382          return new static($this->instanceID, static::polynomialMultiply($this->value, $y->value));
 383      }
 384  
 385      /**
 386       * Returns the modular inverse of a BinaryFieldInteger
 387       *
 388       * @return static
 389       */
 390      public function modInverse()
 391      {
 392          $remainder0 = static::$modulo[$this->instanceID];
 393          $remainder1 = $this->value;
 394  
 395          if ($remainder1 == '') {
 396              return new static($this->instanceID);
 397          }
 398  
 399          $aux0 = "\0";
 400          $aux1 = "\1";
 401          while ($remainder1 != "\1") {
 402              list($q, $r) = static::polynomialDivide($remainder0, $remainder1);
 403              $remainder0 = $remainder1;
 404              $remainder1 = $r;
 405              // the auxiliary in row n is given by the sum of the auxiliary in
 406              // row n-2 and the product of the quotient and the auxiliary in row
 407              // n-1
 408              $temp = static::polynomialMultiply($aux1, $q);
 409              $aux = str_pad($aux0, strlen($temp), "\0", STR_PAD_LEFT) ^
 410                     str_pad($temp, strlen($aux0), "\0", STR_PAD_LEFT);
 411              $aux0 = $aux1;
 412              $aux1 = $aux;
 413          }
 414  
 415          $temp = new static($this->instanceID);
 416          $temp->value = ltrim($aux1, "\0");
 417          return $temp;
 418      }
 419  
 420      /**
 421       * Divides two PrimeFieldIntegers.
 422       *
 423       * @return static
 424       */
 425      public function divide(self $x)
 426      {
 427          static::checkInstance($this, $x);
 428  
 429          $x = $x->modInverse();
 430          return $this->multiply($x);
 431      }
 432  
 433      /**
 434       * Negate
 435       *
 436       * A negative number can be written as 0-12. With modulos, 0 is the same thing as the modulo
 437       * so 0-12 is the same thing as modulo-12
 438       *
 439       * @return object
 440       */
 441      public function negate()
 442      {
 443          $x = str_pad($this->value, strlen(static::$modulo[$this->instanceID]), "\0", STR_PAD_LEFT);
 444  
 445          return new static($this->instanceID, $x ^ static::$modulo[$this->instanceID]);
 446      }
 447  
 448      /**
 449       * Returns the modulo
 450       *
 451       * @return string
 452       */
 453      public static function getModulo($instanceID)
 454      {
 455          return static::$modulo[$instanceID];
 456      }
 457  
 458      /**
 459       * Converts an Integer to a byte string (eg. base-256).
 460       *
 461       * @return string
 462       */
 463      public function toBytes()
 464      {
 465          return str_pad($this->value, strlen(static::$modulo[$this->instanceID]), "\0", STR_PAD_LEFT);
 466      }
 467  
 468      /**
 469       * Converts an Integer to a hex string (eg. base-16).
 470       *
 471       * @return string
 472       */
 473      public function toHex()
 474      {
 475          return Strings::bin2hex($this->toBytes());
 476      }
 477  
 478      /**
 479       * Converts an Integer to a bit string (eg. base-2).
 480       *
 481       * @return string
 482       */
 483      public function toBits()
 484      {
 485          //return str_pad(BinaryField::base256ToBase2($this->value), strlen(static::$modulo[$this->instanceID]), '0', STR_PAD_LEFT);
 486          return BinaryField::base256ToBase2($this->value);
 487      }
 488  
 489      /**
 490       * Converts an Integer to a BigInteger
 491       *
 492       * @return string
 493       */
 494      public function toBigInteger()
 495      {
 496          return new BigInteger($this->value, 256);
 497      }
 498  
 499      /**
 500       *  __toString() magic method
 501       *
 502       */
 503      public function __toString()
 504      {
 505          return (string) $this->toBigInteger();
 506      }
 507  
 508      /**
 509       *  __debugInfo() magic method
 510       *
 511       */
 512      public function __debugInfo()
 513      {
 514          return ['value' => $this->toHex()];
 515      }
 516  }