Subversion Repositories oidplus

<?php

/**

 * Base BigInteger Engine

 *

 * PHP version 5 and 7

 *

 * @author    Jim Wigginton <terrafrost@php.net>

 * @copyright 2017 Jim Wigginton

 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License

 * @link      http://pear.php.net/package/Math_BigInteger

 */

namespace phpseclib3\Math\BigInteger\Engines;

use phpseclib3\Common\Functions\Strings;

use phpseclib3\Crypt\Random;

use phpseclib3\Exception\BadConfigurationException;

use phpseclib3\Math\BigInteger;

/**

 * Base Engine.

 *

 * @author  Jim Wigginton <terrafrost@php.net>

 */

abstract class Engine implements \JsonSerializable

{

    /* final protected */ const PRIMES = [

        3,   5,   7,   11,  13,  17,  19,  23,  29,  31,  37,  41,  43,  47,  53,  59,

        61,  67,  71,  73,  79,  83,  89,  97,  101, 103, 107, 109, 113, 127, 131, 137,

        139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,

        229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,

        317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,

        421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,

        521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617,

        619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727,

        733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,

        839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,

        953, 967, 971, 977, 983, 991, 997,

    ];

    /**

     * BigInteger(0)

     *

     * @var array<class-string<static>, static>

     */

    protected static $zero = [];

    /**

     * BigInteger(1)

     *

     * @var array<class-string<static>, static>

     */

    protected static $one  = [];

    /**

     * BigInteger(2)

     *

     * @var array<class-string<static>, static>

     */

    protected static $two = [];

    /**

     * Modular Exponentiation Engine

     *

     * @var array<class-string<static>, class-string<static>>

     */

    protected static $modexpEngine;

    /**

     * Engine Validity Flag

     *

     * @var array<class-string<static>, bool>

     */

    protected static $isValidEngine;

    /**

     * Holds the BigInteger's value

     *

     * @var \GMP|string|array|int

     */

    protected $value;

    /**

     * Holds the BigInteger's sign

     *

     * @var bool

     */

    protected $is_negative;

    /**

     * Precision

     *

     * @see static::setPrecision()

     * @var int

     */

    protected $precision = -1;

    /**

     * Precision Bitmask

     *

     * @see static::setPrecision()

     * @var static|false

     */

    protected $bitmask = false;

    /**

     * Recurring Modulo Function

     *

     * @var callable

     */

    protected $reduce;

    /**

     * Mode independent value used for serialization.

     *

     * @see self::__sleep()

     * @see self::__wakeup()

     * @var string

     */

    protected $hex;

    /**

     * Default constructor

     *

     * @param int|numeric-string $x integer Base-10 number or base-$base number if $base set.

     * @param int $base

     */

    public function __construct($x = 0, $base = 10)

    {

        if (!array_key_exists(static::class, static::$zero)) {

            static::$zero[static::class] = null; // Placeholder to prevent infinite loop.

            static::$zero[static::class] = new static(0);

            static::$one[static::class] = new static(1);

            static::$two[static::class] = new static(2);

        }

        // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48

        // '0' is the only value like this per http://php.net/empty

        if (empty($x) && (abs($base) != 256 || $x !== '0')) {

            return;

        }

        switch ($base) {

            case -256:

            case 256:

                if ($base == -256 && (ord($x[0]) & 0x80)) {

                    $this->value = ~$x;

                    $this->is_negative = true;

                } else {

                    $this->value = $x;

                    $this->is_negative = false;

                }

                $this->initialize($base);

                if ($this->is_negative) {

                    $temp = $this->add(new static('-1'));

                    $this->value = $temp->value;

                }

                break;

            case -16:

            case 16:

                if ($base > 0 && $x[0] == '-') {

                    $this->is_negative = true;

                    $x = substr($x, 1);

                }

                $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);

                $is_negative = false;

                if ($base < 0 && hexdec($x[0]) >= 8) {

                    $this->is_negative = $is_negative = true;

                    $x = Strings::bin2hex(~Strings::hex2bin($x));

                }

                $this->value = $x;

                $this->initialize($base);

                if ($is_negative) {

                    $temp = $this->add(new static('-1'));

                    $this->value = $temp->value;

                }

                break;

            case -10:

            case 10:

                // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that

                // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals)

                // [^-0-9].*: find any non-numeric characters and then any characters that follow that

                $this->value = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x);

