BigInteger::modPow() - Code Metrics - Inspection of "Update BigInteger.php" - Spomky-Labs/jose - Measure and Improve Code Quality continuously with Scrutinizer

Failed Conditions

Push — PHPSecLib_Rid ( 6a2b08...706d5a )

by Florent

created 2016-07-29 08:10 UTC

BigInteger::modPow() A

↳ Parent: BigInteger

Complexity

Conditions	3
Paths	3

Size

Total Lines	20
Code Lines	11

Duplication

Lines	0
Ratio	0 %

Importance

Changes	5
Bugs	1	Features	0

Metric	Value
c	5
b	1
f	0
dl	0
loc	20
rs	9.4285
cc	3
eloc	11
nc	3
nop	2

<?php

/*
 * The MIT License (MIT)
 *
 * Copyright (c) 2014-2016 Spomky-Labs
 *
 * This software may be modified and distributed under the terms
 * of the MIT license.  See the LICENSE file for details.
 */

namespace Jose\Util;

final class BigInteger
{
    /**
     * Holds the BigInteger's value.
     *
     * @var resource
     */
    private $value;

    /**
     * Holds the BigInteger's magnitude.
     *
     * @var bool
     */
    private $is_negative = false;

    /**
     * Converts base-10 and binary strings (base-256) to BigIntegers.
     *
     * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
     * two's compliment.  The sole exception to this is -10, which is treated the same as 10 is.
     *
     * Here's an example:
     * <code>
     * <?php
     *    $a = new \Jose\Util\in base-16
     *
     *    echo $a->toString(); // outputs 50
     * ?>
     * </code>
     *
     * @param $x base-10 number or base-$base number if $base set.
     * @param int $base
     */
    public function __construct($x = 0, $base = 10)
    {
        if(is_resource($x) && get_resource_type($x) == 'GMP integer') {
            $this->value = $x;
            
            return;
        }
        
        $this->value = gmp_init(0);


        // '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:
                if (ord($x[0]) & 0x80) {
                    $x = ~$x;
                    $this->is_negative = true;
                }
            case 256:
                $sign = $this->is_negative ? '-' : '';
                $this->value = gmp_init($sign.'0x'.bin2hex($x));


                if ($this->is_negative) {
                    $this->is_negative = false;
                    $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
                $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x);

                $this->value = gmp_init($x);

                break;
        }
    }

    /**
     * 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.
     *
     * Here's an example:
     * <code>
     * <?php
     *    $a = new \Jose\Util\ger('65');
     *
     *    echo $a->toBytes(); // outputs chr(65)
     * ?>
     * </code>
     *
     * @param bool $twos_compliment
/**
 * @param array $germany
 * @param array $island
 * @param array $italy
 */
