1<?php
2/**
3 * Crypt_RSA allows to do following operations:
4 *     - key pair generation
5 *     - encryption and decryption
6 *     - signing and sign validation
7 *
8 * PHP versions 4 and 5
9 *
10 * LICENSE: This source file is subject to version 3.0 of the PHP license
11 * that is available through the world-wide-web at the following URI:
12 * http://www.php.net/license/3_0.txt.  If you did not receive a copy of
13 * the PHP License and are unable to obtain it through the web, please
14 * send a note to license@php.net so we can mail you a copy immediately.
15 *
16 * @category   Encryption
17 * @package    Crypt_RSA
18 * @author     Alexander Valyalkin <valyala@gmail.com>
19 * @copyright  2006 Alexander Valyalkin
20 * @license    http://www.php.net/license/3_0.txt  PHP License 3.0
21 * @version    1.2.0b
22 * @link       http://pear.php.net/package/Crypt_RSA
23 */
24
25/**
26 * Crypt_RSA_Math_BCMath class.
27 *
28 * Provides set of math functions, which are used by Crypt_RSA package
29 * This class is a wrapper for PHP BCMath extension.
30 * See http://php.net/manual/en/ref.bc.php for details.
31 *
32 * @category   Encryption
33 * @package    Crypt_RSA
34 * @author     Alexander Valyalkin <valyala@gmail.com>
35 * @copyright  2005, 2006 Alexander Valyalkin
36 * @license    http://www.php.net/license/3_0.txt  PHP License 3.0
37 * @link       http://pear.php.net/package/Crypt_RSA
38 * @version    @package_version@
39 * @access     public
40 */
41class Crypt_RSA_Math_BCMath
42{
43    /**
44     * error description
45     *
46     * @var string
47     * @access public
48     */
49    var $errstr = '';
50
51    /**
52     * Performs Miller-Rabin primality test for number $num
53     * with base $base. Returns true, if $num is strong pseudoprime
54     * by base $base. Else returns false.
55     *
56     * @param string $num
57     * @param string $base
58     * @return bool
59     * @access private
60     */
61    function _millerTest($num, $base)
62    {
63        if (!bccomp($num, '1')) {
64            // 1 is not prime ;)
65            return false;
66        }
67        $tmp = bcsub($num, '1');
68
69        $zero_bits = 0;
70        while (!bccomp(bcmod($tmp, '2'), '0')) {
71            $zero_bits++;
72            $tmp = bcdiv($tmp, '2');
73        }
74
75        $tmp = $this->powmod($base, $tmp, $num);
76        if (!bccomp($tmp, '1')) {
77            // $num is probably prime
78            return true;
79        }
80
81        while ($zero_bits--) {
82            if (!bccomp(bcadd($tmp, '1'), $num)) {
83                // $num is probably prime
84                return true;
85            }
86            $tmp = $this->powmod($tmp, '2', $num);
87        }
88        // $num is composite
89        return false;
90    }
91
92    /**
93     * Crypt_RSA_Math_BCMath constructor.
94     * Checks an existance of PHP BCMath extension.
95     * On failure saves error description in $this->errstr
96     *
97     * @access public
98     */
99    function Crypt_RSA_Math_BCMath()
100    {
101        if (!extension_loaded('bcmath')) {
102            if (!@dl('bcmath.' . PHP_SHLIB_SUFFIX) && !@dl('php_bcmath.' . PHP_SHLIB_SUFFIX)) {
103                // cannot load BCMath extension. Set error string
104                $this->errstr = 'Crypt_RSA package requires the BCMath extension. See http://php.net/manual/en/ref.bc.php for details';
105                return;
106            }
107        }
108    }
109
110    /**
111     * Transforms binary representation of large integer into its native form.
112     *
113     * Example of transformation:
114     *    $str = "\x12\x34\x56\x78\x90";
115     *    $num = 0x9078563412;
116     *
117     * @param string $str
118     * @return string
119     * @access public
120     */
121    function bin2int($str)
122    {
123        $result = '0';
124        $n = strlen($str);
125        do {
126            $result = bcadd(bcmul($result, '256'), ord($str{--$n}));
127        } while ($n > 0);
128        return $result;
129    }
130
131    /**
132     * Transforms large integer into binary representation.
133     *
134     * Example of transformation:
135     *    $num = 0x9078563412;
136     *    $str = "\x12\x34\x56\x78\x90";
137     *
138     * @param string $num
139     * @return string
140     * @access public
141     */
142    function int2bin($num)
143    {
144        $result = '';
145        do {
146            $result .= chr(bcmod($num, '256'));
147            $num = bcdiv($num, '256');
148        } while (bccomp($num, '0'));
149        return $result;
150    }
151
152    /**
153     * Calculates pow($num, $pow) (mod $mod)
154     *
155     * @param string $num
156     * @param string $pow
157     * @param string $mod
158     * @return string
159     * @access public
160     */
161    function powmod($num, $pow, $mod)
162    {
163        if (function_exists('bcpowmod')) {
164            // bcpowmod is only available under PHP5
165            return bcpowmod($num, $pow, $mod);
166        }
167
168        // emulate bcpowmod
169        $result = '1';
170        do {
171            if (!bccomp(bcmod($pow, '2'), '1')) {
172                $result = bcmod(bcmul($result, $num), $mod);
173            }
174            $num = bcmod(bcpow($num, '2'), $mod);
175            $pow = bcdiv($pow, '2');
176        } while (bccomp($pow, '0'));
177        return $result;
178    }
179
180    /**
181     * Calculates $num1 * $num2
182     *
183     * @param string $num1
184     * @param string $num2
185     * @return string
186     * @access public
187     */
188    function mul($num1, $num2)
189    {
190        return bcmul($num1, $num2);
191    }
192
193    /**
194     * Calculates $num1 % $num2
195     *
196     * @param string $num1
197     * @param string $num2
198     * @return string
199     * @access public
200     */
201    function mod($num1, $num2)
202    {
203        return bcmod($num1, $num2);
204    }
205
206    /**
207     * Compares abs($num1) to abs($num2).
208     * Returns:
209     *   -1, if abs($num1) < abs($num2)
210     *   0, if abs($num1) == abs($num2)
211     *   1, if abs($num1) > abs($num2)
212     *
213     * @param string $num1
214     * @param string $num2
215     * @return int
216     * @access public
217     */
218    function cmpAbs($num1, $num2)
219    {
220        return bccomp($num1, $num2);
221    }
222
223    /**
224     * Tests $num on primality. Returns true, if $num is strong pseudoprime.
225     * Else returns false.
226     *
227     * @param string $num
228     * @return bool
229     * @access private
230     */
231    function isPrime($num)
232    {
233        static $primes = null;
234        static $primes_cnt = 0;
235        if (is_null($primes)) {
236            // generate all primes up to 10000
237            $primes = array();
238            for ($i = 0; $i < 10000; $i++) {
239                $primes[] = $i;
240            }
241            $primes[0] = $primes[1] = 0;
242            for ($i = 2; $i < 100; $i++) {
243                while (!$primes[$i]) {
244                    $i++;
245                }
246                $j = $i;
247                for ($j += $i; $j < 10000; $j += $i) {
248                    $primes[$j] = 0;
249                }
250            }
251            $j = 0;
252            for ($i = 0; $i < 10000; $i++) {
253                if ($primes[$i]) {
254                    $primes[$j++] = $primes[$i];
255                }
256            }
257            $primes_cnt = $j;
258        }
259
260        // try to divide number by small primes
261        for ($i = 0; $i < $primes_cnt; $i++) {
262            if (bccomp($num, $primes[$i]) <= 0) {
263                // number is prime
264                return true;
265            }
266            if (!bccomp(bcmod($num, $primes[$i]), '0')) {
267                // number divides by $primes[$i]
268                return false;
269            }
270        }
271
272        /*
273            try Miller-Rabin's probable-primality test for first
274            7 primes as bases
275        */
276        for ($i = 0; $i < 7; $i++) {
277            if (!$this->_millerTest($num, $primes[$i])) {
278                // $num is composite
279                return false;
280            }
281        }
282        // $num is strong pseudoprime
283        return true;
284    }
285
286    /**
287     * Generates prime number with length $bits_cnt
288     * using $random_generator as random generator function.
289     *
290     * @param int $bits_cnt
291     * @param string $rnd_generator
292     * @access public
293     */
294    function getPrime($bits_cnt, $random_generator)
295    {
296        $bytes_n = intval($bits_cnt / 8);
297        $bits_n = $bits_cnt % 8;
298        do {
299            $str = '';
300            for ($i = 0; $i < $bytes_n; $i++) {
301                $str .= chr(call_user_func($random_generator) & 0xff);
302            }
303            $n = call_user_func($random_generator) & 0xff;
304            $n |= 0x80;
305            $n >>= 8 - $bits_n;
306            $str .= chr($n);
307            $num = $this->bin2int($str);
308
309            // search for the next closest prime number after [$num]
310            if (!bccomp(bcmod($num, '2'), '0')) {
311                $num = bcadd($num, '1');
312            }
313            while (!$this->isPrime($num)) {
314                $num = bcadd($num, '2');
315            }
316        } while ($this->bitLen($num) != $bits_cnt);
317        return $num;
318    }
319
320    /**
321     * Calculates $num - 1
322     *
323     * @param string $num
324     * @return string
325     * @access public
326     */
327    function dec($num)
328    {
329        return bcsub($num, '1');
330    }
331
332    /**
333     * Returns true, if $num is equal to one. Else returns false
334     *
335     * @param string $num
336     * @return bool
337     * @access public
338     */
339    function isOne($num)
340    {
341        return !bccomp($num, '1');
342    }
343
344    /**
345     * Finds greatest common divider (GCD) of $num1 and $num2
346     *
347     * @param string $num1
348     * @param string $num2
349     * @return string
350     * @access public
351     */
352    function GCD($num1, $num2)
353    {
354        do {
355            $tmp = bcmod($num1, $num2);
356            $num1 = $num2;
357            $num2 = $tmp;
358        } while (bccomp($num2, '0'));
359        return $num1;
360    }
361
362    /**
363     * Finds inverse number $inv for $num by modulus $mod, such as:
364     *     $inv * $num = 1 (mod $mod)
365     *
366     * @param string $num
367     * @param string $mod
368     * @return string
369     * @access public
370     */
371    function invmod($num, $mod)
372    {
373        $x = '1';
374        $y = '0';
375        $num1 = $mod;
376        do {
377            $tmp = bcmod($num, $num1);
378            $q = bcdiv($num, $num1);
379            $num = $num1;
380            $num1 = $tmp;
381
382            $tmp = bcsub($x, bcmul($y, $q));
383            $x = $y;
384            $y = $tmp;
385        } while (bccomp($num1, '0'));
386        if (bccomp($x, '0') < 0) {
387            $x = bcadd($x, $mod);
388        }
389        return $x;
390    }
391
392    /**
393     * Returns bit length of number $num
394     *
395     * @param string $num
396     * @return int
397     * @access public
398     */
399    function bitLen($num)
400    {
401        $tmp = $this->int2bin($num);
402        $bit_len = strlen($tmp) * 8;
403        $tmp = ord($tmp{strlen($tmp) - 1});
404        if (!$tmp) {
405            $bit_len -= 8;
406        }
407        else {
408            while (!($tmp & 0x80)) {
409                $bit_len--;
410                $tmp <<= 1;
411            }
412        }
413        return $bit_len;
414    }
415
416    /**
417     * Calculates bitwise or of $num1 and $num2,
418     * starting from bit $start_pos for number $num1
419     *
420     * @param string $num1
421     * @param string $num2
422     * @param int $start_pos
423     * @return string
424     * @access public
425     */
426    function bitOr($num1, $num2, $start_pos)
427    {
428        $start_byte = intval($start_pos / 8);
429        $start_bit = $start_pos % 8;
430        $tmp1 = $this->int2bin($num1);
431
432        $num2 = bcmul($num2, 1 << $start_bit);
433        $tmp2 = $this->int2bin($num2);
434        if ($start_byte < strlen($tmp1)) {
435            $tmp2 |= substr($tmp1, $start_byte);
436            $tmp1 = substr($tmp1, 0, $start_byte) . $tmp2;
437        }
438        else {
439            $tmp1 = str_pad($tmp1, $start_byte, "\0") . $tmp2;
440        }
441        return $this->bin2int($tmp1);
442    }
443
444    /**
445     * Returns part of number $num, starting at bit
446     * position $start with length $length
447     *
448     * @param string $num
449     * @param int start
450     * @param int length
451     * @return string
452     * @access public
453     */
454    function subint($num, $start, $length)
455    {
456        $start_byte = intval($start / 8);
457        $start_bit = $start % 8;
458        $byte_length = intval($length / 8);
459        $bit_length = $length % 8;
460        if ($bit_length) {
461            $byte_length++;
462        }
463        $num = bcdiv($num, 1 << $start_bit);
464        $tmp = substr($this->int2bin($num), $start_byte, $byte_length);
465        $tmp = str_pad($tmp, $byte_length, "\0");
466        $tmp = substr_replace($tmp, $tmp{$byte_length - 1} & chr(0xff >> (8 - $bit_length)), $byte_length - 1, 1);
467        return $this->bin2int($tmp);
468    }
469
470    /**
471     * Returns name of current wrapper
472     *
473     * @return string name of current wrapper
474     * @access public
475     */
476    function getWrapperName()
477    {
478        return 'BCMath';
479    }
480}
481
482?>