xref: /dokuwiki/vendor/phpseclib/phpseclib/phpseclib/Math/BinaryField.php (revision 927933f55f286c8bea68959a13975cbcb59eb8ee) 
1<?php
2
3/**
4 * Binary Finite Fields
5 *
6 * Utilizes the factory design pattern
7 *
8 * PHP version 5 and 7
9 *
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;
16
17use phpseclib3\Common\Functions\Strings;
18use phpseclib3\Math\BinaryField\Integer;
19use phpseclib3\Math\Common\FiniteField;
20
21/**
22 * Binary Finite Fields
23 *
24 * @author  Jim Wigginton <terrafrost@php.net>
25 */
26class BinaryField extends FiniteField
27{
28    /**
29     * Instance Counter
30     *
31     * @var int
32     */
33    private static $instanceCounter = 0;
34
35    /**
36     * Keeps track of current instance
37     *
38     * @var int
39     */
40    protected $instanceID;
41
42    /** @var BigInteger */
43    private $randomMax;
44
45    /**
46     * Default constructor
47     */
48    public function __construct(...$indices)
49    {
50        $m = array_shift($indices);
51        if ($m > 571) {
52            /* sect571r1 and sect571k1 are the largest binary curves that https://www.secg.org/sec2-v2.pdf defines
53               altho theoretically there may be legit reasons to use binary finite fields with larger degrees
54               imposing a limit on the maximum size is both reasonable and precedented. in particular,
55               http://tools.ietf.org/html/rfc4253#section-6.1 (The Secure Shell (SSH) Transport Layer Protocol) says
56               "implementations SHOULD check that the packet length is reasonable in order for the implementation to
57                avoid denial of service and/or buffer overflow attacks" */
58            throw new \OutOfBoundsException('Degrees larger than 571 are not supported');
59        }
60        $val = str_repeat('0', $m) . '1';
61        foreach ($indices as $index) {
62            $val[$index] = '1';
63        }
64        $modulo = static::base2ToBase256(strrev($val));
65
66        $mStart = 2 * $m - 2;
67        $t = ceil($m / 8);
68        $finalMask = chr((1 << ($m % 8)) - 1);
69        if ($finalMask == "\0") {
70            $finalMask = "\xFF";
71        }
72        $bitLen = $mStart + 1;
73        $pad = ceil($bitLen / 8);
74        $h = $bitLen & 7;
75        $h = $h ? 8 - $h : 0;
76
77        $r = rtrim(substr($val, 0, -1), '0');
78        $u = [static::base2ToBase256(strrev($r))];
79        for ($i = 1; $i < 8; $i++) {
80            $u[] = static::base2ToBase256(strrev(str_repeat('0', $i) . $r));
81        }
82
83        // implements algorithm 2.40 (in section 2.3.5) in "Guide to Elliptic Curve Cryptography"
84        // with W = 8
85        $reduce = function ($c) use ($u, $mStart, $m, $t, $finalMask, $pad, $h) {
86            $c = str_pad($c, $pad, "\0", STR_PAD_LEFT);
87            for ($i = $mStart; $i >= $m;) {
88                $g = $h >> 3;
89                $mask = $h & 7;
90                $mask = $mask ? 1 << (7 - $mask) : 0x80;
91                for (; $mask > 0; $mask >>= 1, $i--, $h++) {
92                    if (ord($c[$g]) & $mask) {
93                        $temp = $i - $m;
94                        $j = $temp >> 3;
95                        $k = $temp & 7;
96                        $t1 = $j ? substr($c, 0, -$j) : $c;
97                        $length = strlen($t1);
98                        if ($length) {
99                            $t2 = str_pad($u[$k], $length, "\0", STR_PAD_LEFT);
100                            $temp = $t1 ^ $t2;
101                            $c = $j ? substr_replace($c, $temp, 0, $length) : $temp;
102                        }
103                    }
104                }
105            }
106            $c = substr($c, -$t);
107            if (strlen($c) == $t) {
108                $c[0] = $c[0] & $finalMask;
109            }
110            return ltrim($c, "\0");
111        };
112
113        $this->instanceID = self::$instanceCounter++;
114        Integer::setModulo($this->instanceID, $modulo);
115        Integer::setRecurringModuloFunction($this->instanceID, $reduce);
116
117        $this->randomMax = new BigInteger($modulo, 2);
118    }
119
120    /**
121     * Returns an instance of a dynamically generated PrimeFieldInteger class
122     *
123     * @param string $num
124     * @return Integer
125     */
126    public function newInteger($num)
127    {
128        return new Integer($this->instanceID, $num instanceof BigInteger ? $num->toBytes() : $num);
129    }
130
131    /**
132     * Returns an integer on the finite field between one and the prime modulo
133     *
134     * @return Integer
135     */
136    public function randomInteger()
137    {
138        static $one;
139        if (!isset($one)) {
140            $one = new BigInteger(1);
141        }
142
143        return new Integer($this->instanceID, BigInteger::randomRange($one, $this->randomMax)->toBytes());
144    }
145
146    /**
147     * Returns the length of the modulo in bytes
148     *
149     * @return int
150     */
151    public function getLengthInBytes()
152    {
153        return strlen(Integer::getModulo($this->instanceID));
154    }
155
156    /**
157     * Returns the length of the modulo in bits
158     *
159     * @return int
160     */
161    public function getLength()
162    {
163        return strlen(Integer::getModulo($this->instanceID)) << 3;
164    }
165
166    /**
167     * Converts a base-2 string to a base-256 string
168     *
169     * @param string $x
170     * @param int|null $size
171     * @return string
172     */
173    public static function base2ToBase256($x, $size = null)
174    {
175        $str = Strings::bits2bin($x);
176
177        $pad = strlen($x) >> 3;
178        if (strlen($x) & 3) {
179            $pad++;
180        }
181        $str = str_pad($str, $pad, "\0", STR_PAD_LEFT);
182        if (isset($size)) {
183            $str = str_pad($str, $size, "\0", STR_PAD_LEFT);
184        }
185
186        return $str;
187    }
188
189    /**
190     * Converts a base-256 string to a base-2 string
191     *
192     * @param string $x
193     * @return string
194     */
195    public static function base256ToBase2($x)
196    {
197        if (function_exists('gmp_import')) {
198            return gmp_strval(gmp_import($x), 2);
199        }
200
201        return Strings::bin2bits($x);
202    }
203}
204