function finale($germany, $island) {
    return "2:1";
}
     *
     * @return string
     *
     */
    public function toBytes()
    {
        if (gmp_cmp($this->value, gmp_init(0)) === 0) {
            return '';
        }

        $temp = gmp_strval(gmp_abs($this->value), 16);
        $temp = (strlen($temp) & 1) ? '0'.$temp : $temp;
        $temp = hex2bin($temp);

        return ltrim($temp, chr(0));
    }

    /**
     * Adds two BigIntegers.
     *
     * Here's an example:
     * <code>
     * <?php
     *    $a = new \Jose\Util\ger('10');
     *    $b = new \Jose\Util\ger('20');
     *
     *    $c = $a->add($b);
     *
     *    echo $c->toString(); // outputs 30
     * ?>
     * </code>
     *
     * @param \Jose\Util\BigInteger $y
     *
     * @return \Jose\Util\BigInteger
     *
     */
    public function add(BigInteger $y)
    {
        $temp = new static();
        $temp->value = gmp_add($this->value, $y->value);

        return $this->_normalize($temp);
    }

    /**
     * Subtracts two BigIntegers.
     *
     * Here's an example:
     * <code>
     * <?php
     *    $a = new \Jose\Util\ger('10');
     *    $b = new \Jose\Util\ger('20');
     *
     *    $c = $a->subtract($b);
     *
     *    echo $c->toString(); // outputs -10
     * ?>
     * </code>
     *
     * @param \Jose\Util\BigInteger $y
     *
     * @return \Jose\Util\BigInteger
     *
     */
    public function subtract(BigInteger $y)
    {
        $temp = new static();
        $temp->value = gmp_sub($this->value, $y->value);

        return $this->_normalize($temp);
    }

    /**
     * Multiplies two BigIntegers.
     *
     * Here's an example:
     * <code>
     * <?php
     *    $a = new \Jose\Util\ger('10');
     *    $b = new \Jose\Util\ger('20');
     *
     *    $c = $a->multiply($b);
     *
     *    echo $c->toString(); // outputs 200
     * ?>
     * </code>
     *
     * @param \Jose\Util\BigInteger $x
     *
     * @return \Jose\Util\BigInteger
     */
    public function multiply(BigInteger $x)
    {
        $temp = new static();
        $temp->value = gmp_mul($this->value, $x->value);

        return $this->_normalize($temp);
    }

    /**
     * Divides two BigIntegers.
     *
     * Returns an array whose first element contains the quotient and whose second element contains the
     * "common residue".  If the remainder would be positive, the "common residue" and the remainder are the
     * same.  If the remainder would be negative, the "common residue" is equal to the sum of the remainder
     * and the divisor (basically, the "common residue" is the first positive modulo).
     *
     * Here's an example:
     * <code>
     * <?php
     *    $a = new \Jose\Util\ger('10');
     *    $b = new \Jose\Util\ger('20');
     *
     *    list($quotient, $remainder) = $a->divide($b);
     *
     *    echo $quotient->toString(); // outputs 0
     *    echo "\r\n";
     *    echo $remainder->toString(); // outputs 10
     * ?>
     * </code>
     * @param \Jose\Util\BigInteger $y
     *
     * @return \Jose\Util\BigInteger[]
     *
     */
    public function divide(BigInteger $y)
    {
        $quotient = new static();
        $remainder = new static();

        list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);

        if (gmp_sign($remainder->value) < 0) {
            $remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
        }

        return [$this->_normalize($quotient), $this->_normalize($remainder)];
    }

    /**
     * Performs modular exponentiation.
     *
     * Here's an example:
     * <code>
     * <?php
     *    $a = new \Jose\Util\ger('10');
     *    $b = new \Jose\Util\ger('20');
     *    $c = new \Jose\Util\ger('30');
     *
     *    $c = $a->modPow($b, $c);
     *
     *    echo $c->toString(); // outputs 10
     * ?>
     * </code>
     *
     * @param \Jose\Util\BigInteger $e
     * @param \Jose\Util\BigInteger $n
     *
     * @return \Jose\Util\BigInteger
     *
     *    and although the approach involving repeated squaring does vastly better, it, too, is impractical
     *    for our purposes.  The reason being that division - by far the most complicated and time-consuming
     *    of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
     *
     *    Modular reductions resolve this issue.  Although an individual modular reduction takes more time
     *    then an individual division, when performed in succession (with the same modulo), they're a lot faster.
     *
     *    The two most commonly used modular reductions are Barrett and Montgomery reduction.  Montgomery reduction,
     *    although faster, only works when the gcd of the modulo and of the base being used is 1.  In RSA, when the
     *    base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because
     *    the product of two odd numbers is odd), but what about when RSA isn't used?
     *
     *    In contrast, Barrett reduction has no such constraint.  As such, some bigint implementations perform a
     *    Barrett reduction after every operation in the modpow function.  Others perform Barrett reductions when the
     *    modulo is even and Montgomery reductions when the modulo is odd.  BigInteger.java's modPow method, however,
     *    uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and
     *    the other, a power of two - and recombine them, later.  This is the method that this modPow function uses.
     *    {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.
     */
    public function modPow(BigInteger $e, BigInteger $n)
    {
        $n = $n->abs();

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

            $temp = $this->modInverse($n);
            if ($temp === false) {
                return false;
class Author {
    private $name;

    public function __construct($name) {
        $this->name = $name;
    }

    public function getName() {
        return $this->name;
    }
}

abstract class Post {
    public function getAuthor() {
        return 'Johannes';
    }
}

class BlogPost extends Post {
    public function getAuthor() {
        return new Author('Johannes');
    }
}

class ForumPost extends Post { /* ... */ }

function my_function(Post $post) {
    echo strtoupper($post->getAuthor());
}
            }

            return $this->_normalize($temp->modPow($e, $n));
        }

            $temp = new static();
            $temp->value = gmp_powm($this->value, $e->value, $n->value);

            return $this->_normalize($temp);
    }

    /**
     * Calculates modular inverses.
     *
     * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
     *
     * Here's an example:
     * <code>
     * <?php
     *    $a = new \Jose\Util\teger(30);
     *    $b = new \Jose\Util\teger(17);
     *
     *    $c = $a->modInverse($b);
     *    echo $c->toString(); // outputs 4
     *
     *    echo "\r\n";
     *
     *    $d = $a->multiply($c);
     *    list(, $d) = $d->divide($b);
     *    echo $d; // outputs 1 (as per the definition of modular inverse)
     * ?>
     * </code>
     *
     * @param \Jose\Util\BigInteger $n
     *
     * @return \Jose\Util\BigInteger|bool
     *
     */
    public function modInverse(BigInteger $n)
    {
        $temp = new static();
        $temp->value = gmp_invert($this->value, $n->value);

        return ($temp->value === false) ? false : $this->_normalize($temp);
    }

    /**
     * Absolute value.
     *
     * @return \Jose\Util\BigInteger
     */
    public function abs()
    {
        $temp = new static();

        $temp->value = gmp_abs($this->value);

        return $temp;
    }

    /**
     * Compares two numbers.
     *
     * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite.  The reason for this is
     * demonstrated thusly:
     *
     * $x  > $y: $x->compare($y)  > 0
     * $x  < $y: $x->compare($y)  < 0
     * $x == $y: $x->compare($y) == 0
     *
     * Note how the same comparison operator is used.  If you want to test for equality, use $x->equals($y).
     *
     * @param \Jose\Util\BigInteger $y
     *
     * @return int < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
     *
     */
    public function compare(BigInteger $y)
    {
        return gmp_cmp($this->value, $y->value);
    }

    /**
     * Logical Left Shift.
     *
     * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
     *
     * @param int $shift
     *
     * @return \Jose\Util\BigInteger
     *
     */
    public function bitwise_leftShift($shift)
    {
        $temp = new static();

        static $two;

        if (!isset($two)) {
            $two = gmp_init('2');
        }

        $temp->value = gmp_mul($this->value, gmp_pow($two, $shift));

        return $this->_normalize($temp);
    }

    /**
     * Generates a random BigInteger.
     *
     * Byte length is equal to $length. Uses \phpseclib\Crypt\Random if it's loaded and mt_rand if it's not.
     *
     * @param int $size
     *
     * @return \Jose\Util\BigInteger
     */
    private static function _random_number_helper($size)
    {
        return new static(random_bytes($size), 256);
    }

    /**
     * Generate a random number.
     *
     * Returns a random number between $min and $max where $min and $max
     * can be defined using one of the two methods:
     *
     * BigInteger::random($min, $max)
     * BigInteger::random($max, $min)
     *
     * @param \Jose\Util\BigInteger $min
     * @param \Jose\Util\BigInteger $max
     *
     * @return \Jose\Util\BigInteger
     */
    public static function random(BigInteger $min, BigInteger $max)
    {
        $compare = $max->compare($min);

        if (!$compare) {
            return $this->_normalize($min);

        } elseif ($compare < 0) {
            // if $min is bigger then $max, swap $min and $max
            $temp = $max;
            $max = $min;
            $min = $temp;
        }

        static $one;
        if (!isset($one)) {
            $one = new static(1);
        }

        $max = $max->subtract($min->subtract($one));
        $size = strlen(ltrim($max->toBytes(), chr(0)));

        /*
            doing $random % $max doesn't work because some numbers will be more likely to occur than others.
            eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145
            would produce 5 whereas the only value of random that could produce 139 would be 139. ie.
            not all numbers would be equally likely. some would be more likely than others.

            creating a whole new random number until you find one that is within the range doesn't work
            because, for sufficiently small ranges, the likelihood that you'd get a number within that range
            would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability
            would be pretty high that $random would be greater than $max.

            phpseclib works around this using the technique described here:

            http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string
        */
        $random_max = new static(chr(1).str_repeat("\0", $size), 256);
        $random = self::_random_number_helper($size);

        list($max_multiple) = $random_max->divide($max);
        $max_multiple = $max_multiple->multiply($max);

        while ($random->compare($max_multiple) >= 0) {
            $random = $random->subtract($max_multiple);
            $random_max = $random_max->subtract($max_multiple);
            $random = $random->bitwise_leftShift(8);
            $random = $random->add(self::_random_number_helper(1));
            $random_max = $random_max->bitwise_leftShift(8);
            list($max_multiple) = $random_max->divide($max);
            $max_multiple = $max_multiple->multiply($max);
        }
        list(, $random) = $random->divide($max);

        return $random->add($min);
    }

    /**
     * Normalize.
     *
     * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
     *
     * @param \Jose\Util\BigInteger $result
     *
     * @return \Jose\Util\BigInteger
     */
    private function _normalize($result)
    {
        return $result;
    }
}


