1<?php
2
3/**
4 * BigMath: A math library wrapper that abstracts out the underlying
5 * long integer library.
6 *
7 * PHP versions 4 and 5
8 *
9 * LICENSE: See the COPYING file included in this distribution.
10 *
11 * @access private
12 * @package OpenID
13 * @author JanRain, Inc. <openid@janrain.com>
14 * @copyright 2005-2008 Janrain, Inc.
15 * @license http://www.apache.org/licenses/LICENSE-2.0 Apache
16 */
17
18/**
19 * Needed for random number generation
20 */
21require_once 'Auth/OpenID/CryptUtil.php';
22
23/**
24 * Need Auth_OpenID::bytes().
25 */
26require_once 'Auth/OpenID.php';
27
28/**
29 * The superclass of all big-integer math implementations
30 * @access private
31 * @package OpenID
32 */
33abstract class Auth_OpenID_MathLibrary {
34    /**
35     * Given a long integer, returns the number converted to a binary
36     * string.  This function accepts long integer values of arbitrary
37     * magnitude and uses the local large-number math library when
38     * available.
39     *
40     * @param integer $long The long number (can be a normal PHP
41     * integer or a number created by one of the available long number
42     * libraries)
43     * @return string $binary The binary version of $long
44     */
45    function longToBinary($long)
46    {
47        $cmp = $this->cmp($long, 0);
48        if ($cmp < 0) {
49            $msg = __FUNCTION__ . " takes only positive integers.";
50            trigger_error($msg, E_USER_ERROR);
51            return null;
52        }
53
54        if ($cmp == 0) {
55            return "\x00";
56        }
57
58        $bytes = [];
59
60        while ($this->cmp($long, 0) > 0) {
61            array_unshift($bytes, $this->mod($long, 256));
62            $long = $this->div($long, pow(2, 8));
63        }
64
65        if ($bytes && ($bytes[0] > 127)) {
66            array_unshift($bytes, 0);
67        }
68
69        $string = '';
70        foreach ($bytes as $byte) {
71            $string .= pack('C', $byte);
72        }
73
74        return $string;
75    }
76
77    /**
78     * Given a binary string, returns the binary string converted to a
79     * long number.
80     *
81     * @param string $str The binary version of a long number,
82     * probably as a result of calling longToBinary
83     * @return integer $long The long number equivalent of the binary
84     * string $str
85     */
86    function binaryToLong($str)
87    {
88        if ($str === null) {
89            return null;
90        }
91
92        // Use array_merge to return a zero-indexed array instead of a
93        // one-indexed array.
94        $bytes = array_merge(unpack('C*', $str));
95
96        $n = $this->init(0);
97
98        if ($bytes && ($bytes[0] > 127)) {
99            trigger_error("bytesToNum works only for positive integers.",
100                          E_USER_WARNING);
101            return null;
102        }
103
104        foreach ($bytes as $byte) {
105            $n = $this->mul($n, pow(2, 8));
106            $n = $this->add($n, $byte);
107        }
108
109        return $n;
110    }
111
112    function base64ToLong($str)
113    {
114        $b64 = base64_decode($str);
115
116        if ($b64 === false) {
117            return false;
118        }
119
120        return $this->binaryToLong($b64);
121    }
122
123    function longToBase64($str)
124    {
125        return base64_encode($this->longToBinary($str));
126    }
127
128    /**
129     * Returns a random number in the specified range.  This function
130     * accepts $start, $stop, and $step values of arbitrary magnitude
131     * and will utilize the local large-number math library when
132     * available.
133     *
134     * @param integer $stop The end of the range, or the maximum
135     * random number to return
136     * @return integer $result The resulting randomly-generated number
137     */
138    function rand($stop)
139    {
140        static $duplicate_cache = [];
141
142        // Used as the key for the duplicate cache
143        $rbytes = $this->longToBinary($stop);
144
145        if (array_key_exists($rbytes, $duplicate_cache)) {
146            list($duplicate, $nbytes) = $duplicate_cache[$rbytes];
147        } else {
148            if ($rbytes[0] == "\x00") {
149                $nbytes = Auth_OpenID::bytes($rbytes) - 1;
150            } else {
151                $nbytes = Auth_OpenID::bytes($rbytes);
152            }
153
154            $mxrand = $this->pow(256, $nbytes);
155
156            // If we get a number less than this, then it is in the
157            // duplicated range.
158            $duplicate = $this->mod($mxrand, $stop);
159
160            if (count($duplicate_cache) > 10) {
161                $duplicate_cache = [];
162            }
163
164            $duplicate_cache[$rbytes] = [$duplicate, $nbytes];
165        }
166
167        do {
168            $bytes = "\x00" . Auth_OpenID_CryptUtil::getBytes($nbytes);
169            $n = $this->binaryToLong($bytes);
170            // Keep looping if this value is in the low duplicated range
171        } while ($this->cmp($n, $duplicate) < 0);
172
173        return $this->mod($n, $stop);
174    }
175
176    /**
177     * @param int $number
178     * @param int $base
179     * @return int
180     */
181    abstract protected function init($number, $base = 10);
182
183    /**
184     * @param int $x
185     * @param int $y
186     * @return int
187     */
188    abstract public function cmp($x, $y);
189
190    /**
191     * @param int $x
192     * @param int $y
193     * @return int
194     */
195    abstract protected function add($x, $y);
196
197    /**
198     * @param int $x
199     * @param int $y
200     * @return int
201     */
202    abstract protected function mul($x, $y);
203
204    /**
205     * @param int $x
206     * @param int $y
207     * @return int
208     */
209    abstract protected function div($x, $y);
210
211    /**
212     * @param int $base
213     * @param int $modulus
214     * @return int
215     */
216    abstract protected function mod($base, $modulus);
217
218    /**
219     * @param int $base
220     * @param int $exponent
221     * @return int
222     */
223    abstract protected function pow($base, $exponent);
224}
225
226/**
227 * Exposes BCmath math library functionality.
228 *
229 * {@link Auth_OpenID_BcMathWrapper} wraps the functionality provided
230 * by the BCMath extension.
231 *
232 * @access private
233 * @package OpenID
234 */
235class Auth_OpenID_BcMathWrapper extends Auth_OpenID_MathLibrary{
236    public $type = 'bcmath';
237
238    function add($x, $y)
239    {
240        return bcadd($x, $y);
241    }
242
243    function sub($x, $y)
244    {
245        return bcsub($x, $y);
246    }
247
248    function pow($base, $exponent)
249    {
250        return bcpow($base, $exponent);
251    }
252
253    function cmp($x, $y)
254    {
255        return bccomp($x, $y);
256    }
257
258    function init($number, $base = 10)
259    {
260        return $number;
261    }
262
263    function mod($base, $modulus)
264    {
265        return bcmod($base, $modulus);
266    }
267
268    function mul($x, $y)
269    {
270        return bcmul($x, $y);
271    }
272
273    function div($x, $y)
274    {
275        return bcdiv($x, $y);
276    }
277
278    /**
279     * Same as bcpowmod when bcpowmod is missing
280     *
281     * @access private
282     * @param int $base
283     * @param int $exponent
284     * @param int $modulus
285     * @return int
286     */
287    function _powmod($base, $exponent, $modulus)
288    {
289        $square = $this->mod($base, $modulus);
290        $result = 1;
291        while($this->cmp($exponent, 0) > 0) {
292            if ($this->mod($exponent, 2)) {
293                $result = $this->mod($this->mul($result, $square), $modulus);
294            }
295            $square = $this->mod($this->mul($square, $square), $modulus);
296            $exponent = $this->div($exponent, 2);
297        }
298        return $result;
299    }
300
301    function powmod($base, $exponent, $modulus)
302    {
303        if (function_exists('bcpowmod')) {
304            return bcpowmod($base, $exponent, $modulus);
305        } else {
306            return $this->_powmod($base, $exponent, $modulus);
307        }
308    }
309
310    function toString($num)
311    {
312        return $num;
313    }
314}
315
316/**
317 * Exposes GMP math library functionality.
318 *
319 * {@link Auth_OpenID_GmpMathWrapper} wraps the functionality provided
320 * by the GMP extension.
321 *
322 * @access private
323 * @package OpenID
324 */
325class Auth_OpenID_GmpMathWrapper extends Auth_OpenID_MathLibrary{
326    public $type = 'gmp';
327
328    function add($x, $y)
329    {
330        return gmp_add($x, $y);
331    }
332
333    function sub($x, $y)
334    {
335        return gmp_sub($x, $y);
336    }
337
338    function pow($base, $exponent)
339    {
340        return gmp_pow($base, $exponent);
341    }
342
343    function cmp($x, $y)
344    {
345        return gmp_cmp($x, $y);
346    }
347
348    function init($number, $base = 10)
349    {
350        return gmp_init($number, $base);
351    }
352
353    function mod($base, $modulus)
354    {
355        return gmp_mod($base, $modulus);
356    }
357
358    function mul($x, $y)
359    {
360        return gmp_mul($x, $y);
361    }
362
363    function div($x, $y)
364    {
365        return gmp_div_q($x, $y);
366    }
367
368    function powmod($base, $exponent, $modulus)
369    {
370        return gmp_powm($base, $exponent, $modulus);
371    }
372
373    function toString($num)
374    {
375        return gmp_strval($num);
376    }
377}
378
379/**
380 * Define the supported extensions.  An extension array has keys
381 * 'modules', 'extension', and 'class'.  'modules' is an array of PHP
382 * module names which the loading code will attempt to load.  These
383 * values will be suffixed with a library file extension (e.g. ".so").
384 * 'extension' is the name of a PHP extension which will be tested
385 * before 'modules' are loaded.  'class' is the string name of a
386 * {@link Auth_OpenID_MathWrapper} subclass which should be
387 * instantiated if a given extension is present.
388 *
389 * You can define new math library implementations and add them to
390 * this array.
391 */
392function Auth_OpenID_math_extensions()
393{
394    $result = [];
395
396    if (!defined('Auth_OpenID_BUGGY_GMP')) {
397        $result[] = [
398            'modules' => ['gmp', 'php_gmp'],
399            'extension' => 'gmp',
400            'class' => 'Auth_OpenID_GmpMathWrapper',
401        ];
402    }
403
404    $result[] = [
405        'modules' => ['bcmath', 'php_bcmath'],
406        'extension' => 'bcmath',
407        'class' => 'Auth_OpenID_BcMathWrapper',
408    ];
409
410    return $result;
411}
412
413/**
414 * Detect which (if any) math library is available
415 *
416 * @param array $exts
417 * @return bool
418 */
419function Auth_OpenID_detectMathLibrary($exts)
420{
421    foreach ($exts as $extension) {
422        if (extension_loaded($extension['extension'])) {
423            return $extension;
424        }
425    }
426
427    return false;
428}
429
430/**
431 * {@link Auth_OpenID_getMathLib} checks for the presence of long
432 * number extension modules and returns an instance of
433 * {@link Auth_OpenID_MathWrapper} which exposes the module's
434 * functionality.
435 *
436 * Checks for the existence of an extension module described by the
437 * result of {@link Auth_OpenID_math_extensions()} and returns an
438 * instance of a wrapper for that extension module.  If no extension
439 * module is found, an instance of {@link Auth_OpenID_MathWrapper} is
440 * returned, which wraps the native PHP integer implementation.  The
441 * proper calling convention for this method is $lib =
442 * Auth_OpenID_getMathLib().
443 *
444 * This function checks for the existence of specific long number
445 * implementations in the following order: GMP followed by BCmath.
446 *
447 * @return Auth_OpenID_MathLibrary|null
448 *
449 * @package OpenID
450 */
451function Auth_OpenID_getMathLib()
452{
453    // The instance of Auth_OpenID_MathWrapper that we choose to
454    // supply will be stored here, so that subseqent calls to this
455    // method will return a reference to the same object.
456    static $lib = null;
457
458    if (isset($lib)) {
459        return $lib;
460    }
461
462    if (Auth_OpenID_noMathSupport()) {
463        $null = null;
464        return $null;
465    }
466
467    // If this method has not been called before, look at
468    // Auth_OpenID_math_extensions and try to find an extension that
469    // works.
470    $ext = Auth_OpenID_detectMathLibrary(Auth_OpenID_math_extensions());
471    if ($ext === false) {
472        $tried = [];
473        foreach (Auth_OpenID_math_extensions() as $extinfo) {
474            $tried[] = $extinfo['extension'];
475        }
476
477        Auth_OpenID_setNoMathSupport();
478
479        return null;
480    }
481
482    // Instantiate a new wrapper
483    $class = $ext['class'];
484    $lib = new $class();
485
486    return $lib;
487}
488
489function Auth_OpenID_setNoMathSupport()
490{
491    if (!defined('Auth_OpenID_NO_MATH_SUPPORT')) {
492        define('Auth_OpenID_NO_MATH_SUPPORT', true);
493    }
494}
495
496function Auth_OpenID_noMathSupport()
497{
498    return defined('Auth_OpenID_NO_MATH_SUPPORT');
499}
500
501
502