Rev 846 | Rev 1042 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
827 | daniel-mar | 1 | <?php |
2 | |||
3 | /** |
||
4 | * Binary Finite Fields |
||
5 | * |
||
6 | * Utilizes the factory design pattern |
||
7 | * |
||
8 | * PHP version 5 and 7 |
||
9 | * |
||
874 | daniel-mar | 10 | * @category Math |
11 | * @package BigInteger |
||
827 | daniel-mar | 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 | |||
17 | namespace phpseclib3\Math; |
||
18 | |||
19 | use phpseclib3\Common\Functions\Strings; |
||
20 | use phpseclib3\Math\BinaryField\Integer; |
||
21 | use phpseclib3\Math\Common\FiniteField; |
||
22 | |||
23 | /** |
||
24 | * Binary Finite Fields |
||
25 | * |
||
874 | daniel-mar | 26 | * @package Math |
827 | daniel-mar | 27 | * @author Jim Wigginton <terrafrost@php.net> |
874 | daniel-mar | 28 | * @access public |
827 | daniel-mar | 29 | */ |
30 | class 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 | } |