                if (!strlen($this->value) || $this->value == '-') {

                    $this->value = '0';

                }

                $this->initialize($base);

                break;

            case -2:

            case 2:

                if ($base > 0 && $x[0] == '-') {

                    $this->is_negative = true;

                    $x = substr($x, 1);

                }

                $x = preg_replace('#^([01]*).*#', '$1', $x);

                $temp = new static(Strings::bits2bin($x), 128 * $base); // ie. either -16 or +16

                $this->value = $temp->value;

                if ($temp->is_negative) {

                    $this->is_negative = true;

                }

                break;

            default:

                // base not supported, so we'll let $this == 0

        }

    }

    /**

     * Sets engine type.

     *

     * Throws an exception if the type is invalid

     *

     * @param class-string<Engine> $engine

     */

    public static function setModExpEngine($engine)

    {

        $fqengine = '\\phpseclib3\\Math\\BigInteger\\Engines\\' . static::ENGINE_DIR . '\\' . $engine;

        if (!class_exists($fqengine) || !method_exists($fqengine, 'isValidEngine')) {

            throw new \InvalidArgumentException("$engine is not a valid engine");

        }

        if (!$fqengine::isValidEngine()) {

            throw new BadConfigurationException("$engine is not setup correctly on this system");

        }

        static::$modexpEngine[static::class] = $fqengine;

    }

    /**

     * Converts a BigInteger to a byte string (eg. base-256).

     *

     * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're

     * saved as two's compliment.

     * @return string

     */

    protected function toBytesHelper()

    {

        $comparison = $this->compare(new static());

        if ($comparison == 0) {

            return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';

        }

        $temp = $comparison < 0 ? $this->add(new static(1)) : $this;

        $bytes = $temp->toBytes();

        if (!strlen($bytes)) { // eg. if the number we're trying to convert is -1

            $bytes = chr(0);

        }

        if (ord($bytes[0]) & 0x80) {

            $bytes = chr(0) . $bytes;

        }

        return $comparison < 0 ? ~$bytes : $bytes;

    }

    /**

     * Converts a BigInteger to a hex string (eg. base-16).

     *

     * @param bool $twos_compliment

     * @return string

     */

    public function toHex($twos_compliment = false)

    {

        return Strings::bin2hex($this->toBytes($twos_compliment));

    }

    /**

     * Converts a BigInteger to a bit string (eg. base-2).

     *

     * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're

     * saved as two's compliment.

     *

     * @param bool $twos_compliment

     * @return string

     */

    public function toBits($twos_compliment = false)

    {

        $hex = $this->toBytes($twos_compliment);

        $bits = Strings::bin2bits($hex);

        $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0');

        if ($twos_compliment && $this->compare(new static()) > 0 && $this->precision <= 0) {

            return '0' . $result;

        }

        return $result;

    }

    /**

     * Calculates modular inverses.

     *

     * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.

     *

     * {@internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information.}

     *

     * @param Engine $n

     * @return static|false

     */

    protected function modInverseHelper(Engine $n)

    {

        // $x mod -$n == $x mod $n.

        $n = $n->abs();

        if ($this->compare(static::$zero[static::class]) < 0) {

            $temp = $this->abs();

            $temp = $temp->modInverse($n);

            return $this->normalize($n->subtract($temp));

        }

        extract($this->extendedGCD($n));

        /**

         * @var Engine $gcd

         * @var Engine $x

         */

        if (!$gcd->equals(static::$one[static::class])) {

            return false;

        }

        $x = $x->compare(static::$zero[static::class]) < 0 ? $x->add($n) : $x;

        return $this->compare(static::$zero[static::class]) < 0 ? $this->normalize($n->subtract($x)) : $this->normalize($x);

    }

    /**

     * Serialize

     *

     * Will be called, automatically, when serialize() is called on a BigInteger object.

     *

     * @return array

     */

    public function __sleep()

    {

        $this->hex = $this->toHex(true);

        $vars = ['hex'];

        if ($this->precision > 0) {

            $vars[] = 'precision';

        }

        return $vars;

    }

    /**

     * Serialize

     *

     * Will be called, automatically, when unserialize() is called on a BigInteger object.

     *

     * @return void

     */

    public function __wakeup()

    {

        $temp = new static($this->hex, -16);

        $this->value = $temp->value;

        $this->is_negative = $temp->is_negative;

        if ($this->precision > 0) {

            // recalculate $this->bitmask

            $this->setPrecision($this->precision);

        }

    }

    /**

     * JSON Serialize

     *

     * Will be called, automatically, when json_encode() is called on a BigInteger object.

     */

    #[\ReturnTypeWillChange]

    public function jsonSerialize()

    {

        $result = ['hex' => $this->toHex(true)];

        if ($this->precision > 0) {

            $result['precision'] = $this->precision;

        }

        return $result;

    }

    /**

     * Converts a BigInteger to a base-10 number.

     *

     * @return string

     */

    public function __toString()

    {

        return $this->toString();

    }

    /**

     *  __debugInfo() magic method

     *

     * Will be called, automatically, when print_r() or var_dump() are called

     *

     * @return array

     */

    public function __debugInfo()

    {

        $result = [

            'value' => '0x' . $this->toHex(true),

            'engine' => basename(static::class)

        ];

        return $this->precision > 0 ? $result + ['precision' => $this->precision] : $result;

    }

    /**

     * Set Precision

     *

     * Some bitwise operations give different results depending on the precision being used.  Examples include left

     * shift, not, and rotates.

     *

     * @param int $bits

     */

    public function setPrecision($bits)

    {

        if ($bits < 1) {

            $this->precision = -1;

            $this->bitmask = false;

            return;

        }

        $this->precision = $bits;

        $this->bitmask = static::setBitmask($bits);

        $temp = $this->normalize($this);

        $this->value = $temp->value;

    }

    /**

     * Get Precision

     *

     * Returns the precision if it exists, -1 if it doesn't

     *

     * @return int

     */

    public function getPrecision()

    {

        return $this->precision;

    }

    /**

     * Set Bitmask

     * @return static

     * @param int $bits

     * @see self::setPrecision()

     */

    protected static function setBitmask($bits)

    {

        return new static(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);

    }

    /**

     * Logical Not

     *

     * @return Engine|string

     */

    public function bitwise_not()

    {

        // calculuate "not" without regard to $this->precision

        // (will always result in a smaller number.  ie. ~1 isn't 1111 1110 - it's 0)

        $temp = $this->toBytes();

        if ($temp == '') {

            return $this->normalize(static::$zero[static::class]);

        }

        $pre_msb = decbin(ord($temp[0]));

        $temp = ~$temp;

        $msb = decbin(ord($temp[0]));

        if (strlen($msb) == 8) {

            $msb = substr($msb, strpos($msb, '0'));

        }

        $temp[0] = chr(bindec($msb));

        // see if we need to add extra leading 1's

        $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8;

        $new_bits = $this->precision - $current_bits;

        if ($new_bits <= 0) {

            return $this->normalize(new static($temp, 256));

        }

        // generate as many leading 1's as we need to.

        $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);

        self::base256_lshift($leading_ones, $current_bits);

        $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT);

        return $this->normalize(new static($leading_ones | $temp, 256));

    }

    /**

     * Logical Left Shift

     *

     * Shifts binary strings $shift bits, essentially multiplying by 2**$shift.

     *

     * @param string $x

     * @param int $shift

     * @return void

     */

    protected static function base256_lshift(&$x, $shift)

    {

        if ($shift == 0) {

            return;

        }

        $num_bytes = $shift >> 3; // eg. floor($shift/8)

        $shift &= 7; // eg. $shift % 8

        $carry = 0;

        for ($i = strlen($x) - 1; $i >= 0; --$i) {

            $temp = ord($x[$i]) << $shift | $carry;

            $x[$i] = chr($temp);

            $carry = $temp >> 8;

        }

        $carry = ($carry != 0) ? chr($carry) : '';

        $x = $carry . $x . str_repeat(chr(0), $num_bytes);

    }

    /**

     * Logical Left Rotate

     *

     * Instead of the top x bits being dropped they're appended to the shifted bit string.

     *

     * @param int $shift

     * @return Engine

     */

    public function bitwise_leftRotate($shift)

    {

        $bits = $this->toBytes();

        if ($this->precision > 0) {

            $precision = $this->precision;

            if (static::FAST_BITWISE) {

                $mask = $this->bitmask->toBytes();

            } else {

                $mask = $this->bitmask->subtract(new static(1));

                $mask = $mask->toBytes();

            }

        } else {

            $temp = ord($bits[0]);

            for ($i = 0; $temp >> $i; ++$i) {

            }

            $precision = 8 * strlen($bits) - 8 + $i;

            $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);

        }

        if ($shift < 0) {

            $shift += $precision;

        }

        $shift %= $precision;

        if (!$shift) {

            return clone $this;

        }

        $left = $this->bitwise_leftShift($shift);

        $left = $left->bitwise_and(new static($mask, 256));

        $right = $this->bitwise_rightShift($precision - $shift);

        $result = static::FAST_BITWISE ? $left->bitwise_or($right) : $left->add($right);

        return $this->normalize($result);

    }

    /**

     * Logical Right Rotate

     *

     * Instead of the bottom x bits being dropped they're prepended to the shifted bit string.

     *

     * @param int $shift

     * @return Engine

     */

    public function bitwise_rightRotate($shift)

    {

        return $this->bitwise_leftRotate(-$shift);

    }

    /**

     * Returns the smallest and largest n-bit number

     *

     * @param int $bits

     * @return array{min: static, max: static}

     */

    public static function minMaxBits($bits)

    {

        $bytes = $bits >> 3;

        $min = str_repeat(chr(0), $bytes);

        $max = str_repeat(chr(0xFF), $bytes);

        $msb = $bits & 7;

        if ($msb) {

            $min = chr(1 << ($msb - 1)) . $min;

            $max = chr((1 << $msb) - 1) . $max;

        } else {

            $min[0] = chr(0x80);

        }

        return [

            'min' => new static($min, 256),

            'max' => new static($max, 256)

        ];

    }

    /**

     * Return the size of a BigInteger in bits

     *

     * @return int

     */

    public function getLength()

    {

        return strlen($this->toBits());

    }

    /**

     * Return the size of a BigInteger in bytes

     *

     * @return int

     */

    public function getLengthInBytes()

    {

        return strlen($this->toBytes());

    }

    /**

     * Performs some pre-processing for powMod

     *

     * @param Engine $e

     * @param Engine $n

     * @return static|false

     */

    protected function powModOuter(Engine $e, Engine $n)

    {

        $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();

        if ($e->compare(new static()) < 0) {

            $e = $e->abs();

            $temp = $this->modInverse($n);

            if ($temp === false) {

                return false;

            }

            return $this->normalize($temp->powModInner($e, $n));

        }

        return $this->powModInner($e, $n);

    }

    /**

     * Sliding Window k-ary Modular Exponentiation

     *

     * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} /

     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}.  In a departure from those algorithims,

     * however, this function performs a modular reduction after every multiplication and squaring operation.

     * As such, this function has the same preconditions that the reductions being used do.

     *

     * @template T of Engine

     * @param Engine $x

     * @param Engine $e

     * @param Engine $n

     * @param class-string<T> $class

     * @return T

     */

    protected static function slidingWindow(Engine $x, Engine $e, Engine $n, $class)

    {

        static $window_ranges = [7, 25, 81, 241, 673, 1793]; // from BigInteger.java's oddModPow function

        //static $window_ranges = [0, 7, 36, 140, 450, 1303, 3529]; // from MPM 7.3.1

        $e_bits = $e->toBits();

        $e_length = strlen($e_bits);

        // calculate the appropriate window size.

        // $window_size == 3 if $window_ranges is between 25 and 81, for example.

        for ($i = 0, $window_size = 1; $i < count($window_ranges) && $e_length > $window_ranges[$i]; ++$window_size, ++$i) {

        }

        $n_value = $n->value;

        if (method_exists(static::class, 'generateCustomReduction')) {

            static::generateCustomReduction($n, $class);

        }

        // precompute $this^0 through $this^$window_size

        $powers = [];

        $powers[1] = static::prepareReduce($x->value, $n_value, $class);

        $powers[2] = static::squareReduce($powers[1], $n_value, $class);

        // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end

        // in a 1.  ie. it's supposed to be odd.

        $temp = 1 << ($window_size - 1);

        for ($i = 1; $i < $temp; ++$i) {

            $i2 = $i << 1;

            $powers[$i2 + 1] = static::multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $class);