[RESOLVED] RSA implementation in pure PHP

I spent a lot of time researching this and couldn’t find an existing implementation of the RSA algorithm in pure PHP (besides with PEAR, which requires you to have access to PEAR, making the ending application much less portable). So I ended up creating one myself. Here are the capabilities and limitations of this implementation:

[B]Capabilities:[/B]

[LIST]

[B]Limitations:[/B]

[LIST]

This code is released under the GPL license… google it for more information. There is no warranty, express or implied, and all that mumbo jumbo. Just use it however you want and nobody’s gonna get all up in your business about it.

[code=php]<?php
class RSA_Handler {
function encrypt($text, $key) {
//The complete encryption function.
//Accepts plain text and outputs a numeric code (divided into blocks by spaces)
list($p, $r) = unserialize(base64_decode($key));
$in = $this->blockify($text, 100); //Cut it into blocks of 100 characters (seems to fit well without getting too big)
$out = ”;
foreach($in as $block) {
if($block)
$out .= $this->crypt_num($this->txt2num($block), $p, $r) . ” “;
}
return $out;
}
function decrypt($code, $key) {
//The complete decryption function
//Accepts data in the format which was created by the encrypt function
//(numbers divided into blocks in, text out)
list($q, $r) = unserialize(base64_decode($key));
$in = explode(” “, $code);
$out = ”;
foreach($in as $block) {
if($block)
$out .= $this->num2txt($this->crypt_num($block, $q, $r));
}
return $out;
}
function generate_keypair($digits = 310) {
set_time_limit(60);
$km = new RSA_keymaker();
$keys = $km->make_keys($digits);
//The keys are separated into arrays and then serialized and encoded in base64
//This makes it easier to store and transmit them
//
//The private key should probably be encrypted with a user-supplied key (in AES or DES3)…
//This way it can be stored on the server, yet still be secure. The user-supplied key should not be stored.
$pub = base64_encode(serialize(array($keys[0], $keys[2])));
$priv = base64_encode(serialize(array($keys[1], $keys[2])));
return array($pub, $priv);
}
function crypt_num($num, $key, $mod) {
//This is the same function whether you are encrypting or decrypting.
$out = $this->powmod($num, $key, $mod);
return $out;
}
function blockify($in, $b_length) {
//Add spaces to the end of text so it fits evenly into the block size
$x = bcmod(strlen($in), $b_length);
while($x > 0) {
$in = str_pad($in, 1, ” “);
$x–;
}
return str_split($in, $b_length);
}
function txt2num($str) {
//Turns regular text into a number that can be manipulated by the RSA algorithm
$result = ‘0’;
$n = strlen($str);
do {
$result = bcadd(bcmul($result, ‘256’), ord($str{–$n}));
} while ($n > 0);
return $result;
}
function num2txt($num) {
//Turns the numeric representation of text (as output by txt2num) back into text
$result = ”;
do {
$result .= chr(bcmod($num, ‘256’));
$num = bcdiv($num, ‘256’);
} while (bccomp($num, ‘0’));
return $result;
}
function powmod($num, $pow, $mod) {
if (function_exists(‘bcpowmod’)) {
// bcpowmod is only available under PHP5
return bcpowmod($num, $pow, $mod);
}
// emulate bcpowmod
$result = ‘1’;
do {
if (!bccomp(bcmod($pow, ‘2’), ‘1’)) {
$result = bcmod(bcmul($result, $num), $mod);
}
$num = bcmod(bcpow($num, ‘2’), $mod);
$pow = bcdiv($pow, ‘2’);
} while (bccomp($pow, ‘0’));
return $result;
}
}
class RSA_keymaker {
static $primes = null;
static $primes_cnt = 0;
static $prefix;
function __construct() {
if(is_null($this->primes)) {
//Make $this->primes an array of all primes under 10,000
//We will use this list to rule out the “easy” composite (non-prime) numbers
for ($i = 0; $i < 10000; $i++) {
$numbers[] = $i;
}
$numbers[0] = $numbers[1] = 0;
foreach ($numbers as $i => $num) {
if(!$num) {
continue;
}
$j = $i;
for ($j += $i; $j < 10000; $j += $i) {
$numbers[$j] = 0;
}
}
$j = 0;
foreach($numbers as $num) {
if ($num) {
$this->primes[$j++] = $num;
}
}
$this->primes_cnt = $j;
}
$this->prefix = rand(10000, 99999);
}
function make_keys($digits = 310, $u = false, $v = false) {
//Select 2 random prime numbers each at half the digits of our total
//We use a prefix so the first 5 numbers are the same, so that the primes are similar in value
if(!$u)
$u = $this->make_prime(intval($digits/2), $this->prefix);
if(!$v)
$v = $this->make_prime(intval($digits/2), $this->prefix);
//Make sure they are at least 1 quadrillion numbers apart
while(substr($prime1, -16, 2) < (substr($prime2, -16, 2) + 2) &amp;&amp; substr($prime1, -16, 2) > (substr($prime2, -16, 2) – 2) ) {
$prime2 = $pm->make_prime(intval($digits/2));
}
$r = bcmul($u, $v);
$phir = bcmul(bcsub($u, 1), bcsub($v, 1));
//Pick a value for p (The Public key). We will make it smaller than half so the private key will be longer
$p = $this->make_prime(intval($digits/3), false);
//Find the inverse of p using the Extended Euclidian Algorithm
$q = $this->euclid($p, $phir);
return array($p, $q, $r);
}
function make_prime($digits, $prefix = false) {
$ent = $this->entropyarray();
$e_cnt = count($ent);
//If a prefix is defined, use it as the first (prefix length) numbers
//This is to keep the two numbers closer together in value
$pre_len = $prefix ? strlen($prefix) : 0;
$num = $prefix;
for($i = 0; $i < ($digits – $pre_len); $i++) {
//Create a long integer where the first number is 1-9 and the last is 1,3,7 or 9
if($i == ($digits – $pre_len – 1)) {
while($spec != 1 &amp;&amp; $spec != 3 &amp;&amp; $spec != 7 &amp; $spec != 9) {
$spec = rand(1,9);
}
$num .= $spec;
$spec = 0;
} elseif($i == 0)
$num .= rand(1,9);
else

$num .= bcmod(rand(0,9) + $ent[bcmod($i, $e_cnt)], 10);
}
while(!$this->is_prime($num)) {
//If the number is not prime, add 2 or 4 (since it is currently an odd number)
//This will keep the number odd and skip 5 to speed up the primality testing
if(substr($num, -1, 1) == 3)
$num = bcadd($num, 4);
else

$num = bcadd($num, 2);
$tries++;
}
return $num;
}
function entropyarray() {
//create a long number based on as much entropy as possible
$a = base_convert(substr(md5(microtime()), 0, 10), 16, 10);
$b = mt_rand();
$c = base_convert(substr(sha1(@exec(‘uptime’)), 0, 10), 16, 10);
//make sure it is only numbers
$all = str_split(preg_replace(“[^0-9]”, “”, bcadd(bcmul($a, $b), $c)));
shuffle($all);
return $all;
}
function is_prime($num) {
if(bccomp($num, 1) < 1)
return >false;
//Clear the easy stuff (divide by all primes under 10,000)
for($i=0; $i < $this->primes_cnt; $i++) {
if(bccomp($num, $this->primes[$i]) == 0)
return >true;
if(!bcmod($num, $this->primes[$i]))
return >false;
}
//Try the more complex method with the first 7 primes as bases
for($i = 0; $i < 7; $i++) {
if(!$this->_millerTest($num, $this->primes[$i]))
return >false; //Number is composite
}
//Strong probability that the number is prime
return >true;
}
function _millerTest($num, $base) {
if(!bccomp($num, ‘1’)) {
// 1 is not prime 😉
return >false;
}
$tmp = bcsub($num, ‘1’);
$zero_bits = 0;
while (!bccomp(bcmod($tmp, ‘2’), ‘0’)) {
$zero_bits++;
$tmp = bcdiv($tmp, ‘2’);
}
$tmp = $this->powmod($base, $tmp, $num);
if (!bccomp($tmp, ‘1’)) {
// $num is probably prime
return >true;
}
while ($zero_bits–) {
if (!bccomp(bcadd($tmp, ‘1’), $num)) {
// $num is probably prime
return >true;
}
$tmp = $this->powmod($tmp, ‘2’, $num);
}
// $num is composite
return >false;
}
function euclid($num, $mod) {
//The Extended Euclidian Algorithm
$x = ‘1’;
$y = ‘0’;
$num1 = $mod;
do {
$tmp = bcmod($num, $num1);
$q = bcdiv($num, $num1);
$num = $num1;
$num1 = $tmp;
$tmp = bcsub($x, bcmul($y, $q));
$x = $y;
$y = $tmp;
} while (bccomp($num1, ‘0’));
if (bccomp($x, ‘0’) < 0) {
$x = bcadd($x, $mod);
}
return $x;
}
function powmod($num, $pow, $mod) {
if (function_exists(‘bcpowmod’)) {
// bcpowmod is only available under PHP5
return bcpowmod($num, $pow, $mod);
}
// emulate bcpowmod
$result = ‘1’;
do {
if (!bccomp(bcmod($pow, ‘2’), ‘1’)) {
$result = bcmod(bcmul($result, $num), $mod);
}
$num = bcmod(bcpow($num, ‘2’), $mod);
$pow = bcdiv($pow, ‘2’);
} while (bccomp($pow, ‘0’));
return $result;
}
}
?>[/code]

Also in #PHP _↴