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