1<?php
2
3/**
4 * Prime Finite Fields
5 *
6 * PHP version 5 and 7
7 *
8 * @category  Math
9 * @package   BigInteger
10 * @author    Jim Wigginton <terrafrost@php.net>
11 * @copyright 2017 Jim Wigginton
12 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
13 */
14
15namespace phpseclib3\Math\PrimeField;
16
17use ParagonIE\ConstantTime\Hex;
18use phpseclib3\Math\BigInteger;
19use phpseclib3\Math\Common\FiniteField\Integer as Base;
20
21/**
22 * Prime Finite Fields
23 *
24 * @package Math
25 * @author  Jim Wigginton <terrafrost@php.net>
26 * @access  public
27 */
28class Integer extends Base
29{
30    /**
31     * Holds the PrimeField's value
32     *
33     * @var BigInteger
34     */
35    protected $value;
36
37    /**
38     * Keeps track of current instance
39     *
40     * @var int
41     */
42    protected $instanceID;
43
44    /**
45     * Holds the PrimeField's modulo
46     *
47     * @var array<int, BigInteger>
48     */
49    protected static $modulo;
50
51    /**
52     * Holds a pre-generated function to perform modulo reductions
53     *
54     * @var array<int, callable(BigInteger):BigInteger>
55     */
56    protected static $reduce;
57
58    /**
59     * Zero
60     *
61     * @var BigInteger
62     */
63    protected static $zero;
64
65    /**
66     * Default constructor
67     *
68     * @param int $instanceID
69     */
70    public function __construct($instanceID, BigInteger $num = null)
71    {
72        $this->instanceID = $instanceID;
73        if (!isset($num)) {
74            $this->value = clone static::$zero[static::class];
75        } else {
76            $reduce = static::$reduce[$instanceID];
77            $this->value = $reduce($num);
78        }
79    }
80
81    /**
82     * Set the modulo for a given instance
83     *
84     * @param int $instanceID
85     * @return void
86     */
87    public static function setModulo($instanceID, BigInteger $modulo)
88    {
89        static::$modulo[$instanceID] = $modulo;
90    }
91
92    /**
93     * Set the modulo for a given instance
94     *
95     * @param int $instanceID
96     * @return void
97     */
98    public static function setRecurringModuloFunction($instanceID, callable $function)
99    {
100        static::$reduce[$instanceID] = $function;
101        if (!isset(static::$zero[static::class])) {
102            static::$zero[static::class] = new BigInteger();
103        }
104    }
105
106    /**
107     * Delete the modulo for a given instance
108     */
109    public static function cleanupCache($instanceID)
110    {
111        unset(static::$modulo[$instanceID]);
112        unset(static::$reduce[$instanceID]);
113    }
114
115    /**
116     * Returns the modulo
117     *
118     * @param int $instanceID
119     * @return BigInteger
120     */
121    public static function getModulo($instanceID)
122    {
123        return static::$modulo[$instanceID];
124    }
125
126    /**
127     * Tests a parameter to see if it's of the right instance
128     *
129     * Throws an exception if the incorrect class is being utilized
130     *
131     * @return void
132     */
133    public static function checkInstance(self $x, self $y)
134    {
135        if ($x->instanceID != $y->instanceID) {
136            throw new \UnexpectedValueException('The instances of the two PrimeField\Integer objects do not match');
137        }
138    }
139
140    /**
141     * Tests the equality of two numbers.
142     *
143     * @return bool
144     */
145    public function equals(self $x)
146    {
147        static::checkInstance($this, $x);
148
149        return $this->value->equals($x->value);
150    }
151
152    /**
153     * Compares two numbers.
154     *
155     * @return int
156     */
157    public function compare(self $x)
158    {
159        static::checkInstance($this, $x);
160
161        return $this->value->compare($x->value);
162    }
163
164    /**
165     * Adds two PrimeFieldIntegers.
166     *
167     * @return static
168     */
169    public function add(self $x)
170    {
171        static::checkInstance($this, $x);
172
173        $temp = new static($this->instanceID);
174        $temp->value = $this->value->add($x->value);
175        if ($temp->value->compare(static::$modulo[$this->instanceID]) >= 0) {
176            $temp->value = $temp->value->subtract(static::$modulo[$this->instanceID]);
177        }
178
179        return $temp;
180    }
181
182    /**
183     * Subtracts two PrimeFieldIntegers.
184     *
185     * @return static
186     */
187    public function subtract(self $x)
188    {
189        static::checkInstance($this, $x);
190
191        $temp = new static($this->instanceID);
192        $temp->value = $this->value->subtract($x->value);
193        if ($temp->value->isNegative()) {
194            $temp->value = $temp->value->add(static::$modulo[$this->instanceID]);
195        }
196
197        return $temp;
198    }
199
200    /**
201     * Multiplies two PrimeFieldIntegers.
202     *
203     * @return static
204     */
205    public function multiply(self $x)
206    {
207        static::checkInstance($this, $x);
208
209        return new static($this->instanceID, $this->value->multiply($x->value));
210    }
211
212    /**
213     * Divides two PrimeFieldIntegers.
214     *
215     * @return static
216     */
217    public function divide(self $x)
218    {
219        static::checkInstance($this, $x);
220
221        $denominator = $x->value->modInverse(static::$modulo[$this->instanceID]);
222        return new static($this->instanceID, $this->value->multiply($denominator));
223    }
224
225    /**
226     * Performs power operation on a PrimeFieldInteger.
227     *
228     * @return static
229     */
230    public function pow(BigInteger $x)
231    {
232        $temp = new static($this->instanceID);
233        $temp->value = $this->value->powMod($x, static::$modulo[$this->instanceID]);
234
235        return $temp;
236    }
237
238    /**
239     * Calculates the square root
240     *
241     * @link https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
242     * @return static|false
243     */
244    public function squareRoot()
245    {
246        static $one, $two;
247        if (!isset($one)) {
248            $one = new BigInteger(1);
249            $two = new BigInteger(2);
250        }
251        $reduce = static::$reduce[$this->instanceID];
252        $p_1 = static::$modulo[$this->instanceID]->subtract($one);
253        $q = clone $p_1;
254        $s = BigInteger::scan1divide($q);
255        list($pow) = $p_1->divide($two);
256        for ($z = $one; !$z->equals(static::$modulo[$this->instanceID]); $z = $z->add($one)) {
257            $temp = $z->powMod($pow, static::$modulo[$this->instanceID]);
258            if ($temp->equals($p_1)) {
259                break;
260            }
261        }
262
263        $m = new BigInteger($s);
264        $c = $z->powMod($q, static::$modulo[$this->instanceID]);
265        $t = $this->value->powMod($q, static::$modulo[$this->instanceID]);
266        list($temp) = $q->add($one)->divide($two);
267        $r = $this->value->powMod($temp, static::$modulo[$this->instanceID]);
268
269        while (!$t->equals($one)) {
270            $i = clone $one;
271
272            while (!$t->powMod($two->pow($i), static::$modulo[$this->instanceID])->equals($one)) {
273                $i = $i->add($one);
274            }
275
276            if ($i->compare($m) >= 0) {
277                return false;
278            }
279            $b = $c->powMod($two->pow($m->subtract($i)->subtract($one)), static::$modulo[$this->instanceID]);
280            $m = $i;
281            $c = $reduce($b->multiply($b));
282            $t = $reduce($t->multiply($c));
283            $r = $reduce($r->multiply($b));
284        }
285
286        return new static($this->instanceID, $r);
287    }
288
289    /**
290     * Is Odd?
291     *
292     * @return bool
293     */
294    public function isOdd()
295    {
296        return $this->value->isOdd();
297    }
298
299    /**
300     * Negate
301     *
302     * A negative number can be written as 0-12. With modulos, 0 is the same thing as the modulo
303     * so 0-12 is the same thing as modulo-12
304     *
305     * @return static
306     */
307    public function negate()
308    {
309        return new static($this->instanceID, static::$modulo[$this->instanceID]->subtract($this->value));
310    }
311
312    /**
313     * Converts an Integer to a byte string (eg. base-256).
314     *
315     * @return string
316     */
317    public function toBytes()
318    {
319        $length = static::$modulo[$this->instanceID]->getLengthInBytes();
320        return str_pad($this->value->toBytes(), $length, "\0", STR_PAD_LEFT);
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 Hex::encode($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     * @access public
405     * @return string
406     */
407    public function __toString()
408    {
409        return (string) $this->value;
410    }
411
412    /**
413     *  __debugInfo() magic method
414     *
415     * @access public
416     * @return array
417     */
418    public function __debugInfo()
419    {
420        return ['value' => $this->toHex()];
421    }
422}
423