* Rivest/Shamir/Adelman (RSA) compatible functions
* to generate keys and encode/decode plaintext messages.
* Plaintext must contain only ASCII(32) - ASCII(126) characters.
*Send questions and suggestions to Ilya Rudev <www <at> polar-lights <dot> com> (Polar Lights Labs)
*most part of code ported from different
*C++, JS and Flash
*RSA examples found in books and in the net :)
*supplied with Hacker Hunter authentication system.
*http://www.polar-lights.com/hackerhunter/
*It is distributed in the hope that it will be useful, but
*WITHOUT ANY WARRANTY; without even the implied warranty of
*MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*See the GNU General Public License for more details.
*With a great thanks to:
*Glenn Haecker <ghaecker <at> idworld <dot> net>
*Segey Semenov <sergei2002 <at> mail <dot> ru>
*Suivan <ssuuii <at> gmx <dot> net>
*/
/*Function for generating keys. Return array where
$array[0] -> modulo N
$array[1] -> public key E
$array[2] -> private key D
Public key pair is N and E
Private key pair is N and D
*/
function generate_keys ($show_debug=0){
global $primes, $maxprimes;
while (empty($e) || empty($d)) {
/*finding 2 small prime numbers $p and $q
$p and $q must be different*/
$p = $primes[mt_rand(0, $maxprimes)];
while (empty($q) || ($p==$q)) $q = $primes[mt_rand(0, $maxprimes)];
//second part of public and private pairs - N
$n = $p*$q;
//$pi (we need it to calculate D and E)
$pi = ($p - 1) * ($q - 1);
/* modulus function */
function mo ($g, $l) {
return $g - ($l * floor ($g/$l));
}
/*
* Standard method of calculating D
* D = E-1 (mod N)
* It's presumed D will be found in less then 16 iterations
*/
function extend ($Ee, $Epi) {
$u1 = 1;
$u2 = 0;
$u3 = $Epi;
$v1 = 0;
$v2 = 1;
$v3 = $Ee;
while ($v3 != 0) {
$qq = floor($u3/$v3);
$t1 = $u1 - $qq * $v1;
$t2 = $u2 - $qq * $v2;
$t3 = $u3 - $qq * $v3;
$u1 = $v1;
$u2 = $v2;
$u3 = $v3;
$v1 = $t1;
$v2 = $t2;
$v3 = $t3;
$z = 1;
}
$uu = $u1;
$vv = $u2;
if ($vv < 0) {
$inverse = $vv + $Epi;
} else {
$inverse = $vv;
}
return $inverse;
}
/* This function return Greatest Common Divisor for $e and $pi numbers */
function GCD($e, $pi) {
$y = $e;
$x = $pi;
while ($y != 0) {
$w = mo($x , $y);
$x = $y;
$y = $w;
}
return $x;
}
/*function for calculating E under conditions:
GCD(N, E) = 1 and 1<E<N
If each test E is prime, there will be much less loops in that fuction
and smaller E means less JS calculations on client side */
/*
* Calculating E under conditions:
* GCD(N, E) = 1 and 1<E<N
* If E is prime, there will be fewer loops in the function.
* Smaller E also means reduced JS calculations on client side.
*/
function tofindE($pi) {
global $primes, $maxprimes;
$great = 0;
$cc = mt_rand (0, $maxprimes);
$startcc = $cc;
while ($cc >= 0) {
$se = $primes[$cc];
$great = GCD($se, $pi);
$cc--;
if ($great == 1) break;
}
if ($great == 0) {
$cc = $startcc + 1;
while ($cc <= $maxprimes) {
$se = $primes[$cc];
$great = GCD($se, $pi);
$cc++;
if ($great == 1) break;
}
}
return $se;
}
/*
* ENCRYPT function returns
*, X = M^E (mod N)
* Please check http://www.ge.kochi-ct.ac.jp/cgi-bin-takagi/calcmodp
* and Flash5 RSA .fla by R.Vijay <rveejay0 <at> hotmail <dot> com> at
* http://www.digitalillusion.co.in/lab/rsaencyp.htm
* It is one of the simplest examples for binary RSA calculations
*
* Each letter in the message is represented as its ASCII code number - 30
* 3 letters in each block with 1 in the beginning and end.
* For example string
*, AAA
* will become
*, 13535351 (A = ASCII 65-30 = 35)
* we can build these blocks because the smalest prime available is 4507
*, 4507^2 = 20313049
* This means that
*, 1. Modulo N will always be < 19999991
*, 2. Letters > ASCII 128 must not occur in plain text message
*/
function rsa_encrypt ($m, $e, $n) {
$asci = array ();
for ($i=0; $i<strlen($m); $i+=3) {
$tmpasci="1";
for ($h=0; $h<3; $h++) {
if ($i+$h <strlen($m)) {
$tmpstr = ord (substr ($m, $i+$h, 1)) - 30;
if (strlen($tmpstr) < 2) {
$tmpstr ="0".$tmpstr;
}
} else {
break;
}
$tmpasci .=$tmpstr;
}
array_push($asci, $tmpasci."1");
}
//Each number is then encrypted using the RSA formula: block ^E mod N
for ($k=0; $k< count ($asci); $k++) {
$resultmod = powmod($asci[$k], $e, $n);
$coded .= $resultmod." ";
}
return trim($coded);
}
/*
ENCRYPT function returns
M = X^D (mod N)
*/
function rsa_decrypt ($c, $d, $n) {
//Strip the blank spaces from the ecrypted text and store it in an array
$decryptarray = split(" ", $c);
for ($u=0; $u<count ($decryptarray); $u++) {
if ($decryptarray[$u] == "") {
array_splice($decryptarray, $u, 1);
}
}
//Each number is then decrypted using the RSA formula: block ^D mod N
for ($u=0; $u< count($decryptarray); $u++) {
$resultmod = powmod($decryptarray[$u], $d, $n);
//remove leading and trailing '1' digits
$deencrypt.= substr ($resultmod, 1, strlen($resultmod)-2);
}
//Each ASCII code number + 30 in the message is represented as its letter
for ($u=0; $u<strlen($deencrypt); $u+=2) {
$resultd .= chr(substr ($deencrypt, $u, 2) + 30);
}
return $resultd;
}
Load balance : Server 03
