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