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 <terrafrost@php.net> 19 * @copyright 2017 Jim Wigginton 20 * @license http://www.opensource.org/licenses/mit-license.html MIT License 21 */ 22 23namespace phpseclib3\Math\BinaryField; 24 25use ParagonIE\ConstantTime\Hex; 26use phpseclib3\Math\BigInteger; 27use phpseclib3\Math\BinaryField; 28use phpseclib3\Math\Common\FiniteField\Integer as Base; 29 30/** 31 * Binary Finite Fields 32 * 33 * @package Math 34 * @author Jim Wigginton <terrafrost@php.net> 35 * @access public 36 */ 37class 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} 523