1<?php
2
3/**
4 * Base BigInteger Engine
5 *
6 * PHP version 5 and 7
7 *
8 * @category  Math
9 * @package   BigInteger
10 * @author    Jim Wigginton <terrafrost@php.net>
11 * @copyright 2017 Jim Wigginton
12 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
13 * @link      http://pear.php.net/package/Math_BigInteger
14 */
15
16namespace phpseclib3\Math\BigInteger\Engines;
17
18use ParagonIE\ConstantTime\Hex;
19use phpseclib3\Common\Functions\Strings;
20use phpseclib3\Crypt\Random;
21use phpseclib3\Exception\BadConfigurationException;
22use phpseclib3\Math\BigInteger;
23
24/**
25 * Base Engine.
26 *
27 * @package Engine
28 * @author  Jim Wigginton <terrafrost@php.net>
29 * @access  public
30 */
31abstract class Engine implements \JsonSerializable
32{
33    /* final protected */ const PRIMES = [
34        3,   5,   7,   11,  13,  17,  19,  23,  29,  31,  37,  41,  43,  47,  53,  59,
35        61,  67,  71,  73,  79,  83,  89,  97,  101, 103, 107, 109, 113, 127, 131, 137,
36        139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
37        229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
38        317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
39        421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
40        521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617,
41        619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727,
42        733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
43        839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
44        953, 967, 971, 977, 983, 991, 997,
45    ];
46
47    /**
48     * BigInteger(0)
49     *
50     * @var array<class-string<static>, static>
51     */
52    protected static $zero = [];
53
54    /**
55     * BigInteger(1)
56     *
57     * @var array<class-string<static>, static>
58     */
59    protected static $one  = [];
60
61    /**
62     * BigInteger(2)
63     *
64     * @var array<class-string<static>, static>
65     */
66    protected static $two = [];
67
68    /**
69     * Modular Exponentiation Engine
70     *
71     * @var array<class-string<static>, class-string<static>>
72     */
73    protected static $modexpEngine;
74
75    /**
76     * Engine Validity Flag
77     *
78     * @var array<class-string<static>, bool>
79     */
80    protected static $isValidEngine;
81
82    /**
83     * Holds the BigInteger's value
84     *
85     * @var \GMP|string|array|int
86     */
87    protected $value;
88
89    /**
90     * Holds the BigInteger's sign
91     *
92     * @var bool
93     */
94    protected $is_negative;
95
96    /**
97     * Precision
98     *
99     * @see static::setPrecision()
100     * @var int
101     */
102    protected $precision = -1;
103
104    /**
105     * Precision Bitmask
106     *
107     * @see static::setPrecision()
108     * @var static|false
109     */
110    protected $bitmask = false;
111
112    /**
113     * Recurring Modulo Function
114     *
115     * @var callable
116     */
117    protected $reduce;
118
119    /**
120     * Mode independent value used for serialization.
121     *
122     * @see self::__sleep()
123     * @see self::__wakeup()
124     * @var string
125     */
126    protected $hex;
127
128    /**
129     * Default constructor
130     *
131     * @param int|numeric-string $x integer Base-10 number or base-$base number if $base set.
132     * @param int $base
133     */
134    public function __construct($x = 0, $base = 10)
135    {
136        if (!array_key_exists(static::class, static::$zero)) {
137            static::$zero[static::class] = null; // Placeholder to prevent infinite loop.
138            static::$zero[static::class] = new static(0);
139            static::$one[static::class] = new static(1);
140            static::$two[static::class] = new static(2);
141        }
142
143        // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48
144        // '0' is the only value like this per http://php.net/empty
145        if (empty($x) && (abs($base) != 256 || $x !== '0')) {
146            return;
147        }
148
149        switch ($base) {
150            case -256:
151            case 256:
152                if ($base == -256 && (ord($x[0]) & 0x80)) {
153                    $this->value = ~$x;
154                    $this->is_negative = true;
155                } else {
156                    $this->value = $x;
157                    $this->is_negative = false;
158                }
159
160                $this->initialize($base);
161
162                if ($this->is_negative) {
163                    $temp = $this->add(new static('-1'));
164                    $this->value = $temp->value;
165                }
166                break;
167            case -16:
168            case 16:
169                if ($base > 0 && $x[0] == '-') {
170                    $this->is_negative = true;
171                    $x = substr($x, 1);
172                }
173
174                $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);
175
176                $is_negative = false;
177                if ($base < 0 && hexdec($x[0]) >= 8) {
178                    $this->is_negative = $is_negative = true;
179                    $x = Hex::encode(~Hex::decode($x));
180                }
181
182                $this->value = $x;
183                $this->initialize($base);
184
185                if ($is_negative) {
186                    $temp = $this->add(new static('-1'));
187                    $this->value = $temp->value;
188                }
189                break;
190            case -10:
191            case 10:
192                // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that
193                // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals)
194                // [^-0-9].*: find any non-numeric characters and then any characters that follow that
195                $this->value = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x);
196                if (!strlen($this->value) || $this->value == '-') {
197                    $this->value = '0';
198                }
199                $this->initialize($base);
200                break;
201            case -2:
202            case 2:
203                if ($base > 0 && $x[0] == '-') {
204                    $this->is_negative = true;
205                    $x = substr($x, 1);
206                }
207
208                $x = preg_replace('#^([01]*).*#', '$1', $x);
209
210                $temp = new static(Strings::bits2bin($x), 128 * $base); // ie. either -16 or +16
211                $this->value = $temp->value;
212                if ($temp->is_negative) {
213                    $this->is_negative = true;
214                }
215
216                break;
217            default:
218                // base not supported, so we'll let $this == 0
219        }
220    }
221
222    /**
223     * Sets engine type.
224     *
225     * Throws an exception if the type is invalid
226     *
227     * @param class-string<Engine> $engine
228     */
229    public static function setModExpEngine($engine)
230    {
231        $fqengine = '\\phpseclib3\\Math\\BigInteger\\Engines\\' . static::ENGINE_DIR . '\\' . $engine;
232        if (!class_exists($fqengine) || !method_exists($fqengine, 'isValidEngine')) {
233            throw new \InvalidArgumentException("$engine is not a valid engine");
234        }
235        if (!$fqengine::isValidEngine()) {
236            throw new BadConfigurationException("$engine is not setup correctly on this system");
237        }
238        static::$modexpEngine[static::class] = $fqengine;
239    }
240
241    /**
242     * Converts a BigInteger to a byte string (eg. base-256).
243     *
244     * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
245     * saved as two's compliment.
246     * @return string
247     */
248    protected function toBytesHelper()
249    {
250        $comparison = $this->compare(new static());
251        if ($comparison == 0) {
252            return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
253        }
254
255        $temp = $comparison < 0 ? $this->add(new static(1)) : $this;
256        $bytes = $temp->toBytes();
257
258        if (!strlen($bytes)) { // eg. if the number we're trying to convert is -1
259            $bytes = chr(0);
260        }
261
262        if (ord($bytes[0]) & 0x80) {
263            $bytes = chr(0) . $bytes;
264        }
265
266        return $comparison < 0 ? ~$bytes : $bytes;
267    }
268
269    /**
270     * Converts a BigInteger to a hex string (eg. base-16).
271     *
272     * @param bool $twos_compliment
273     * @return string
274     */
275    public function toHex($twos_compliment = false)
276    {
277        return Hex::encode($this->toBytes($twos_compliment));
278    }
279
280    /**
281     * Converts a BigInteger to a bit string (eg. base-2).
282     *
283     * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
284     * saved as two's compliment.
285     *
286     * @param bool $twos_compliment
287     * @return string
288     */
289    public function toBits($twos_compliment = false)
290    {
291        $hex = $this->toBytes($twos_compliment);
292        $bits = Strings::bin2bits($hex);
293
294        $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0');
295
296        if ($twos_compliment && $this->compare(new static()) > 0 && $this->precision <= 0) {
297            return '0' . $result;
298        }
299
300        return $result;
301    }
302
303    /**
304     * Calculates modular inverses.
305     *
306     * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
307     *
308     * {@internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information.}
309     *
310     * @param Engine $n
311     * @return static|false
312     */
313    protected function modInverseHelper(Engine $n)
314    {
315        // $x mod -$n == $x mod $n.
316        $n = $n->abs();
317
318        if ($this->compare(static::$zero[static::class]) < 0) {
319            $temp = $this->abs();
320            $temp = $temp->modInverse($n);
321            return $this->normalize($n->subtract($temp));
322        }
323
324        extract($this->extendedGCD($n));
325        /**
326         * @var Engine $gcd
327         * @var Engine $x
328         */
329
330        if (!$gcd->equals(static::$one[static::class])) {
331            return false;
332        }
333
334        $x = $x->compare(static::$zero[static::class]) < 0 ? $x->add($n) : $x;
335
336        return $this->compare(static::$zero[static::class]) < 0 ? $this->normalize($n->subtract($x)) : $this->normalize($x);
337    }
338
339    /**
340     * Serialize
341     *
342     * Will be called, automatically, when serialize() is called on a BigInteger object.
343     *
344     * @return array
345     */
346    public function __sleep()
347    {
348        $this->hex = $this->toHex(true);
349        $vars = ['hex'];
350        if ($this->precision > 0) {
351            $vars[] = 'precision';
352        }
353        return $vars;
354    }
355
356    /**
357     * Serialize
358     *
359     * Will be called, automatically, when unserialize() is called on a BigInteger object.
360     *
361     * @return void
362     */
363    public function __wakeup()
364    {
365        $temp = new static($this->hex, -16);
366        $this->value = $temp->value;
367        $this->is_negative = $temp->is_negative;
368        if ($this->precision > 0) {
369            // recalculate $this->bitmask
370            $this->setPrecision($this->precision);
371        }
372    }
373
374    /**
375     * JSON Serialize
376     *
377     * Will be called, automatically, when json_encode() is called on a BigInteger object.
378     */
379    #[\ReturnTypeWillChange]
380    public function jsonSerialize()
381    {
382        $result = ['hex' => $this->toHex(true)];
383        if ($this->precision > 0) {
384            $result['precision'] = $this->precision;
385        }
386        return $result;
387    }
388
389    /**
390     * Converts a BigInteger to a base-10 number.
391     *
392     * @return string
393     */
394    public function __toString()
395    {
396        return $this->toString();
397    }
398
399    /**
400     *  __debugInfo() magic method
401     *
402     * Will be called, automatically, when print_r() or var_dump() are called
403     *
404     * @return array
405     */
406    public function __debugInfo()
407    {
408        $result = [
409            'value' => '0x' . $this->toHex(true),
410            'engine' => basename(static::class)
411        ];
412        return $this->precision > 0 ? $result + ['precision' => $this->precision] : $result;
413    }
414
415    /**
416     * Set Precision
417     *
418     * Some bitwise operations give different results depending on the precision being used.  Examples include left
419     * shift, not, and rotates.
420     *
421     * @param int $bits
422     */
423    public function setPrecision($bits)
424    {
425        if ($bits < 1) {
426            $this->precision = -1;
427            $this->bitmask = false;
428
429            return;
430        }
431        $this->precision = $bits;
432        $this->bitmask = static::setBitmask($bits);
433
434        $temp = $this->normalize($this);
435        $this->value = $temp->value;
436    }
437
438    /**
439     * Get Precision
440     *
441     * Returns the precision if it exists, -1 if it doesn't
442     *
443     * @return int
444     */
445    public function getPrecision()
446    {
447        return $this->precision;
448    }
449
450    /**
451     * Set Bitmask
452     * @return static
453     * @param int $bits
454     * @see self::setPrecision()
455     */
456    protected static function setBitmask($bits)
457    {
458        return new static(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
459    }
460
461    /**
462     * Logical Not
463     *
464     * @return Engine|string
465     */
466    public function bitwise_not()
467    {
468        // calculuate "not" without regard to $this->precision
469        // (will always result in a smaller number.  ie. ~1 isn't 1111 1110 - it's 0)
470        $temp = $this->toBytes();
471        if ($temp == '') {
472            return $this->normalize(static::$zero[static::class]);
473        }
474        $pre_msb = decbin(ord($temp[0]));
475        $temp = ~$temp;
476        $msb = decbin(ord($temp[0]));
477        if (strlen($msb) == 8) {
478            $msb = substr($msb, strpos($msb, '0'));
479        }
480        $temp[0] = chr(bindec($msb));
481
482        // see if we need to add extra leading 1's
483        $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8;
484        $new_bits = $this->precision - $current_bits;
485        if ($new_bits <= 0) {
486            return $this->normalize(new static($temp, 256));
487        }
488
489        // generate as many leading 1's as we need to.
490        $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
491
492        self::base256_lshift($leading_ones, $current_bits);
493
494        $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT);
495
496        return $this->normalize(new static($leading_ones | $temp, 256));
497    }
498
499    /**
500     * Logical Left Shift
501     *
502     * Shifts binary strings $shift bits, essentially multiplying by 2**$shift.
503     *
504     * @param string $x
505     * @param int $shift
506     * @return void
507     */
508    protected static function base256_lshift(&$x, $shift)
509    {
510        if ($shift == 0) {
511            return;
512        }
513
514        $num_bytes = $shift >> 3; // eg. floor($shift/8)
515        $shift &= 7; // eg. $shift % 8
516
517        $carry = 0;
518        for ($i = strlen($x) - 1; $i >= 0; --$i) {
519            $temp = ord($x[$i]) << $shift | $carry;
520            $x[$i] = chr($temp);
521            $carry = $temp >> 8;
522        }
523        $carry = ($carry != 0) ? chr($carry) : '';
524        $x = $carry . $x . str_repeat(chr(0), $num_bytes);
525    }
526
527    /**
528     * Logical Left Rotate
529     *
530     * Instead of the top x bits being dropped they're appended to the shifted bit string.
531     *
532     * @param int $shift
533     * @return Engine
534     */
535    public function bitwise_leftRotate($shift)
536    {
537        $bits = $this->toBytes();
538
539        if ($this->precision > 0) {
540            $precision = $this->precision;
541            if (static::FAST_BITWISE) {
542                $mask = $this->bitmask->toBytes();
543            } else {
544                $mask = $this->bitmask->subtract(new static(1));
545                $mask = $mask->toBytes();
546            }
547        } else {
548            $temp = ord($bits[0]);
549            for ($i = 0; $temp >> $i; ++$i) {
550            }
551            $precision = 8 * strlen($bits) - 8 + $i;
552            $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
553        }
554
555        if ($shift < 0) {
556            $shift += $precision;
557        }
558        $shift %= $precision;
559
560        if (!$shift) {
561            return clone $this;
562        }
563
564        $left = $this->bitwise_leftShift($shift);
565        $left = $left->bitwise_and(new static($mask, 256));
566        $right = $this->bitwise_rightShift($precision - $shift);
567        $result = static::FAST_BITWISE ? $left->bitwise_or($right) : $left->add($right);
568        return $this->normalize($result);
569    }
570
571    /**
572     * Logical Right Rotate
573     *
574     * Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
575     *
576     * @param int $shift
577     * @return Engine
578     */
579    public function bitwise_rightRotate($shift)
580    {
581        return $this->bitwise_leftRotate(-$shift);
582    }
583
584    /**
585     * Returns the smallest and largest n-bit number
586     *
587     * @param int $bits
588     * @return array{min: static, max: static}
589     */
590    public static function minMaxBits($bits)
591    {
592        $bytes = $bits >> 3;
593        $min = str_repeat(chr(0), $bytes);
594        $max = str_repeat(chr(0xFF), $bytes);
595        $msb = $bits & 7;
596        if ($msb) {
597            $min = chr(1 << ($msb - 1)) . $min;
598            $max = chr((1 << $msb) - 1) . $max;
599        } else {
600            $min[0] = chr(0x80);
601        }
602        return [
603            'min' => new static($min, 256),
604            'max' => new static($max, 256)
605        ];
606    }
607
608    /**
609     * Return the size of a BigInteger in bits
610     *
611     * @return int
612     */
613    public function getLength()
614    {
615        return strlen($this->toBits());
616    }
617
618    /**
619     * Return the size of a BigInteger in bytes
620     *
621     * @return int
622     */
623    public function getLengthInBytes()
624    {
625        return strlen($this->toBytes());
626    }
627
628    /**
629     * Performs some pre-processing for powMod
630     *
631     * @param Engine $e
632     * @param Engine $n
633     * @return static|false
634     */
635    protected function powModOuter(Engine $e, Engine $n)
636    {
637        $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();
638
639        if ($e->compare(new static()) < 0) {
640            $e = $e->abs();
641
642            $temp = $this->modInverse($n);
643            if ($temp === false) {
644                return false;
645            }
646
647            return $this->normalize($temp->powModInner($e, $n));
648        }
649
650        return $this->powModInner($e, $n);
651    }
652
653    /**
654     * Sliding Window k-ary Modular Exponentiation
655     *
656     * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} /
657     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}.  In a departure from those algorithims,
658     * however, this function performs a modular reduction after every multiplication and squaring operation.
659     * As such, this function has the same preconditions that the reductions being used do.
660     *
661     * @template T of Engine
662     * @param Engine $x
663     * @param Engine $e
664     * @param Engine $n
665     * @param class-string<T> $class
666     * @return T
667     */
668    protected static function slidingWindow(Engine $x, Engine $e, Engine $n, $class)
669    {
670        static $window_ranges = [7, 25, 81, 241, 673, 1793]; // from BigInteger.java's oddModPow function
671        //static $window_ranges = [0, 7, 36, 140, 450, 1303, 3529]; // from MPM 7.3.1
672
673        $e_bits = $e->toBits();
674        $e_length = strlen($e_bits);
675
676        // calculate the appropriate window size.
677        // $window_size == 3 if $window_ranges is between 25 and 81, for example.
678        for ($i = 0, $window_size = 1; $i < count($window_ranges) && $e_length > $window_ranges[$i]; ++$window_size, ++$i) {
679        }
680
681        $n_value = $n->value;
682
683        if (method_exists(static::class, 'generateCustomReduction')) {
684            static::generateCustomReduction($n, $class);
685        }
686
687        // precompute $this^0 through $this^$window_size
688        $powers = [];
689        $powers[1] = static::prepareReduce($x->value, $n_value, $class);
690        $powers[2] = static::squareReduce($powers[1], $n_value, $class);
691
692        // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end
693        // in a 1.  ie. it's supposed to be odd.
694        $temp = 1 << ($window_size - 1);
695        for ($i = 1; $i < $temp; ++$i) {
696            $i2 = $i << 1;
697            $powers[$i2 + 1] = static::multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $class);
698        }
699
700        $result = new $class(1);
701        $result = static::prepareReduce($result->value, $n_value, $class);
702
703        for ($i = 0; $i < $e_length;) {
704            if (!$e_bits[$i]) {
705                $result = static::squareReduce($result, $n_value, $class);
706                ++$i;
707            } else {
708                for ($j = $window_size - 1; $j > 0; --$j) {
709                    if (!empty($e_bits[$i + $j])) {
710                        break;
711                    }
712                }
713
714                // eg. the length of substr($e_bits, $i, $j + 1)
715                for ($k = 0; $k <= $j; ++$k) {
716                    $result = static::squareReduce($result, $n_value, $class);
717                }
718
719                $result = static::multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $class);
720
721                $i += $j + 1;
722            }
723        }
724
725        $temp = new $class();
726        $temp->value = static::reduce($result, $n_value, $class);
727
728        return $temp;
729    }
730
731    /**
732     * Generates a random number of a certain size
733     *
734     * Bit length is equal to $size
735     *
736     * @param int $size
737     * @return Engine
738     */
739    public static function random($size)
740    {
741        extract(static::minMaxBits($size));
742        /**
743         * @var BigInteger $min
744         * @var BigInteger $max
745         */
746        return static::randomRange($min, $max);
747    }
748
749    /**
750     * Generates a random prime number of a certain size
751     *
752     * Bit length is equal to $size
753     *
754     * @param int $size
755     * @return Engine
756     */
757    public static function randomPrime($size)
758    {
759        extract(static::minMaxBits($size));
760        /**
761         * @var static $min
762         * @var static $max
763         */
764        return static::randomRangePrime($min, $max);
765    }
766
767    /**
768     * Performs some pre-processing for randomRangePrime
769     *
770     * @param Engine $min
771     * @param Engine $max
772     * @return static|false
773     */
774    protected static function randomRangePrimeOuter(Engine $min, Engine $max)
775    {
776        $compare = $max->compare($min);
777
778        if (!$compare) {
779            return $min->isPrime() ? $min : false;
780        } elseif ($compare < 0) {
781            // if $min is bigger then $max, swap $min and $max
782            $temp = $max;
783            $max = $min;
784            $min = $temp;
785        }
786
787        $x = static::randomRange($min, $max);
788
789        return static::randomRangePrimeInner($x, $min, $max);
790    }
791
792    /**
793     * Generate a random number between a range
794     *
795     * Returns a random number between $min and $max where $min and $max
796     * can be defined using one of the two methods:
797     *
798     * BigInteger::randomRange($min, $max)
799     * BigInteger::randomRange($max, $min)
800     *
801     * @param Engine $min
802     * @param Engine $max
803     * @return Engine
804     */
805    protected static function randomRangeHelper(Engine $min, Engine $max)
806    {
807        $compare = $max->compare($min);
808
809        if (!$compare) {
810            return $min;
811        } elseif ($compare < 0) {
812            // if $min is bigger then $max, swap $min and $max
813            $temp = $max;
814            $max = $min;
815            $min = $temp;
816        }
817
818        if (!isset(static::$one[static::class])) {
819            static::$one[static::class] = new static(1);
820        }
821
822        $max = $max->subtract($min->subtract(static::$one[static::class]));
823
824        $size = strlen(ltrim($max->toBytes(), chr(0)));
825
826        /*
827            doing $random % $max doesn't work because some numbers will be more likely to occur than others.
828            eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145
829            would produce 5 whereas the only value of random that could produce 139 would be 139. ie.
830            not all numbers would be equally likely. some would be more likely than others.
831
832            creating a whole new random number until you find one that is within the range doesn't work
833            because, for sufficiently small ranges, the likelihood that you'd get a number within that range
834            would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability
835            would be pretty high that $random would be greater than $max.
836
837            phpseclib works around this using the technique described here:
838
839            http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string
840        */
841        $random_max = new static(chr(1) . str_repeat("\0", $size), 256);
842        $random = new static(Random::string($size), 256);
843
844        list($max_multiple) = $random_max->divide($max);
845        $max_multiple = $max_multiple->multiply($max);
846
847        while ($random->compare($max_multiple) >= 0) {
848            $random = $random->subtract($max_multiple);
849            $random_max = $random_max->subtract($max_multiple);
850            $random = $random->bitwise_leftShift(8);
851            $random = $random->add(new static(Random::string(1), 256));
852            $random_max = $random_max->bitwise_leftShift(8);
853            list($max_multiple) = $random_max->divide($max);
854            $max_multiple = $max_multiple->multiply($max);
855        }
856        list(, $random) = $random->divide($max);
857
858        return $random->add($min);
859    }
860
861    /**
862     * Performs some post-processing for randomRangePrime
863     *
864     * @param Engine $x
865     * @param Engine $min
866     * @param Engine $max
867     * @return static|false
868     */
869    protected static function randomRangePrimeInner(Engine $x, Engine $min, Engine $max)
870    {
871        if (!isset(static::$two[static::class])) {
872            static::$two[static::class] = new static('2');
873        }
874
875        $x->make_odd();
876        if ($x->compare($max) > 0) {
877            // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range
878            if ($min->equals($max)) {
879                return false;
880            }
881            $x = clone $min;
882            $x->make_odd();
883        }
884
885        $initial_x = clone $x;
886
887        while (true) {
888            if ($x->isPrime()) {
889                return $x;
890            }
891
892            $x = $x->add(static::$two[static::class]);
893
894            if ($x->compare($max) > 0) {
895                $x = clone $min;
896                if ($x->equals(static::$two[static::class])) {
897                    return $x;
898                }
899                $x->make_odd();
900            }
901
902            if ($x->equals($initial_x)) {
903                return false;
904            }
905        }
906    }
907
908    /**
909     * Sets the $t parameter for primality testing
910     *
911     * @return int
912     */
913    protected function setupIsPrime()
914    {
915        $length = $this->getLengthInBytes();
916
917        // see HAC 4.49 "Note (controlling the error probability)"
918        // @codingStandardsIgnoreStart
919             if ($length >= 163) { $t =  2; } // floor(1300 / 8)
920        else if ($length >= 106) { $t =  3; } // floor( 850 / 8)
921        else if ($length >= 81 ) { $t =  4; } // floor( 650 / 8)
922        else if ($length >= 68 ) { $t =  5; } // floor( 550 / 8)
923        else if ($length >= 56 ) { $t =  6; } // floor( 450 / 8)
924        else if ($length >= 50 ) { $t =  7; } // floor( 400 / 8)
925        else if ($length >= 43 ) { $t =  8; } // floor( 350 / 8)
926        else if ($length >= 37 ) { $t =  9; } // floor( 300 / 8)
927        else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8)
928        else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8)
929        else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8)
930        else                     { $t = 27; }
931        // @codingStandardsIgnoreEnd
932
933        return $t;
934    }
935
936    /**
937     * Tests Primality
938     *
939     * Uses the {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}.
940     * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24} for more info.
941     *
942     * @param int $t
943     * @return bool
944     */
945    protected function testPrimality($t)
946    {
947        if (!$this->testSmallPrimes()) {
948            return false;
949        }
950
951        $n   = clone $this;
952        $n_1 = $n->subtract(static::$one[static::class]);
953        $n_2 = $n->subtract(static::$two[static::class]);
954
955        $r = clone $n_1;
956        $s = static::scan1divide($r);
957
958        for ($i = 0; $i < $t; ++$i) {
959            $a = static::randomRange(static::$two[static::class], $n_2);
960            $y = $a->modPow($r, $n);
961
962            if (!$y->equals(static::$one[static::class]) && !$y->equals($n_1)) {
963                for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) {
964                    $y = $y->modPow(static::$two[static::class], $n);
965                    if ($y->equals(static::$one[static::class])) {
966                        return false;
967                    }
968                }
969
970                if (!$y->equals($n_1)) {
971                    return false;
972                }
973            }
974        }
975
976        return true;
977    }
978
979    /**
980     * Checks a numer to see if it's prime
981     *
982     * Assuming the $t parameter is not set, this function has an error rate of 2**-80.  The main motivation for the
983     * $t parameter is distributability.  BigInteger::randomPrime() can be distributed across multiple pageloads
984     * on a website instead of just one.
985     *
986     * @param int|bool $t
987     * @return bool
988     */
989    public function isPrime($t = false)
990    {
991        if (!$t) {
992            $t = $this->setupIsPrime();
993        }
994        return $this->testPrimality($t);
995    }
996
997    /**
998     * Performs a few preliminary checks on root
999     *
1000     * @param int $n
1001     * @return Engine
1002     */
1003    protected function rootHelper($n)
1004    {
1005        if ($n < 1) {
1006            return clone static::$zero[static::class];
1007        } // we want positive exponents
1008        if ($this->compare(static::$one[static::class]) < 0) {
1009            return clone static::$zero[static::class];
1010        } // we want positive numbers
1011        if ($this->compare(static::$two[static::class]) < 0) {
1012            return clone static::$one[static::class];
1013        } // n-th root of 1 or 2 is 1
1014
1015        return $this->rootInner($n);
1016    }
1017
1018    /**
1019     * Calculates the nth root of a biginteger.
1020     *
1021     * Returns the nth root of a positive biginteger, where n defaults to 2
1022     *
1023     * {@internal This function is based off of {@link http://mathforum.org/library/drmath/view/52605.html this page} and {@link http://stackoverflow.com/questions/11242920/calculating-nth-root-with-bcmath-in-php this stackoverflow question}.}
1024     *
1025     * @param int $n
1026     * @return Engine
1027     */
1028    protected function rootInner($n)
1029    {
1030        $n = new static($n);
1031
1032        // g is our guess number
1033        $g = static::$two[static::class];
1034        // while (g^n < num) g=g*2
1035        while ($g->pow($n)->compare($this) < 0) {
1036            $g = $g->multiply(static::$two[static::class]);
1037        }
1038        // if (g^n==num) num is a power of 2, we're lucky, end of job
1039        // == 0 bccomp(bcpow($g, $n), $n->value)==0
1040        if ($g->pow($n)->equals($this) > 0) {
1041            $root = $g;
1042            return $this->normalize($root);
1043        }
1044
1045        // if we're here num wasn't a power of 2 :(
1046        $og = $g; // og means original guess and here is our upper bound
1047        $g = $g->divide(static::$two[static::class])[0]; // g is set to be our lower bound
1048        $step = $og->subtract($g)->divide(static::$two[static::class])[0]; // step is the half of upper bound - lower bound
1049        $g = $g->add($step); // we start at lower bound + step , basically in the middle of our interval
1050
1051        // while step>1
1052
1053        while ($step->compare(static::$one[static::class]) == 1) {
1054            $guess = $g->pow($n);
1055            $step = $step->divide(static::$two[static::class])[0];
1056            $comp = $guess->compare($this); // compare our guess with real number
1057            switch ($comp) {
1058                case -1: // if guess is lower we add the new step
1059                    $g = $g->add($step);
1060                    break;
1061                case 1: // if guess is higher we sub the new step
1062                    $g = $g->subtract($step);
1063                    break;
1064                case 0: // if guess is exactly the num we're done, we return the value
1065                    $root = $g;
1066                    break 2;
1067            }
1068        }
1069
1070        if ($comp == 1) {
1071            $g = $g->subtract($step);
1072        }
1073
1074        // whatever happened, g is the closest guess we can make so return it
1075        $root = $g;
1076
1077        return $this->normalize($root);
1078    }
1079
1080    /**
1081     * Calculates the nth root of a biginteger.
1082     *
1083     * @param int $n
1084     * @return Engine
1085     */
1086    public function root($n = 2)
1087    {
1088        return $this->rootHelper($n);
1089    }
1090
1091    /**
1092     * Return the minimum BigInteger between an arbitrary number of BigIntegers.
1093     *
1094     * @param array $nums
1095     * @return Engine
1096     */
1097    protected static function minHelper(array $nums)
1098    {
1099        if (count($nums) == 1) {
1100            return $nums[0];
1101        }
1102        $min = $nums[0];
1103        for ($i = 1; $i < count($nums); $i++) {
1104            $min = $min->compare($nums[$i]) > 0 ? $nums[$i] : $min;
1105        }
1106        return $min;
1107    }
1108
1109    /**
1110     * Return the minimum BigInteger between an arbitrary number of BigIntegers.
1111     *
1112     * @param array $nums
1113     * @return Engine
1114     */
1115    protected static function maxHelper(array $nums)
1116    {
1117        if (count($nums) == 1) {
1118            return $nums[0];
1119        }
1120        $max = $nums[0];
1121        for ($i = 1; $i < count($nums); $i++) {
1122            $max = $max->compare($nums[$i]) < 0 ? $nums[$i] : $max;
1123        }
1124        return $max;
1125    }
1126
1127    /**
1128     * Create Recurring Modulo Function
1129     *
1130     * Sometimes it may be desirable to do repeated modulos with the same number outside of
1131     * modular exponentiation
1132     *
1133     * @return callable
1134     */
1135    public function createRecurringModuloFunction()
1136    {
1137        $class = static::class;
1138
1139        $fqengine = !method_exists(static::$modexpEngine[static::class], 'reduce') ?
1140            '\\phpseclib3\\Math\\BigInteger\\Engines\\' . static::ENGINE_DIR . '\\DefaultEngine' :
1141            static::$modexpEngine[static::class];
1142        if (method_exists($fqengine, 'generateCustomReduction')) {
1143            $func = $fqengine::generateCustomReduction($this, static::class);
1144            return eval('return function(' . static::class . ' $x) use ($func, $class) {
1145                $r = new $class();
1146                $r->value = $func($x->value);
1147                return $r;
1148            };');
1149        }
1150        $n = $this->value;
1151        return eval('return function(' . static::class . ' $x) use ($n, $fqengine, $class) {
1152            $r = new $class();
1153            $r->value = $fqengine::reduce($x->value, $n, $class);
1154            return $r;
1155        };');
1156    }
1157
1158    /**
1159     * Calculates the greatest common divisor and Bezout's identity.
1160     *
1161     * @param Engine $n
1162     * @return array{gcd: Engine, x: Engine, y: Engine}
1163     */
1164    protected function extendedGCDHelper(Engine $n)
1165    {
1166        $u = clone $this;
1167        $v = clone $n;
1168
1169        $one = new static(1);
1170        $zero = new static();
1171
1172        $a = clone $one;
1173        $b = clone $zero;
1174        $c = clone $zero;
1175        $d = clone $one;
1176
1177        while (!$v->equals($zero)) {
1178            list($q) = $u->divide($v);
1179
1180            $temp = $u;
1181            $u = $v;
1182            $v = $temp->subtract($v->multiply($q));
1183
1184            $temp = $a;
1185            $a = $c;
1186            $c = $temp->subtract($a->multiply($q));
1187
1188            $temp = $b;
1189            $b = $d;
1190            $d = $temp->subtract($b->multiply($q));
1191        }
1192
1193        return [
1194            'gcd' => $u,
1195            'x' => $a,
1196            'y' => $b
1197        ];
1198    }
1199
1200    /**
1201     * Bitwise Split
1202     *
1203     * Splits BigInteger's into chunks of $split bits
1204     *
1205     * @param int $split
1206     * @return Engine[]
1207     */
1208    public function bitwise_split($split)
1209    {
1210        if ($split < 1) {
1211            throw new \RuntimeException('Offset must be greater than 1');
1212        }
1213
1214        $mask = static::$one[static::class]->bitwise_leftShift($split)->subtract(static::$one[static::class]);
1215
1216        $num = clone $this;
1217
1218        $vals = [];
1219        while (!$num->equals(static::$zero[static::class])) {
1220            $vals[] = $num->bitwise_and($mask);
1221            $num = $num->bitwise_rightShift($split);
1222        }
1223
1224        return array_reverse($vals);
1225    }
1226
1227    /**
1228     * Logical And
1229     *
1230     * @param Engine $x
1231     * @return Engine
1232     */
1233    protected function bitwiseAndHelper(Engine $x)
1234    {
1235        $left = $this->toBytes(true);
1236        $right = $x->toBytes(true);
1237
1238        $length = max(strlen($left), strlen($right));
1239
1240        $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
1241        $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
1242
1243        return $this->normalize(new static($left & $right, -256));
1244    }
1245
1246    /**
1247     * Logical Or
1248     *
1249     * @param Engine $x
1250     * @return Engine
1251     */
1252    protected function bitwiseOrHelper(Engine $x)
1253    {
1254        $left = $this->toBytes(true);
1255        $right = $x->toBytes(true);
1256
1257        $length = max(strlen($left), strlen($right));
1258
1259        $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
1260        $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
1261
1262        return $this->normalize(new static($left | $right, -256));
1263    }
1264
1265    /**
1266     * Logical Exclusive Or
1267     *
1268     * @param Engine $x
1269     * @return Engine
1270     */
1271    protected function bitwiseXorHelper(Engine $x)
1272    {
1273        $left = $this->toBytes(true);
1274        $right = $x->toBytes(true);
1275
1276        $length = max(strlen($left), strlen($right));
1277
1278
1279        $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
1280        $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
1281        return $this->normalize(new static($left ^ $right, -256));
1282    }
1283}
1284