1<?php
2
3/**
4 * Binary Finite Fields
5 *
6 * Utilizes the factory design pattern
7 *
8 * PHP version 5 and 7
9 *
10 * @category  Math
11 * @package   BigInteger
12 * @author    Jim Wigginton <terrafrost@php.net>
13 * @copyright 2017 Jim Wigginton
14 * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
15 */
16
17namespace phpseclib3\Math;
18
19use phpseclib3\Common\Functions\Strings;
20use phpseclib3\Math\BinaryField\Integer;
21use phpseclib3\Math\Common\FiniteField;
22
23/**
24 * Binary Finite Fields
25 *
26 * @package Math
27 * @author  Jim Wigginton <terrafrost@php.net>
28 * @access  public
29 */
30class BinaryField extends FiniteField
31{
32    /**
33     * Instance Counter
34     *
35     * @var int
36     */
37    private static $instanceCounter = 0;
38
39    /**
40     * Keeps track of current instance
41     *
42     * @var int
43     */
44    protected $instanceID;
45
46    /** @var BigInteger */
47    private $randomMax;
48
49    /**
50     * Default constructor
51     */
52    public function __construct(...$indices)
53    {
54        $m = array_shift($indices);
55        $val = str_repeat('0', $m) . '1';
56        foreach ($indices as $index) {
57            $val[$index] = '1';
58        }
59        $modulo = static::base2ToBase256(strrev($val));
60
61        $mStart = 2 * $m - 2;
62        $t = ceil($m / 8);
63        $finalMask = chr((1 << ($m % 8)) - 1);
64        if ($finalMask == "\0") {
65            $finalMask = "\xFF";
66        }
67        $bitLen = $mStart + 1;
68        $pad = ceil($bitLen / 8);
69        $h = $bitLen & 7;
70        $h = $h ? 8 - $h : 0;
71
72        $r = rtrim(substr($val, 0, -1), '0');
73        $u = [static::base2ToBase256(strrev($r))];
74        for ($i = 1; $i < 8; $i++) {
75            $u[] = static::base2ToBase256(strrev(str_repeat('0', $i) . $r));
76        }
77
78        // implements algorithm 2.40 (in section 2.3.5) in "Guide to Elliptic Curve Cryptography"
79        // with W = 8
80        $reduce = function ($c) use ($u, $mStart, $m, $t, $finalMask, $pad, $h) {
81            $c = str_pad($c, $pad, "\0", STR_PAD_LEFT);
82            for ($i = $mStart; $i >= $m;) {
83                $g = $h >> 3;
84                $mask = $h & 7;
85                $mask = $mask ? 1 << (7 - $mask) : 0x80;
86                for (; $mask > 0; $mask >>= 1, $i--, $h++) {
87                    if (ord($c[$g]) & $mask) {
88                        $temp = $i - $m;
89                        $j = $temp >> 3;
90                        $k = $temp & 7;
91                        $t1 = $j ? substr($c, 0, -$j) : $c;
92                        $length = strlen($t1);
93                        if ($length) {
94                            $t2 = str_pad($u[$k], $length, "\0", STR_PAD_LEFT);
95                            $temp = $t1 ^ $t2;
96                            $c = $j ? substr_replace($c, $temp, 0, $length) : $temp;
97                        }
98                    }
99                }
100            }
101            $c = substr($c, -$t);
102            if (strlen($c) == $t) {
103                $c[0] = $c[0] & $finalMask;
104            }
105            return ltrim($c, "\0");
106        };
107
108        $this->instanceID = self::$instanceCounter++;
109        Integer::setModulo($this->instanceID, $modulo);
110        Integer::setRecurringModuloFunction($this->instanceID, $reduce);
111
112        $this->randomMax = new BigInteger($modulo, 2);
113    }
114
115    /**
116     * Returns an instance of a dynamically generated PrimeFieldInteger class
117     *
118     * @param string $num
119     * @return Integer
120     */
121    public function newInteger($num)
122    {
123        return new Integer($this->instanceID, $num instanceof BigInteger ? $num->toBytes() : $num);
124    }
125
126    /**
127     * Returns an integer on the finite field between one and the prime modulo
128     *
129     * @return Integer
130     */
131    public function randomInteger()
132    {
133        static $one;
134        if (!isset($one)) {
135            $one = new BigInteger(1);
136        }
137
138        return new Integer($this->instanceID, BigInteger::randomRange($one, $this->randomMax)->toBytes());
139    }
140
141    /**
142     * Returns the length of the modulo in bytes
143     *
144     * @return int
145     */
146    public function getLengthInBytes()
147    {
148        return strlen(Integer::getModulo($this->instanceID));
149    }
150
151    /**
152     * Returns the length of the modulo in bits
153     *
154     * @return int
155     */
156    public function getLength()
157    {
158        return strlen(Integer::getModulo($this->instanceID)) << 3;
159    }
160
161    /**
162     * Converts a base-2 string to a base-256 string
163     *
164     * @param string $x
165     * @param int|null $size
166     * @return string
167     */
168    public static function base2ToBase256($x, $size = null)
169    {
170        $str = Strings::bits2bin($x);
171
172        $pad = strlen($x) >> 3;
173        if (strlen($x) & 3) {
174            $pad++;
175        }
176        $str = str_pad($str, $pad, "\0", STR_PAD_LEFT);
177        if (isset($size)) {
178            $str = str_pad($str, $size, "\0", STR_PAD_LEFT);
179        }
180
181        return $str;
182    }
183
184    /**
185     * Converts a base-256 string to a base-2 string
186     *
187     * @param string $x
188     * @return string
189     */
190    public static function base256ToBase2($x)
191    {
192        if (function_exists('gmp_import')) {
193            return gmp_strval(gmp_import($x), 2);
194        }
195
196        return Strings::bin2bits($x);
197    }
198}
199