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
21namespace phpseclib3\Math\BinaryField;
22
23use phpseclib3\Common\Functions\Strings;
24use phpseclib3\Math\BigInteger;
25use phpseclib3\Math\BinaryField;
26use phpseclib3\Math\Common\FiniteField\Integer as Base;
27
28/**
29 * Binary Finite Fields
30 *
31 * @author  Jim Wigginton <terrafrost@php.net>
32 */
33class 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}
517