1			<?php
2
3			/*
4			* The MIT License (MIT)
5			*
6			* Copyright (c) 2014-2016 Spomky-Labs
7			*
8			* This software may be modified and distributed under the terms
9			* of the MIT license. See the LICENSE file for details.
10			*/
11
12			namespace Jose\Util;
13
14			final class BigInteger
15			{
16			/**
17			* Holds the BigInteger's value.
18			*
19			* @var resource
20			*/
21			private $value;
22
23			/**
24			* Holds the BigInteger's magnitude.
25			*
26			* @var bool
27			*/
28			private $is_negative = false;
29
30			/**
31			* Converts base-10 and binary strings (base-256) to BigIntegers.
32			*
33			* If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
34			* two's compliment. The sole exception to this is -10, which is treated the same as 10 is.
35			*
36			* Here's an example:
37			* <code>
38			* <?php
39			* $a = new \Jose\Util\in base-16
40			*
41			* echo $a->toString(); // outputs 50
42			* ?>
43			* </code>
44			*
45			* @param $x base-10 number or base-$base number if $base set.
46			* @param int $base
47			*/
48			public function __construct($x = 0, $base = 10)
49			{
50			if(is_resource($x) && get_resource_type($x) == 'GMP integer') {
51			$this->value = $x;
52
53			return;
54			}
55
56			$this->value = gmp_init(0);
			0 ignored issues – show Documentation Bug introduced 2016-07-29 07:32 UTC by Report Bug Copy Issue Report It seems like `gmp_init(0)` of type `object<GMP>` is incompatible with the declared type `resource` of property `$value`. Our type inference engine has found an assignment to a property that is incompatible with the declared type of that property. Either this assignment is in error or the assigned type should be added to the documentation/type hint for that property.. Loading history...
57
58			// '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48
59			// '0' is the only value like this per http://php.net/empty
60			if (empty($x) && (abs($base) != 256 \|\| $x !== '0')) {
			0 ignored issues – show Unused Code Bug introduced 2016-07-28 23:33 UTC by Report Bug Copy Issue Report The strict comparison `!==` seems to always evaluate to `true` as the types of `$x` (`integer`) and `'0'` (`string`) can never be identical. Maybe you want to use a loose comparison `!=` instead? Loading history...
61			return;
62			}
63
64			switch ($base) {
65			case -256:
66			if (ord($x[0]) & 0x80) {
67			$x = ~$x;
68			$this->is_negative = true;
69			}
70			case 256:
71			$sign = $this->is_negative ? '-' : '';
72			$this->value = gmp_init($sign.'0x'.bin2hex($x));
			0 ignored issues – show Documentation Bug introduced 2016-07-29 07:32 UTC by Report Bug Copy Issue Report It seems like `gmp_init($sign . '0x' . bin2hex($x))` of type `object<GMP>` is incompatible with the declared type `resource` of property `$value`. Our type inference engine has found an assignment to a property that is incompatible with the declared type of that property. Either this assignment is in error or the assigned type should be added to the documentation/type hint for that property.. Loading history...
73
74			if ($this->is_negative) {
75			$this->is_negative = false;
76			$temp = $this->add(new static('-1'));
77			$this->value = $temp->value;
78			}
79			break;
80			case 10:
81			case -10:
82			// (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that
83			// (?<=^\|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals)
84			// [^-0-9].*: find any non-numeric characters and then any characters that follow that
85			$x = preg_replace('#(?<!^)(?:-).\|(?<=^\|-)0\|[^-0-9].*#', '', $x);
86
87			$this->value = gmp_init($x);
			0 ignored issues – show Documentation Bug introduced 2016-07-29 07:32 UTC by Report Bug Copy Issue Report It seems like `gmp_init($x)` of type `object<GMP>` is incompatible with the declared type `resource` of property `$value`. Our type inference engine has found an assignment to a property that is incompatible with the declared type of that property. Either this assignment is in error or the assigned type should be added to the documentation/type hint for that property.. Loading history...
88			break;
89			}
90			}
91
92			/**
93			* Converts a BigInteger to a byte string (eg. base-256).
94			*
95			* Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
96			* saved as two's compliment.
97			*
98			* Here's an example:
99			* <code>
100			* <?php
101			* $a = new \Jose\Util\ger('65');
102			*
103			* echo $a->toBytes(); // outputs chr(65)
104			* ?>
105			* </code>
106			*
107			* @param bool $twos_compliment
			0 ignored issues – show Bug introduced 2016-07-29 08:23 UTC by Report Bug Copy Issue Report There is no parameter named `$twos_compliment`. Was it maybe removed? This check looks for PHPDoc comments describing methods or function parameters that do not exist on the corresponding method or function. Consider the following example. The parameter `$italy` is not defined by the method `finale(...)`. /** * @param array $germany * @param array $island * @param array $italy */ function finale($germany, $island) { return "2:1"; } The most likely cause is that the parameter was removed, but the annotation was not. Loading history...
108			*
109			* @return string
110			*
111			*/
112			public function toBytes()
113			{
114			if (gmp_cmp($this->value, gmp_init(0)) === 0) {
115			return '';
116			}
117
118			$temp = gmp_strval(gmp_abs($this->value), 16);
119			$temp = (strlen($temp) & 1) ? '0'.$temp : $temp;
120			$temp = hex2bin($temp);
121
122			return ltrim($temp, chr(0));
123			}
124
125			/**
126			* Adds two BigIntegers.
127			*
128			* Here's an example:
129			* <code>
130			* <?php
131			* $a = new \Jose\Util\ger('10');
132			* $b = new \Jose\Util\ger('20');
133			*
134			* $c = $a->add($b);
135			*
136			* echo $c->toString(); // outputs 30
137			* ?>
138			* </code>
139			*
140			* @param \Jose\Util\BigInteger $y
141			*
142			* @return \Jose\Util\BigInteger
143			*
144			*/
145			public function add(BigInteger $y)
146			{
147			$temp = new static();
148			$temp->value = gmp_add($this->value, $y->value);
149
150			return $this->_normalize($temp);
151			}
152
153			/**
154			* Subtracts two BigIntegers.
155			*
156			* Here's an example:
157			* <code>
158			* <?php
159			* $a = new \Jose\Util\ger('10');
160			* $b = new \Jose\Util\ger('20');
161			*
162			* $c = $a->subtract($b);
163			*
164			* echo $c->toString(); // outputs -10
165			* ?>
166			* </code>
167			*
168			* @param \Jose\Util\BigInteger $y
169			*
170			* @return \Jose\Util\BigInteger
171			*
172			*/
173			public function subtract(BigInteger $y)
174			{
175			$temp = new static();
176			$temp->value = gmp_sub($this->value, $y->value);
177
178			return $this->_normalize($temp);
179			}
180
181			/**
182			* Multiplies two BigIntegers.
183			*
184			* Here's an example:
185			* <code>
186			* <?php
187			* $a = new \Jose\Util\ger('10');
188			* $b = new \Jose\Util\ger('20');
189			*
190			* $c = $a->multiply($b);
191			*
192			* echo $c->toString(); // outputs 200
193			* ?>
194			* </code>
195			*
196			* @param \Jose\Util\BigInteger $x
197			*
198			* @return \Jose\Util\BigInteger
199			*/
200			public function multiply(BigInteger $x)
201			{
202			$temp = new static();
203			$temp->value = gmp_mul($this->value, $x->value);
204
205			return $this->_normalize($temp);
206			}
207
208			/**
209			* Divides two BigIntegers.
210			*
211			* Returns an array whose first element contains the quotient and whose second element contains the
212			* "common residue". If the remainder would be positive, the "common residue" and the remainder are the
213			* same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder
214			* and the divisor (basically, the "common residue" is the first positive modulo).
215			*
216			* Here's an example:
217			* <code>
218			* <?php
219			* $a = new \Jose\Util\ger('10');
220			* $b = new \Jose\Util\ger('20');
221			*
222			* list($quotient, $remainder) = $a->divide($b);
223			*
224			* echo $quotient->toString(); // outputs 0
225			* echo "\r\n";
226			* echo $remainder->toString(); // outputs 10
227			* ?>
228			* </code>
229			* @param \Jose\Util\BigInteger $y
230			*
231			* @return \Jose\Util\BigInteger[]
232			*
233			*/
234			public function divide(BigInteger $y)
235			{
236			$quotient = new static();
237			$remainder = new static();
238
239			list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);
240
241			if (gmp_sign($remainder->value) < 0) {
242			$remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
243			}
244
245			return [$this->_normalize($quotient), $this->_normalize($remainder)];
246			}
247
248			/**
249			* Performs modular exponentiation.
250			*
251			* Here's an example:
252			* <code>
253			* <?php
254			* $a = new \Jose\Util\ger('10');
255			* $b = new \Jose\Util\ger('20');
256			* $c = new \Jose\Util\ger('30');
257			*
258			* $c = $a->modPow($b, $c);
259			*
260			* echo $c->toString(); // outputs 10
261			* ?>
262			* </code>
263			*
264			* @param \Jose\Util\BigInteger $e
265			* @param \Jose\Util\BigInteger $n
266			*
267			* @return \Jose\Util\BigInteger
268			*
269			* and although the approach involving repeated squaring does vastly better, it, too, is impractical
270			* for our purposes. The reason being that division - by far the most complicated and time-consuming
271			* of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
272			*
273			* Modular reductions resolve this issue. Although an individual modular reduction takes more time
274			* then an individual division, when performed in succession (with the same modulo), they're a lot faster.
275			*
276			* The two most commonly used modular reductions are Barrett and Montgomery reduction. Montgomery reduction,
277			* although faster, only works when the gcd of the modulo and of the base being used is 1. In RSA, when the
278			* base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because
279			* the product of two odd numbers is odd), but what about when RSA isn't used?
280			*
281			* In contrast, Barrett reduction has no such constraint. As such, some bigint implementations perform a
282			* Barrett reduction after every operation in the modpow function. Others perform Barrett reductions when the
283			* modulo is even and Montgomery reductions when the modulo is odd. BigInteger.java's modPow method, however,
284			* uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and
285			* the other, a power of two - and recombine them, later. This is the method that this modPow function uses.
286			* {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.
287			*/
288			public function modPow(BigInteger $e, BigInteger $n)
289			{
290			$n = $n->abs();
291
292			if ($e->compare(new static()) < 0) {
293			$e = $e->abs();
294
295			$temp = $this->modInverse($n);
296			if ($temp === false) {
297			return false;
			0 ignored issues – show Bug Best Practice introduced 2016-07-28 23:33 UTC by Report Bug Copy Issue Report The return type of `return false;` (`false`) is incompatible with the return type documented by `Jose\Util\BigInteger::modPow` of type `Jose\Util\BigInteger`. If you return a value from a function or method, it should be a sub-type of the type that is given by the parent type f.e. an interface, or abstract method. This is more formally defined by the Lizkov substitution principle, and guarantees that classes that depend on the parent type can use any instance of a child type interchangably. This principle also belongs to the SOLID principles for object oriented design. Let’s take a look at an example: class Author { private $name; public function __construct($name) { $this->name = $name; } public function getName() { return $this->name; } } abstract class Post { public function getAuthor() { return 'Johannes'; } } class BlogPost extends Post { public function getAuthor() { return new Author('Johannes'); } } class ForumPost extends Post { /* ... */ } function my_function(Post $post) { echo strtoupper($post->getAuthor()); } Our function `my_function` expects a `Post` object, and outputs the author of the post. The base class `Post` returns a simple string and outputting a simple string will work just fine. However, the child class `BlogPost` which is a sub-type of `Post` instead decided to return an `object`, and is therefore violating the SOLID principles. If a `BlogPost` were passed to `my_function`, PHP would not complain, but ultimately fail when executing the `strtoupper` call in its body. Loading history...
298			}
299
300			return $this->_normalize($temp->modPow($e, $n));
301			}
302
303			$temp = new static();
304			$temp->value = gmp_powm($this->value, $e->value, $n->value);
305
306			return $this->_normalize($temp);
307			}
308
309			/**
310			* Calculates modular inverses.
311			*
312			* Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses.
313			*
314			* Here's an example:
315			* <code>
316			* <?php
317			* $a = new \Jose\Util\teger(30);
318			* $b = new \Jose\Util\teger(17);
319			*
320			* $c = $a->modInverse($b);
321			* echo $c->toString(); // outputs 4
322			*
323			* echo "\r\n";
324			*
325			* $d = $a->multiply($c);
326			* list(, $d) = $d->divide($b);
327			* echo $d; // outputs 1 (as per the definition of modular inverse)
328			* ?>
329			* </code>
330			*
331			* @param \Jose\Util\BigInteger $n
332			*
333			* @return \Jose\Util\BigInteger\|bool
334			*
335			*/
336			public function modInverse(BigInteger $n)
337			{
338			$temp = new static();
339			$temp->value = gmp_invert($this->value, $n->value);
340
341			return ($temp->value === false) ? false : $this->_normalize($temp);
342			}
343
344			/**
345			* Absolute value.
346			*
347			* @return \Jose\Util\BigInteger
348			*/
349			public function abs()
350			{
351			$temp = new static();
352
353			$temp->value = gmp_abs($this->value);
354
355			return $temp;
356			}
357
358			/**
359			* Compares two numbers.
360			*
361			* Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this is
362			* demonstrated thusly:
363			*
364			* $x > $y: $x->compare($y) > 0
365			* $x < $y: $x->compare($y) < 0
366			* $x == $y: $x->compare($y) == 0
367			*
368			* Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y).
369			*
370			* @param \Jose\Util\BigInteger $y
371			*
372			* @return int < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
373			*
374			*/
375			public function compare(BigInteger $y)
376			{
377			return gmp_cmp($this->value, $y->value);
378			}
379
380			/**
381			* Logical Left Shift.
382			*
383			* Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
384			*
385			* @param int $shift
386			*
387			* @return \Jose\Util\BigInteger
388			*
389			*/
390			public function bitwise_leftShift($shift)
391			{
392			$temp = new static();
393
394			static $two;
395
396			if (!isset($two)) {
397			$two = gmp_init('2');
398			}
399
400			$temp->value = gmp_mul($this->value, gmp_pow($two, $shift));
401
402			return $this->_normalize($temp);
403			}
404
405			/**
406			* Generates a random BigInteger.
407			*
408			* Byte length is equal to $length. Uses \phpseclib\Crypt\Random if it's loaded and mt_rand if it's not.
409			*
410			* @param int $size
411			*
412			* @return \Jose\Util\BigInteger
413			*/
414			private static function _random_number_helper($size)
415			{
416			return new static(random_bytes($size), 256);
417			}
418
419			/**
420			* Generate a random number.
421			*
422			* Returns a random number between $min and $max where $min and $max
423			* can be defined using one of the two methods:
424			*
425			* BigInteger::random($min, $max)
426			* BigInteger::random($max, $min)
427			*
428			* @param \Jose\Util\BigInteger $min
429			* @param \Jose\Util\BigInteger $max
430			*
431			* @return \Jose\Util\BigInteger
432			*/
433			public static function random(BigInteger $min, BigInteger $max)
434			{
435			$compare = $max->compare($min);
436
437			if (!$compare) {
438			return $this->_normalize($min);
			0 ignored issues – show Bug introduced 2016-07-28 23:33 UTC by Report Bug Copy Issue Report The variable `$this` does not exist. Did you forget to declare it? This check marks access to variables or properties that have not been declared yet. While PHP has no explicit notion of declaring a variable, accessing it before a value is assigned to it is most likely a bug. Loading history... Bug introduced 2016-07-28 23:33 UTC by Report Bug Copy Issue Report Usage of "$this" in static methods will cause runtime errors Loading history...
439			} elseif ($compare < 0) {
440			// if $min is bigger then $max, swap $min and $max
441			$temp = $max;
442			$max = $min;
443			$min = $temp;
444			}
445
446			static $one;
447			if (!isset($one)) {
448			$one = new static(1);
449			}
450
451			$max = $max->subtract($min->subtract($one));
452			$size = strlen(ltrim($max->toBytes(), chr(0)));
453
454			/*
455			doing $random % $max doesn't work because some numbers will be more likely to occur than others.
456			eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145
457			would produce 5 whereas the only value of random that could produce 139 would be 139. ie.
458			not all numbers would be equally likely. some would be more likely than others.
459
460			creating a whole new random number until you find one that is within the range doesn't work
461			because, for sufficiently small ranges, the likelihood that you'd get a number within that range
462			would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability
463			would be pretty high that $random would be greater than $max.
464
465			phpseclib works around this using the technique described here:
466
467			http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string
468			*/
469			$random_max = new static(chr(1).str_repeat("\0", $size), 256);
470			$random = self::_random_number_helper($size);
471
472			list($max_multiple) = $random_max->divide($max);
473			$max_multiple = $max_multiple->multiply($max);
474
475			while ($random->compare($max_multiple) >= 0) {
476			$random = $random->subtract($max_multiple);
477			$random_max = $random_max->subtract($max_multiple);
478			$random = $random->bitwise_leftShift(8);
479			$random = $random->add(self::_random_number_helper(1));
480			$random_max = $random_max->bitwise_leftShift(8);
481			list($max_multiple) = $random_max->divide($max);
482			$max_multiple = $max_multiple->multiply($max);
483			}
484			list(, $random) = $random->divide($max);
485
486			return $random->add($min);
487			}
488
489			/**
490			* Normalize.
491			*
492			* Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
493			*
494			* @param \Jose\Util\BigInteger $result
495			*
496			* @return \Jose\Util\BigInteger
497			*/
498			private function _normalize($result)
499			{
500			return $result;
501			}
502			}
503

Spomky-Labs / jose

Push — PHPSecLib_Rid ( 6a2b08...706d5a )

BigInteger::modPow() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like