```/* <![CDATA[ */
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
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
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[]
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 :
182            \$s = static::polynomialMultiply(\$s, \$y);
183            \$length = max(strlen(\$r), strlen(\$s));
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
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);
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
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));
244        }
245
246        switch (true) {
247            case PHP_INT_SIZE == 8 && \$length <= 4:
248                return \$length != 4 ?
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(
267        );
268
269        \$z1 = self::subAdd3(\$z1, \$z2, \$z0);
270
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
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    /**
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));
331        return \$x ^ \$y;
332    }
333
334    /**
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));
347        return \$x ^ \$y ^ \$z;
348    }
349
350    /**
352     *
353     * @return static
354     */
356    {
357        static::checkInstance(\$this, \$y);
358
359        \$length = strlen(static::\$modulo[\$this->instanceID]);
360
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    {
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);
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    {
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    {
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    {
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```