Hi all,
I currently trying to get RSA encryption working in PHP and have
came up against a few issues that i hope somebody on here will be able to
help me with.
Basicly i have it mostly working and am able to generate keys OK
and i can also encrypt/decrypt data that will fit into one message 'block'
(their is currently no code to split a message up into blocks for
encryption). The problem i have it that sometimes the encryption dosent
seem to work correctly. I think that it is do to with me converting data
back and forth between different bases and am 'losing' information
somewhere along the line.
Well if anybody on this list knows a bit about encryption or if
you just want to help i would be very great full if you could look at the
attached code and comment on where my problem might be coming from.
I am making use of the gpm library so you will need that
installed before you are able to run my code.
Also please cc me directly on a any responses as they will get to
me quicker then by just emailing the list alone.
Regards,
William.
--
William Bailey.
http://wb.pro-net.co.uk
<?php
/*
* RSA Encryotion in PHP v0.1 :)
* By William Bailey.
* [EMAIL PROTECTED]
*
* This code is still in its infancy so it will probably not work
* correctly. If you make any bug fixes/improvements or just have
* any random comments then please send them my way.
*
*/
set_time_limit(300);
mt_srand((double)microtime()*10000);
function generate_prime ($bits) {
$number=gmp_init('0');
for($i=$bits; $i>=0; $i--){
$rand=mt_rand()%2;
gmp_setbit($number, $i, $rand);
}
while(gmp_prob_prime($number)<1){
$number=gmp_add($number, 1);
}
if(strlen(gmp_strval($number, 2))!=$bits){
$number=generate_prime($bits);
}else{
//printf('<p>returning %s (%sbit)<br>', gmp_strval($number),
strlen(gmp_strval($number, 2)));
return (string)gmp_strval($number);
}
}
function gen_RSA_keys ($bits=512, $e=17) {
/*
* $bits us the length desired for $n
* ($p and $q will be half as long)
* ($e, $n) is the public key
* ($d, $n) id the provate key
*
* It seems that sometimes php forgets the resource id
* for p and q therefore i have added the while(empty())
* condition to this script so that if php forgets the
* resource id it will just loop and try agian.
*
* This might be because im running the cvs version of
* php. :)
*
* Hopefull this will be resolved soon and should make
* this code fastar as it will not have to generate
* waisted prime numbers.
*/
$e=gmp_init((string)$e);
$p=Null;
while(empty($p)){
do {
$p=gmp_init((string)generate_prime($bits/2));
$t=gmp_sub($p, 1);
} while (gmp_gcd($t, $e)==1);
}
//printf('p is "%s" and has a value if %s <br>', $p, gmp_strval($p));
//flush();
$q=Null;
while(empty($q)){
do {
$q=gmp_init((string)generate_prime($bits/2));
$t=gmp_sub($q, 1);
} while (gmp_gcd($t, $e)==1);
}
//printf('q is "%s" and has a value if %s <br>', $q, gmp_strval($q));
//flush();
$n=gmp_mul($p, $q);
//printf('n is %s<br>', gmp_strval($n));
$t=gmp_add(gmp_sub(gmp_sub($n, $p), $q), 1);
//printf('t is %s<br>', gmp_strval($t));
//printf('e is %s<br>', gmp_strval($e));
$d=mod_inverse((string)gmp_strval($e), (string)gmp_strval($t));
//printf('d is %s<br>', gmp_strval($d));
if(gmp_strval($d)=='1'){
/*
* We dont want d to be 1 so if it is then we
* generate another RSA key.
*/
return gen_RSA_keys ($bits, gmp_strval($e));
}else{
return(array((string)gmp_strval($n), (string)gmp_strval($e),
(string)gmp_strval($d)));
}
}
function gen_RSA_keys2 ($bits=512) {
/*
* $bits us the length desired for $n
* ($p and $q will be half as long)
* ($e, $n) is the public key
* ($d, $n) id the provate key
*
*/
$p=Null;
while(empty($p)){
$p=gmp_init((string)generate_prime($bits/2));
}
$q=Null;
while(empty($q)){
$q=gmp_init((string)generate_prime($bits/2));
}
$n=gmp_mul($p, $q);
$t=gmp_add(gmp_sub(gmp_sub($n, $p), $q), 1);
$e=find_e($t, $q, $q);
$d=mod_inverse((string)gmp_strval($e), (string)gmp_strval($t));
if(gmp_strval($d)=='1'){
/*
* We dont want d to be 1 so if it is then we
* generate another RSA key.
*/
return gen_RSA_keys2 ($bits, gmp_strval($e));
}else{
return(array((string)gmp_strval($n), (string)gmp_strval($e),
(string)gmp_strval($d)));
}
}
function find_e ($t, $p, $q) {
$great=gmp_init(0);
$e=gmp_init(2);
while (gmp_strval($great)!='1') {
$e=gmp_add($e, 1);
$great=gmp_gcd($e,$t);
$t = gmp_mul(gmp_sub($p, 1), gmp_sub($q, 1));
}
return $e;
}
function mod_inverse ($e, $t) {
$e=gmp_init((string)$e);
$t=gmp_init((string)$t);
$u1 = gmp_init(1);
$u2 = gmp_init(0);
$u3 = $t;
$v1 = gmp_init(0);
$v2 = gmp_init(1);
$v3 = $e;
while(gmp_strval($v3)!='0'){
$q=gmp_div($u3,$v3);
$t1=gmp_sub($u1,gmp_mul($q, $v1));
$t2=gmp_sub($u2,gmp_mul($q, $v2));
$t3=gmp_sub($u3,gmp_mul($q, $v3));
$u1=$v1;
$u2=$v2;
$u3=$v3;
$v1=$t1;
$v2=$t2;
$v3=$t3;
}
$uu=$u1;
$vv=$u2;
if(gmp_intval($vv)<0){
return (string)gmp_strval(gmp_add($vv, $t));
}else{
return (string)gmp_strval($vv);
}
}
function powMod ($n, $ed, $m) {
$m=gmp_init((string)$m);
$ed=gmp_init((string)$ed);
$n=gmp_init((string)$n);
if (gmp_cmp($n, 0)==0 || gmp_cmp($ed, 0)<0) {
return 0;
}
$res=1;
$pow=$m;
$ed1=$ed;
while(gmp_strval($ed1)!='0'){
$d=gmp_mod($ed1, 2);
$ed1=gmp_div($ed1, 2);
if(gmp_strval($d)=='1'){
$res=gmp_mod(gmp_mul($res, $pow), $n);
}
$pow=gmp_mod(gmp_mul($pow, $pow), $n);
}
if(gmp_cmp($res, 0)<0){
$res=gmp_add($res, $n);
}
return (string)gmp_strval($res);
}
function hex2bin($data) {
return pack("H*" , $data);
}
function RSA_Encrypt ($ed, $n, $message) {
/*
* This still needs some work. Its needs to be able
* to correctly split up messages into blocks and
* a bug that causes the encrypted data to not decrypt
* correctly also needs addressing. I really need to
* get some help for somebody who know exactly how
* all this encryption stuff works. :)
*/
$ed=gmp_init((string)$ed);
$n=gmp_init((string)$n);
$messageNumber=gmp_init(sprintf('0x%s', bin2hex((string)$message)));
if(gmp_cmp($messageNumber, $n)<0){
/*
* Encrypt message block.
*/
$encMessage=powMod((string)gmp_strval($n), (string)gmp_strval($ed),
(string)gmp_strval($messageNumber));
return hex2bin((string)gmp_strval($encMessage, 16));
}else{
/*
* Split message into smaller blocks.
*/
print('<p>Message too big. I currently cant split messages into blocks :(');
}
}
function RSA_Decrypt ($ed, $n, $message) {
/*
* See comments for encrypt.
*/
$ed=gmp_init((string)$ed);
$n=gmp_init((string)$n);
$messageNumber=gmp_init(sprintf('0x%s', bin2hex((string)$message)));
$message=powMod((string)gmp_strval($n), (string)gmp_strval($ed),
(string)gmp_strval($messageNumber));
return hex2bin(gmp_strval($message, 16));
}
/*
* Test Code.
*/
$size=128;
printf('Generating %dbit RSA Keys. Please wait...<br>', $size);
flush();
list($n, $e, $d)=gen_RSA_keys2($size);
printf('
<p><b>RSA Key:</b>
<p>
<b>Public: </b>
<pre>
(
e: %s
n: %s
)
</pre>
<p>
<b>Private: </b>
<pre>
(
d: %s
n: %s
)
</pre>
', $e, $n, $d, $n);
print('<p>Testing:');
$enc=RSA_Encrypt((string)$e, (string)$n, 'test 1');
print '<p>Enc message 1: ' .$enc;
print '<p>Orig message 1: ' .RSA_Decrypt((string)$d, (string)$n, (string)$enc);
$enc=RSA_Encrypt((string)$e, (string)$n, 'another test #2');
print '<p>Enc message 2: ' .$enc;
print '<p>Orig message 2: ' .RSA_Decrypt((string)$d, (string)$n, (string)$enc);
?>
--
PHP General Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php
