xref: /dokuwiki/vendor/phpseclib/phpseclib/phpseclib/Math/PrimeField/Integer.php (revision 8e88a29b81301f78509349ab1152bb09c229123e) 
1<?php
2
3/**
4 * Prime Finite Fields
5 *
6 * PHP version 5 and 7
7 *
8 * @author    Jim Wigginton <terrafrost@php.net>
9 * @copyright 2017 Jim Wigginton
10 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
11 */
12
13namespace phpseclib3\Math\PrimeField;
14
15use phpseclib3\Common\Functions\Strings;
16use phpseclib3\Math\BigInteger;
17use phpseclib3\Math\Common\FiniteField\Integer as Base;
18
19/**
20 * Prime Finite Fields
21 *
22 * @author  Jim Wigginton <terrafrost@php.net>
23 */
24class Integer extends Base
25{
26    /**
27     * Holds the PrimeField's value
28     *
29     * @var BigInteger
30     */
31    protected $value;
32
33    /**
34     * Keeps track of current instance
35     *
36     * @var int
37     */
38    protected $instanceID;
39
40    /**
41     * Holds the PrimeField's modulo
42     *
43     * @var array<int, BigInteger>
44     */
45    protected static $modulo;
46
47    /**
48     * Holds a pre-generated function to perform modulo reductions
49     *
50     * @var array<int, callable(BigInteger):BigInteger>
51     */
52    protected static $reduce;
53
54    /**
55     * Zero
56     *
57     * @var BigInteger[]
58     */
59    protected static $zero;
60
61    /**
62     * One
63     *
64     * @var BigInteger[]
65     */
66    protected static $one;
67
68    /**
69     * Two
70     *
71     * @var BigInteger[]
72     */
73    protected static $two;
74
75    /**
76     * Default constructor
77     *
78     * @param int $instanceID
79     * @param BigInteger $num
80     */
81    public function __construct($instanceID, $num = null)
82    {
83        $this->instanceID = $instanceID;
84        if (!isset($num)) {
85            $this->value = clone static::$zero[$instanceID];
86        } else {
87            $reduce = static::$reduce[$instanceID];
88            $this->value = $reduce($num);
89        }
90    }
91
92    /**
93     * Set the modulo for a given instance
94     *
95     * @param int $instanceID
96     * @return void
97     */
98    public static function setModulo($instanceID, BigInteger $modulo)
99    {
100        static::$modulo[$instanceID] = $modulo;
101    }
102
103    /**
104     * Set the modulo for a given instance
105     *
106     * @param int $instanceID
107     * @return void
108     */
109    public static function setRecurringModuloFunction($instanceID, callable $function)
110    {
111        static::$reduce[$instanceID] = $function;
112        if (!isset(static::$zero[$instanceID])) {
113            static::$zero[$instanceID] = new BigInteger();
114        }
115    }
116
117    /**
118     * Delete the modulo for a given instance
119     */
120    public static function cleanupCache($instanceID)
121    {
122        unset(static::$modulo[$instanceID]);
123        unset(static::$reduce[$instanceID]);
124        unset(static::$zero[$instanceID]);
125        unset(static::$one[$instanceID]);
126        unset(static::$two[$instanceID]);
127    }
128
129    /**
130     * Returns the modulo
131     *
132     * @param int $instanceID
133     * @return BigInteger
134     */
135    public static function getModulo($instanceID)
136    {
137        return static::$modulo[$instanceID];
138    }
139
140    /**
141     * Tests a parameter to see if it's of the right instance
142     *
143     * Throws an exception if the incorrect class is being utilized
144     *
145     * @return void
146     */
147    public static function checkInstance(self $x, self $y)
148    {
149        if ($x->instanceID != $y->instanceID) {
150            throw new \UnexpectedValueException('The instances of the two PrimeField\Integer objects do not match');
151        }
152    }
153
154    /**
155     * Tests the equality of two numbers.
156     *
157     * @return bool
158     */
159    public function equals(self $x)
160    {
161        static::checkInstance($this, $x);
162
163        return $this->value->equals($x->value);
164    }
165
166    /**
167     * Compares two numbers.
168     *
169     * @return int
170     */
171    public function compare(self $x)
172    {
173        static::checkInstance($this, $x);
174
175        return $this->value->compare($x->value);
176    }
177
178    /**
179     * Adds two PrimeFieldIntegers.
180     *
181     * @return static
182     */
183    public function add(self $x)
184    {
185        static::checkInstance($this, $x);
186
187        $temp = new static($this->instanceID);
188        $temp->value = $this->value->add($x->value);
189        if ($temp->value->compare(static::$modulo[$this->instanceID]) >= 0) {
190            $temp->value = $temp->value->subtract(static::$modulo[$this->instanceID]);
191        }
192
193        return $temp;
194    }
195
196    /**
197     * Subtracts two PrimeFieldIntegers.
198     *
199     * @return static
200     */
201    public function subtract(self $x)
202    {
203        static::checkInstance($this, $x);
204
205        $temp = new static($this->instanceID);
206        $temp->value = $this->value->subtract($x->value);
207        if ($temp->value->isNegative()) {
208            $temp->value = $temp->value->add(static::$modulo[$this->instanceID]);
209        }
210
211        return $temp;
212    }
213
214    /**
215     * Multiplies two PrimeFieldIntegers.
216     *
217     * @return static
218     */
219    public function multiply(self $x)
220    {
221        static::checkInstance($this, $x);
222
223        return new static($this->instanceID, $this->value->multiply($x->value));
224    }
225
226    /**
227     * Divides two PrimeFieldIntegers.
228     *
229     * @return static
230     */
231    public function divide(self $x)
232    {
233        static::checkInstance($this, $x);
234
235        $denominator = $x->value->modInverse(static::$modulo[$this->instanceID]);
236        return new static($this->instanceID, $this->value->multiply($denominator));
237    }
238
239    /**
240     * Performs power operation on a PrimeFieldInteger.
241     *
242     * @return static
243     */
244    public function pow(BigInteger $x)
245    {
246        $temp = new static($this->instanceID);
247        $temp->value = $this->value->powMod($x, static::$modulo[$this->instanceID]);
248
249        return $temp;
250    }
251
252    /**
253     * Calculates the square root
254     *
255     * @link https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
256     * @return static|false
257     */
258    public function squareRoot()
259    {
260        if (!isset(static::$one[$this->instanceID])) {
261            static::$one[$this->instanceID] = new BigInteger(1);
262            static::$two[$this->instanceID] = new BigInteger(2);
263        }
264        $one = &static::$one[$this->instanceID];
265        $two = &static::$two[$this->instanceID];
266        $modulo = &static::$modulo[$this->instanceID];
267        $reduce = &static::$reduce[$this->instanceID];
268
269        $p_1 = $modulo->subtract($one);
270        $q = clone $p_1;
271        $s = BigInteger::scan1divide($q);
272        list($pow) = $p_1->divide($two);
273        for ($z = $one; !$z->equals($modulo); $z = $z->add($one)) {
274            $temp = $z->powMod($pow, $modulo);
275            if ($temp->equals($p_1)) {
276                break;
277            }
278        }
279
280        $m = new BigInteger($s);
281        $c = $z->powMod($q, $modulo);
282        $t = $this->value->powMod($q, $modulo);
283        list($temp) = $q->add($one)->divide($two);
284        $r = $this->value->powMod($temp, $modulo);
285
286        while (!$t->equals($one)) {
287            for ($i = clone $one; $i->compare($m) < 0; $i = $i->add($one)) {
288                if ($t->powMod($two->pow($i), $modulo)->equals($one)) {
289                    break;
290                }
291            }
292
293            if ($i->compare($m) == 0) {
294                return false;
295            }
296            $b = $c->powMod($two->pow($m->subtract($i)->subtract($one)), $modulo);
297            $m = $i;
298            $c = $reduce($b->multiply($b));
299            $t = $reduce($t->multiply($c));
300            $r = $reduce($r->multiply($b));
301        }
302
303        return new static($this->instanceID, $r);
304    }
305
306    /**
307     * Is Odd?
308     *
309     * @return bool
310     */
311    public function isOdd()
312    {
313        return $this->value->isOdd();
314    }
315
316    /**
317     * Negate
318     *
319     * A negative number can be written as 0-12. With modulos, 0 is the same thing as the modulo
320     * so 0-12 is the same thing as modulo-12
321     *
322     * @return static
323     */
324    public function negate()
325    {
326        return new static($this->instanceID, static::$modulo[$this->instanceID]->subtract($this->value));
327    }
328
329    /**
330     * Converts an Integer to a byte string (eg. base-256).
331     *
332     * @return string
333     */
334    public function toBytes()
335    {
336        if (isset(static::$modulo[$this->instanceID])) {
337            $length = static::$modulo[$this->instanceID]->getLengthInBytes();
338            return str_pad($this->value->toBytes(), $length, "\0", STR_PAD_LEFT);
339        }
340        return $this->value->toBytes();
341    }
342
343    /**
344     * Converts an Integer to a hex string (eg. base-16).
345     *
346     * @return string
347     */
348    public function toHex()
349    {
350        return Strings::bin2hex($this->toBytes());
351    }
352
353    /**
354     * Converts an Integer to a bit string (eg. base-2).
355     *
356     * @return string
357     */
358    public function toBits()
359    {
360        // return $this->value->toBits();
361        static $length;
362        if (!isset($length)) {
363            $length = static::$modulo[$this->instanceID]->getLength();
364        }
365
366        return str_pad($this->value->toBits(), $length, '0', STR_PAD_LEFT);
367    }
368
369    /**
370     * Returns the w-ary non-adjacent form (wNAF)
371     *
372     * @param int $w optional
373     * @return array<int, int>
374     */
375    public function getNAF($w = 1)
376    {
377        $w++;
378
379        $zero = &static::$zero[$this->instanceID];
380
381        $mask = new BigInteger((1 << $w) - 1);
382        $sub = new BigInteger(1 << $w);
383        //$sub = new BigInteger(1 << ($w - 1));
384        $d = $this->toBigInteger();
385        $d_i = [];
386
387        $i = 0;
388        while ($d->compare($zero) > 0) {
389            if ($d->isOdd()) {
390                // start mods
391
392                $bigInteger = $d->testBit($w - 1) ?
393                    $d->bitwise_and($mask)->subtract($sub) :
394                    //$sub->subtract($d->bitwise_and($mask)) :
395                    $d->bitwise_and($mask);
396                // end mods
397                $d = $d->subtract($bigInteger);
398                $d_i[$i] = (int) $bigInteger->toString();
399            } else {
400                $d_i[$i] = 0;
401            }
402            $shift = !$d->equals($zero) && $d->bitwise_and($mask)->equals($zero) ? $w : 1; // $w or $w + 1?
403            $d = $d->bitwise_rightShift($shift);
404            while (--$shift > 0) {
405                $d_i[++$i] = 0;
406            }
407            $i++;
408        }
409
410        return $d_i;
411    }
412
413    /**
414     * Converts an Integer to a BigInteger
415     *
416     * @return BigInteger
417     */
418    public function toBigInteger()
419    {
420        return clone $this->value;
421    }
422
423    /**
424     *  __toString() magic method
425     *
426     * @return string
427     */
428    public function __toString()
429    {
430        return (string) $this->value;
431    }
432
433    /**
434     *  __debugInfo() magic method
435     *
436     * @return array
437     */
438    public function __debugInfo()
439    {
440        return ['value' => $this->toHex()];
441    }
442}
443