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?>