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