1 | <?php |
||||||||
2 | |||||||||
3 | /** |
||||||||
4 | * Pure-PHP arbitrary precision integer arithmetic library. |
||||||||
5 | * |
||||||||
6 | * Supports base-2, base-10, base-16, and base-256 numbers. Uses the GMP or BCMath extensions, if available, |
||||||||
7 | * and an internal implementation, otherwise. |
||||||||
8 | * |
||||||||
9 | * PHP version 5 |
||||||||
10 | * |
||||||||
11 | * {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the |
||||||||
12 | * {@link self::MODE_INTERNAL self::MODE_INTERNAL} mode) |
||||||||
13 | * |
||||||||
14 | * BigInteger uses base-2**26 to perform operations such as multiplication and division and |
||||||||
15 | * base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction. Because the largest possible |
||||||||
16 | * value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating |
||||||||
17 | * point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are |
||||||||
18 | * used. As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %, |
||||||||
19 | * which only supports integers. Although this fact will slow this library down, the fact that such a high |
||||||||
20 | * base is being used should more than compensate. |
||||||||
21 | * |
||||||||
22 | * Numbers are stored in {@link http://en.wikipedia.org/wiki/Endianness little endian} format. ie. |
||||||||
23 | * (new \phpseclib\Math\BigInteger(pow(2, 26)))->value = array(0, 1) |
||||||||
24 | * |
||||||||
25 | * Useful resources are as follows: |
||||||||
26 | * |
||||||||
27 | * - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)} |
||||||||
28 | * - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)} |
||||||||
29 | * - Java's BigInteger classes. See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip |
||||||||
30 | * |
||||||||
31 | * Here's an example of how to use this library: |
||||||||
32 | * <code> |
||||||||
33 | * <?php |
||||||||
34 | * $a = new \phpseclib\Math\BigInteger(2); |
||||||||
35 | * $b = new \phpseclib\Math\BigInteger(3); |
||||||||
36 | * |
||||||||
37 | * $c = $a->add($b); |
||||||||
38 | * |
||||||||
39 | * echo $c->toString(); // outputs 5 |
||||||||
40 | * ?> |
||||||||
41 | * </code> |
||||||||
42 | * |
||||||||
43 | * @category Math |
||||||||
44 | * @package BigInteger |
||||||||
45 | * @author Jim Wigginton <[email protected]> |
||||||||
46 | * @copyright 2006 Jim Wigginton |
||||||||
47 | * @license http://www.opensource.org/licenses/mit-license.html MIT License |
||||||||
48 | * @link http://pear.php.net/package/Math_BigInteger |
||||||||
49 | */ |
||||||||
50 | |||||||||
51 | namespace phpseclib\Math; |
||||||||
52 | |||||||||
53 | use phpseclib\Crypt\Random; |
||||||||
54 | |||||||||
55 | /** |
||||||||
56 | * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256 |
||||||||
57 | * numbers. |
||||||||
58 | * |
||||||||
59 | * @package BigInteger |
||||||||
60 | * @author Jim Wigginton <[email protected]> |
||||||||
61 | * @access public |
||||||||
62 | */ |
||||||||
63 | class BigInteger |
||||||||
64 | { |
||||||||
65 | /**#@+ |
||||||||
66 | * Reduction constants |
||||||||
67 | * |
||||||||
68 | * @access private |
||||||||
69 | * @see BigInteger::_reduce() |
||||||||
70 | */ |
||||||||
71 | /** |
||||||||
72 | * @see BigInteger::_montgomery() |
||||||||
73 | * @see BigInteger::_prepMontgomery() |
||||||||
74 | */ |
||||||||
75 | public const MONTGOMERY = 0; |
||||||||
76 | /** |
||||||||
77 | * @see BigInteger::_barrett() |
||||||||
78 | */ |
||||||||
79 | public const BARRETT = 1; |
||||||||
80 | /** |
||||||||
81 | * @see BigInteger::_mod2() |
||||||||
82 | */ |
||||||||
83 | public const POWEROF2 = 2; |
||||||||
84 | /** |
||||||||
85 | * @see BigInteger::_remainder() |
||||||||
86 | */ |
||||||||
87 | public const CLASSIC = 3; |
||||||||
88 | /** |
||||||||
89 | * @see BigInteger::__clone() |
||||||||
90 | */ |
||||||||
91 | public const NONE = 4; |
||||||||
92 | /**#@-*/ |
||||||||
93 | |||||||||
94 | /**#@+ |
||||||||
95 | * Array constants |
||||||||
96 | * |
||||||||
97 | * Rather than create a thousands and thousands of new BigInteger objects in repeated function calls to add() and |
||||||||
98 | * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them. |
||||||||
99 | * |
||||||||
100 | * @access private |
||||||||
101 | */ |
||||||||
102 | /** |
||||||||
103 | * $result[self::VALUE] contains the value. |
||||||||
104 | */ |
||||||||
105 | public const VALUE = 0; |
||||||||
106 | /** |
||||||||
107 | * $result[self::SIGN] contains the sign. |
||||||||
108 | */ |
||||||||
109 | public const SIGN = 1; |
||||||||
110 | /**#@-*/ |
||||||||
111 | |||||||||
112 | /**#@+ |
||||||||
113 | * @access private |
||||||||
114 | * @see BigInteger::_montgomery() |
||||||||
115 | * @see BigInteger::_barrett() |
||||||||
116 | */ |
||||||||
117 | /** |
||||||||
118 | * Cache constants |
||||||||
119 | * |
||||||||
120 | * $cache[self::VARIABLE] tells us whether or not the cached data is still valid. |
||||||||
121 | */ |
||||||||
122 | public const VARIABLE = 0; |
||||||||
123 | /** |
||||||||
124 | * $cache[self::DATA] contains the cached data. |
||||||||
125 | */ |
||||||||
126 | public const DATA = 1; |
||||||||
127 | /**#@-*/ |
||||||||
128 | |||||||||
129 | /**#@+ |
||||||||
130 | * Mode constants. |
||||||||
131 | * |
||||||||
132 | * @access private |
||||||||
133 | * @see BigInteger::__construct() |
||||||||
134 | */ |
||||||||
135 | /** |
||||||||
136 | * To use the pure-PHP implementation |
||||||||
137 | */ |
||||||||
138 | public const MODE_INTERNAL = 1; |
||||||||
139 | /** |
||||||||
140 | * To use the BCMath library |
||||||||
141 | * |
||||||||
142 | * (if enabled; otherwise, the internal implementation will be used) |
||||||||
143 | */ |
||||||||
144 | public const MODE_BCMATH = 2; |
||||||||
145 | /** |
||||||||
146 | * To use the GMP library |
||||||||
147 | * |
||||||||
148 | * (if present; otherwise, either the BCMath or the internal implementation will be used) |
||||||||
149 | */ |
||||||||
150 | public const MODE_GMP = 3; |
||||||||
151 | /**#@-*/ |
||||||||
152 | |||||||||
153 | /** |
||||||||
154 | * Karatsuba Cutoff |
||||||||
155 | * |
||||||||
156 | * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication? |
||||||||
157 | * |
||||||||
158 | * @access private |
||||||||
159 | */ |
||||||||
160 | public const KARATSUBA_CUTOFF = 25; |
||||||||
161 | |||||||||
162 | /**#@+ |
||||||||
163 | * Static properties used by the pure-PHP implementation. |
||||||||
164 | * |
||||||||
165 | * @see __construct() |
||||||||
166 | */ |
||||||||
167 | protected static $base; |
||||||||
168 | protected static $baseFull; |
||||||||
169 | protected static $maxDigit; |
||||||||
170 | protected static $msb; |
||||||||
171 | |||||||||
172 | /** |
||||||||
173 | * $max10 in greatest $max10Len satisfying |
||||||||
174 | * $max10 = 10**$max10Len <= 2**$base. |
||||||||
175 | */ |
||||||||
176 | protected static $max10; |
||||||||
177 | |||||||||
178 | /** |
||||||||
179 | * $max10Len in greatest $max10Len satisfying |
||||||||
180 | * $max10 = 10**$max10Len <= 2**$base. |
||||||||
181 | */ |
||||||||
182 | protected static $max10Len; |
||||||||
183 | protected static $maxDigit2; |
||||||||
184 | /**#@-*/ |
||||||||
185 | |||||||||
186 | /** |
||||||||
187 | * Holds the BigInteger's value. |
||||||||
188 | * |
||||||||
189 | * @var array |
||||||||
190 | * @access private |
||||||||
191 | */ |
||||||||
192 | public $value; |
||||||||
193 | |||||||||
194 | /** |
||||||||
195 | * Holds the BigInteger's magnitude. |
||||||||
196 | * |
||||||||
197 | * @var bool |
||||||||
198 | * @access private |
||||||||
199 | */ |
||||||||
200 | public $is_negative = false; |
||||||||
201 | |||||||||
202 | /** |
||||||||
203 | * Precision |
||||||||
204 | * |
||||||||
205 | * @see self::setPrecision() |
||||||||
206 | * @access private |
||||||||
207 | */ |
||||||||
208 | public $precision = -1; |
||||||||
209 | |||||||||
210 | /** |
||||||||
211 | * Precision Bitmask |
||||||||
212 | * |
||||||||
213 | * @see self::setPrecision() |
||||||||
214 | * @access private |
||||||||
215 | */ |
||||||||
216 | public $bitmask = false; |
||||||||
217 | |||||||||
218 | /** |
||||||||
219 | * Mode independent value used for serialization. |
||||||||
220 | * |
||||||||
221 | * If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for |
||||||||
222 | * a variable that'll be serializable regardless of whether or not extensions are being used. Unlike $this->value, |
||||||||
223 | * however, $this->hex is only calculated when $this->__sleep() is called. |
||||||||
224 | * |
||||||||
225 | * @see self::__sleep() |
||||||||
226 | * @see self::__wakeup() |
||||||||
227 | * @var string |
||||||||
228 | * @access private |
||||||||
229 | */ |
||||||||
230 | public $hex; |
||||||||
231 | |||||||||
232 | /** |
||||||||
233 | * Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers. |
||||||||
234 | * |
||||||||
235 | * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using |
||||||||
236 | * two's compliment. The sole exception to this is -10, which is treated the same as 10 is. |
||||||||
237 | * |
||||||||
238 | * Here's an example: |
||||||||
239 | * <code> |
||||||||
240 | * <?php |
||||||||
241 | * $a = new \phpseclib\Math\BigInteger('0x32', 16); // 50 in base-16 |
||||||||
242 | * |
||||||||
243 | * echo $a->toString(); // outputs 50 |
||||||||
244 | * ?> |
||||||||
245 | * </code> |
||||||||
246 | * |
||||||||
247 | * @param $x base-10 number or base-$base number if $base set. |
||||||||
0 ignored issues
–
show
Documentation
Bug
introduced
by
Loading history...
|
|||||||||
248 | * @param int $base |
||||||||
249 | * @return \phpseclib\Math\BigInteger |
||||||||
250 | * @access public |
||||||||
251 | */ |
||||||||
252 | public function __construct($x = 0, $base = 10) |
||||||||
253 | { |
||||||||
254 | if (!defined('MATH_BIGINTEGER_MODE')) { |
||||||||
255 | switch (true) { |
||||||||
256 | case extension_loaded('gmp'): |
||||||||
257 | define('MATH_BIGINTEGER_MODE', self::MODE_GMP); |
||||||||
258 | break; |
||||||||
259 | case extension_loaded('bcmath'): |
||||||||
260 | define('MATH_BIGINTEGER_MODE', self::MODE_BCMATH); |
||||||||
261 | break; |
||||||||
262 | default: |
||||||||
263 | define('MATH_BIGINTEGER_MODE', self::MODE_INTERNAL); |
||||||||
264 | } |
||||||||
265 | } |
||||||||
266 | |||||||||
267 | if (extension_loaded('openssl') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) { |
||||||||
268 | // some versions of XAMPP have mismatched versions of OpenSSL which causes it not to work |
||||||||
269 | define('MATH_BIGINTEGER_OPENSSL_ENABLED', true); |
||||||||
270 | } |
||||||||
271 | |||||||||
272 | if (!defined('PHP_INT_SIZE')) { |
||||||||
273 | define('PHP_INT_SIZE', 4); |
||||||||
274 | } |
||||||||
275 | |||||||||
276 | if (empty(self::$base) && MATH_BIGINTEGER_MODE == self::MODE_INTERNAL) { |
||||||||
277 | switch (PHP_INT_SIZE) { |
||||||||
278 | case 8: // use 64-bit integers if int size is 8 bytes |
||||||||
279 | self::$base = 31; |
||||||||
280 | self::$baseFull = 0x80000000; |
||||||||
281 | self::$maxDigit = 0x7FFFFFFF; |
||||||||
282 | self::$msb = 0x40000000; |
||||||||
283 | self::$max10 = 1000000000; |
||||||||
284 | self::$max10Len = 9; |
||||||||
285 | self::$maxDigit2 = pow(2, 62); |
||||||||
286 | break; |
||||||||
287 | //case 4: // use 64-bit floats if int size is 4 bytes |
||||||||
288 | default: |
||||||||
289 | self::$base = 26; |
||||||||
290 | self::$baseFull = 0x4000000; |
||||||||
291 | self::$maxDigit = 0x3FFFFFF; |
||||||||
292 | self::$msb = 0x2000000; |
||||||||
293 | self::$max10 = 10000000; |
||||||||
294 | self::$max10Len = 7; |
||||||||
295 | self::$maxDigit2 = pow(2, 52); // pow() prevents truncation |
||||||||
296 | } |
||||||||
297 | } |
||||||||
298 | |||||||||
299 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
300 | case self::MODE_GMP: |
||||||||
301 | switch (true) { |
||||||||
302 | case is_resource($x) && get_resource_type($x) == 'GMP integer': |
||||||||
303 | // PHP 5.6 switched GMP from using resources to objects |
||||||||
304 | case $x instanceof \GMP: |
||||||||
305 | $this->value = $x; |
||||||||
306 | return; |
||||||||
307 | } |
||||||||
308 | $this->value = gmp_init(0); |
||||||||
0 ignored issues
–
show
It seems like
gmp_init(0) of type GMP or resource is incompatible with the declared type array 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...
|
|||||||||
309 | break; |
||||||||
310 | case self::MODE_BCMATH: |
||||||||
311 | $this->value = '0'; |
||||||||
312 | break; |
||||||||
313 | default: |
||||||||
314 | $this->value = array(); |
||||||||
315 | } |
||||||||
316 | |||||||||
317 | // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48 |
||||||||
318 | // '0' is the only value like this per http://php.net/empty |
||||||||
319 | if (empty($x) && (abs($base) != 256 || $x !== '0')) { |
||||||||
320 | return; |
||||||||
321 | } |
||||||||
322 | |||||||||
323 | switch ($base) { |
||||||||
324 | case -256: |
||||||||
325 | if (ord($x[0]) & 0x80) { |
||||||||
326 | $x = ~$x; |
||||||||
327 | $this->is_negative = true; |
||||||||
328 | } |
||||||||
329 | // no break |
||||||||
330 | case 256: |
||||||||
331 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
332 | case self::MODE_GMP: |
||||||||
333 | $sign = $this->is_negative ? '-' : ''; |
||||||||
334 | $this->value = gmp_init($sign . '0x' . bin2hex($x)); |
||||||||
335 | break; |
||||||||
336 | case self::MODE_BCMATH: |
||||||||
337 | // round $len to the nearest 4 (thanks, DavidMJ!) |
||||||||
338 | $len = (strlen($x) + 3) & 0xFFFFFFFC; |
||||||||
339 | |||||||||
340 | $x = str_pad($x, $len, chr(0), STR_PAD_LEFT); |
||||||||
341 | |||||||||
342 | for ($i = 0; $i < $len; $i+= 4) { |
||||||||
343 | $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32 |
||||||||
344 | $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])), 0); |
||||||||
345 | } |
||||||||
346 | |||||||||
347 | if ($this->is_negative) { |
||||||||
348 | $this->value = '-' . $this->value; |
||||||||
349 | } |
||||||||
350 | |||||||||
351 | break; |
||||||||
352 | // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb) |
||||||||
353 | default: |
||||||||
354 | while (strlen($x)) { |
||||||||
355 | $this->value[] = $this->_bytes2int($this->_base256_rshift($x, self::$base)); |
||||||||
356 | } |
||||||||
357 | } |
||||||||
358 | |||||||||
359 | if ($this->is_negative) { |
||||||||
360 | if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) { |
||||||||
361 | $this->is_negative = false; |
||||||||
362 | } |
||||||||
363 | $temp = $this->add(new static('-1')); |
||||||||
364 | $this->value = $temp->value; |
||||||||
365 | } |
||||||||
366 | break; |
||||||||
367 | case 16: |
||||||||
368 | case -16: |
||||||||
369 | if ($base > 0 && $x[0] == '-') { |
||||||||
370 | $this->is_negative = true; |
||||||||
371 | $x = substr($x, 1); |
||||||||
372 | } |
||||||||
373 | |||||||||
374 | $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x); |
||||||||
375 | |||||||||
376 | $is_negative = false; |
||||||||
377 | if ($base < 0 && hexdec($x[0]) >= 8) { |
||||||||
378 | $this->is_negative = $is_negative = true; |
||||||||
379 | $x = bin2hex(~pack('H*', $x)); |
||||||||
380 | } |
||||||||
381 | |||||||||
382 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
383 | case self::MODE_GMP: |
||||||||
384 | $temp = $this->is_negative ? '-0x' . $x : '0x' . $x; |
||||||||
385 | $this->value = gmp_init($temp); |
||||||||
386 | $this->is_negative = false; |
||||||||
387 | break; |
||||||||
388 | case self::MODE_BCMATH: |
||||||||
389 | $x = (strlen($x) & 1) ? '0' . $x : $x; |
||||||||
390 | $temp = new static(pack('H*', $x), 256); |
||||||||
391 | $this->value = $this->is_negative ? '-' . $temp->value : $temp->value; |
||||||||
0 ignored issues
–
show
Are you sure
$temp->value of type array can be used in concatenation ?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
392 | $this->is_negative = false; |
||||||||
393 | break; |
||||||||
394 | default: |
||||||||
395 | $x = (strlen($x) & 1) ? '0' . $x : $x; |
||||||||
396 | $temp = new static(pack('H*', $x), 256); |
||||||||
397 | $this->value = $temp->value; |
||||||||
398 | } |
||||||||
399 | |||||||||
400 | if ($is_negative) { |
||||||||
401 | $temp = $this->add(new static('-1')); |
||||||||
402 | $this->value = $temp->value; |
||||||||
403 | } |
||||||||
404 | break; |
||||||||
405 | case 10: |
||||||||
406 | case -10: |
||||||||
407 | // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that |
||||||||
408 | // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals) |
||||||||
409 | // [^-0-9].*: find any non-numeric characters and then any characters that follow that |
||||||||
410 | $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x); |
||||||||
411 | |||||||||
412 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
413 | case self::MODE_GMP: |
||||||||
414 | $this->value = gmp_init($x); |
||||||||
415 | break; |
||||||||
416 | case self::MODE_BCMATH: |
||||||||
417 | // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different |
||||||||
418 | // results then doing it on '-1' does (modInverse does $x[0]) |
||||||||
419 | $this->value = $x === '-' ? '0' : (string) $x; |
||||||||
420 | break; |
||||||||
421 | default: |
||||||||
422 | $temp = new static(); |
||||||||
423 | |||||||||
424 | $multiplier = new static(); |
||||||||
425 | $multiplier->value = array(self::$max10); |
||||||||
426 | |||||||||
427 | if ($x[0] == '-') { |
||||||||
428 | $this->is_negative = true; |
||||||||
429 | $x = substr($x, 1); |
||||||||
430 | } |
||||||||
431 | |||||||||
432 | $x = str_pad($x, strlen($x) + ((self::$max10Len - 1) * strlen($x)) % self::$max10Len, 0, STR_PAD_LEFT); |
||||||||
433 | while (strlen($x)) { |
||||||||
434 | $temp = $temp->multiply($multiplier); |
||||||||
435 | $temp = $temp->add(new static($this->_int2bytes(substr($x, 0, self::$max10Len)), 256)); |
||||||||
0 ignored issues
–
show
substr($x, 0, self::max10Len) of type string is incompatible with the type integer expected by parameter $x of phpseclib\Math\BigInteger::_int2bytes() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
436 | $x = substr($x, self::$max10Len); |
||||||||
437 | } |
||||||||
438 | |||||||||
439 | $this->value = $temp->value; |
||||||||
440 | } |
||||||||
441 | break; |
||||||||
442 | case 2: // base-2 support originally implemented by Lluis Pamies - thanks! |
||||||||
443 | case -2: |
||||||||
444 | if ($base > 0 && $x[0] == '-') { |
||||||||
445 | $this->is_negative = true; |
||||||||
446 | $x = substr($x, 1); |
||||||||
447 | } |
||||||||
448 | |||||||||
449 | $x = preg_replace('#^([01]*).*#', '$1', $x); |
||||||||
450 | $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT); |
||||||||
451 | |||||||||
452 | $str = '0x'; |
||||||||
453 | while (strlen($x)) { |
||||||||
454 | $part = substr($x, 0, 4); |
||||||||
455 | $str.= dechex(bindec($part)); |
||||||||
0 ignored issues
–
show
It seems like
bindec($part) can also be of type double ; however, parameter $number of dechex() does only seem to accept integer , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
456 | $x = substr($x, 4); |
||||||||
457 | } |
||||||||
458 | |||||||||
459 | if ($this->is_negative) { |
||||||||
460 | $str = '-' . $str; |
||||||||
461 | } |
||||||||
462 | |||||||||
463 | $temp = new static($str, 8 * $base); // ie. either -16 or +16 |
||||||||
464 | $this->value = $temp->value; |
||||||||
465 | $this->is_negative = $temp->is_negative; |
||||||||
466 | |||||||||
467 | break; |
||||||||
468 | default: |
||||||||
469 | // base not supported, so we'll let $this == 0 |
||||||||
470 | } |
||||||||
471 | } |
||||||||
472 | |||||||||
473 | /** |
||||||||
474 | * Converts a BigInteger to a byte string (eg. base-256). |
||||||||
475 | * |
||||||||
476 | * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're |
||||||||
477 | * saved as two's compliment. |
||||||||
478 | * |
||||||||
479 | * Here's an example: |
||||||||
480 | * <code> |
||||||||
481 | * <?php |
||||||||
482 | * $a = new \phpseclib\Math\BigInteger('65'); |
||||||||
483 | * |
||||||||
484 | * echo $a->toBytes(); // outputs chr(65) |
||||||||
485 | * ?> |
||||||||
486 | * </code> |
||||||||
487 | * |
||||||||
488 | * @param bool $twos_compliment |
||||||||
489 | * @return string |
||||||||
490 | * @access public |
||||||||
491 | * @internal Converts a base-2**26 number to base-2**8 |
||||||||
492 | */ |
||||||||
493 | public function toBytes($twos_compliment = false) |
||||||||
494 | { |
||||||||
495 | if ($twos_compliment) { |
||||||||
496 | $comparison = $this->compare(new static()); |
||||||||
497 | if ($comparison == 0) { |
||||||||
498 | return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; |
||||||||
499 | } |
||||||||
500 | |||||||||
501 | $temp = $comparison < 0 ? $this->add(new static(1)) : $this->copy(); |
||||||||
502 | $bytes = $temp->toBytes(); |
||||||||
503 | |||||||||
504 | if (empty($bytes)) { // eg. if the number we're trying to convert is -1 |
||||||||
505 | $bytes = chr(0); |
||||||||
506 | } |
||||||||
507 | |||||||||
508 | if (ord($bytes[0]) & 0x80) { |
||||||||
509 | $bytes = chr(0) . $bytes; |
||||||||
510 | } |
||||||||
511 | |||||||||
512 | return $comparison < 0 ? ~$bytes : $bytes; |
||||||||
513 | } |
||||||||
514 | |||||||||
515 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
516 | case self::MODE_GMP: |
||||||||
517 | if (gmp_cmp($this->value, gmp_init(0)) == 0) { |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_cmp() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
518 | return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; |
||||||||
519 | } |
||||||||
520 | |||||||||
521 | $temp = gmp_strval(gmp_abs($this->value), 16); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_abs() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
522 | $temp = (strlen($temp) & 1) ? '0' . $temp : $temp; |
||||||||
523 | $temp = pack('H*', $temp); |
||||||||
524 | |||||||||
525 | return $this->precision > 0 ? |
||||||||
526 | substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) : |
||||||||
527 | ltrim($temp, chr(0)); |
||||||||
528 | case self::MODE_BCMATH: |
||||||||
529 | if ($this->value === '0') { |
||||||||
530 | return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; |
||||||||
531 | } |
||||||||
532 | |||||||||
533 | $value = ''; |
||||||||
534 | $current = $this->value; |
||||||||
535 | |||||||||
536 | if ($current[0] == '-') { |
||||||||
537 | $current = substr($current, 1); |
||||||||
0 ignored issues
–
show
$current of type array is incompatible with the type string expected by parameter $string of substr() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
538 | } |
||||||||
539 | |||||||||
540 | while (bccomp($current, '0', 0) > 0) { |
||||||||
0 ignored issues
–
show
It seems like
$current can also be of type array ; however, parameter $left_operand of bccomp() does only seem to accept string , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
541 | $temp = bcmod($current, '16777216'); |
||||||||
0 ignored issues
–
show
It seems like
$current can also be of type array ; however, parameter $dividend of bcmod() does only seem to accept string , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
542 | $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value; |
||||||||
0 ignored issues
–
show
It seems like
$temp can also be of type string ; however, parameter $ascii of chr() does only seem to accept integer , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
543 | $current = bcdiv($current, '16777216', 0); |
||||||||
0 ignored issues
–
show
It seems like
$current can also be of type array ; however, parameter $dividend of bcdiv() does only seem to accept string , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
544 | } |
||||||||
545 | |||||||||
546 | return $this->precision > 0 ? |
||||||||
547 | substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) : |
||||||||
548 | ltrim($value, chr(0)); |
||||||||
549 | } |
||||||||
550 | |||||||||
551 | if (!count($this->value)) { |
||||||||
552 | return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; |
||||||||
553 | } |
||||||||
554 | $result = $this->_int2bytes($this->value[count($this->value) - 1]); |
||||||||
555 | |||||||||
556 | $temp = $this->copy(); |
||||||||
557 | |||||||||
558 | for ($i = count($temp->value) - 2; $i >= 0; --$i) { |
||||||||
559 | $temp->_base256_lshift($result, self::$base); |
||||||||
560 | $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT); |
||||||||
561 | } |
||||||||
562 | |||||||||
563 | return $this->precision > 0 ? |
||||||||
564 | str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) : |
||||||||
565 | $result; |
||||||||
566 | } |
||||||||
567 | |||||||||
568 | /** |
||||||||
569 | * Converts a BigInteger to a hex string (eg. base-16)). |
||||||||
570 | * |
||||||||
571 | * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're |
||||||||
572 | * saved as two's compliment. |
||||||||
573 | * |
||||||||
574 | * Here's an example: |
||||||||
575 | * <code> |
||||||||
576 | * <?php |
||||||||
577 | * $a = new \phpseclib\Math\BigInteger('65'); |
||||||||
578 | * |
||||||||
579 | * echo $a->toHex(); // outputs '41' |
||||||||
580 | * ?> |
||||||||
581 | * </code> |
||||||||
582 | * |
||||||||
583 | * @param bool $twos_compliment |
||||||||
584 | * @return string |
||||||||
585 | * @access public |
||||||||
586 | * @internal Converts a base-2**26 number to base-2**8 |
||||||||
587 | */ |
||||||||
588 | public function toHex($twos_compliment = false) |
||||||||
589 | { |
||||||||
590 | return bin2hex($this->toBytes($twos_compliment)); |
||||||||
591 | } |
||||||||
592 | |||||||||
593 | /** |
||||||||
594 | * Converts a BigInteger to a bit string (eg. base-2). |
||||||||
595 | * |
||||||||
596 | * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're |
||||||||
597 | * saved as two's compliment. |
||||||||
598 | * |
||||||||
599 | * Here's an example: |
||||||||
600 | * <code> |
||||||||
601 | * <?php |
||||||||
602 | * $a = new \phpseclib\Math\BigInteger('65'); |
||||||||
603 | * |
||||||||
604 | * echo $a->toBits(); // outputs '1000001' |
||||||||
605 | * ?> |
||||||||
606 | * </code> |
||||||||
607 | * |
||||||||
608 | * @param bool $twos_compliment |
||||||||
609 | * @return string |
||||||||
610 | * @access public |
||||||||
611 | * @internal Converts a base-2**26 number to base-2**2 |
||||||||
612 | */ |
||||||||
613 | public function toBits($twos_compliment = false) |
||||||||
614 | { |
||||||||
615 | $hex = $this->toHex($twos_compliment); |
||||||||
616 | $bits = ''; |
||||||||
617 | for ($i = strlen($hex) - 8, $start = strlen($hex) & 7; $i >= $start; $i-=8) { |
||||||||
618 | $bits = str_pad(decbin(hexdec(substr($hex, $i, 8))), 32, '0', STR_PAD_LEFT) . $bits; |
||||||||
0 ignored issues
–
show
It seems like
hexdec(substr($hex, $i, 8)) can also be of type double ; however, parameter $number of decbin() does only seem to accept integer , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
619 | } |
||||||||
620 | if ($start) { // hexdec('') == 0 |
||||||||
621 | $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8, '0', STR_PAD_LEFT) . $bits; |
||||||||
622 | } |
||||||||
623 | $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0'); |
||||||||
624 | |||||||||
625 | if ($twos_compliment && $this->compare(new static()) > 0 && $this->precision <= 0) { |
||||||||
626 | return '0' . $result; |
||||||||
627 | } |
||||||||
628 | |||||||||
629 | return $result; |
||||||||
630 | } |
||||||||
631 | |||||||||
632 | /** |
||||||||
633 | * Converts a BigInteger to a base-10 number. |
||||||||
634 | * |
||||||||
635 | * Here's an example: |
||||||||
636 | * <code> |
||||||||
637 | * <?php |
||||||||
638 | * $a = new \phpseclib\Math\BigInteger('50'); |
||||||||
639 | * |
||||||||
640 | * echo $a->toString(); // outputs 50 |
||||||||
641 | * ?> |
||||||||
642 | * </code> |
||||||||
643 | * |
||||||||
644 | * @return string |
||||||||
645 | * @access public |
||||||||
646 | * @internal Converts a base-2**26 number to base-10**7 (which is pretty much base-10) |
||||||||
647 | */ |
||||||||
648 | public function toString() |
||||||||
649 | { |
||||||||
650 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
651 | case self::MODE_GMP: |
||||||||
652 | return gmp_strval($this->value); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $gmpnumber of gmp_strval() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
653 | case self::MODE_BCMATH: |
||||||||
654 | if ($this->value === '0') { |
||||||||
655 | return '0'; |
||||||||
656 | } |
||||||||
657 | |||||||||
658 | return ltrim($this->value, '0'); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type string expected by parameter $str of ltrim() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
659 | } |
||||||||
660 | |||||||||
661 | if (!count($this->value)) { |
||||||||
662 | return '0'; |
||||||||
663 | } |
||||||||
664 | |||||||||
665 | $temp = $this->copy(); |
||||||||
666 | $temp->is_negative = false; |
||||||||
667 | |||||||||
668 | $divisor = new static(); |
||||||||
669 | $divisor->value = array(self::$max10); |
||||||||
670 | $result = ''; |
||||||||
671 | while (count($temp->value)) { |
||||||||
672 | list($temp, $mod) = $temp->divide($divisor); |
||||||||
673 | $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', self::$max10Len, '0', STR_PAD_LEFT) . $result; |
||||||||
674 | } |
||||||||
675 | $result = ltrim($result, '0'); |
||||||||
676 | if (empty($result)) { |
||||||||
677 | $result = '0'; |
||||||||
678 | } |
||||||||
679 | |||||||||
680 | if ($this->is_negative) { |
||||||||
681 | $result = '-' . $result; |
||||||||
682 | } |
||||||||
683 | |||||||||
684 | return $result; |
||||||||
685 | } |
||||||||
686 | |||||||||
687 | /** |
||||||||
688 | * Copy an object |
||||||||
689 | * |
||||||||
690 | * PHP5 passes objects by reference while PHP4 passes by value. As such, we need a function to guarantee |
||||||||
691 | * that all objects are passed by value, when appropriate. More information can be found here: |
||||||||
692 | * |
||||||||
693 | * {@link http://php.net/language.oop5.basic#51624} |
||||||||
694 | * |
||||||||
695 | * @access public |
||||||||
696 | * @see self::__clone() |
||||||||
697 | * @return \phpseclib\Math\BigInteger |
||||||||
698 | */ |
||||||||
699 | public function copy() |
||||||||
700 | { |
||||||||
701 | $temp = new static(); |
||||||||
702 | $temp->value = $this->value; |
||||||||
703 | $temp->is_negative = $this->is_negative; |
||||||||
704 | $temp->precision = $this->precision; |
||||||||
705 | $temp->bitmask = $this->bitmask; |
||||||||
706 | return $temp; |
||||||||
707 | } |
||||||||
708 | |||||||||
709 | /** |
||||||||
710 | * __toString() magic method |
||||||||
711 | * |
||||||||
712 | * Will be called, automatically, if you're supporting just PHP5. If you're supporting PHP4, you'll need to call |
||||||||
713 | * toString(). |
||||||||
714 | * |
||||||||
715 | * @access public |
||||||||
716 | * @internal Implemented per a suggestion by Techie-Michael - thanks! |
||||||||
717 | */ |
||||||||
718 | public function __toString() |
||||||||
719 | { |
||||||||
720 | return $this->toString(); |
||||||||
721 | } |
||||||||
722 | |||||||||
723 | /** |
||||||||
724 | * __clone() magic method |
||||||||
725 | * |
||||||||
726 | * Although you can call BigInteger::__toString() directly in PHP5, you cannot call BigInteger::__clone() directly |
||||||||
727 | * in PHP5. You can in PHP4 since it's not a magic method, but in PHP5, you have to call it by using the PHP5 |
||||||||
728 | * only syntax of $y = clone $x. As such, if you're trying to write an application that works on both PHP4 and |
||||||||
729 | * PHP5, call BigInteger::copy(), instead. |
||||||||
730 | * |
||||||||
731 | * @access public |
||||||||
732 | * @see self::copy() |
||||||||
733 | * @return \phpseclib\Math\BigInteger |
||||||||
734 | */ |
||||||||
735 | public function __clone() |
||||||||
736 | { |
||||||||
737 | return $this->copy(); |
||||||||
738 | } |
||||||||
739 | |||||||||
740 | /** |
||||||||
741 | * __sleep() magic method |
||||||||
742 | * |
||||||||
743 | * Will be called, automatically, when serialize() is called on a BigInteger object. |
||||||||
744 | * |
||||||||
745 | * @see self::__wakeup() |
||||||||
746 | * @access public |
||||||||
747 | */ |
||||||||
748 | public function __sleep() |
||||||||
749 | { |
||||||||
750 | $this->hex = $this->toHex(true); |
||||||||
751 | $vars = array('hex'); |
||||||||
752 | if ($this->precision > 0) { |
||||||||
753 | $vars[] = 'precision'; |
||||||||
754 | } |
||||||||
755 | return $vars; |
||||||||
756 | } |
||||||||
757 | |||||||||
758 | /** |
||||||||
759 | * __wakeup() magic method |
||||||||
760 | * |
||||||||
761 | * Will be called, automatically, when unserialize() is called on a BigInteger object. |
||||||||
762 | * |
||||||||
763 | * @see self::__sleep() |
||||||||
764 | * @access public |
||||||||
765 | */ |
||||||||
766 | public function __wakeup() |
||||||||
767 | { |
||||||||
768 | $temp = new static($this->hex, -16); |
||||||||
769 | $this->value = $temp->value; |
||||||||
770 | $this->is_negative = $temp->is_negative; |
||||||||
771 | if ($this->precision > 0) { |
||||||||
772 | // recalculate $this->bitmask |
||||||||
773 | $this->setPrecision($this->precision); |
||||||||
774 | } |
||||||||
775 | } |
||||||||
776 | |||||||||
777 | /** |
||||||||
778 | * __debugInfo() magic method |
||||||||
779 | * |
||||||||
780 | * Will be called, automatically, when print_r() or var_dump() are called |
||||||||
781 | * |
||||||||
782 | * @access public |
||||||||
783 | */ |
||||||||
784 | public function __debugInfo() |
||||||||
785 | { |
||||||||
786 | $opts = array(); |
||||||||
787 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
788 | case self::MODE_GMP: |
||||||||
789 | $engine = 'gmp'; |
||||||||
790 | break; |
||||||||
791 | case self::MODE_BCMATH: |
||||||||
792 | $engine = 'bcmath'; |
||||||||
793 | break; |
||||||||
794 | case self::MODE_INTERNAL: |
||||||||
795 | $engine = 'internal'; |
||||||||
796 | $opts[] = PHP_INT_SIZE == 8 ? '64-bit' : '32-bit'; |
||||||||
797 | } |
||||||||
798 | if (MATH_BIGINTEGER_MODE != self::MODE_GMP && defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) { |
||||||||
799 | $opts[] = 'OpenSSL'; |
||||||||
800 | } |
||||||||
801 | if (!empty($opts)) { |
||||||||
802 | $engine.= ' (' . implode($opts, ', ') . ')'; |
||||||||
0 ignored issues
–
show
Comprehensibility
Best Practice
introduced
by
The call to
implode() has too many arguments starting with ', ' .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
This check compares calls to functions or methods with their respective definitions. If the call has more arguments than are defined, it raises an issue. If a function is defined several times with a different number of parameters, the check may pick up the wrong definition and report false positives. One codebase where this has been known to happen is Wordpress. Please note the @ignore annotation hint above.
Loading history...
|
|||||||||
803 | } |
||||||||
804 | return array( |
||||||||
805 | 'value' => '0x' . $this->toHex(true), |
||||||||
806 | 'engine' => $engine |
||||||||
807 | ); |
||||||||
808 | } |
||||||||
809 | |||||||||
810 | /** |
||||||||
811 | * Adds two BigIntegers. |
||||||||
812 | * |
||||||||
813 | * Here's an example: |
||||||||
814 | * <code> |
||||||||
815 | * <?php |
||||||||
816 | * $a = new \phpseclib\Math\BigInteger('10'); |
||||||||
817 | * $b = new \phpseclib\Math\BigInteger('20'); |
||||||||
818 | * |
||||||||
819 | * $c = $a->add($b); |
||||||||
820 | * |
||||||||
821 | * echo $c->toString(); // outputs 30 |
||||||||
822 | * ?> |
||||||||
823 | * </code> |
||||||||
824 | * |
||||||||
825 | * @param \phpseclib\Math\BigInteger $y |
||||||||
826 | * @return \phpseclib\Math\BigInteger |
||||||||
827 | * @access public |
||||||||
828 | * @internal Performs base-2**52 addition |
||||||||
829 | */ |
||||||||
830 | public function add($y) |
||||||||
831 | { |
||||||||
832 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
833 | case self::MODE_GMP: |
||||||||
834 | $temp = new static(); |
||||||||
835 | $temp->value = gmp_add($this->value, $y->value); |
||||||||
0 ignored issues
–
show
It seems like
gmp_add($this->value, $y->value) of type GMP or resource is incompatible with the declared type array 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...
$y->value of type array is incompatible with the type GMP|resource|string expected by parameter $b of gmp_add() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_add() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
836 | |||||||||
837 | return $this->_normalize($temp); |
||||||||
838 | case self::MODE_BCMATH: |
||||||||
839 | $temp = new static(); |
||||||||
840 | $temp->value = bcadd($this->value, $y->value, 0); |
||||||||
0 ignored issues
–
show
$y->value of type array is incompatible with the type string expected by parameter $right_operand of bcadd() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$this->value of type array is incompatible with the type string expected by parameter $left_operand of bcadd() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
841 | |||||||||
842 | return $this->_normalize($temp); |
||||||||
843 | } |
||||||||
844 | |||||||||
845 | $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative); |
||||||||
846 | |||||||||
847 | $result = new static(); |
||||||||
848 | $result->value = $temp[self::VALUE]; |
||||||||
849 | $result->is_negative = $temp[self::SIGN]; |
||||||||
850 | |||||||||
851 | return $this->_normalize($result); |
||||||||
852 | } |
||||||||
853 | |||||||||
854 | /** |
||||||||
855 | * Performs addition. |
||||||||
856 | * |
||||||||
857 | * @param array $x_value |
||||||||
858 | * @param bool $x_negative |
||||||||
859 | * @param array $y_value |
||||||||
860 | * @param bool $y_negative |
||||||||
861 | * @return array |
||||||||
862 | * @access private |
||||||||
863 | */ |
||||||||
864 | public function _add($x_value, $x_negative, $y_value, $y_negative) |
||||||||
865 | { |
||||||||
866 | $x_size = count($x_value); |
||||||||
867 | $y_size = count($y_value); |
||||||||
868 | |||||||||
869 | if ($x_size == 0) { |
||||||||
870 | return array( |
||||||||
871 | self::VALUE => $y_value, |
||||||||
872 | self::SIGN => $y_negative |
||||||||
873 | ); |
||||||||
874 | } elseif ($y_size == 0) { |
||||||||
875 | return array( |
||||||||
876 | self::VALUE => $x_value, |
||||||||
877 | self::SIGN => $x_negative |
||||||||
878 | ); |
||||||||
879 | } |
||||||||
880 | |||||||||
881 | // subtract, if appropriate |
||||||||
882 | if ($x_negative != $y_negative) { |
||||||||
883 | if ($x_value == $y_value) { |
||||||||
884 | return array( |
||||||||
885 | self::VALUE => array(), |
||||||||
886 | self::SIGN => false |
||||||||
887 | ); |
||||||||
888 | } |
||||||||
889 | |||||||||
890 | $temp = $this->_subtract($x_value, false, $y_value, false); |
||||||||
891 | $temp[self::SIGN] = $this->_compare($x_value, false, $y_value, false) > 0 ? |
||||||||
892 | $x_negative : $y_negative; |
||||||||
893 | |||||||||
894 | return $temp; |
||||||||
895 | } |
||||||||
896 | |||||||||
897 | if ($x_size < $y_size) { |
||||||||
898 | $size = $x_size; |
||||||||
899 | $value = $y_value; |
||||||||
900 | } else { |
||||||||
901 | $size = $y_size; |
||||||||
902 | $value = $x_value; |
||||||||
903 | } |
||||||||
904 | |||||||||
905 | $value[count($value)] = 0; // just in case the carry adds an extra digit |
||||||||
906 | |||||||||
907 | $carry = 0; |
||||||||
908 | for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) { |
||||||||
909 | $sum = $x_value[$j] * self::$baseFull + $x_value[$i] + $y_value[$j] * self::$baseFull + $y_value[$i] + $carry; |
||||||||
910 | $carry = $sum >= self::$maxDigit2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1 |
||||||||
911 | $sum = $carry ? $sum - self::$maxDigit2 : $sum; |
||||||||
912 | |||||||||
913 | $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31); |
||||||||
914 | |||||||||
915 | $value[$i] = (int) ($sum - self::$baseFull * $temp); // eg. a faster alternative to fmod($sum, 0x4000000) |
||||||||
916 | $value[$j] = $temp; |
||||||||
917 | } |
||||||||
918 | |||||||||
919 | if ($j == $size) { // ie. if $y_size is odd |
||||||||
920 | $sum = $x_value[$i] + $y_value[$i] + $carry; |
||||||||
921 | $carry = $sum >= self::$baseFull; |
||||||||
922 | $value[$i] = $carry ? $sum - self::$baseFull : $sum; |
||||||||
923 | ++$i; // ie. let $i = $j since we've just done $value[$i] |
||||||||
924 | } |
||||||||
925 | |||||||||
926 | if ($carry) { |
||||||||
927 | for (; $value[$i] == self::$maxDigit; ++$i) { |
||||||||
928 | $value[$i] = 0; |
||||||||
929 | } |
||||||||
930 | ++$value[$i]; |
||||||||
931 | } |
||||||||
932 | |||||||||
933 | return array( |
||||||||
934 | self::VALUE => $this->_trim($value), |
||||||||
935 | self::SIGN => $x_negative |
||||||||
936 | ); |
||||||||
937 | } |
||||||||
938 | |||||||||
939 | /** |
||||||||
940 | * Subtracts two BigIntegers. |
||||||||
941 | * |
||||||||
942 | * Here's an example: |
||||||||
943 | * <code> |
||||||||
944 | * <?php |
||||||||
945 | * $a = new \phpseclib\Math\BigInteger('10'); |
||||||||
946 | * $b = new \phpseclib\Math\BigInteger('20'); |
||||||||
947 | * |
||||||||
948 | * $c = $a->subtract($b); |
||||||||
949 | * |
||||||||
950 | * echo $c->toString(); // outputs -10 |
||||||||
951 | * ?> |
||||||||
952 | * </code> |
||||||||
953 | * |
||||||||
954 | * @param \phpseclib\Math\BigInteger $y |
||||||||
955 | * @return \phpseclib\Math\BigInteger |
||||||||
956 | * @access public |
||||||||
957 | * @internal Performs base-2**52 subtraction |
||||||||
958 | */ |
||||||||
959 | public function subtract($y) |
||||||||
960 | { |
||||||||
961 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
962 | case self::MODE_GMP: |
||||||||
963 | $temp = new static(); |
||||||||
964 | $temp->value = gmp_sub($this->value, $y->value); |
||||||||
0 ignored issues
–
show
$y->value of type array is incompatible with the type GMP|resource|string expected by parameter $b of gmp_sub() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
It seems like
gmp_sub($this->value, $y->value) of type GMP or resource is incompatible with the declared type array 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...
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_sub() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
965 | |||||||||
966 | return $this->_normalize($temp); |
||||||||
967 | case self::MODE_BCMATH: |
||||||||
968 | $temp = new static(); |
||||||||
969 | $temp->value = bcsub($this->value, $y->value, 0); |
||||||||
0 ignored issues
–
show
$y->value of type array is incompatible with the type string expected by parameter $right_operand of bcsub() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$this->value of type array is incompatible with the type string expected by parameter $left_operand of bcsub() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
970 | |||||||||
971 | return $this->_normalize($temp); |
||||||||
972 | } |
||||||||
973 | |||||||||
974 | $temp = $this->_subtract($this->value, $this->is_negative, $y->value, $y->is_negative); |
||||||||
975 | |||||||||
976 | $result = new static(); |
||||||||
977 | $result->value = $temp[self::VALUE]; |
||||||||
978 | $result->is_negative = $temp[self::SIGN]; |
||||||||
979 | |||||||||
980 | return $this->_normalize($result); |
||||||||
981 | } |
||||||||
982 | |||||||||
983 | /** |
||||||||
984 | * Performs subtraction. |
||||||||
985 | * |
||||||||
986 | * @param array $x_value |
||||||||
987 | * @param bool $x_negative |
||||||||
988 | * @param array $y_value |
||||||||
989 | * @param bool $y_negative |
||||||||
990 | * @return array |
||||||||
991 | * @access private |
||||||||
992 | */ |
||||||||
993 | public function _subtract($x_value, $x_negative, $y_value, $y_negative) |
||||||||
994 | { |
||||||||
995 | $x_size = count($x_value); |
||||||||
996 | $y_size = count($y_value); |
||||||||
997 | |||||||||
998 | if ($x_size == 0) { |
||||||||
999 | return array( |
||||||||
1000 | self::VALUE => $y_value, |
||||||||
1001 | self::SIGN => !$y_negative |
||||||||
1002 | ); |
||||||||
1003 | } elseif ($y_size == 0) { |
||||||||
1004 | return array( |
||||||||
1005 | self::VALUE => $x_value, |
||||||||
1006 | self::SIGN => $x_negative |
||||||||
1007 | ); |
||||||||
1008 | } |
||||||||
1009 | |||||||||
1010 | // add, if appropriate (ie. -$x - +$y or +$x - -$y) |
||||||||
1011 | if ($x_negative != $y_negative) { |
||||||||
1012 | $temp = $this->_add($x_value, false, $y_value, false); |
||||||||
1013 | $temp[self::SIGN] = $x_negative; |
||||||||
1014 | |||||||||
1015 | return $temp; |
||||||||
1016 | } |
||||||||
1017 | |||||||||
1018 | $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative); |
||||||||
1019 | |||||||||
1020 | if (!$diff) { |
||||||||
1021 | return array( |
||||||||
1022 | self::VALUE => array(), |
||||||||
1023 | self::SIGN => false |
||||||||
1024 | ); |
||||||||
1025 | } |
||||||||
1026 | |||||||||
1027 | // switch $x and $y around, if appropriate. |
||||||||
1028 | if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) { |
||||||||
1029 | $temp = $x_value; |
||||||||
1030 | $x_value = $y_value; |
||||||||
1031 | $y_value = $temp; |
||||||||
1032 | |||||||||
1033 | $x_negative = !$x_negative; |
||||||||
1034 | |||||||||
1035 | $x_size = count($x_value); |
||||||||
0 ignored issues
–
show
|
|||||||||
1036 | $y_size = count($y_value); |
||||||||
1037 | } |
||||||||
1038 | |||||||||
1039 | // at this point, $x_value should be at least as big as - if not bigger than - $y_value |
||||||||
1040 | |||||||||
1041 | $carry = 0; |
||||||||
1042 | for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) { |
||||||||
1043 | $sum = $x_value[$j] * self::$baseFull + $x_value[$i] - $y_value[$j] * self::$baseFull - $y_value[$i] - $carry; |
||||||||
1044 | $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1 |
||||||||
1045 | $sum = $carry ? $sum + self::$maxDigit2 : $sum; |
||||||||
1046 | |||||||||
1047 | $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31); |
||||||||
1048 | |||||||||
1049 | $x_value[$i] = (int) ($sum - self::$baseFull * $temp); |
||||||||
1050 | $x_value[$j] = $temp; |
||||||||
1051 | } |
||||||||
1052 | |||||||||
1053 | if ($j == $y_size) { // ie. if $y_size is odd |
||||||||
1054 | $sum = $x_value[$i] - $y_value[$i] - $carry; |
||||||||
1055 | $carry = $sum < 0; |
||||||||
1056 | $x_value[$i] = $carry ? $sum + self::$baseFull : $sum; |
||||||||
1057 | ++$i; |
||||||||
1058 | } |
||||||||
1059 | |||||||||
1060 | if ($carry) { |
||||||||
1061 | for (; !$x_value[$i]; ++$i) { |
||||||||
1062 | $x_value[$i] = self::$maxDigit; |
||||||||
1063 | } |
||||||||
1064 | --$x_value[$i]; |
||||||||
1065 | } |
||||||||
1066 | |||||||||
1067 | return array( |
||||||||
1068 | self::VALUE => $this->_trim($x_value), |
||||||||
1069 | self::SIGN => $x_negative |
||||||||
1070 | ); |
||||||||
1071 | } |
||||||||
1072 | |||||||||
1073 | /** |
||||||||
1074 | * Multiplies two BigIntegers |
||||||||
1075 | * |
||||||||
1076 | * Here's an example: |
||||||||
1077 | * <code> |
||||||||
1078 | * <?php |
||||||||
1079 | * $a = new \phpseclib\Math\BigInteger('10'); |
||||||||
1080 | * $b = new \phpseclib\Math\BigInteger('20'); |
||||||||
1081 | * |
||||||||
1082 | * $c = $a->multiply($b); |
||||||||
1083 | * |
||||||||
1084 | * echo $c->toString(); // outputs 200 |
||||||||
1085 | * ?> |
||||||||
1086 | * </code> |
||||||||
1087 | * |
||||||||
1088 | * @param \phpseclib\Math\BigInteger $x |
||||||||
1089 | * @return \phpseclib\Math\BigInteger |
||||||||
1090 | * @access public |
||||||||
1091 | */ |
||||||||
1092 | public function multiply($x) |
||||||||
1093 | { |
||||||||
1094 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
1095 | case self::MODE_GMP: |
||||||||
1096 | $temp = new static(); |
||||||||
1097 | $temp->value = gmp_mul($this->value, $x->value); |
||||||||
0 ignored issues
–
show
It seems like
gmp_mul($this->value, $x->value) of type GMP or resource is incompatible with the declared type array 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...
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_mul() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$x->value of type array is incompatible with the type GMP|resource|string expected by parameter $b of gmp_mul() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1098 | |||||||||
1099 | return $this->_normalize($temp); |
||||||||
1100 | case self::MODE_BCMATH: |
||||||||
1101 | $temp = new static(); |
||||||||
1102 | $temp->value = bcmul($this->value, $x->value, 0); |
||||||||
0 ignored issues
–
show
$x->value of type array is incompatible with the type string expected by parameter $right_operand of bcmul() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$this->value of type array is incompatible with the type string expected by parameter $left_operand of bcmul() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1103 | |||||||||
1104 | return $this->_normalize($temp); |
||||||||
1105 | } |
||||||||
1106 | |||||||||
1107 | $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative); |
||||||||
1108 | |||||||||
1109 | $product = new static(); |
||||||||
1110 | $product->value = $temp[self::VALUE]; |
||||||||
1111 | $product->is_negative = $temp[self::SIGN]; |
||||||||
1112 | |||||||||
1113 | return $this->_normalize($product); |
||||||||
1114 | } |
||||||||
1115 | |||||||||
1116 | /** |
||||||||
1117 | * Performs multiplication. |
||||||||
1118 | * |
||||||||
1119 | * @param array $x_value |
||||||||
1120 | * @param bool $x_negative |
||||||||
1121 | * @param array $y_value |
||||||||
1122 | * @param bool $y_negative |
||||||||
1123 | * @return array |
||||||||
1124 | * @access private |
||||||||
1125 | */ |
||||||||
1126 | public function _multiply($x_value, $x_negative, $y_value, $y_negative) |
||||||||
1127 | { |
||||||||
1128 | //if ( $x_value == $y_value ) { |
||||||||
1129 | // return array( |
||||||||
1130 | // self::VALUE => $this->_square($x_value), |
||||||||
1131 | // self::SIGN => $x_sign != $y_value |
||||||||
1132 | // ); |
||||||||
1133 | //} |
||||||||
1134 | |||||||||
1135 | $x_length = count($x_value); |
||||||||
1136 | $y_length = count($y_value); |
||||||||
1137 | |||||||||
1138 | if (!$x_length || !$y_length) { // a 0 is being multiplied |
||||||||
1139 | return array( |
||||||||
1140 | self::VALUE => array(), |
||||||||
1141 | self::SIGN => false |
||||||||
1142 | ); |
||||||||
1143 | } |
||||||||
1144 | |||||||||
1145 | return array( |
||||||||
1146 | self::VALUE => min($x_length, $y_length) < 2 * self::KARATSUBA_CUTOFF ? |
||||||||
1147 | $this->_trim($this->_regularMultiply($x_value, $y_value)) : |
||||||||
1148 | $this->_trim($this->_karatsuba($x_value, $y_value)), |
||||||||
1149 | self::SIGN => $x_negative != $y_negative |
||||||||
1150 | ); |
||||||||
1151 | } |
||||||||
1152 | |||||||||
1153 | /** |
||||||||
1154 | * Performs long multiplication on two BigIntegers |
||||||||
1155 | * |
||||||||
1156 | * Modeled after 'multiply' in MutableBigInteger.java. |
||||||||
1157 | * |
||||||||
1158 | * @param array $x_value |
||||||||
1159 | * @param array $y_value |
||||||||
1160 | * @return array |
||||||||
1161 | * @access private |
||||||||
1162 | */ |
||||||||
1163 | public function _regularMultiply($x_value, $y_value) |
||||||||
1164 | { |
||||||||
1165 | $x_length = count($x_value); |
||||||||
1166 | $y_length = count($y_value); |
||||||||
1167 | |||||||||
1168 | if (!$x_length || !$y_length) { // a 0 is being multiplied |
||||||||
1169 | return array(); |
||||||||
1170 | } |
||||||||
1171 | |||||||||
1172 | if ($x_length < $y_length) { |
||||||||
1173 | $temp = $x_value; |
||||||||
1174 | $x_value = $y_value; |
||||||||
1175 | $y_value = $temp; |
||||||||
1176 | |||||||||
1177 | $x_length = count($x_value); |
||||||||
1178 | $y_length = count($y_value); |
||||||||
1179 | } |
||||||||
1180 | |||||||||
1181 | $product_value = $this->_array_repeat(0, $x_length + $y_length); |
||||||||
1182 | |||||||||
1183 | // the following for loop could be removed if the for loop following it |
||||||||
1184 | // (the one with nested for loops) initially set $i to 0, but |
||||||||
1185 | // doing so would also make the result in one set of unnecessary adds, |
||||||||
1186 | // since on the outermost loops first pass, $product->value[$k] is going |
||||||||
1187 | // to always be 0 |
||||||||
1188 | |||||||||
1189 | $carry = 0; |
||||||||
1190 | |||||||||
1191 | for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0 |
||||||||
1192 | $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0 |
||||||||
1193 | $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); |
||||||||
1194 | $product_value[$j] = (int) ($temp - self::$baseFull * $carry); |
||||||||
1195 | } |
||||||||
1196 | |||||||||
1197 | $product_value[$j] = $carry; |
||||||||
1198 | |||||||||
1199 | // the above for loop is what the previous comment was talking about. the |
||||||||
1200 | // following for loop is the "one with nested for loops" |
||||||||
1201 | for ($i = 1; $i < $y_length; ++$i) { |
||||||||
1202 | $carry = 0; |
||||||||
1203 | |||||||||
1204 | for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) { |
||||||||
1205 | $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry; |
||||||||
1206 | $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); |
||||||||
1207 | $product_value[$k] = (int) ($temp - self::$baseFull * $carry); |
||||||||
1208 | } |
||||||||
1209 | |||||||||
1210 | $product_value[$k] = $carry; |
||||||||
1211 | } |
||||||||
1212 | |||||||||
1213 | return $product_value; |
||||||||
1214 | } |
||||||||
1215 | |||||||||
1216 | /** |
||||||||
1217 | * Performs Karatsuba multiplication on two BigIntegers |
||||||||
1218 | * |
||||||||
1219 | * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and |
||||||||
1220 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}. |
||||||||
1221 | * |
||||||||
1222 | * @param array $x_value |
||||||||
1223 | * @param array $y_value |
||||||||
1224 | * @return array |
||||||||
1225 | * @access private |
||||||||
1226 | */ |
||||||||
1227 | public function _karatsuba($x_value, $y_value) |
||||||||
1228 | { |
||||||||
1229 | $m = min(count($x_value) >> 1, count($y_value) >> 1); |
||||||||
1230 | |||||||||
1231 | if ($m < self::KARATSUBA_CUTOFF) { |
||||||||
1232 | return $this->_regularMultiply($x_value, $y_value); |
||||||||
1233 | } |
||||||||
1234 | |||||||||
1235 | $x1 = array_slice($x_value, $m); |
||||||||
1236 | $x0 = array_slice($x_value, 0, $m); |
||||||||
1237 | $y1 = array_slice($y_value, $m); |
||||||||
1238 | $y0 = array_slice($y_value, 0, $m); |
||||||||
1239 | |||||||||
1240 | $z2 = $this->_karatsuba($x1, $y1); |
||||||||
1241 | $z0 = $this->_karatsuba($x0, $y0); |
||||||||
1242 | |||||||||
1243 | $z1 = $this->_add($x1, false, $x0, false); |
||||||||
1244 | $temp = $this->_add($y1, false, $y0, false); |
||||||||
1245 | $z1 = $this->_karatsuba($z1[self::VALUE], $temp[self::VALUE]); |
||||||||
1246 | $temp = $this->_add($z2, false, $z0, false); |
||||||||
1247 | $z1 = $this->_subtract($z1, false, $temp[self::VALUE], false); |
||||||||
1248 | |||||||||
1249 | $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2); |
||||||||
1250 | $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]); |
||||||||
1251 | |||||||||
1252 | $xy = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]); |
||||||||
1253 | $xy = $this->_add($xy[self::VALUE], $xy[self::SIGN], $z0, false); |
||||||||
1254 | |||||||||
1255 | return $xy[self::VALUE]; |
||||||||
1256 | } |
||||||||
1257 | |||||||||
1258 | /** |
||||||||
1259 | * Performs squaring |
||||||||
1260 | * |
||||||||
1261 | * @param array $x |
||||||||
1262 | * @return array |
||||||||
1263 | * @access private |
||||||||
1264 | */ |
||||||||
1265 | public function _square($x = false) |
||||||||
1266 | { |
||||||||
1267 | return count($x) < 2 * self::KARATSUBA_CUTOFF ? |
||||||||
0 ignored issues
–
show
It seems like
$x can also be of type false ; however, parameter $var of count() does only seem to accept Countable|array , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1268 | $this->_trim($this->_baseSquare($x)) : |
||||||||
0 ignored issues
–
show
It seems like
$x can also be of type false ; however, parameter $value of phpseclib\Math\BigInteger::_baseSquare() does only seem to accept array , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1269 | $this->_trim($this->_karatsubaSquare($x)); |
||||||||
0 ignored issues
–
show
It seems like
$x can also be of type false ; however, parameter $value of phpseclib\Math\BigInteger::_karatsubaSquare() does only seem to accept array , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1270 | } |
||||||||
1271 | |||||||||
1272 | /** |
||||||||
1273 | * Performs traditional squaring on two BigIntegers |
||||||||
1274 | * |
||||||||
1275 | * Squaring can be done faster than multiplying a number by itself can be. See |
||||||||
1276 | * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} / |
||||||||
1277 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information. |
||||||||
1278 | * |
||||||||
1279 | * @param array $value |
||||||||
1280 | * @return array |
||||||||
1281 | * @access private |
||||||||
1282 | */ |
||||||||
1283 | public function _baseSquare($value) |
||||||||
1284 | { |
||||||||
1285 | if (empty($value)) { |
||||||||
1286 | return array(); |
||||||||
1287 | } |
||||||||
1288 | $square_value = $this->_array_repeat(0, 2 * count($value)); |
||||||||
1289 | |||||||||
1290 | for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) { |
||||||||
1291 | $i2 = $i << 1; |
||||||||
1292 | |||||||||
1293 | $temp = $square_value[$i2] + $value[$i] * $value[$i]; |
||||||||
1294 | $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); |
||||||||
1295 | $square_value[$i2] = (int) ($temp - self::$baseFull * $carry); |
||||||||
1296 | |||||||||
1297 | // note how we start from $i+1 instead of 0 as we do in multiplication. |
||||||||
1298 | for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) { |
||||||||
1299 | $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry; |
||||||||
1300 | $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); |
||||||||
1301 | $square_value[$k] = (int) ($temp - self::$baseFull * $carry); |
||||||||
1302 | } |
||||||||
1303 | |||||||||
1304 | // the following line can yield values larger 2**15. at this point, PHP should switch |
||||||||
1305 | // over to floats. |
||||||||
1306 | $square_value[$i + $max_index + 1] = $carry; |
||||||||
1307 | } |
||||||||
1308 | |||||||||
1309 | return $square_value; |
||||||||
1310 | } |
||||||||
1311 | |||||||||
1312 | /** |
||||||||
1313 | * Performs Karatsuba "squaring" on two BigIntegers |
||||||||
1314 | * |
||||||||
1315 | * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and |
||||||||
1316 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}. |
||||||||
1317 | * |
||||||||
1318 | * @param array $value |
||||||||
1319 | * @return array |
||||||||
1320 | * @access private |
||||||||
1321 | */ |
||||||||
1322 | public function _karatsubaSquare($value) |
||||||||
1323 | { |
||||||||
1324 | $m = count($value) >> 1; |
||||||||
1325 | |||||||||
1326 | if ($m < self::KARATSUBA_CUTOFF) { |
||||||||
1327 | return $this->_baseSquare($value); |
||||||||
1328 | } |
||||||||
1329 | |||||||||
1330 | $x1 = array_slice($value, $m); |
||||||||
1331 | $x0 = array_slice($value, 0, $m); |
||||||||
1332 | |||||||||
1333 | $z2 = $this->_karatsubaSquare($x1); |
||||||||
1334 | $z0 = $this->_karatsubaSquare($x0); |
||||||||
1335 | |||||||||
1336 | $z1 = $this->_add($x1, false, $x0, false); |
||||||||
1337 | $z1 = $this->_karatsubaSquare($z1[self::VALUE]); |
||||||||
1338 | $temp = $this->_add($z2, false, $z0, false); |
||||||||
1339 | $z1 = $this->_subtract($z1, false, $temp[self::VALUE], false); |
||||||||
1340 | |||||||||
1341 | $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2); |
||||||||
1342 | $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]); |
||||||||
1343 | |||||||||
1344 | $xx = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]); |
||||||||
1345 | $xx = $this->_add($xx[self::VALUE], $xx[self::SIGN], $z0, false); |
||||||||
1346 | |||||||||
1347 | return $xx[self::VALUE]; |
||||||||
1348 | } |
||||||||
1349 | |||||||||
1350 | /** |
||||||||
1351 | * Divides two BigIntegers. |
||||||||
1352 | * |
||||||||
1353 | * Returns an array whose first element contains the quotient and whose second element contains the |
||||||||
1354 | * "common residue". If the remainder would be positive, the "common residue" and the remainder are the |
||||||||
1355 | * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder |
||||||||
1356 | * and the divisor (basically, the "common residue" is the first positive modulo). |
||||||||
1357 | * |
||||||||
1358 | * Here's an example: |
||||||||
1359 | * <code> |
||||||||
1360 | * <?php |
||||||||
1361 | * $a = new \phpseclib\Math\BigInteger('10'); |
||||||||
1362 | * $b = new \phpseclib\Math\BigInteger('20'); |
||||||||
1363 | * |
||||||||
1364 | * list($quotient, $remainder) = $a->divide($b); |
||||||||
1365 | * |
||||||||
1366 | * echo $quotient->toString(); // outputs 0 |
||||||||
1367 | * echo "\r\n"; |
||||||||
1368 | * echo $remainder->toString(); // outputs 10 |
||||||||
1369 | * ?> |
||||||||
1370 | * </code> |
||||||||
1371 | * |
||||||||
1372 | * @param \phpseclib\Math\BigInteger $y |
||||||||
1373 | * @return array |
||||||||
1374 | * @access public |
||||||||
1375 | * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}. |
||||||||
1376 | */ |
||||||||
1377 | public function divide($y) |
||||||||
1378 | { |
||||||||
1379 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
1380 | case self::MODE_GMP: |
||||||||
1381 | $quotient = new static(); |
||||||||
1382 | $remainder = new static(); |
||||||||
1383 | |||||||||
1384 | list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $n of gmp_div_qr() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$y->value of type array is incompatible with the type GMP|resource|string expected by parameter $d of gmp_div_qr() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1385 | |||||||||
1386 | if (gmp_sign($remainder->value) < 0) { |
||||||||
1387 | $remainder->value = gmp_add($remainder->value, gmp_abs($y->value)); |
||||||||
0 ignored issues
–
show
$y->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_abs() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
It seems like
gmp_add($remainder->value, gmp_abs($y->value)) of type GMP or resource is incompatible with the declared type array 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...
|
|||||||||
1388 | } |
||||||||
1389 | |||||||||
1390 | return array($this->_normalize($quotient), $this->_normalize($remainder)); |
||||||||
1391 | case self::MODE_BCMATH: |
||||||||
1392 | $quotient = new static(); |
||||||||
1393 | $remainder = new static(); |
||||||||
1394 | |||||||||
1395 | $quotient->value = bcdiv($this->value, $y->value, 0); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type string expected by parameter $dividend of bcdiv() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
It seems like
bcdiv($this->value, $y->value, 0) can also be of type string . However, the property $value is declared as type array . Maybe add an additional type check?
Our type inference engine has found a suspicous assignment of a value to a property. This check raises an issue when a value that can be of a mixed type is assigned to a property that is type hinted more strictly. For example, imagine you have a variable Either this assignment is in error or a type check should be added for that assignment. class Id
{
public $id;
public function __construct($id)
{
$this->id = $id;
}
}
class Account
{
/** @var Id $id */
public $id;
}
$account_id = false;
if (starsAreRight()) {
$account_id = new Id(42);
}
$account = new Account();
if ($account instanceof Id)
{
$account->id = $account_id;
}
Loading history...
$y->value of type array is incompatible with the type string expected by parameter $divisor of bcdiv() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1396 | $remainder->value = bcmod($this->value, $y->value); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type string expected by parameter $dividend of bcmod() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$y->value of type array is incompatible with the type string expected by parameter $divisor of bcmod() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1397 | |||||||||
1398 | if ($remainder->value[0] == '-') { |
||||||||
1399 | $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0); |
||||||||
0 ignored issues
–
show
$y->value of type array is incompatible with the type string expected by parameter $string of substr() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
It seems like
$y->value[0] == '-' ? su...->value, 1) : $y->value can also be of type array ; however, parameter $right_operand of bcadd() does only seem to accept string , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1400 | } |
||||||||
1401 | |||||||||
1402 | return array($this->_normalize($quotient), $this->_normalize($remainder)); |
||||||||
1403 | } |
||||||||
1404 | |||||||||
1405 | if (count($y->value) == 1) { |
||||||||
1406 | list($q, $r) = $this->_divide_digit($this->value, $y->value[0]); |
||||||||
1407 | $quotient = new static(); |
||||||||
1408 | $remainder = new static(); |
||||||||
1409 | $quotient->value = $q; |
||||||||
1410 | $remainder->value = array($r); |
||||||||
1411 | $quotient->is_negative = $this->is_negative != $y->is_negative; |
||||||||
1412 | return array($this->_normalize($quotient), $this->_normalize($remainder)); |
||||||||
1413 | } |
||||||||
1414 | |||||||||
1415 | static $zero; |
||||||||
1416 | if (!isset($zero)) { |
||||||||
1417 | $zero = new static(); |
||||||||
1418 | } |
||||||||
1419 | |||||||||
1420 | $x = $this->copy(); |
||||||||
1421 | $y = $y->copy(); |
||||||||
1422 | |||||||||
1423 | $x_sign = $x->is_negative; |
||||||||
1424 | $y_sign = $y->is_negative; |
||||||||
1425 | |||||||||
1426 | $x->is_negative = $y->is_negative = false; |
||||||||
1427 | |||||||||
1428 | $diff = $x->compare($y); |
||||||||
1429 | |||||||||
1430 | if (!$diff) { |
||||||||
1431 | $temp = new static(); |
||||||||
1432 | $temp->value = array(1); |
||||||||
1433 | $temp->is_negative = $x_sign != $y_sign; |
||||||||
1434 | return array($this->_normalize($temp), $this->_normalize(new static())); |
||||||||
1435 | } |
||||||||
1436 | |||||||||
1437 | if ($diff < 0) { |
||||||||
1438 | // if $x is negative, "add" $y. |
||||||||
1439 | if ($x_sign) { |
||||||||
1440 | $x = $y->subtract($x); |
||||||||
1441 | } |
||||||||
1442 | return array($this->_normalize(new static()), $this->_normalize($x)); |
||||||||
1443 | } |
||||||||
1444 | |||||||||
1445 | // normalize $x and $y as described in HAC 14.23 / 14.24 |
||||||||
1446 | $msb = $y->value[count($y->value) - 1]; |
||||||||
1447 | for ($shift = 0; !($msb & self::$msb); ++$shift) { |
||||||||
1448 | $msb <<= 1; |
||||||||
1449 | } |
||||||||
1450 | $x->_lshift($shift); |
||||||||
1451 | $y->_lshift($shift); |
||||||||
1452 | $y_value = &$y->value; |
||||||||
1453 | |||||||||
1454 | $x_max = count($x->value) - 1; |
||||||||
1455 | $y_max = count($y->value) - 1; |
||||||||
1456 | |||||||||
1457 | $quotient = new static(); |
||||||||
1458 | $quotient_value = &$quotient->value; |
||||||||
1459 | $quotient_value = $this->_array_repeat(0, $x_max - $y_max + 1); |
||||||||
1460 | |||||||||
1461 | static $temp, $lhs, $rhs; |
||||||||
1462 | if (!isset($temp)) { |
||||||||
1463 | $temp = new static(); |
||||||||
1464 | $lhs = new static(); |
||||||||
1465 | $rhs = new static(); |
||||||||
1466 | } |
||||||||
1467 | $temp_value = &$temp->value; |
||||||||
1468 | $rhs_value = &$rhs->value; |
||||||||
1469 | |||||||||
1470 | // $temp = $y << ($x_max - $y_max-1) in base 2**26 |
||||||||
1471 | $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value); |
||||||||
1472 | |||||||||
1473 | while ($x->compare($temp) >= 0) { |
||||||||
1474 | // calculate the "common residue" |
||||||||
1475 | ++$quotient_value[$x_max - $y_max]; |
||||||||
1476 | $x = $x->subtract($temp); |
||||||||
1477 | $x_max = count($x->value) - 1; |
||||||||
1478 | } |
||||||||
1479 | |||||||||
1480 | for ($i = $x_max; $i >= $y_max + 1; --$i) { |
||||||||
1481 | $x_value = &$x->value; |
||||||||
1482 | $x_window = array( |
||||||||
1483 | isset($x_value[$i]) ? $x_value[$i] : 0, |
||||||||
1484 | isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0, |
||||||||
1485 | isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0 |
||||||||
1486 | ); |
||||||||
1487 | $y_window = array( |
||||||||
1488 | $y_value[$y_max], |
||||||||
1489 | ($y_max > 0) ? $y_value[$y_max - 1] : 0 |
||||||||
1490 | ); |
||||||||
1491 | |||||||||
1492 | $q_index = $i - $y_max - 1; |
||||||||
1493 | if ($x_window[0] == $y_window[0]) { |
||||||||
1494 | $quotient_value[$q_index] = self::$maxDigit; |
||||||||
1495 | } else { |
||||||||
1496 | $quotient_value[$q_index] = $this->_safe_divide( |
||||||||
1497 | $x_window[0] * self::$baseFull + $x_window[1], |
||||||||
1498 | $y_window[0] |
||||||||
1499 | ); |
||||||||
1500 | } |
||||||||
1501 | |||||||||
1502 | $temp_value = array($y_window[1], $y_window[0]); |
||||||||
1503 | |||||||||
1504 | $lhs->value = array($quotient_value[$q_index]); |
||||||||
1505 | $lhs = $lhs->multiply($temp); |
||||||||
1506 | |||||||||
1507 | $rhs_value = array($x_window[2], $x_window[1], $x_window[0]); |
||||||||
1508 | |||||||||
1509 | while ($lhs->compare($rhs) > 0) { |
||||||||
1510 | --$quotient_value[$q_index]; |
||||||||
1511 | |||||||||
1512 | $lhs->value = array($quotient_value[$q_index]); |
||||||||
1513 | $lhs = $lhs->multiply($temp); |
||||||||
1514 | } |
||||||||
1515 | |||||||||
1516 | $adjust = $this->_array_repeat(0, $q_index); |
||||||||
1517 | $temp_value = array($quotient_value[$q_index]); |
||||||||
1518 | $temp = $temp->multiply($y); |
||||||||
1519 | $temp_value = &$temp->value; |
||||||||
1520 | $temp_value = array_merge($adjust, $temp_value); |
||||||||
1521 | |||||||||
1522 | $x = $x->subtract($temp); |
||||||||
1523 | |||||||||
1524 | if ($x->compare($zero) < 0) { |
||||||||
1525 | $temp_value = array_merge($adjust, $y_value); |
||||||||
1526 | $x = $x->add($temp); |
||||||||
1527 | |||||||||
1528 | --$quotient_value[$q_index]; |
||||||||
1529 | } |
||||||||
1530 | |||||||||
1531 | $x_max = count($x_value) - 1; |
||||||||
0 ignored issues
–
show
|
|||||||||
1532 | } |
||||||||
1533 | |||||||||
1534 | // unnormalize the remainder |
||||||||
1535 | $x->_rshift($shift); |
||||||||
1536 | |||||||||
1537 | $quotient->is_negative = $x_sign != $y_sign; |
||||||||
1538 | |||||||||
1539 | // calculate the "common residue", if appropriate |
||||||||
1540 | if ($x_sign) { |
||||||||
1541 | $y->_rshift($shift); |
||||||||
1542 | $x = $y->subtract($x); |
||||||||
1543 | } |
||||||||
1544 | |||||||||
1545 | return array($this->_normalize($quotient), $this->_normalize($x)); |
||||||||
1546 | } |
||||||||
1547 | |||||||||
1548 | /** |
||||||||
1549 | * Divides a BigInteger by a regular integer |
||||||||
1550 | * |
||||||||
1551 | * abc / x = a00 / x + b0 / x + c / x |
||||||||
1552 | * |
||||||||
1553 | * @param array $dividend |
||||||||
1554 | * @param array $divisor |
||||||||
1555 | * @return array |
||||||||
1556 | * @access private |
||||||||
1557 | */ |
||||||||
1558 | public function _divide_digit($dividend, $divisor) |
||||||||
1559 | { |
||||||||
1560 | $carry = 0; |
||||||||
1561 | $result = array(); |
||||||||
1562 | |||||||||
1563 | for ($i = count($dividend) - 1; $i >= 0; --$i) { |
||||||||
1564 | $temp = self::$baseFull * $carry + $dividend[$i]; |
||||||||
1565 | $result[$i] = $this->_safe_divide($temp, $divisor); |
||||||||
0 ignored issues
–
show
$divisor of type array is incompatible with the type integer expected by parameter $y of phpseclib\Math\BigInteger::_safe_divide() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1566 | $carry = (int) ($temp - $divisor * $result[$i]); |
||||||||
1567 | } |
||||||||
1568 | |||||||||
1569 | return array($result, $carry); |
||||||||
1570 | } |
||||||||
1571 | |||||||||
1572 | /** |
||||||||
1573 | * Performs modular exponentiation. |
||||||||
1574 | * |
||||||||
1575 | * Here's an example: |
||||||||
1576 | * <code> |
||||||||
1577 | * <?php |
||||||||
1578 | * $a = new \phpseclib\Math\BigInteger('10'); |
||||||||
1579 | * $b = new \phpseclib\Math\BigInteger('20'); |
||||||||
1580 | * $c = new \phpseclib\Math\BigInteger('30'); |
||||||||
1581 | * |
||||||||
1582 | * $c = $a->modPow($b, $c); |
||||||||
1583 | * |
||||||||
1584 | * echo $c->toString(); // outputs 10 |
||||||||
1585 | * ?> |
||||||||
1586 | * </code> |
||||||||
1587 | * |
||||||||
1588 | * @param \phpseclib\Math\BigInteger $e |
||||||||
1589 | * @param \phpseclib\Math\BigInteger $n |
||||||||
1590 | * @return \phpseclib\Math\BigInteger |
||||||||
1591 | * @access public |
||||||||
1592 | * @internal The most naive approach to modular exponentiation has very unreasonable requirements, and |
||||||||
1593 | * and although the approach involving repeated squaring does vastly better, it, too, is impractical |
||||||||
1594 | * for our purposes. The reason being that division - by far the most complicated and time-consuming |
||||||||
1595 | * of the basic operations (eg. +,-,*,/) - occurs multiple times within it. |
||||||||
1596 | * |
||||||||
1597 | * Modular reductions resolve this issue. Although an individual modular reduction takes more time |
||||||||
1598 | * then an individual division, when performed in succession (with the same modulo), they're a lot faster. |
||||||||
1599 | * |
||||||||
1600 | * The two most commonly used modular reductions are Barrett and Montgomery reduction. Montgomery reduction, |
||||||||
1601 | * although faster, only works when the gcd of the modulo and of the base being used is 1. In RSA, when the |
||||||||
1602 | * base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because |
||||||||
1603 | * the product of two odd numbers is odd), but what about when RSA isn't used? |
||||||||
1604 | * |
||||||||
1605 | * In contrast, Barrett reduction has no such constraint. As such, some bigint implementations perform a |
||||||||
1606 | * Barrett reduction after every operation in the modpow function. Others perform Barrett reductions when the |
||||||||
1607 | * modulo is even and Montgomery reductions when the modulo is odd. BigInteger.java's modPow method, however, |
||||||||
1608 | * uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and |
||||||||
1609 | * the other, a power of two - and recombine them, later. This is the method that this modPow function uses. |
||||||||
1610 | * {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates. |
||||||||
1611 | */ |
||||||||
1612 | public function modPow($e, $n) |
||||||||
1613 | { |
||||||||
1614 | $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs(); |
||||||||
1615 | |||||||||
1616 | if ($e->compare(new static()) < 0) { |
||||||||
1617 | $e = $e->abs(); |
||||||||
1618 | |||||||||
1619 | $temp = $this->modInverse($n); |
||||||||
0 ignored issues
–
show
It seems like
$n can also be of type true ; however, parameter $n of phpseclib\Math\BigInteger::modInverse() does only seem to accept phpseclib\Math\BigInteger , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1620 | if ($temp === false) { |
||||||||
1621 | return false; |
||||||||
1622 | } |
||||||||
1623 | |||||||||
1624 | return $this->_normalize($temp->modPow($e, $n)); |
||||||||
0 ignored issues
–
show
It seems like
$n can also be of type true ; however, parameter $n of phpseclib\Math\BigInteger::modPow() does only seem to accept phpseclib\Math\BigInteger , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1625 | } |
||||||||
1626 | |||||||||
1627 | if (MATH_BIGINTEGER_MODE == self::MODE_GMP) { |
||||||||
1628 | $temp = new static(); |
||||||||
1629 | $temp->value = gmp_powm($this->value, $e->value, $n->value); |
||||||||
0 ignored issues
–
show
It seems like
gmp_powm($this->value, $e->value, $n->value) of type GMP or resource is incompatible with the declared type array 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...
$n->value of type array is incompatible with the type GMP|resource|string expected by parameter $mod of gmp_powm() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $base of gmp_powm() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$e->value of type array is incompatible with the type GMP|resource|string expected by parameter $exp of gmp_powm() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1630 | |||||||||
1631 | return $this->_normalize($temp); |
||||||||
1632 | } |
||||||||
1633 | |||||||||
1634 | if ($this->compare(new static()) < 0 || $this->compare($n) > 0) { |
||||||||
0 ignored issues
–
show
It seems like
$n can also be of type true ; however, parameter $y of phpseclib\Math\BigInteger::compare() does only seem to accept phpseclib\Math\BigInteger , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1635 | list(, $temp) = $this->divide($n); |
||||||||
0 ignored issues
–
show
It seems like
$n can also be of type true ; however, parameter $y of phpseclib\Math\BigInteger::divide() does only seem to accept phpseclib\Math\BigInteger , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1636 | return $temp->modPow($e, $n); |
||||||||
1637 | } |
||||||||
1638 | |||||||||
1639 | if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) { |
||||||||
1640 | $components = array( |
||||||||
1641 | 'modulus' => $n->toBytes(true), |
||||||||
1642 | 'publicExponent' => $e->toBytes(true) |
||||||||
1643 | ); |
||||||||
1644 | |||||||||
1645 | $components = array( |
||||||||
1646 | 'modulus' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']), |
||||||||
1647 | 'publicExponent' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent']) |
||||||||
1648 | ); |
||||||||
1649 | |||||||||
1650 | $RSAPublicKey = pack( |
||||||||
1651 | 'Ca*a*a*', |
||||||||
1652 | 48, |
||||||||
1653 | $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])), |
||||||||
1654 | $components['modulus'], |
||||||||
1655 | $components['publicExponent'] |
||||||||
1656 | ); |
||||||||
1657 | |||||||||
1658 | $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA |
||||||||
1659 | $RSAPublicKey = chr(0) . $RSAPublicKey; |
||||||||
1660 | $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey; |
||||||||
1661 | |||||||||
1662 | $encapsulated = pack( |
||||||||
1663 | 'Ca*a*', |
||||||||
1664 | 48, |
||||||||
1665 | $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)), |
||||||||
1666 | $rsaOID . $RSAPublicKey |
||||||||
1667 | ); |
||||||||
1668 | |||||||||
1669 | $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" . |
||||||||
1670 | chunk_split(base64_encode($encapsulated)) . |
||||||||
1671 | '-----END PUBLIC KEY-----'; |
||||||||
1672 | |||||||||
1673 | $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT); |
||||||||
1674 | |||||||||
1675 | if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING)) { |
||||||||
1676 | return new static($result, 256); |
||||||||
1677 | } |
||||||||
1678 | } |
||||||||
1679 | |||||||||
1680 | if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) { |
||||||||
1681 | $temp = new static(); |
||||||||
1682 | $temp->value = bcpowmod($this->value, $e->value, $n->value, 0); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type string expected by parameter $base of bcpowmod() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$e->value of type array is incompatible with the type string expected by parameter $exponent of bcpowmod() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$n->value of type array is incompatible with the type string expected by parameter $modulus of bcpowmod() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1683 | |||||||||
1684 | return $this->_normalize($temp); |
||||||||
1685 | } |
||||||||
1686 | |||||||||
1687 | if (empty($e->value)) { |
||||||||
1688 | $temp = new static(); |
||||||||
1689 | $temp->value = array(1); |
||||||||
1690 | return $this->_normalize($temp); |
||||||||
1691 | } |
||||||||
1692 | |||||||||
1693 | if ($e->value == array(1)) { |
||||||||
1694 | list(, $temp) = $this->divide($n); |
||||||||
1695 | return $this->_normalize($temp); |
||||||||
1696 | } |
||||||||
1697 | |||||||||
1698 | if ($e->value == array(2)) { |
||||||||
1699 | $temp = new static(); |
||||||||
1700 | $temp->value = $this->_square($this->value); |
||||||||
1701 | list(, $temp) = $temp->divide($n); |
||||||||
1702 | return $this->_normalize($temp); |
||||||||
1703 | } |
||||||||
1704 | |||||||||
1705 | return $this->_normalize($this->_slidingWindow($e, $n, self::BARRETT)); |
||||||||
0 ignored issues
–
show
It seems like
$n can also be of type true ; however, parameter $n of phpseclib\Math\BigInteger::_slidingWindow() does only seem to accept phpseclib\Math\BigInteger , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1706 | |||||||||
1707 | // the following code, although not callable, can be run independently of the above code |
||||||||
1708 | // although the above code performed better in my benchmarks the following could might |
||||||||
1709 | // perform better under different circumstances. in lieu of deleting it it's just been |
||||||||
1710 | // made uncallable |
||||||||
1711 | |||||||||
1712 | // is the modulo odd? |
||||||||
1713 | if ($n->value[0] & 1) { |
||||||||
1714 | return $this->_normalize($this->_slidingWindow($e, $n, self::MONTGOMERY)); |
||||||||
1715 | } |
||||||||
1716 | // if it's not, it's even |
||||||||
1717 | |||||||||
1718 | // find the lowest set bit (eg. the max pow of 2 that divides $n) |
||||||||
1719 | for ($i = 0; $i < count($n->value); ++$i) { |
||||||||
0 ignored issues
–
show
It seems like you are calling the size function
count() as part of the test condition. You might want to compute the size beforehand, and not on each iteration.
If the size of the collection does not change during the iteration, it is generally a good practice to compute it beforehand, and not on each iteration: for ($i=0; $i<count($array); $i++) { // calls count() on each iteration
}
// Better
for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once
}
Loading history...
|
|||||||||
1720 | if ($n->value[$i]) { |
||||||||
1721 | $temp = decbin($n->value[$i]); |
||||||||
1722 | $j = strlen($temp) - strrpos($temp, '1') - 1; |
||||||||
1723 | $j+= 26 * $i; |
||||||||
1724 | break; |
||||||||
1725 | } |
||||||||
1726 | } |
||||||||
1727 | // at this point, 2^$j * $n/(2^$j) == $n |
||||||||
1728 | |||||||||
1729 | $mod1 = $n->copy(); |
||||||||
1730 | $mod1->_rshift($j); |
||||||||
1731 | $mod2 = new static(); |
||||||||
1732 | $mod2->value = array(1); |
||||||||
1733 | $mod2->_lshift($j); |
||||||||
1734 | |||||||||
1735 | $part1 = ($mod1->value != array(1)) ? $this->_slidingWindow($e, $mod1, self::MONTGOMERY) : new static(); |
||||||||
1736 | $part2 = $this->_slidingWindow($e, $mod2, self::POWEROF2); |
||||||||
1737 | |||||||||
1738 | $y1 = $mod2->modInverse($mod1); |
||||||||
1739 | $y2 = $mod1->modInverse($mod2); |
||||||||
1740 | |||||||||
1741 | $result = $part1->multiply($mod2); |
||||||||
1742 | $result = $result->multiply($y1); |
||||||||
1743 | |||||||||
1744 | $temp = $part2->multiply($mod1); |
||||||||
1745 | $temp = $temp->multiply($y2); |
||||||||
1746 | |||||||||
1747 | $result = $result->add($temp); |
||||||||
1748 | list(, $result) = $result->divide($n); |
||||||||
1749 | |||||||||
1750 | return $this->_normalize($result); |
||||||||
1751 | } |
||||||||
1752 | |||||||||
1753 | /** |
||||||||
1754 | * Performs modular exponentiation. |
||||||||
1755 | * |
||||||||
1756 | * Alias for modPow(). |
||||||||
1757 | * |
||||||||
1758 | * @param \phpseclib\Math\BigInteger $e |
||||||||
1759 | * @param \phpseclib\Math\BigInteger $n |
||||||||
1760 | * @return \phpseclib\Math\BigInteger |
||||||||
1761 | * @access public |
||||||||
1762 | */ |
||||||||
1763 | public function powMod($e, $n) |
||||||||
1764 | { |
||||||||
1765 | return $this->modPow($e, $n); |
||||||||
1766 | } |
||||||||
1767 | |||||||||
1768 | /** |
||||||||
1769 | * Sliding Window k-ary Modular Exponentiation |
||||||||
1770 | * |
||||||||
1771 | * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} / |
||||||||
1772 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}. In a departure from those algorithims, |
||||||||
1773 | * however, this function performs a modular reduction after every multiplication and squaring operation. |
||||||||
1774 | * As such, this function has the same preconditions that the reductions being used do. |
||||||||
1775 | * |
||||||||
1776 | * @param \phpseclib\Math\BigInteger $e |
||||||||
1777 | * @param \phpseclib\Math\BigInteger $n |
||||||||
1778 | * @param int $mode |
||||||||
1779 | * @return \phpseclib\Math\BigInteger |
||||||||
1780 | * @access private |
||||||||
1781 | */ |
||||||||
1782 | public function _slidingWindow($e, $n, $mode) |
||||||||
1783 | { |
||||||||
1784 | static $window_ranges = array(7, 25, 81, 241, 673, 1793); // from BigInteger.java's oddModPow function |
||||||||
1785 | //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1 |
||||||||
1786 | |||||||||
1787 | $e_value = $e->value; |
||||||||
1788 | $e_length = count($e_value) - 1; |
||||||||
1789 | $e_bits = decbin($e_value[$e_length]); |
||||||||
1790 | for ($i = $e_length - 1; $i >= 0; --$i) { |
||||||||
1791 | $e_bits.= str_pad(decbin($e_value[$i]), self::$base, '0', STR_PAD_LEFT); |
||||||||
1792 | } |
||||||||
1793 | |||||||||
1794 | $e_length = strlen($e_bits); |
||||||||
1795 | |||||||||
1796 | // calculate the appropriate window size. |
||||||||
1797 | // $window_size == 3 if $window_ranges is between 25 and 81, for example. |
||||||||
1798 | for ($i = 0, $window_size = 1; $i < count($window_ranges) && $e_length > $window_ranges[$i]; ++$window_size, ++$i) { |
||||||||
1799 | } |
||||||||
1800 | |||||||||
1801 | $n_value = $n->value; |
||||||||
1802 | |||||||||
1803 | // precompute $this^0 through $this^$window_size |
||||||||
1804 | $powers = array(); |
||||||||
1805 | $powers[1] = $this->_prepareReduce($this->value, $n_value, $mode); |
||||||||
1806 | $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode); |
||||||||
1807 | |||||||||
1808 | // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end |
||||||||
1809 | // in a 1. ie. it's supposed to be odd. |
||||||||
1810 | $temp = 1 << ($window_size - 1); |
||||||||
1811 | for ($i = 1; $i < $temp; ++$i) { |
||||||||
1812 | $i2 = $i << 1; |
||||||||
1813 | $powers[$i2 + 1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode); |
||||||||
1814 | } |
||||||||
1815 | |||||||||
1816 | $result = array(1); |
||||||||
1817 | $result = $this->_prepareReduce($result, $n_value, $mode); |
||||||||
1818 | |||||||||
1819 | for ($i = 0; $i < $e_length;) { |
||||||||
1820 | if (!$e_bits[$i]) { |
||||||||
1821 | $result = $this->_squareReduce($result, $n_value, $mode); |
||||||||
1822 | ++$i; |
||||||||
1823 | } else { |
||||||||
1824 | for ($j = $window_size - 1; $j > 0; --$j) { |
||||||||
1825 | if (!empty($e_bits[$i + $j])) { |
||||||||
1826 | break; |
||||||||
1827 | } |
||||||||
1828 | } |
||||||||
1829 | |||||||||
1830 | // eg. the length of substr($e_bits, $i, $j + 1) |
||||||||
1831 | for ($k = 0; $k <= $j; ++$k) { |
||||||||
1832 | $result = $this->_squareReduce($result, $n_value, $mode); |
||||||||
1833 | } |
||||||||
1834 | |||||||||
1835 | $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $mode); |
||||||||
1836 | |||||||||
1837 | $i += $j + 1; |
||||||||
1838 | } |
||||||||
1839 | } |
||||||||
1840 | |||||||||
1841 | $temp = new static(); |
||||||||
1842 | $temp->value = $this->_reduce($result, $n_value, $mode); |
||||||||
1843 | |||||||||
1844 | return $temp; |
||||||||
1845 | } |
||||||||
1846 | |||||||||
1847 | /** |
||||||||
1848 | * Modular reduction |
||||||||
1849 | * |
||||||||
1850 | * For most $modes this will return the remainder. |
||||||||
1851 | * |
||||||||
1852 | * @see self::_slidingWindow() |
||||||||
1853 | * @access private |
||||||||
1854 | * @param array $x |
||||||||
1855 | * @param array $n |
||||||||
1856 | * @param int $mode |
||||||||
1857 | * @return array |
||||||||
1858 | */ |
||||||||
1859 | public function _reduce($x, $n, $mode) |
||||||||
1860 | { |
||||||||
1861 | switch ($mode) { |
||||||||
1862 | case self::MONTGOMERY: |
||||||||
1863 | return $this->_montgomery($x, $n); |
||||||||
1864 | case self::BARRETT: |
||||||||
1865 | return $this->_barrett($x, $n); |
||||||||
1866 | case self::POWEROF2: |
||||||||
1867 | $lhs = new static(); |
||||||||
1868 | $lhs->value = $x; |
||||||||
1869 | $rhs = new static(); |
||||||||
1870 | $rhs->value = $n; |
||||||||
1871 | return $x->_mod2($n); |
||||||||
1872 | case self::CLASSIC: |
||||||||
1873 | $lhs = new static(); |
||||||||
1874 | $lhs->value = $x; |
||||||||
1875 | $rhs = new static(); |
||||||||
1876 | $rhs->value = $n; |
||||||||
1877 | list(, $temp) = $lhs->divide($rhs); |
||||||||
1878 | return $temp->value; |
||||||||
1879 | case self::NONE: |
||||||||
1880 | return $x; |
||||||||
1881 | default: |
||||||||
1882 | // an invalid $mode was provided |
||||||||
1883 | } |
||||||||
1884 | } |
||||||||
1885 | |||||||||
1886 | /** |
||||||||
1887 | * Modular reduction preperation |
||||||||
1888 | * |
||||||||
1889 | * @see self::_slidingWindow() |
||||||||
1890 | * @access private |
||||||||
1891 | * @param array $x |
||||||||
1892 | * @param array $n |
||||||||
1893 | * @param int $mode |
||||||||
1894 | * @return array |
||||||||
1895 | */ |
||||||||
1896 | public function _prepareReduce($x, $n, $mode) |
||||||||
1897 | { |
||||||||
1898 | if ($mode == self::MONTGOMERY) { |
||||||||
1899 | return $this->_prepMontgomery($x, $n); |
||||||||
1900 | } |
||||||||
1901 | return $this->_reduce($x, $n, $mode); |
||||||||
1902 | } |
||||||||
1903 | |||||||||
1904 | /** |
||||||||
1905 | * Modular multiply |
||||||||
1906 | * |
||||||||
1907 | * @see self::_slidingWindow() |
||||||||
1908 | * @access private |
||||||||
1909 | * @param array $x |
||||||||
1910 | * @param array $y |
||||||||
1911 | * @param array $n |
||||||||
1912 | * @param int $mode |
||||||||
1913 | * @return array |
||||||||
1914 | */ |
||||||||
1915 | public function _multiplyReduce($x, $y, $n, $mode) |
||||||||
1916 | { |
||||||||
1917 | if ($mode == self::MONTGOMERY) { |
||||||||
1918 | return $this->_montgomeryMultiply($x, $y, $n); |
||||||||
1919 | } |
||||||||
1920 | $temp = $this->_multiply($x, false, $y, false); |
||||||||
1921 | return $this->_reduce($temp[self::VALUE], $n, $mode); |
||||||||
1922 | } |
||||||||
1923 | |||||||||
1924 | /** |
||||||||
1925 | * Modular square |
||||||||
1926 | * |
||||||||
1927 | * @see self::_slidingWindow() |
||||||||
1928 | * @access private |
||||||||
1929 | * @param array $x |
||||||||
1930 | * @param array $n |
||||||||
1931 | * @param int $mode |
||||||||
1932 | * @return array |
||||||||
1933 | */ |
||||||||
1934 | public function _squareReduce($x, $n, $mode) |
||||||||
1935 | { |
||||||||
1936 | if ($mode == self::MONTGOMERY) { |
||||||||
1937 | return $this->_montgomeryMultiply($x, $x, $n); |
||||||||
1938 | } |
||||||||
1939 | return $this->_reduce($this->_square($x), $n, $mode); |
||||||||
0 ignored issues
–
show
$this->_square($x) of type phpseclib\Math\BigInteger is incompatible with the type array expected by parameter $x of phpseclib\Math\BigInteger::_reduce() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
1940 | } |
||||||||
1941 | |||||||||
1942 | /** |
||||||||
1943 | * Modulos for Powers of Two |
||||||||
1944 | * |
||||||||
1945 | * Calculates $x%$n, where $n = 2**$e, for some $e. Since this is basically the same as doing $x & ($n-1), |
||||||||
1946 | * we'll just use this function as a wrapper for doing that. |
||||||||
1947 | * |
||||||||
1948 | * @see self::_slidingWindow() |
||||||||
1949 | * @access private |
||||||||
1950 | * @param \phpseclib\Math\BigInteger |
||||||||
1951 | * @return \phpseclib\Math\BigInteger |
||||||||
1952 | */ |
||||||||
1953 | public function _mod2($n) |
||||||||
1954 | { |
||||||||
1955 | $temp = new static(); |
||||||||
1956 | $temp->value = array(1); |
||||||||
1957 | return $this->bitwise_and($n->subtract($temp)); |
||||||||
1958 | } |
||||||||
1959 | |||||||||
1960 | /** |
||||||||
1961 | * Barrett Modular Reduction |
||||||||
1962 | * |
||||||||
1963 | * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} / |
||||||||
1964 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information. Modified slightly, |
||||||||
1965 | * so as not to require negative numbers (initially, this script didn't support negative numbers). |
||||||||
1966 | * |
||||||||
1967 | * Employs "folding", as described at |
||||||||
1968 | * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}. To quote from |
||||||||
1969 | * it, "the idea [behind folding] is to find a value x' such that x (mod m) = x' (mod m), with x' being smaller than x." |
||||||||
1970 | * |
||||||||
1971 | * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that |
||||||||
1972 | * usable on account of (1) its not using reasonable radix points as discussed in |
||||||||
1973 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable |
||||||||
1974 | * radix points, it only works when there are an even number of digits in the denominator. The reason for (2) is that |
||||||||
1975 | * (x >> 1) + (x >> 1) != x / 2 + x / 2. If x is even, they're the same, but if x is odd, they're not. See the in-line |
||||||||
1976 | * comments for details. |
||||||||
1977 | * |
||||||||
1978 | * @see self::_slidingWindow() |
||||||||
1979 | * @access private |
||||||||
1980 | * @param array $n |
||||||||
1981 | * @param array $m |
||||||||
1982 | * @return array |
||||||||
1983 | */ |
||||||||
1984 | public function _barrett($n, $m) |
||||||||
1985 | { |
||||||||
1986 | static $cache = array( |
||||||||
1987 | self::VARIABLE => array(), |
||||||||
1988 | self::DATA => array() |
||||||||
1989 | ); |
||||||||
1990 | |||||||||
1991 | $m_length = count($m); |
||||||||
1992 | |||||||||
1993 | // if ($this->_compare($n, $this->_square($m)) >= 0) { |
||||||||
1994 | if (count($n) > 2 * $m_length) { |
||||||||
1995 | $lhs = new static(); |
||||||||
1996 | $rhs = new static(); |
||||||||
1997 | $lhs->value = $n; |
||||||||
1998 | $rhs->value = $m; |
||||||||
1999 | list(, $temp) = $lhs->divide($rhs); |
||||||||
2000 | return $temp->value; |
||||||||
2001 | } |
||||||||
2002 | |||||||||
2003 | // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced |
||||||||
2004 | if ($m_length < 5) { |
||||||||
2005 | return $this->_regularBarrett($n, $m); |
||||||||
2006 | } |
||||||||
2007 | |||||||||
2008 | // n = 2 * m.length |
||||||||
2009 | |||||||||
2010 | if (($key = array_search($m, $cache[self::VARIABLE])) === false) { |
||||||||
2011 | $key = count($cache[self::VARIABLE]); |
||||||||
0 ignored issues
–
show
|
|||||||||
2012 | $cache[self::VARIABLE][] = $m; |
||||||||
2013 | |||||||||
2014 | $lhs = new static(); |
||||||||
2015 | $lhs_value = &$lhs->value; |
||||||||
2016 | $lhs_value = $this->_array_repeat(0, $m_length + ($m_length >> 1)); |
||||||||
2017 | $lhs_value[] = 1; |
||||||||
2018 | $rhs = new static(); |
||||||||
2019 | $rhs->value = $m; |
||||||||
2020 | |||||||||
2021 | list($u, $m1) = $lhs->divide($rhs); |
||||||||
2022 | $u = $u->value; |
||||||||
2023 | $m1 = $m1->value; |
||||||||
2024 | |||||||||
2025 | $cache[self::DATA][] = array( |
||||||||
2026 | 'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1) |
||||||||
2027 | 'm1'=> $m1 // m.length |
||||||||
2028 | ); |
||||||||
2029 | } else { |
||||||||
2030 | extract($cache[self::DATA][$key]); |
||||||||
2031 | } |
||||||||
2032 | |||||||||
2033 | $cutoff = $m_length + ($m_length >> 1); |
||||||||
2034 | $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1) |
||||||||
2035 | $msd = array_slice($n, $cutoff); // m.length >> 1 |
||||||||
2036 | $lsd = $this->_trim($lsd); |
||||||||
2037 | $temp = $this->_multiply($msd, false, $m1, false); |
||||||||
2038 | $n = $this->_add($lsd, false, $temp[self::VALUE], false); // m.length + (m.length >> 1) + 1 |
||||||||
0 ignored issues
–
show
$lsd of type phpseclib\Math\BigInteger is incompatible with the type array expected by parameter $x_value of phpseclib\Math\BigInteger::_add() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2039 | |||||||||
2040 | if ($m_length & 1) { |
||||||||
2041 | return $this->_regularBarrett($n[self::VALUE], $m); |
||||||||
2042 | } |
||||||||
2043 | |||||||||
2044 | // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2 |
||||||||
2045 | $temp = array_slice($n[self::VALUE], $m_length - 1); |
||||||||
2046 | // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2 |
||||||||
2047 | // if odd: ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1 |
||||||||
2048 | $temp = $this->_multiply($temp, false, $u, false); |
||||||||
2049 | // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1 |
||||||||
2050 | // if odd: (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) |
||||||||
2051 | $temp = array_slice($temp[self::VALUE], ($m_length >> 1) + 1); |
||||||||
2052 | // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1 |
||||||||
2053 | // if odd: (m.length - (m.length >> 1)) + m.length = 2 * m.length - (m.length >> 1) |
||||||||
2054 | $temp = $this->_multiply($temp, false, $m, false); |
||||||||
2055 | |||||||||
2056 | // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit |
||||||||
2057 | // number from a m.length + (m.length >> 1) + 1 digit number. ie. there'd be an extra digit and the while loop |
||||||||
2058 | // following this comment would loop a lot (hence our calling _regularBarrett() in that situation). |
||||||||
2059 | |||||||||
2060 | $result = $this->_subtract($n[self::VALUE], false, $temp[self::VALUE], false); |
||||||||
2061 | |||||||||
2062 | while ($this->_compare($result[self::VALUE], $result[self::SIGN], $m, false) >= 0) { |
||||||||
2063 | $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $m, false); |
||||||||
2064 | } |
||||||||
2065 | |||||||||
2066 | return $result[self::VALUE]; |
||||||||
2067 | } |
||||||||
2068 | |||||||||
2069 | /** |
||||||||
2070 | * (Regular) Barrett Modular Reduction |
||||||||
2071 | * |
||||||||
2072 | * For numbers with more than four digits BigInteger::_barrett() is faster. The difference between that and this |
||||||||
2073 | * is that this function does not fold the denominator into a smaller form. |
||||||||
2074 | * |
||||||||
2075 | * @see self::_slidingWindow() |
||||||||
2076 | * @access private |
||||||||
2077 | * @param array $x |
||||||||
2078 | * @param array $n |
||||||||
2079 | * @return array |
||||||||
2080 | */ |
||||||||
2081 | public function _regularBarrett($x, $n) |
||||||||
2082 | { |
||||||||
2083 | static $cache = array( |
||||||||
2084 | self::VARIABLE => array(), |
||||||||
2085 | self::DATA => array() |
||||||||
2086 | ); |
||||||||
2087 | |||||||||
2088 | $n_length = count($n); |
||||||||
2089 | |||||||||
2090 | if (count($x) > 2 * $n_length) { |
||||||||
2091 | $lhs = new static(); |
||||||||
2092 | $rhs = new static(); |
||||||||
2093 | $lhs->value = $x; |
||||||||
2094 | $rhs->value = $n; |
||||||||
2095 | list(, $temp) = $lhs->divide($rhs); |
||||||||
2096 | return $temp->value; |
||||||||
2097 | } |
||||||||
2098 | |||||||||
2099 | if (($key = array_search($n, $cache[self::VARIABLE])) === false) { |
||||||||
2100 | $key = count($cache[self::VARIABLE]); |
||||||||
2101 | $cache[self::VARIABLE][] = $n; |
||||||||
2102 | $lhs = new static(); |
||||||||
2103 | $lhs_value = &$lhs->value; |
||||||||
2104 | $lhs_value = $this->_array_repeat(0, 2 * $n_length); |
||||||||
2105 | $lhs_value[] = 1; |
||||||||
2106 | $rhs = new static(); |
||||||||
2107 | $rhs->value = $n; |
||||||||
2108 | list($temp, ) = $lhs->divide($rhs); // m.length |
||||||||
2109 | $cache[self::DATA][] = $temp->value; |
||||||||
2110 | } |
||||||||
2111 | |||||||||
2112 | // 2 * m.length - (m.length - 1) = m.length + 1 |
||||||||
2113 | $temp = array_slice($x, $n_length - 1); |
||||||||
2114 | // (m.length + 1) + m.length = 2 * m.length + 1 |
||||||||
2115 | $temp = $this->_multiply($temp, false, $cache[self::DATA][$key], false); |
||||||||
2116 | // (2 * m.length + 1) - (m.length - 1) = m.length + 2 |
||||||||
2117 | $temp = array_slice($temp[self::VALUE], $n_length + 1); |
||||||||
2118 | |||||||||
2119 | // m.length + 1 |
||||||||
2120 | $result = array_slice($x, 0, $n_length + 1); |
||||||||
2121 | // m.length + 1 |
||||||||
2122 | $temp = $this->_multiplyLower($temp, false, $n, false, $n_length + 1); |
||||||||
2123 | // $temp == array_slice($temp->_multiply($temp, false, $n, false)->value, 0, $n_length + 1) |
||||||||
2124 | |||||||||
2125 | if ($this->_compare($result, false, $temp[self::VALUE], $temp[self::SIGN]) < 0) { |
||||||||
2126 | $corrector_value = $this->_array_repeat(0, $n_length + 1); |
||||||||
2127 | $corrector_value[count($corrector_value)] = 1; |
||||||||
2128 | $result = $this->_add($result, false, $corrector_value, false); |
||||||||
2129 | $result = $result[self::VALUE]; |
||||||||
2130 | } |
||||||||
2131 | |||||||||
2132 | // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits |
||||||||
2133 | $result = $this->_subtract($result, false, $temp[self::VALUE], $temp[self::SIGN]); |
||||||||
2134 | while ($this->_compare($result[self::VALUE], $result[self::SIGN], $n, false) > 0) { |
||||||||
2135 | $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $n, false); |
||||||||
2136 | } |
||||||||
2137 | |||||||||
2138 | return $result[self::VALUE]; |
||||||||
2139 | } |
||||||||
2140 | |||||||||
2141 | /** |
||||||||
2142 | * Performs long multiplication up to $stop digits |
||||||||
2143 | * |
||||||||
2144 | * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved. |
||||||||
2145 | * |
||||||||
2146 | * @see self::_regularBarrett() |
||||||||
2147 | * @param array $x_value |
||||||||
2148 | * @param bool $x_negative |
||||||||
2149 | * @param array $y_value |
||||||||
2150 | * @param bool $y_negative |
||||||||
2151 | * @param int $stop |
||||||||
2152 | * @return array |
||||||||
2153 | * @access private |
||||||||
2154 | */ |
||||||||
2155 | public function _multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop) |
||||||||
2156 | { |
||||||||
2157 | $x_length = count($x_value); |
||||||||
2158 | $y_length = count($y_value); |
||||||||
2159 | |||||||||
2160 | if (!$x_length || !$y_length) { // a 0 is being multiplied |
||||||||
2161 | return array( |
||||||||
2162 | self::VALUE => array(), |
||||||||
2163 | self::SIGN => false |
||||||||
2164 | ); |
||||||||
2165 | } |
||||||||
2166 | |||||||||
2167 | if ($x_length < $y_length) { |
||||||||
2168 | $temp = $x_value; |
||||||||
2169 | $x_value = $y_value; |
||||||||
2170 | $y_value = $temp; |
||||||||
2171 | |||||||||
2172 | $x_length = count($x_value); |
||||||||
2173 | $y_length = count($y_value); |
||||||||
2174 | } |
||||||||
2175 | |||||||||
2176 | $product_value = $this->_array_repeat(0, $x_length + $y_length); |
||||||||
2177 | |||||||||
2178 | // the following for loop could be removed if the for loop following it |
||||||||
2179 | // (the one with nested for loops) initially set $i to 0, but |
||||||||
2180 | // doing so would also make the result in one set of unnecessary adds, |
||||||||
2181 | // since on the outermost loops first pass, $product->value[$k] is going |
||||||||
2182 | // to always be 0 |
||||||||
2183 | |||||||||
2184 | $carry = 0; |
||||||||
2185 | |||||||||
2186 | for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i |
||||||||
2187 | $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0 |
||||||||
2188 | $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); |
||||||||
2189 | $product_value[$j] = (int) ($temp - self::$baseFull * $carry); |
||||||||
2190 | } |
||||||||
2191 | |||||||||
2192 | if ($j < $stop) { |
||||||||
2193 | $product_value[$j] = $carry; |
||||||||
2194 | } |
||||||||
2195 | |||||||||
2196 | // the above for loop is what the previous comment was talking about. the |
||||||||
2197 | // following for loop is the "one with nested for loops" |
||||||||
2198 | |||||||||
2199 | for ($i = 1; $i < $y_length; ++$i) { |
||||||||
2200 | $carry = 0; |
||||||||
2201 | |||||||||
2202 | for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) { |
||||||||
2203 | $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry; |
||||||||
2204 | $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); |
||||||||
2205 | $product_value[$k] = (int) ($temp - self::$baseFull * $carry); |
||||||||
2206 | } |
||||||||
2207 | |||||||||
2208 | if ($k < $stop) { |
||||||||
2209 | $product_value[$k] = $carry; |
||||||||
2210 | } |
||||||||
2211 | } |
||||||||
2212 | |||||||||
2213 | return array( |
||||||||
2214 | self::VALUE => $this->_trim($product_value), |
||||||||
2215 | self::SIGN => $x_negative != $y_negative |
||||||||
2216 | ); |
||||||||
2217 | } |
||||||||
2218 | |||||||||
2219 | /** |
||||||||
2220 | * Montgomery Modular Reduction |
||||||||
2221 | * |
||||||||
2222 | * ($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n. |
||||||||
2223 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=170 MPM 6.3} provides insights on how this can be |
||||||||
2224 | * improved upon (basically, by using the comba method). gcd($n, 2) must be equal to one for this function |
||||||||
2225 | * to work correctly. |
||||||||
2226 | * |
||||||||
2227 | * @see self::_prepMontgomery() |
||||||||
2228 | * @see self::_slidingWindow() |
||||||||
2229 | * @access private |
||||||||
2230 | * @param array $x |
||||||||
2231 | * @param array $n |
||||||||
2232 | * @return array |
||||||||
2233 | */ |
||||||||
2234 | public function _montgomery($x, $n) |
||||||||
2235 | { |
||||||||
2236 | static $cache = array( |
||||||||
2237 | self::VARIABLE => array(), |
||||||||
2238 | self::DATA => array() |
||||||||
2239 | ); |
||||||||
2240 | |||||||||
2241 | if (($key = array_search($n, $cache[self::VARIABLE])) === false) { |
||||||||
2242 | $key = count($cache[self::VARIABLE]); |
||||||||
2243 | $cache[self::VARIABLE][] = $x; |
||||||||
2244 | $cache[self::DATA][] = $this->_modInverse67108864($n); |
||||||||
2245 | } |
||||||||
2246 | |||||||||
2247 | $k = count($n); |
||||||||
2248 | |||||||||
2249 | $result = array(self::VALUE => $x); |
||||||||
2250 | |||||||||
2251 | for ($i = 0; $i < $k; ++$i) { |
||||||||
2252 | $temp = $result[self::VALUE][$i] * $cache[self::DATA][$key]; |
||||||||
2253 | $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31)); |
||||||||
2254 | $temp = $this->_regularMultiply(array($temp), $n); |
||||||||
2255 | $temp = array_merge($this->_array_repeat(0, $i), $temp); |
||||||||
2256 | $result = $this->_add($result[self::VALUE], false, $temp, false); |
||||||||
2257 | } |
||||||||
2258 | |||||||||
2259 | $result[self::VALUE] = array_slice($result[self::VALUE], $k); |
||||||||
2260 | |||||||||
2261 | if ($this->_compare($result, false, $n, false) >= 0) { |
||||||||
2262 | $result = $this->_subtract($result[self::VALUE], false, $n, false); |
||||||||
2263 | } |
||||||||
2264 | |||||||||
2265 | return $result[self::VALUE]; |
||||||||
2266 | } |
||||||||
2267 | |||||||||
2268 | /** |
||||||||
2269 | * Montgomery Multiply |
||||||||
2270 | * |
||||||||
2271 | * Interleaves the montgomery reduction and long multiplication algorithms together as described in |
||||||||
2272 | * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36} |
||||||||
2273 | * |
||||||||
2274 | * @see self::_prepMontgomery() |
||||||||
2275 | * @see self::_montgomery() |
||||||||
2276 | * @access private |
||||||||
2277 | * @param array $x |
||||||||
2278 | * @param array $y |
||||||||
2279 | * @param array $m |
||||||||
2280 | * @return array |
||||||||
2281 | */ |
||||||||
2282 | public function _montgomeryMultiply($x, $y, $m) |
||||||||
2283 | { |
||||||||
2284 | $temp = $this->_multiply($x, false, $y, false); |
||||||||
2285 | return $this->_montgomery($temp[self::VALUE], $m); |
||||||||
2286 | |||||||||
2287 | // the following code, although not callable, can be run independently of the above code |
||||||||
2288 | // although the above code performed better in my benchmarks the following could might |
||||||||
2289 | // perform better under different circumstances. in lieu of deleting it it's just been |
||||||||
2290 | // made uncallable |
||||||||
2291 | |||||||||
2292 | static $cache = array( |
||||||||
2293 | self::VARIABLE => array(), |
||||||||
2294 | self::DATA => array() |
||||||||
2295 | ); |
||||||||
2296 | |||||||||
2297 | if (($key = array_search($m, $cache[self::VARIABLE])) === false) { |
||||||||
2298 | $key = count($cache[self::VARIABLE]); |
||||||||
2299 | $cache[self::VARIABLE][] = $m; |
||||||||
2300 | $cache[self::DATA][] = $this->_modInverse67108864($m); |
||||||||
2301 | } |
||||||||
2302 | |||||||||
2303 | $n = max(count($x), count($y), count($m)); |
||||||||
2304 | $x = array_pad($x, $n, 0); |
||||||||
2305 | $y = array_pad($y, $n, 0); |
||||||||
2306 | $m = array_pad($m, $n, 0); |
||||||||
2307 | $a = array(self::VALUE => $this->_array_repeat(0, $n + 1)); |
||||||||
2308 | for ($i = 0; $i < $n; ++$i) { |
||||||||
2309 | $temp = $a[self::VALUE][0] + $x[$i] * $y[0]; |
||||||||
2310 | $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31)); |
||||||||
2311 | $temp = $temp * $cache[self::DATA][$key]; |
||||||||
2312 | $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31)); |
||||||||
2313 | $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false); |
||||||||
2314 | $a = $this->_add($a[self::VALUE], false, $temp[self::VALUE], false); |
||||||||
2315 | $a[self::VALUE] = array_slice($a[self::VALUE], 1); |
||||||||
2316 | } |
||||||||
2317 | if ($this->_compare($a[self::VALUE], false, $m, false) >= 0) { |
||||||||
2318 | $a = $this->_subtract($a[self::VALUE], false, $m, false); |
||||||||
2319 | } |
||||||||
2320 | return $a[self::VALUE]; |
||||||||
2321 | } |
||||||||
2322 | |||||||||
2323 | /** |
||||||||
2324 | * Prepare a number for use in Montgomery Modular Reductions |
||||||||
2325 | * |
||||||||
2326 | * @see self::_montgomery() |
||||||||
2327 | * @see self::_slidingWindow() |
||||||||
2328 | * @access private |
||||||||
2329 | * @param array $x |
||||||||
2330 | * @param array $n |
||||||||
2331 | * @return array |
||||||||
2332 | */ |
||||||||
2333 | public function _prepMontgomery($x, $n) |
||||||||
2334 | { |
||||||||
2335 | $lhs = new static(); |
||||||||
2336 | $lhs->value = array_merge($this->_array_repeat(0, count($n)), $x); |
||||||||
2337 | $rhs = new static(); |
||||||||
2338 | $rhs->value = $n; |
||||||||
2339 | |||||||||
2340 | list(, $temp) = $lhs->divide($rhs); |
||||||||
2341 | return $temp->value; |
||||||||
2342 | } |
||||||||
2343 | |||||||||
2344 | /** |
||||||||
2345 | * Modular Inverse of a number mod 2**26 (eg. 67108864) |
||||||||
2346 | * |
||||||||
2347 | * Based off of the bnpInvDigit function implemented and justified in the following URL: |
||||||||
2348 | * |
||||||||
2349 | * {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js} |
||||||||
2350 | * |
||||||||
2351 | * The following URL provides more info: |
||||||||
2352 | * |
||||||||
2353 | * {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85} |
||||||||
2354 | * |
||||||||
2355 | * As for why we do all the bitmasking... strange things can happen when converting from floats to ints. For |
||||||||
2356 | * instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields |
||||||||
2357 | * int(-2147483648). To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't |
||||||||
2358 | * auto-converted to floats. The outermost bitmask is present because without it, there's no guarantee that |
||||||||
2359 | * the "residue" returned would be the so-called "common residue". We use fmod, in the last step, because the |
||||||||
2360 | * maximum possible $x is 26 bits and the maximum $result is 16 bits. Thus, we have to be able to handle up to |
||||||||
2361 | * 40 bits, which only 64-bit floating points will support. |
||||||||
2362 | * |
||||||||
2363 | * Thanks to Pedro Gimeno Fortea for input! |
||||||||
2364 | * |
||||||||
2365 | * @see self::_montgomery() |
||||||||
2366 | * @access private |
||||||||
2367 | * @param array $x |
||||||||
2368 | * @return int |
||||||||
2369 | */ |
||||||||
2370 | public function _modInverse67108864($x) // 2**26 == 67,108,864 |
||||||||
2371 | { |
||||||||
2372 | $x = -$x[0]; |
||||||||
2373 | $result = $x & 0x3; // x**-1 mod 2**2 |
||||||||
2374 | $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4 |
||||||||
2375 | $result = ($result * (2 - ($x & 0xFF) * $result)) & 0xFF; // x**-1 mod 2**8 |
||||||||
2376 | $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16 |
||||||||
2377 | $result = fmod($result * (2 - fmod($x * $result, self::$baseFull)), self::$baseFull); // x**-1 mod 2**26 |
||||||||
2378 | return $result & self::$maxDigit; |
||||||||
2379 | } |
||||||||
2380 | |||||||||
2381 | /** |
||||||||
2382 | * Calculates modular inverses. |
||||||||
2383 | * |
||||||||
2384 | * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses. |
||||||||
2385 | * |
||||||||
2386 | * Here's an example: |
||||||||
2387 | * <code> |
||||||||
2388 | * <?php |
||||||||
2389 | * $a = new \phpseclib\Math\BigInteger(30); |
||||||||
2390 | * $b = new \phpseclib\Math\BigInteger(17); |
||||||||
2391 | * |
||||||||
2392 | * $c = $a->modInverse($b); |
||||||||
2393 | * echo $c->toString(); // outputs 4 |
||||||||
2394 | * |
||||||||
2395 | * echo "\r\n"; |
||||||||
2396 | * |
||||||||
2397 | * $d = $a->multiply($c); |
||||||||
2398 | * list(, $d) = $d->divide($b); |
||||||||
2399 | * echo $d; // outputs 1 (as per the definition of modular inverse) |
||||||||
2400 | * ?> |
||||||||
2401 | * </code> |
||||||||
2402 | * |
||||||||
2403 | * @param \phpseclib\Math\BigInteger $n |
||||||||
2404 | * @return \phpseclib\Math\BigInteger|false |
||||||||
2405 | * @access public |
||||||||
2406 | * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information. |
||||||||
2407 | */ |
||||||||
2408 | public function modInverse($n) |
||||||||
2409 | { |
||||||||
2410 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
2411 | case self::MODE_GMP: |
||||||||
2412 | $temp = new static(); |
||||||||
2413 | $temp->value = gmp_invert($this->value, $n->value); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_invert() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$n->value of type array is incompatible with the type GMP|resource|string expected by parameter $b of gmp_invert() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
It seems like
gmp_invert($this->value, $n->value) of type GMP or false or resource is incompatible with the declared type array 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...
|
|||||||||
2414 | |||||||||
2415 | return ($temp->value === false) ? false : $this->_normalize($temp); |
||||||||
2416 | } |
||||||||
2417 | |||||||||
2418 | static $zero, $one; |
||||||||
2419 | if (!isset($zero)) { |
||||||||
2420 | $zero = new static(); |
||||||||
2421 | $one = new static(1); |
||||||||
2422 | } |
||||||||
2423 | |||||||||
2424 | // $x mod -$n == $x mod $n. |
||||||||
2425 | $n = $n->abs(); |
||||||||
2426 | |||||||||
2427 | if ($this->compare($zero) < 0) { |
||||||||
2428 | $temp = $this->abs(); |
||||||||
2429 | $temp = $temp->modInverse($n); |
||||||||
2430 | return $this->_normalize($n->subtract($temp)); |
||||||||
0 ignored issues
–
show
It seems like
$temp can also be of type false ; however, parameter $y of phpseclib\Math\BigInteger::subtract() does only seem to accept phpseclib\Math\BigInteger , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2431 | } |
||||||||
2432 | |||||||||
2433 | extract($this->extendedGCD($n)); |
||||||||
0 ignored issues
–
show
$this->extendedGCD($n) of type phpseclib\Math\BigInteger is incompatible with the type array expected by parameter $var_array of extract() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2434 | |||||||||
2435 | if (!$gcd->equals($one)) { |
||||||||
2436 | return false; |
||||||||
2437 | } |
||||||||
2438 | |||||||||
2439 | $x = $x->compare($zero) < 0 ? $x->add($n) : $x; |
||||||||
2440 | |||||||||
2441 | return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x); |
||||||||
2442 | } |
||||||||
2443 | |||||||||
2444 | /** |
||||||||
2445 | * Calculates the greatest common divisor and Bezout's identity. |
||||||||
2446 | * |
||||||||
2447 | * Say you have 693 and 609. The GCD is 21. Bezout's identity states that there exist integers x and y such that |
||||||||
2448 | * 693*x + 609*y == 21. In point of fact, there are actually an infinite number of x and y combinations and which |
||||||||
2449 | * combination is returned is dependent upon which mode is in use. See |
||||||||
2450 | * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information. |
||||||||
2451 | * |
||||||||
2452 | * Here's an example: |
||||||||
2453 | * <code> |
||||||||
2454 | * <?php |
||||||||
2455 | * $a = new \phpseclib\Math\BigInteger(693); |
||||||||
2456 | * $b = new \phpseclib\Math\BigInteger(609); |
||||||||
2457 | * |
||||||||
2458 | * extract($a->extendedGCD($b)); |
||||||||
2459 | * |
||||||||
2460 | * echo $gcd->toString() . "\r\n"; // outputs 21 |
||||||||
2461 | * echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21 |
||||||||
2462 | * ?> |
||||||||
2463 | * </code> |
||||||||
2464 | * |
||||||||
2465 | * @param \phpseclib\Math\BigInteger $n |
||||||||
2466 | * @return \phpseclib\Math\BigInteger |
||||||||
2467 | * @access public |
||||||||
2468 | * @internal Calculates the GCD using the binary xGCD algorithim described in |
||||||||
2469 | * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=19 HAC 14.61}. As the text above 14.61 notes, |
||||||||
2470 | * the more traditional algorithim requires "relatively costly multiple-precision divisions". |
||||||||
2471 | */ |
||||||||
2472 | public function extendedGCD($n) |
||||||||
2473 | { |
||||||||
2474 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
2475 | case self::MODE_GMP: |
||||||||
2476 | extract(gmp_gcdext($this->value, $n->value)); |
||||||||
0 ignored issues
–
show
$n->value of type array is incompatible with the type GMP|resource|string expected by parameter $b of gmp_gcdext() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_gcdext() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2477 | |||||||||
2478 | return array( |
||||||||
2479 | 'gcd' => $this->_normalize(new static($g)), |
||||||||
2480 | 'x' => $this->_normalize(new static($s)), |
||||||||
2481 | 'y' => $this->_normalize(new static($t)) |
||||||||
2482 | ); |
||||||||
2483 | case self::MODE_BCMATH: |
||||||||
2484 | // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works |
||||||||
2485 | // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway. as is, |
||||||||
2486 | // the basic extended euclidean algorithim is what we're using. |
||||||||
2487 | |||||||||
2488 | $u = $this->value; |
||||||||
2489 | $v = $n->value; |
||||||||
2490 | |||||||||
2491 | $a = '1'; |
||||||||
2492 | $b = '0'; |
||||||||
2493 | $c = '0'; |
||||||||
2494 | $d = '1'; |
||||||||
2495 | |||||||||
2496 | while (bccomp($v, '0', 0) != 0) { |
||||||||
0 ignored issues
–
show
$v of type array is incompatible with the type string expected by parameter $left_operand of bccomp() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2497 | $q = bcdiv($u, $v, 0); |
||||||||
0 ignored issues
–
show
$u of type array is incompatible with the type string expected by parameter $dividend of bcdiv() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$v of type array is incompatible with the type string expected by parameter $divisor of bcdiv() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2498 | |||||||||
2499 | $temp = $u; |
||||||||
2500 | $u = $v; |
||||||||
2501 | $v = bcsub($temp, bcmul($v, $q, 0), 0); |
||||||||
0 ignored issues
–
show
$v of type array is incompatible with the type string expected by parameter $left_operand of bcmul() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$temp of type array is incompatible with the type string expected by parameter $left_operand of bcsub() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2502 | |||||||||
2503 | $temp = $a; |
||||||||
2504 | $a = $c; |
||||||||
2505 | $c = bcsub($temp, bcmul($a, $q, 0), 0); |
||||||||
2506 | |||||||||
2507 | $temp = $b; |
||||||||
2508 | $b = $d; |
||||||||
2509 | $d = bcsub($temp, bcmul($b, $q, 0), 0); |
||||||||
2510 | } |
||||||||
2511 | |||||||||
2512 | return array( |
||||||||
2513 | 'gcd' => $this->_normalize(new static($u)), |
||||||||
2514 | 'x' => $this->_normalize(new static($a)), |
||||||||
2515 | 'y' => $this->_normalize(new static($b)) |
||||||||
2516 | ); |
||||||||
2517 | } |
||||||||
2518 | |||||||||
2519 | $y = $n->copy(); |
||||||||
2520 | $x = $this->copy(); |
||||||||
2521 | $g = new static(); |
||||||||
2522 | $g->value = array(1); |
||||||||
2523 | |||||||||
2524 | while (!(($x->value[0] & 1)|| ($y->value[0] & 1))) { |
||||||||
2525 | $x->_rshift(1); |
||||||||
2526 | $y->_rshift(1); |
||||||||
2527 | $g->_lshift(1); |
||||||||
2528 | } |
||||||||
2529 | |||||||||
2530 | $u = $x->copy(); |
||||||||
2531 | $v = $y->copy(); |
||||||||
2532 | |||||||||
2533 | $a = new static(); |
||||||||
2534 | $b = new static(); |
||||||||
2535 | $c = new static(); |
||||||||
2536 | $d = new static(); |
||||||||
2537 | |||||||||
2538 | $a->value = $d->value = $g->value = array(1); |
||||||||
2539 | $b->value = $c->value = array(); |
||||||||
2540 | |||||||||
2541 | while (!empty($u->value)) { |
||||||||
2542 | while (!($u->value[0] & 1)) { |
||||||||
2543 | $u->_rshift(1); |
||||||||
2544 | if ((!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1))) { |
||||||||
2545 | $a = $a->add($y); |
||||||||
2546 | $b = $b->subtract($x); |
||||||||
2547 | } |
||||||||
2548 | $a->_rshift(1); |
||||||||
2549 | $b->_rshift(1); |
||||||||
2550 | } |
||||||||
2551 | |||||||||
2552 | while (!($v->value[0] & 1)) { |
||||||||
2553 | $v->_rshift(1); |
||||||||
2554 | if ((!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1))) { |
||||||||
2555 | $c = $c->add($y); |
||||||||
2556 | $d = $d->subtract($x); |
||||||||
2557 | } |
||||||||
2558 | $c->_rshift(1); |
||||||||
2559 | $d->_rshift(1); |
||||||||
2560 | } |
||||||||
2561 | |||||||||
2562 | if ($u->compare($v) >= 0) { |
||||||||
2563 | $u = $u->subtract($v); |
||||||||
2564 | $a = $a->subtract($c); |
||||||||
2565 | $b = $b->subtract($d); |
||||||||
2566 | } else { |
||||||||
2567 | $v = $v->subtract($u); |
||||||||
2568 | $c = $c->subtract($a); |
||||||||
2569 | $d = $d->subtract($b); |
||||||||
2570 | } |
||||||||
2571 | } |
||||||||
2572 | |||||||||
2573 | return array( |
||||||||
2574 | 'gcd' => $this->_normalize($g->multiply($v)), |
||||||||
2575 | 'x' => $this->_normalize($c), |
||||||||
2576 | 'y' => $this->_normalize($d) |
||||||||
2577 | ); |
||||||||
2578 | } |
||||||||
2579 | |||||||||
2580 | /** |
||||||||
2581 | * Calculates the greatest common divisor |
||||||||
2582 | * |
||||||||
2583 | * Say you have 693 and 609. The GCD is 21. |
||||||||
2584 | * |
||||||||
2585 | * Here's an example: |
||||||||
2586 | * <code> |
||||||||
2587 | * <?php |
||||||||
2588 | * $a = new \phpseclib\Math\BigInteger(693); |
||||||||
2589 | * $b = new \phpseclib\Math\BigInteger(609); |
||||||||
2590 | * |
||||||||
2591 | * $gcd = a->extendedGCD($b); |
||||||||
2592 | * |
||||||||
2593 | * echo $gcd->toString() . "\r\n"; // outputs 21 |
||||||||
2594 | * ?> |
||||||||
2595 | * </code> |
||||||||
2596 | * |
||||||||
2597 | * @param \phpseclib\Math\BigInteger $n |
||||||||
2598 | * @return \phpseclib\Math\BigInteger |
||||||||
2599 | * @access public |
||||||||
2600 | */ |
||||||||
2601 | public function gcd($n) |
||||||||
2602 | { |
||||||||
2603 | extract($this->extendedGCD($n)); |
||||||||
0 ignored issues
–
show
$this->extendedGCD($n) of type phpseclib\Math\BigInteger is incompatible with the type array expected by parameter $var_array of extract() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2604 | return $gcd; |
||||||||
2605 | } |
||||||||
2606 | |||||||||
2607 | /** |
||||||||
2608 | * Absolute value. |
||||||||
2609 | * |
||||||||
2610 | * @return \phpseclib\Math\BigInteger |
||||||||
2611 | * @access public |
||||||||
2612 | */ |
||||||||
2613 | public function abs() |
||||||||
2614 | { |
||||||||
2615 | $temp = new static(); |
||||||||
2616 | |||||||||
2617 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
2618 | case self::MODE_GMP: |
||||||||
2619 | $temp->value = gmp_abs($this->value); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_abs() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
It seems like
gmp_abs($this->value) of type GMP or resource is incompatible with the declared type array 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...
|
|||||||||
2620 | break; |
||||||||
2621 | case self::MODE_BCMATH: |
||||||||
2622 | $temp->value = (bccomp($this->value, '0', 0) < 0) ? substr($this->value, 1) : $this->value; |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type string expected by parameter $left_operand of bccomp() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$this->value of type array is incompatible with the type string expected by parameter $string of substr() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2623 | break; |
||||||||
2624 | default: |
||||||||
2625 | $temp->value = $this->value; |
||||||||
2626 | } |
||||||||
2627 | |||||||||
2628 | return $temp; |
||||||||
2629 | } |
||||||||
2630 | |||||||||
2631 | /** |
||||||||
2632 | * Compares two numbers. |
||||||||
2633 | * |
||||||||
2634 | * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this is |
||||||||
2635 | * demonstrated thusly: |
||||||||
2636 | * |
||||||||
2637 | * $x > $y: $x->compare($y) > 0 |
||||||||
2638 | * $x < $y: $x->compare($y) < 0 |
||||||||
2639 | * $x == $y: $x->compare($y) == 0 |
||||||||
2640 | * |
||||||||
2641 | * Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y). |
||||||||
2642 | * |
||||||||
2643 | * @param \phpseclib\Math\BigInteger $y |
||||||||
2644 | * @return int < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal. |
||||||||
2645 | * @access public |
||||||||
2646 | * @see self::equals() |
||||||||
2647 | * @internal Could return $this->subtract($x), but that's not as fast as what we do do. |
||||||||
2648 | */ |
||||||||
2649 | public function compare($y) |
||||||||
2650 | { |
||||||||
2651 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
2652 | case self::MODE_GMP: |
||||||||
2653 | return gmp_cmp($this->value, $y->value); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_cmp() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$y->value of type array is incompatible with the type GMP|resource|string expected by parameter $b of gmp_cmp() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2654 | case self::MODE_BCMATH: |
||||||||
2655 | return bccomp($this->value, $y->value, 0); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type string expected by parameter $left_operand of bccomp() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$y->value of type array is incompatible with the type string expected by parameter $right_operand of bccomp() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2656 | } |
||||||||
2657 | |||||||||
2658 | return $this->_compare($this->value, $this->is_negative, $y->value, $y->is_negative); |
||||||||
2659 | } |
||||||||
2660 | |||||||||
2661 | /** |
||||||||
2662 | * Compares two numbers. |
||||||||
2663 | * |
||||||||
2664 | * @param array $x_value |
||||||||
2665 | * @param bool $x_negative |
||||||||
2666 | * @param array $y_value |
||||||||
2667 | * @param bool $y_negative |
||||||||
2668 | * @return int |
||||||||
2669 | * @see self::compare() |
||||||||
2670 | * @access private |
||||||||
2671 | */ |
||||||||
2672 | public function _compare($x_value, $x_negative, $y_value, $y_negative) |
||||||||
2673 | { |
||||||||
2674 | if ($x_negative != $y_negative) { |
||||||||
2675 | return (!$x_negative && $y_negative) ? 1 : -1; |
||||||||
2676 | } |
||||||||
2677 | |||||||||
2678 | $result = $x_negative ? -1 : 1; |
||||||||
2679 | |||||||||
2680 | if (count($x_value) != count($y_value)) { |
||||||||
2681 | return (count($x_value) > count($y_value)) ? $result : -$result; |
||||||||
2682 | } |
||||||||
2683 | $size = max(count($x_value), count($y_value)); |
||||||||
2684 | |||||||||
2685 | $x_value = array_pad($x_value, $size, 0); |
||||||||
2686 | $y_value = array_pad($y_value, $size, 0); |
||||||||
2687 | |||||||||
2688 | for ($i = count($x_value) - 1; $i >= 0; --$i) { |
||||||||
2689 | if ($x_value[$i] != $y_value[$i]) { |
||||||||
2690 | return ($x_value[$i] > $y_value[$i]) ? $result : -$result; |
||||||||
2691 | } |
||||||||
2692 | } |
||||||||
2693 | |||||||||
2694 | return 0; |
||||||||
2695 | } |
||||||||
2696 | |||||||||
2697 | /** |
||||||||
2698 | * Tests the equality of two numbers. |
||||||||
2699 | * |
||||||||
2700 | * If you need to see if one number is greater than or less than another number, use BigInteger::compare() |
||||||||
2701 | * |
||||||||
2702 | * @param \phpseclib\Math\BigInteger $x |
||||||||
2703 | * @return bool |
||||||||
2704 | * @access public |
||||||||
2705 | * @see self::compare() |
||||||||
2706 | */ |
||||||||
2707 | public function equals($x) |
||||||||
2708 | { |
||||||||
2709 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
2710 | case self::MODE_GMP: |
||||||||
2711 | return gmp_cmp($this->value, $x->value) == 0; |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_cmp() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$x->value of type array is incompatible with the type GMP|resource|string expected by parameter $b of gmp_cmp() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2712 | default: |
||||||||
2713 | return $this->value === $x->value && $this->is_negative == $x->is_negative; |
||||||||
2714 | } |
||||||||
2715 | } |
||||||||
2716 | |||||||||
2717 | /** |
||||||||
2718 | * Set Precision |
||||||||
2719 | * |
||||||||
2720 | * Some bitwise operations give different results depending on the precision being used. Examples include left |
||||||||
2721 | * shift, not, and rotates. |
||||||||
2722 | * |
||||||||
2723 | * @param int $bits |
||||||||
2724 | * @access public |
||||||||
2725 | */ |
||||||||
2726 | public function setPrecision($bits) |
||||||||
2727 | { |
||||||||
2728 | $this->precision = $bits; |
||||||||
2729 | if (MATH_BIGINTEGER_MODE != self::MODE_BCMATH) { |
||||||||
2730 | $this->bitmask = new static(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256); |
||||||||
2731 | } else { |
||||||||
2732 | $this->bitmask = new static(bcpow('2', $bits, 0)); |
||||||||
2733 | } |
||||||||
2734 | |||||||||
2735 | $temp = $this->_normalize($this); |
||||||||
2736 | $this->value = $temp->value; |
||||||||
2737 | } |
||||||||
2738 | |||||||||
2739 | /** |
||||||||
2740 | * Logical And |
||||||||
2741 | * |
||||||||
2742 | * @param \phpseclib\Math\BigInteger $x |
||||||||
2743 | * @access public |
||||||||
2744 | * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat> |
||||||||
2745 | * @return \phpseclib\Math\BigInteger |
||||||||
2746 | */ |
||||||||
2747 | public function bitwise_and($x) |
||||||||
2748 | { |
||||||||
2749 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
2750 | case self::MODE_GMP: |
||||||||
2751 | $temp = new static(); |
||||||||
2752 | $temp->value = gmp_and($this->value, $x->value); |
||||||||
0 ignored issues
–
show
It seems like
gmp_and($this->value, $x->value) of type GMP or resource is incompatible with the declared type array 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...
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_and() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$x->value of type array is incompatible with the type GMP|resource|string expected by parameter $b of gmp_and() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2753 | |||||||||
2754 | return $this->_normalize($temp); |
||||||||
2755 | case self::MODE_BCMATH: |
||||||||
2756 | $left = $this->toBytes(); |
||||||||
2757 | $right = $x->toBytes(); |
||||||||
2758 | |||||||||
2759 | $length = max(strlen($left), strlen($right)); |
||||||||
2760 | |||||||||
2761 | $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); |
||||||||
2762 | $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); |
||||||||
2763 | |||||||||
2764 | return $this->_normalize(new static($left & $right, 256)); |
||||||||
0 ignored issues
–
show
|
|||||||||
2765 | } |
||||||||
2766 | |||||||||
2767 | $result = $this->copy(); |
||||||||
2768 | |||||||||
2769 | $length = min(count($x->value), count($this->value)); |
||||||||
2770 | |||||||||
2771 | $result->value = array_slice($result->value, 0, $length); |
||||||||
2772 | |||||||||
2773 | for ($i = 0; $i < $length; ++$i) { |
||||||||
2774 | $result->value[$i]&= $x->value[$i]; |
||||||||
2775 | } |
||||||||
2776 | |||||||||
2777 | return $this->_normalize($result); |
||||||||
2778 | } |
||||||||
2779 | |||||||||
2780 | /** |
||||||||
2781 | * Logical Or |
||||||||
2782 | * |
||||||||
2783 | * @param \phpseclib\Math\BigInteger $x |
||||||||
2784 | * @access public |
||||||||
2785 | * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat> |
||||||||
2786 | * @return \phpseclib\Math\BigInteger |
||||||||
2787 | */ |
||||||||
2788 | public function bitwise_or($x) |
||||||||
2789 | { |
||||||||
2790 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
2791 | case self::MODE_GMP: |
||||||||
2792 | $temp = new static(); |
||||||||
2793 | $temp->value = gmp_or($this->value, $x->value); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_or() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
It seems like
gmp_or($this->value, $x->value) of type GMP or resource is incompatible with the declared type array 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...
$x->value of type array is incompatible with the type GMP|resource|string expected by parameter $b of gmp_or() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2794 | |||||||||
2795 | return $this->_normalize($temp); |
||||||||
2796 | case self::MODE_BCMATH: |
||||||||
2797 | $left = $this->toBytes(); |
||||||||
2798 | $right = $x->toBytes(); |
||||||||
2799 | |||||||||
2800 | $length = max(strlen($left), strlen($right)); |
||||||||
2801 | |||||||||
2802 | $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); |
||||||||
2803 | $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); |
||||||||
2804 | |||||||||
2805 | return $this->_normalize(new static($left | $right, 256)); |
||||||||
0 ignored issues
–
show
|
|||||||||
2806 | } |
||||||||
2807 | |||||||||
2808 | $length = max(count($this->value), count($x->value)); |
||||||||
2809 | $result = $this->copy(); |
||||||||
2810 | $result->value = array_pad($result->value, $length, 0); |
||||||||
2811 | $x->value = array_pad($x->value, $length, 0); |
||||||||
2812 | |||||||||
2813 | for ($i = 0; $i < $length; ++$i) { |
||||||||
2814 | $result->value[$i]|= $x->value[$i]; |
||||||||
2815 | } |
||||||||
2816 | |||||||||
2817 | return $this->_normalize($result); |
||||||||
2818 | } |
||||||||
2819 | |||||||||
2820 | /** |
||||||||
2821 | * Logical Exclusive-Or |
||||||||
2822 | * |
||||||||
2823 | * @param \phpseclib\Math\BigInteger $x |
||||||||
2824 | * @access public |
||||||||
2825 | * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat> |
||||||||
2826 | * @return \phpseclib\Math\BigInteger |
||||||||
2827 | */ |
||||||||
2828 | public function bitwise_xor($x) |
||||||||
2829 | { |
||||||||
2830 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
2831 | case self::MODE_GMP: |
||||||||
2832 | $temp = new static(); |
||||||||
2833 | $temp->value = gmp_xor($this->value, $x->value); |
||||||||
0 ignored issues
–
show
$x->value of type array is incompatible with the type GMP|resource|string expected by parameter $b of gmp_xor() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_xor() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
It seems like
gmp_xor($this->value, $x->value) of type GMP or resource is incompatible with the declared type array 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...
|
|||||||||
2834 | |||||||||
2835 | return $this->_normalize($temp); |
||||||||
2836 | case self::MODE_BCMATH: |
||||||||
2837 | $left = $this->toBytes(); |
||||||||
2838 | $right = $x->toBytes(); |
||||||||
2839 | |||||||||
2840 | $length = max(strlen($left), strlen($right)); |
||||||||
2841 | |||||||||
2842 | $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); |
||||||||
2843 | $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); |
||||||||
2844 | |||||||||
2845 | return $this->_normalize(new static($left ^ $right, 256)); |
||||||||
2846 | } |
||||||||
2847 | |||||||||
2848 | $length = max(count($this->value), count($x->value)); |
||||||||
2849 | $result = $this->copy(); |
||||||||
2850 | $result->value = array_pad($result->value, $length, 0); |
||||||||
2851 | $x->value = array_pad($x->value, $length, 0); |
||||||||
2852 | |||||||||
2853 | for ($i = 0; $i < $length; ++$i) { |
||||||||
2854 | $result->value[$i]^= $x->value[$i]; |
||||||||
2855 | } |
||||||||
2856 | |||||||||
2857 | return $this->_normalize($result); |
||||||||
2858 | } |
||||||||
2859 | |||||||||
2860 | /** |
||||||||
2861 | * Logical Not |
||||||||
2862 | * |
||||||||
2863 | * @access public |
||||||||
2864 | * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat> |
||||||||
2865 | * @return \phpseclib\Math\BigInteger |
||||||||
2866 | */ |
||||||||
2867 | public function bitwise_not() |
||||||||
2868 | { |
||||||||
2869 | // calculuate "not" without regard to $this->precision |
||||||||
2870 | // (will always result in a smaller number. ie. ~1 isn't 1111 1110 - it's 0) |
||||||||
2871 | $temp = $this->toBytes(); |
||||||||
2872 | if ($temp == '') { |
||||||||
2873 | return ''; |
||||||||
2874 | } |
||||||||
2875 | $pre_msb = decbin(ord($temp[0])); |
||||||||
2876 | $temp = ~$temp; |
||||||||
2877 | $msb = decbin(ord($temp[0])); |
||||||||
2878 | if (strlen($msb) == 8) { |
||||||||
2879 | $msb = substr($msb, strpos($msb, '0')); |
||||||||
2880 | } |
||||||||
2881 | $temp[0] = chr(bindec($msb)); |
||||||||
0 ignored issues
–
show
It seems like
bindec($msb) can also be of type double ; however, parameter $ascii of chr() does only seem to accept integer , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2882 | |||||||||
2883 | // see if we need to add extra leading 1's |
||||||||
2884 | $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8; |
||||||||
2885 | $new_bits = $this->precision - $current_bits; |
||||||||
2886 | if ($new_bits <= 0) { |
||||||||
2887 | return $this->_normalize(new static($temp, 256)); |
||||||||
2888 | } |
||||||||
2889 | |||||||||
2890 | // generate as many leading 1's as we need to. |
||||||||
2891 | $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3); |
||||||||
2892 | $this->_base256_lshift($leading_ones, $current_bits); |
||||||||
2893 | |||||||||
2894 | $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT); |
||||||||
2895 | |||||||||
2896 | return $this->_normalize(new static($leading_ones | $temp, 256)); |
||||||||
2897 | } |
||||||||
2898 | |||||||||
2899 | /** |
||||||||
2900 | * Logical Right Shift |
||||||||
2901 | * |
||||||||
2902 | * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift. |
||||||||
2903 | * |
||||||||
2904 | * @param int $shift |
||||||||
2905 | * @return \phpseclib\Math\BigInteger |
||||||||
2906 | * @access public |
||||||||
2907 | * @internal The only version that yields any speed increases is the internal version. |
||||||||
2908 | */ |
||||||||
2909 | public function bitwise_rightShift($shift) |
||||||||
2910 | { |
||||||||
2911 | $temp = new static(); |
||||||||
2912 | |||||||||
2913 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
2914 | case self::MODE_GMP: |
||||||||
2915 | static $two; |
||||||||
2916 | |||||||||
2917 | if (!isset($two)) { |
||||||||
2918 | $two = gmp_init('2'); |
||||||||
2919 | } |
||||||||
2920 | |||||||||
2921 | $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift)); |
||||||||
0 ignored issues
–
show
It seems like
gmp_div_q($this->value, gmp_pow($two, $shift)) of type GMP or resource is incompatible with the declared type array 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...
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_div_q() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2922 | |||||||||
2923 | break; |
||||||||
2924 | case self::MODE_BCMATH: |
||||||||
2925 | $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type string expected by parameter $dividend of bcdiv() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2926 | |||||||||
2927 | break; |
||||||||
2928 | default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten |
||||||||
2929 | // and I don't want to do that... |
||||||||
2930 | $temp->value = $this->value; |
||||||||
2931 | $temp->_rshift($shift); |
||||||||
2932 | } |
||||||||
2933 | |||||||||
2934 | return $this->_normalize($temp); |
||||||||
2935 | } |
||||||||
2936 | |||||||||
2937 | /** |
||||||||
2938 | * Logical Left Shift |
||||||||
2939 | * |
||||||||
2940 | * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift. |
||||||||
2941 | * |
||||||||
2942 | * @param int $shift |
||||||||
2943 | * @return \phpseclib\Math\BigInteger |
||||||||
2944 | * @access public |
||||||||
2945 | * @internal The only version that yields any speed increases is the internal version. |
||||||||
2946 | */ |
||||||||
2947 | public function bitwise_leftShift($shift) |
||||||||
2948 | { |
||||||||
2949 | $temp = new static(); |
||||||||
2950 | |||||||||
2951 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
2952 | case self::MODE_GMP: |
||||||||
2953 | static $two; |
||||||||
2954 | |||||||||
2955 | if (!isset($two)) { |
||||||||
2956 | $two = gmp_init('2'); |
||||||||
2957 | } |
||||||||
2958 | |||||||||
2959 | $temp->value = gmp_mul($this->value, gmp_pow($two, $shift)); |
||||||||
0 ignored issues
–
show
It seems like
gmp_mul($this->value, gmp_pow($two, $shift)) of type GMP or resource is incompatible with the declared type array 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...
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_mul() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2960 | |||||||||
2961 | break; |
||||||||
2962 | case self::MODE_BCMATH: |
||||||||
2963 | $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type string expected by parameter $left_operand of bcmul() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
2964 | |||||||||
2965 | break; |
||||||||
2966 | default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten |
||||||||
2967 | // and I don't want to do that... |
||||||||
2968 | $temp->value = $this->value; |
||||||||
2969 | $temp->_lshift($shift); |
||||||||
2970 | } |
||||||||
2971 | |||||||||
2972 | return $this->_normalize($temp); |
||||||||
2973 | } |
||||||||
2974 | |||||||||
2975 | /** |
||||||||
2976 | * Logical Left Rotate |
||||||||
2977 | * |
||||||||
2978 | * Instead of the top x bits being dropped they're appended to the shifted bit string. |
||||||||
2979 | * |
||||||||
2980 | * @param int $shift |
||||||||
2981 | * @return \phpseclib\Math\BigInteger |
||||||||
2982 | * @access public |
||||||||
2983 | */ |
||||||||
2984 | public function bitwise_leftRotate($shift) |
||||||||
2985 | { |
||||||||
2986 | $bits = $this->toBytes(); |
||||||||
2987 | |||||||||
2988 | if ($this->precision > 0) { |
||||||||
2989 | $precision = $this->precision; |
||||||||
2990 | if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) { |
||||||||
2991 | $mask = $this->bitmask->subtract(new static(1)); |
||||||||
2992 | $mask = $mask->toBytes(); |
||||||||
2993 | } else { |
||||||||
2994 | $mask = $this->bitmask->toBytes(); |
||||||||
2995 | } |
||||||||
2996 | } else { |
||||||||
2997 | $temp = ord($bits[0]); |
||||||||
2998 | for ($i = 0; $temp >> $i; ++$i) { |
||||||||
2999 | } |
||||||||
3000 | $precision = 8 * strlen($bits) - 8 + $i; |
||||||||
3001 | $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3); |
||||||||
3002 | } |
||||||||
3003 | |||||||||
3004 | if ($shift < 0) { |
||||||||
3005 | $shift+= $precision; |
||||||||
3006 | } |
||||||||
3007 | $shift%= $precision; |
||||||||
3008 | |||||||||
3009 | if (!$shift) { |
||||||||
3010 | return $this->copy(); |
||||||||
3011 | } |
||||||||
3012 | |||||||||
3013 | $left = $this->bitwise_leftShift($shift); |
||||||||
3014 | $left = $left->bitwise_and(new static($mask, 256)); |
||||||||
3015 | $right = $this->bitwise_rightShift($precision - $shift); |
||||||||
3016 | $result = MATH_BIGINTEGER_MODE != self::MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right); |
||||||||
3017 | return $this->_normalize($result); |
||||||||
3018 | } |
||||||||
3019 | |||||||||
3020 | /** |
||||||||
3021 | * Logical Right Rotate |
||||||||
3022 | * |
||||||||
3023 | * Instead of the bottom x bits being dropped they're prepended to the shifted bit string. |
||||||||
3024 | * |
||||||||
3025 | * @param int $shift |
||||||||
3026 | * @return \phpseclib\Math\BigInteger |
||||||||
3027 | * @access public |
||||||||
3028 | */ |
||||||||
3029 | public function bitwise_rightRotate($shift) |
||||||||
3030 | { |
||||||||
3031 | return $this->bitwise_leftRotate(-$shift); |
||||||||
3032 | } |
||||||||
3033 | |||||||||
3034 | /** |
||||||||
3035 | * Generates a random BigInteger |
||||||||
3036 | * |
||||||||
3037 | * Byte length is equal to $length. Uses \phpseclib\Crypt\Random if it's loaded and mt_rand if it's not. |
||||||||
3038 | * |
||||||||
3039 | * @param int $length |
||||||||
3040 | * @return \phpseclib\Math\BigInteger |
||||||||
3041 | * @access private |
||||||||
3042 | */ |
||||||||
3043 | public function _random_number_helper($size) |
||||||||
3044 | { |
||||||||
3045 | $random = Random::string($size); |
||||||||
3046 | return new static($random, 256); |
||||||||
3047 | } |
||||||||
3048 | |||||||||
3049 | /** |
||||||||
3050 | * Generate a random number |
||||||||
3051 | * |
||||||||
3052 | * Returns a random number between $min and $max where $min and $max |
||||||||
3053 | * can be defined using one of the two methods: |
||||||||
3054 | * |
||||||||
3055 | * $min->random($max) |
||||||||
3056 | * $max->random($min) |
||||||||
3057 | * |
||||||||
3058 | * @param \phpseclib\Math\BigInteger $arg1 |
||||||||
3059 | * @param \phpseclib\Math\BigInteger $arg2 |
||||||||
3060 | * @return \phpseclib\Math\BigInteger |
||||||||
3061 | * @access public |
||||||||
3062 | * @internal The API for creating random numbers used to be $a->random($min, $max), where $a was a BigInteger object. |
||||||||
3063 | * That method is still supported for BC purposes. |
||||||||
3064 | */ |
||||||||
3065 | public function random($arg1, $arg2 = false) |
||||||||
3066 | { |
||||||||
3067 | if ($arg1 === false) { |
||||||||
3068 | return false; |
||||||||
3069 | } |
||||||||
3070 | |||||||||
3071 | if ($arg2 === false) { |
||||||||
3072 | $max = $arg1; |
||||||||
3073 | $min = $this; |
||||||||
3074 | } else { |
||||||||
3075 | $min = $arg1; |
||||||||
3076 | $max = $arg2; |
||||||||
3077 | } |
||||||||
3078 | |||||||||
3079 | $compare = $max->compare($min); |
||||||||
3080 | |||||||||
3081 | if (!$compare) { |
||||||||
3082 | return $this->_normalize($min); |
||||||||
3083 | } elseif ($compare < 0) { |
||||||||
3084 | // if $min is bigger then $max, swap $min and $max |
||||||||
3085 | $temp = $max; |
||||||||
3086 | $max = $min; |
||||||||
3087 | $min = $temp; |
||||||||
3088 | } |
||||||||
3089 | |||||||||
3090 | static $one; |
||||||||
3091 | if (!isset($one)) { |
||||||||
3092 | $one = new static(1); |
||||||||
3093 | } |
||||||||
3094 | |||||||||
3095 | $max = $max->subtract($min->subtract($one)); |
||||||||
3096 | $size = strlen(ltrim($max->toBytes(), chr(0))); |
||||||||
3097 | |||||||||
3098 | /* |
||||||||
3099 | doing $random % $max doesn't work because some numbers will be more likely to occur than others. |
||||||||
3100 | eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145 |
||||||||
3101 | would produce 5 whereas the only value of random that could produce 139 would be 139. ie. |
||||||||
3102 | not all numbers would be equally likely. some would be more likely than others. |
||||||||
3103 | |||||||||
3104 | creating a whole new random number until you find one that is within the range doesn't work |
||||||||
3105 | because, for sufficiently small ranges, the likelihood that you'd get a number within that range |
||||||||
3106 | would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability |
||||||||
3107 | would be pretty high that $random would be greater than $max. |
||||||||
3108 | |||||||||
3109 | phpseclib works around this using the technique described here: |
||||||||
3110 | |||||||||
3111 | http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string |
||||||||
3112 | */ |
||||||||
3113 | $random_max = new static(chr(1) . str_repeat("\0", $size), 256); |
||||||||
3114 | $random = $this->_random_number_helper($size); |
||||||||
3115 | |||||||||
3116 | list($max_multiple) = $random_max->divide($max); |
||||||||
3117 | $max_multiple = $max_multiple->multiply($max); |
||||||||
3118 | |||||||||
3119 | while ($random->compare($max_multiple) >= 0) { |
||||||||
3120 | $random = $random->subtract($max_multiple); |
||||||||
3121 | $random_max = $random_max->subtract($max_multiple); |
||||||||
3122 | $random = $random->bitwise_leftShift(8); |
||||||||
3123 | $random = $random->add($this->_random_number_helper(1)); |
||||||||
3124 | $random_max = $random_max->bitwise_leftShift(8); |
||||||||
3125 | list($max_multiple) = $random_max->divide($max); |
||||||||
3126 | $max_multiple = $max_multiple->multiply($max); |
||||||||
3127 | } |
||||||||
3128 | list(, $random) = $random->divide($max); |
||||||||
3129 | |||||||||
3130 | return $this->_normalize($random->add($min)); |
||||||||
3131 | } |
||||||||
3132 | |||||||||
3133 | /** |
||||||||
3134 | * Generate a random prime number. |
||||||||
3135 | * |
||||||||
3136 | * If there's not a prime within the given range, false will be returned. |
||||||||
3137 | * If more than $timeout seconds have elapsed, give up and return false. |
||||||||
3138 | * |
||||||||
3139 | * @param \phpseclib\Math\BigInteger $arg1 |
||||||||
3140 | * @param \phpseclib\Math\BigInteger $arg2 |
||||||||
3141 | * @param int $timeout |
||||||||
3142 | * @return Math_BigInteger|false |
||||||||
3143 | * @access public |
||||||||
3144 | * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=15 HAC 4.44}. |
||||||||
3145 | */ |
||||||||
3146 | public function randomPrime($arg1, $arg2 = false, $timeout = false) |
||||||||
3147 | { |
||||||||
3148 | if ($arg1 === false) { |
||||||||
3149 | return false; |
||||||||
3150 | } |
||||||||
3151 | |||||||||
3152 | if ($arg2 === false) { |
||||||||
3153 | $max = $arg1; |
||||||||
3154 | $min = $this; |
||||||||
3155 | } else { |
||||||||
3156 | $min = $arg1; |
||||||||
3157 | $max = $arg2; |
||||||||
3158 | } |
||||||||
3159 | |||||||||
3160 | $compare = $max->compare($min); |
||||||||
3161 | |||||||||
3162 | if (!$compare) { |
||||||||
3163 | return $min->isPrime() ? $min : false; |
||||||||
3164 | } elseif ($compare < 0) { |
||||||||
3165 | // if $min is bigger then $max, swap $min and $max |
||||||||
3166 | $temp = $max; |
||||||||
3167 | $max = $min; |
||||||||
3168 | $min = $temp; |
||||||||
3169 | } |
||||||||
3170 | |||||||||
3171 | static $one, $two; |
||||||||
3172 | if (!isset($one)) { |
||||||||
3173 | $one = new static(1); |
||||||||
3174 | $two = new static(2); |
||||||||
3175 | } |
||||||||
3176 | |||||||||
3177 | $start = time(); |
||||||||
3178 | |||||||||
3179 | $x = $this->random($min, $max); |
||||||||
3180 | |||||||||
3181 | // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>. |
||||||||
3182 | if (MATH_BIGINTEGER_MODE == self::MODE_GMP && extension_loaded('gmp')) { |
||||||||
3183 | $p = new static(); |
||||||||
3184 | $p->value = gmp_nextprime($x->value); |
||||||||
0 ignored issues
–
show
$x->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_nextprime() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
3185 | |||||||||
3186 | if ($p->compare($max) <= 0) { |
||||||||
3187 | return $p; |
||||||||
3188 | } |
||||||||
3189 | |||||||||
3190 | if (!$min->equals($x)) { |
||||||||
3191 | $x = $x->subtract($one); |
||||||||
3192 | } |
||||||||
3193 | |||||||||
3194 | return $x->randomPrime($min, $x); |
||||||||
3195 | } |
||||||||
3196 | |||||||||
3197 | if ($x->equals($two)) { |
||||||||
3198 | return $x; |
||||||||
3199 | } |
||||||||
3200 | |||||||||
3201 | $x->_make_odd(); |
||||||||
3202 | if ($x->compare($max) > 0) { |
||||||||
3203 | // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range |
||||||||
3204 | if ($min->equals($max)) { |
||||||||
3205 | return false; |
||||||||
3206 | } |
||||||||
3207 | $x = $min->copy(); |
||||||||
3208 | $x->_make_odd(); |
||||||||
3209 | } |
||||||||
3210 | |||||||||
3211 | $initial_x = $x->copy(); |
||||||||
3212 | |||||||||
3213 | while (true) { |
||||||||
3214 | if ($timeout !== false && time() - $start > $timeout) { |
||||||||
3215 | return false; |
||||||||
3216 | } |
||||||||
3217 | |||||||||
3218 | if ($x->isPrime()) { |
||||||||
3219 | return $x; |
||||||||
3220 | } |
||||||||
3221 | |||||||||
3222 | $x = $x->add($two); |
||||||||
3223 | |||||||||
3224 | if ($x->compare($max) > 0) { |
||||||||
3225 | $x = $min->copy(); |
||||||||
3226 | if ($x->equals($two)) { |
||||||||
3227 | return $x; |
||||||||
3228 | } |
||||||||
3229 | $x->_make_odd(); |
||||||||
3230 | } |
||||||||
3231 | |||||||||
3232 | if ($x->equals($initial_x)) { |
||||||||
3233 | return false; |
||||||||
3234 | } |
||||||||
3235 | } |
||||||||
3236 | } |
||||||||
3237 | |||||||||
3238 | /** |
||||||||
3239 | * Make the current number odd |
||||||||
3240 | * |
||||||||
3241 | * If the current number is odd it'll be unchanged. If it's even, one will be added to it. |
||||||||
3242 | * |
||||||||
3243 | * @see self::randomPrime() |
||||||||
3244 | * @access private |
||||||||
3245 | */ |
||||||||
3246 | public function _make_odd() |
||||||||
3247 | { |
||||||||
3248 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
3249 | case self::MODE_GMP: |
||||||||
3250 | gmp_setbit($this->value, 0); |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_setbit() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
3251 | break; |
||||||||
3252 | case self::MODE_BCMATH: |
||||||||
3253 | if ($this->value[strlen($this->value) - 1] % 2 == 0) { |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type string expected by parameter $string of strlen() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
3254 | $this->value = bcadd($this->value, '1'); |
||||||||
0 ignored issues
–
show
It seems like
bcadd($this->value, '1') of type string is incompatible with the declared type array 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...
$this->value of type array is incompatible with the type string expected by parameter $left_operand of bcadd() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
3255 | } |
||||||||
3256 | break; |
||||||||
3257 | default: |
||||||||
3258 | $this->value[0] |= 1; |
||||||||
3259 | } |
||||||||
3260 | } |
||||||||
3261 | |||||||||
3262 | /** |
||||||||
3263 | * Checks a numer to see if it's prime |
||||||||
3264 | * |
||||||||
3265 | * Assuming the $t parameter is not set, this function has an error rate of 2**-80. The main motivation for the |
||||||||
3266 | * $t parameter is distributability. BigInteger::randomPrime() can be distributed across multiple pageloads |
||||||||
3267 | * on a website instead of just one. |
||||||||
3268 | * |
||||||||
3269 | * @param \phpseclib\Math\BigInteger $t |
||||||||
3270 | * @return bool |
||||||||
3271 | * @access public |
||||||||
3272 | * @internal Uses the |
||||||||
3273 | * {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}. See |
||||||||
3274 | * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24}. |
||||||||
3275 | */ |
||||||||
3276 | public function isPrime($t = false) |
||||||||
3277 | { |
||||||||
3278 | $length = strlen($this->toBytes()); |
||||||||
3279 | |||||||||
3280 | if (!$t) { |
||||||||
3281 | // see HAC 4.49 "Note (controlling the error probability)" |
||||||||
3282 | // @codingStandardsIgnoreStart |
||||||||
3283 | if ($length >= 163) { |
||||||||
3284 | $t = 2; |
||||||||
3285 | } // floor(1300 / 8) |
||||||||
3286 | elseif ($length >= 106) { |
||||||||
3287 | $t = 3; |
||||||||
3288 | } // floor( 850 / 8) |
||||||||
3289 | elseif ($length >= 81) { |
||||||||
3290 | $t = 4; |
||||||||
3291 | } // floor( 650 / 8) |
||||||||
3292 | elseif ($length >= 68) { |
||||||||
3293 | $t = 5; |
||||||||
3294 | } // floor( 550 / 8) |
||||||||
3295 | elseif ($length >= 56) { |
||||||||
3296 | $t = 6; |
||||||||
3297 | } // floor( 450 / 8) |
||||||||
3298 | elseif ($length >= 50) { |
||||||||
3299 | $t = 7; |
||||||||
3300 | } // floor( 400 / 8) |
||||||||
3301 | elseif ($length >= 43) { |
||||||||
3302 | $t = 8; |
||||||||
3303 | } // floor( 350 / 8) |
||||||||
3304 | elseif ($length >= 37) { |
||||||||
3305 | $t = 9; |
||||||||
3306 | } // floor( 300 / 8) |
||||||||
3307 | elseif ($length >= 31) { |
||||||||
3308 | $t = 12; |
||||||||
3309 | } // floor( 250 / 8) |
||||||||
3310 | elseif ($length >= 25) { |
||||||||
3311 | $t = 15; |
||||||||
3312 | } // floor( 200 / 8) |
||||||||
3313 | elseif ($length >= 18) { |
||||||||
3314 | $t = 18; |
||||||||
3315 | } // floor( 150 / 8) |
||||||||
3316 | else { |
||||||||
3317 | $t = 27; |
||||||||
3318 | } |
||||||||
3319 | // @codingStandardsIgnoreEnd |
||||||||
3320 | } |
||||||||
3321 | |||||||||
3322 | // ie. gmp_testbit($this, 0) |
||||||||
3323 | // ie. isEven() or !isOdd() |
||||||||
3324 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
3325 | case self::MODE_GMP: |
||||||||
3326 | return gmp_prob_prime($this->value, $t) != 0; |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type GMP|resource|string expected by parameter $a of gmp_prob_prime() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
It seems like
$t can also be of type phpseclib\Math\BigInteger ; however, parameter $reps of gmp_prob_prime() does only seem to accept integer , maybe add an additional type check?
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
3327 | case self::MODE_BCMATH: |
||||||||
3328 | if ($this->value === '2') { |
||||||||
3329 | return true; |
||||||||
3330 | } |
||||||||
3331 | if ($this->value[strlen($this->value) - 1] % 2 == 0) { |
||||||||
0 ignored issues
–
show
$this->value of type array is incompatible with the type string expected by parameter $string of strlen() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
3332 | return false; |
||||||||
3333 | } |
||||||||
3334 | break; |
||||||||
3335 | default: |
||||||||
3336 | if ($this->value == array(2)) { |
||||||||
3337 | return true; |
||||||||
3338 | } |
||||||||
3339 | if (~$this->value[0] & 1) { |
||||||||
3340 | return false; |
||||||||
3341 | } |
||||||||
3342 | } |
||||||||
3343 | |||||||||
3344 | static $primes, $zero, $one, $two; |
||||||||
3345 | |||||||||
3346 | if (!isset($primes)) { |
||||||||
3347 | $primes = array( |
||||||||
3348 | 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, |
||||||||
3349 | 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, |
||||||||
3350 | 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, |
||||||||
3351 | 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, |
||||||||
3352 | 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, |
||||||||
3353 | 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, |
||||||||
3354 | 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, |
||||||||
3355 | 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, |
||||||||
3356 | 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, |
||||||||
3357 | 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, |
||||||||
3358 | 953, 967, 971, 977, 983, 991, 997 |
||||||||
3359 | ); |
||||||||
3360 | |||||||||
3361 | if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) { |
||||||||
3362 | for ($i = 0; $i < count($primes); ++$i) { |
||||||||
0 ignored issues
–
show
It seems like you are calling the size function
count() as part of the test condition. You might want to compute the size beforehand, and not on each iteration.
If the size of the collection does not change during the iteration, it is generally a good practice to compute it beforehand, and not on each iteration: for ($i=0; $i<count($array); $i++) { // calls count() on each iteration
}
// Better
for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once
}
Loading history...
|
|||||||||
3363 | $primes[$i] = new static($primes[$i]); |
||||||||
3364 | } |
||||||||
3365 | } |
||||||||
3366 | |||||||||
3367 | $zero = new static(); |
||||||||
3368 | $one = new static(1); |
||||||||
3369 | $two = new static(2); |
||||||||
3370 | } |
||||||||
3371 | |||||||||
3372 | if ($this->equals($one)) { |
||||||||
3373 | return false; |
||||||||
3374 | } |
||||||||
3375 | |||||||||
3376 | // see HAC 4.4.1 "Random search for probable primes" |
||||||||
3377 | if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) { |
||||||||
3378 | foreach ($primes as $prime) { |
||||||||
3379 | list(, $r) = $this->divide($prime); |
||||||||
3380 | if ($r->equals($zero)) { |
||||||||
3381 | return $this->equals($prime); |
||||||||
3382 | } |
||||||||
3383 | } |
||||||||
3384 | } else { |
||||||||
3385 | $value = $this->value; |
||||||||
3386 | foreach ($primes as $prime) { |
||||||||
3387 | list(, $r) = $this->_divide_digit($value, $prime); |
||||||||
3388 | if (!$r) { |
||||||||
3389 | return count($value) == 1 && $value[0] == $prime; |
||||||||
3390 | } |
||||||||
3391 | } |
||||||||
3392 | } |
||||||||
3393 | |||||||||
3394 | $n = $this->copy(); |
||||||||
3395 | $n_1 = $n->subtract($one); |
||||||||
3396 | $n_2 = $n->subtract($two); |
||||||||
3397 | |||||||||
3398 | $r = $n_1->copy(); |
||||||||
3399 | $r_value = $r->value; |
||||||||
3400 | // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s)); |
||||||||
3401 | if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) { |
||||||||
3402 | $s = 0; |
||||||||
3403 | // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals($one) check earlier |
||||||||
3404 | while ($r->value[strlen($r->value) - 1] % 2 == 0) { |
||||||||
3405 | $r->value = bcdiv($r->value, '2', 0); |
||||||||
0 ignored issues
–
show
$r->value of type array is incompatible with the type string expected by parameter $dividend of bcdiv() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
It seems like
bcdiv($r->value, '2', 0) can also be of type string . However, the property $value is declared as type array . Maybe add an additional type check?
Our type inference engine has found a suspicous assignment of a value to a property. This check raises an issue when a value that can be of a mixed type is assigned to a property that is type hinted more strictly. For example, imagine you have a variable Either this assignment is in error or a type check should be added for that assignment. class Id
{
public $id;
public function __construct($id)
{
$this->id = $id;
}
}
class Account
{
/** @var Id $id */
public $id;
}
$account_id = false;
if (starsAreRight()) {
$account_id = new Id(42);
}
$account = new Account();
if ($account instanceof Id)
{
$account->id = $account_id;
}
Loading history...
|
|||||||||
3406 | ++$s; |
||||||||
3407 | } |
||||||||
3408 | } else { |
||||||||
3409 | for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) { |
||||||||
3410 | $temp = ~$r_value[$i] & 0xFFFFFF; |
||||||||
3411 | for ($j = 1; ($temp >> $j) & 1; ++$j) { |
||||||||
3412 | } |
||||||||
3413 | if ($j != 25) { |
||||||||
3414 | break; |
||||||||
3415 | } |
||||||||
3416 | } |
||||||||
3417 | $s = 26 * $i + $j - 1; |
||||||||
0 ignored issues
–
show
Comprehensibility
Best Practice
introduced
by
|
|||||||||
3418 | $r->_rshift($s); |
||||||||
3419 | } |
||||||||
3420 | |||||||||
3421 | for ($i = 0; $i < $t; ++$i) { |
||||||||
3422 | $a = $this->random($two, $n_2); |
||||||||
3423 | $y = $a->modPow($r, $n); |
||||||||
3424 | |||||||||
3425 | if (!$y->equals($one) && !$y->equals($n_1)) { |
||||||||
3426 | for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) { |
||||||||
3427 | $y = $y->modPow($two, $n); |
||||||||
3428 | if ($y->equals($one)) { |
||||||||
3429 | return false; |
||||||||
3430 | } |
||||||||
3431 | } |
||||||||
3432 | |||||||||
3433 | if (!$y->equals($n_1)) { |
||||||||
3434 | return false; |
||||||||
3435 | } |
||||||||
3436 | } |
||||||||
3437 | } |
||||||||
3438 | return true; |
||||||||
3439 | } |
||||||||
3440 | |||||||||
3441 | /** |
||||||||
3442 | * Logical Left Shift |
||||||||
3443 | * |
||||||||
3444 | * Shifts BigInteger's by $shift bits. |
||||||||
3445 | * |
||||||||
3446 | * @param int $shift |
||||||||
3447 | * @access private |
||||||||
3448 | */ |
||||||||
3449 | public function _lshift($shift) |
||||||||
3450 | { |
||||||||
3451 | if ($shift == 0) { |
||||||||
3452 | return; |
||||||||
3453 | } |
||||||||
3454 | |||||||||
3455 | $num_digits = (int) ($shift / self::$base); |
||||||||
3456 | $shift %= self::$base; |
||||||||
3457 | $shift = 1 << $shift; |
||||||||
3458 | |||||||||
3459 | $carry = 0; |
||||||||
3460 | |||||||||
3461 | for ($i = 0; $i < count($this->value); ++$i) { |
||||||||
0 ignored issues
–
show
It seems like you are calling the size function
count() as part of the test condition. You might want to compute the size beforehand, and not on each iteration.
If the size of the collection does not change during the iteration, it is generally a good practice to compute it beforehand, and not on each iteration: for ($i=0; $i<count($array); $i++) { // calls count() on each iteration
}
// Better
for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once
}
Loading history...
|
|||||||||
3462 | $temp = $this->value[$i] * $shift + $carry; |
||||||||
3463 | $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31); |
||||||||
3464 | $this->value[$i] = (int) ($temp - $carry * self::$baseFull); |
||||||||
3465 | } |
||||||||
3466 | |||||||||
3467 | if ($carry) { |
||||||||
3468 | $this->value[count($this->value)] = $carry; |
||||||||
3469 | } |
||||||||
3470 | |||||||||
3471 | while ($num_digits--) { |
||||||||
3472 | array_unshift($this->value, 0); |
||||||||
3473 | } |
||||||||
3474 | } |
||||||||
3475 | |||||||||
3476 | /** |
||||||||
3477 | * Logical Right Shift |
||||||||
3478 | * |
||||||||
3479 | * Shifts BigInteger's by $shift bits. |
||||||||
3480 | * |
||||||||
3481 | * @param int $shift |
||||||||
3482 | * @access private |
||||||||
3483 | */ |
||||||||
3484 | public function _rshift($shift) |
||||||||
3485 | { |
||||||||
3486 | if ($shift == 0) { |
||||||||
3487 | return; |
||||||||
3488 | } |
||||||||
3489 | |||||||||
3490 | $num_digits = (int) ($shift / self::$base); |
||||||||
3491 | $shift %= self::$base; |
||||||||
3492 | $carry_shift = self::$base - $shift; |
||||||||
3493 | $carry_mask = (1 << $shift) - 1; |
||||||||
3494 | |||||||||
3495 | if ($num_digits) { |
||||||||
3496 | $this->value = array_slice($this->value, $num_digits); |
||||||||
3497 | } |
||||||||
3498 | |||||||||
3499 | $carry = 0; |
||||||||
3500 | |||||||||
3501 | for ($i = count($this->value) - 1; $i >= 0; --$i) { |
||||||||
3502 | $temp = $this->value[$i] >> $shift | $carry; |
||||||||
3503 | $carry = ($this->value[$i] & $carry_mask) << $carry_shift; |
||||||||
3504 | $this->value[$i] = $temp; |
||||||||
3505 | } |
||||||||
3506 | |||||||||
3507 | $this->value = $this->_trim($this->value); |
||||||||
0 ignored issues
–
show
It seems like
$this->_trim($this->value) of type phpseclib\Math\BigInteger is incompatible with the declared type array 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...
|
|||||||||
3508 | } |
||||||||
3509 | |||||||||
3510 | /** |
||||||||
3511 | * Normalize |
||||||||
3512 | * |
||||||||
3513 | * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision |
||||||||
3514 | * |
||||||||
3515 | * @param \phpseclib\Math\BigInteger |
||||||||
3516 | * @return \phpseclib\Math\BigInteger |
||||||||
3517 | * @see self::_trim() |
||||||||
3518 | * @access private |
||||||||
3519 | */ |
||||||||
3520 | public function _normalize($result) |
||||||||
3521 | { |
||||||||
3522 | $result->precision = $this->precision; |
||||||||
3523 | $result->bitmask = $this->bitmask; |
||||||||
3524 | |||||||||
3525 | switch (MATH_BIGINTEGER_MODE) { |
||||||||
3526 | case self::MODE_GMP: |
||||||||
3527 | if ($this->bitmask !== false) { |
||||||||
3528 | $result->value = gmp_and($result->value, $result->bitmask->value); |
||||||||
3529 | } |
||||||||
3530 | |||||||||
3531 | return $result; |
||||||||
3532 | case self::MODE_BCMATH: |
||||||||
3533 | if (!empty($result->bitmask->value)) { |
||||||||
3534 | $result->value = bcmod($result->value, $result->bitmask->value); |
||||||||
3535 | } |
||||||||
3536 | |||||||||
3537 | return $result; |
||||||||
3538 | } |
||||||||
3539 | |||||||||
3540 | $value = &$result->value; |
||||||||
3541 | |||||||||
3542 | if (!count($value)) { |
||||||||
3543 | return $result; |
||||||||
3544 | } |
||||||||
3545 | |||||||||
3546 | $value = $this->_trim($value); |
||||||||
3547 | |||||||||
3548 | if (!empty($result->bitmask->value)) { |
||||||||
3549 | $length = min(count($value), count($this->bitmask->value)); |
||||||||
0 ignored issues
–
show
$value of type phpseclib\Math\BigInteger is incompatible with the type Countable|array expected by parameter $var of count() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
3550 | $value = array_slice($value, 0, $length); |
||||||||
0 ignored issues
–
show
$value of type phpseclib\Math\BigInteger is incompatible with the type array expected by parameter $array of array_slice() .
(
Ignorable by Annotation
)
If this is a false-positive, you can also ignore this issue in your code via the
Loading history...
|
|||||||||
3551 | |||||||||
3552 | for ($i = 0; $i < $length; ++$i) { |
||||||||
3553 | $value[$i] = $value[$i] & $this->bitmask->value[$i]; |
||||||||
3554 | } |
||||||||
3555 | } |
||||||||
3556 | |||||||||
3557 | return $result; |
||||||||
3558 | } |
||||||||
3559 | |||||||||
3560 | /** |
||||||||
3561 | * Trim |
||||||||
3562 | * |
||||||||
3563 | * Removes leading zeros |
||||||||
3564 | * |
||||||||
3565 | * @param array $value |
||||||||
3566 | * @return \phpseclib\Math\BigInteger |
||||||||
3567 | * @access private |
||||||||
3568 | */ |
||||||||
3569 | public function _trim($value) |
||||||||
3570 | { |
||||||||
3571 | for ($i = count($value) - 1; $i >= 0; --$i) { |
||||||||
3572 | if ($value[$i]) { |
||||||||
3573 | break; |
||||||||
3574 | } |
||||||||
3575 | unset($value[$i]); |
||||||||
3576 | } |
||||||||
3577 | |||||||||
3578 | return $value; |
||||||||
3579 | } |
||||||||
3580 | |||||||||
3581 | /** |
||||||||
3582 | * Array Repeat |
||||||||
3583 | * |
||||||||
3584 | * @param $input Array |
||||||||
3585 | * @param $multiplier mixed |
||||||||
3586 | * @return array |
||||||||
3587 | * @access private |
||||||||
3588 | */ |
||||||||
3589 | public function _array_repeat($input, $multiplier) |
||||||||
3590 | { |
||||||||
3591 | return ($multiplier) ? array_fill(0, $multiplier, $input) : array(); |
||||||||
3592 | } |
||||||||
3593 | |||||||||
3594 | /** |
||||||||
3595 | * Logical Left Shift |
||||||||
3596 | * |
||||||||
3597 | * Shifts binary strings $shift bits, essentially multiplying by 2**$shift. |
||||||||
3598 | * |
||||||||
3599 | * @param $x String |
||||||||
3600 | * @param $shift Integer |
||||||||
3601 | * @return string |
||||||||
3602 | * @access private |
||||||||
3603 | */ |
||||||||
3604 | public function _base256_lshift(&$x, $shift) |
||||||||
3605 | { |
||||||||
3606 | if ($shift == 0) { |
||||||||
3607 | return; |
||||||||
3608 | } |
||||||||
3609 | |||||||||
3610 | $num_bytes = $shift >> 3; // eg. floor($shift/8) |
||||||||
3611 | $shift &= 7; // eg. $shift % 8 |
||||||||
3612 | |||||||||
3613 | $carry = 0; |
||||||||
3614 | for ($i = strlen($x) - 1; $i >= 0; --$i) { |
||||||||
3615 | $temp = ord($x[$i]) << $shift | $carry; |
||||||||
3616 | $x[$i] = chr($temp); |
||||||||
3617 | $carry = $temp >> 8; |
||||||||
3618 | } |
||||||||
3619 | $carry = ($carry != 0) ? chr($carry) : ''; |
||||||||
3620 | $x = $carry . $x . str_repeat(chr(0), $num_bytes); |
||||||||
3621 | } |
||||||||
3622 | |||||||||
3623 | /** |
||||||||
3624 | * Logical Right Shift |
||||||||
3625 | * |
||||||||
3626 | * Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder. |
||||||||
3627 | * |
||||||||
3628 | * @param $x String |
||||||||
3629 | * @param $shift Integer |
||||||||
3630 | * @return string |
||||||||
3631 | * @access private |
||||||||
3632 | */ |
||||||||
3633 | public function _base256_rshift(&$x, $shift) |
||||||||
3634 | { |
||||||||
3635 | if ($shift == 0) { |
||||||||
3636 | $x = ltrim($x, chr(0)); |
||||||||
3637 | return ''; |
||||||||
3638 | } |
||||||||
3639 | |||||||||
3640 | $num_bytes = $shift >> 3; // eg. floor($shift/8) |
||||||||
3641 | $shift &= 7; // eg. $shift % 8 |
||||||||
3642 | |||||||||
3643 | $remainder = ''; |
||||||||
3644 | if ($num_bytes) { |
||||||||
3645 | $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes; |
||||||||
3646 | $remainder = substr($x, $start); |
||||||||
3647 | $x = substr($x, 0, -$num_bytes); |
||||||||
3648 | } |
||||||||
3649 | |||||||||
3650 | $carry = 0; |
||||||||
3651 | $carry_shift = 8 - $shift; |
||||||||
3652 | for ($i = 0; $i < strlen($x); ++$i) { |
||||||||
3653 | $temp = (ord($x[$i]) >> $shift) | $carry; |
||||||||
3654 | $carry = (ord($x[$i]) << $carry_shift) & 0xFF; |
||||||||
3655 | $x[$i] = chr($temp); |
||||||||
3656 | } |
||||||||
3657 | $x = ltrim($x, chr(0)); |
||||||||
3658 | |||||||||
3659 | $remainder = chr($carry >> $carry_shift) . $remainder; |
||||||||
3660 | |||||||||
3661 | return ltrim($remainder, chr(0)); |
||||||||
3662 | } |
||||||||
3663 | |||||||||
3664 | // one quirk about how the following functions are implemented is that PHP defines N to be an unsigned long |
||||||||
3665 | // at 32-bits, while java's longs are 64-bits. |
||||||||
3666 | |||||||||
3667 | /** |
||||||||
3668 | * Converts 32-bit integers to bytes. |
||||||||
3669 | * |
||||||||
3670 | * @param int $x |
||||||||
3671 | * @return string |
||||||||
3672 | * @access private |
||||||||
3673 | */ |
||||||||
3674 | public function _int2bytes($x) |
||||||||
3675 | { |
||||||||
3676 | return ltrim(pack('N', $x), chr(0)); |
||||||||
3677 | } |
||||||||
3678 | |||||||||
3679 | /** |
||||||||
3680 | * Converts bytes to 32-bit integers |
||||||||
3681 | * |
||||||||
3682 | * @param string $x |
||||||||
3683 | * @return int |
||||||||
3684 | * @access private |
||||||||
3685 | */ |
||||||||
3686 | public function _bytes2int($x) |
||||||||
3687 | { |
||||||||
3688 | $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT)); |
||||||||
3689 | return $temp['int']; |
||||||||
3690 | } |
||||||||
3691 | |||||||||
3692 | /** |
||||||||
3693 | * DER-encode an integer |
||||||||
3694 | * |
||||||||
3695 | * The ability to DER-encode integers is needed to create RSA public keys for use with OpenSSL |
||||||||
3696 | * |
||||||||
3697 | * @see self::modPow() |
||||||||
3698 | * @access private |
||||||||
3699 | * @param int $length |
||||||||
3700 | * @return string |
||||||||
3701 | */ |
||||||||
3702 | public function _encodeASN1Length($length) |
||||||||
3703 | { |
||||||||
3704 | if ($length <= 0x7F) { |
||||||||
3705 | return chr($length); |
||||||||
3706 | } |
||||||||
3707 | |||||||||
3708 | $temp = ltrim(pack('N', $length), chr(0)); |
||||||||
3709 | return pack('Ca*', 0x80 | strlen($temp), $temp); |
||||||||
3710 | } |
||||||||
3711 | |||||||||
3712 | /** |
||||||||
3713 | * Single digit division |
||||||||
3714 | * |
||||||||
3715 | * Even if int64 is being used the division operator will return a float64 value |
||||||||
3716 | * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't |
||||||||
3717 | * have the precision of int64 this is a problem so, when int64 is being used, |
||||||||
3718 | * we'll guarantee that the dividend is divisible by first subtracting the remainder. |
||||||||
3719 | * |
||||||||
3720 | * @access private |
||||||||
3721 | * @param int $x |
||||||||
3722 | * @param int $y |
||||||||
3723 | * @return int |
||||||||
3724 | */ |
||||||||
3725 | public function _safe_divide($x, $y) |
||||||||
3726 | { |
||||||||
3727 | if (self::$base === 26) { |
||||||||
3728 | return (int) ($x / $y); |
||||||||
3729 | } |
||||||||
3730 | |||||||||
3731 | // self::$base === 31 |
||||||||
3732 | return ($x - ($x % $y)) / $y; |
||||||||
3733 | } |
||||||||
3734 | } |
||||||||
3735 |