RSA encryption algorithm and it's methematical background and it's application in php

          Mathematics Behind RSA Encryption Algorithm

 rsa cryptography uses properties of  humongous numbers as large power of bigger numbers we can't calculate this mathematics directly when numbers are so huge. so here we use tricky mathematics called Modular Airthmathics.

we uses Modular Airthmathic because we we don't have to work with large numbers in Modular Airthmatic.     

For example:	5 module 3 is 2
because:	5 = 1 * 3 + 2.

example: 40mod10=30mod10=0.
because:40=4*10+0.
             30=3*10+0.

Modular multiplication of many numbers-
X = 36 * 53 * 91 * 17 * 22 (mod 29) .

now 36(mod29)=7.

      53(mod29)=24.

      91(mod29)=4.

      17(mod29)=17.

      22(mod29)=22.

hence X=7*24*4*17*22(mod29).

         X=14.

Modular Powers-

compute 11⁴³ (mod 13). As we saw before we start with squaring this number: 
11² (mod 13) = 121 (mod 13) = 4 (mod 13) 
11⁴ (mod 13) = (11²)² (mod 13) = 4² (mod 13) = 16 (mod 13) = 3 (mod 13) 
11⁸ (mod 13) = (11⁴)² (mod 13) = 3² (mod 13) = 9 (mod 13) 
11¹⁶ (mod 13) = (11⁸)² (mod 13) = 9² (mod 13) = 81 (mod 13) = 3 (mod 13) 
11³² (mod 13) = (11¹⁶)² (mod 13) = 3² (mod 13) = 9 (mod 13)

hence 11⁴³ (mod 13) =11 * 4 * 9 * 9 (mod 13)=2.

     NOW HAVE A LOOK ON RSA CRYPTOGRAPHY ALGORITHM

STEP BY STEP
1.choose two random  prime numbers P and Q.

2.calculate N=PXQ.

3.select the public key E such that it is not the factor of (P-1) and (Q-1).
4.select the private key D such that the following equation is true-
DXEmod(P-1)X(Q-1)=1.
5.For Encryption calculates the encrypted message (ET) from the 
plain Text(PT) as follows:
ET=PT^E mod N .
6.For decryption  calculates the plain text (PT) from the encrypted text (ET)
as follows:
PT=ET^D mod N.

NOW Lets make a application that will work on RSA algorithm in php

h

//greatest common divisior between two numbers- 
//i will use this function in public key generating
function gcd($x,$y)
{
  
 if($x > $y)
 { 
  if($y!=0)
  {
   if($x%$y==0)
   {
    return $y;
   }
   else
   {   
    return gcd($y,$x%$y);
    
   }
  }
 }
 elseif($y > $x)
 {
   if($x!=0)
  {
   if($y%$x==0)
   {
    return $x;
   }
   else
   {   
    return gcd($x,$y%$x);
    
   }
  }
 } 
}   
//prime number checking function
//i will use this function in generating random primes
 function primes($x)
     {  
      if($x > 2){
      $z=2;
      while($x > $z)
        { 
         
         $p=$x%$z;
         if($p==0)
         {
            $v= 0;
            break;
         }
         else
         {
            $v= 1; 
            
         }
         $z++;
        }
        return $v;
              }
       elseif($x==2)
       {
        $v=1;
        return $v;
       }       
     }     
//giving first $n primes 

function prime_up_to_n($n)
      {
       $p=0; $pp=array();
       $k=2;
       while($p!=$n)
       {
        $t=primes($k);
        if($t==1)
        {
          $p++;
          array_push($pp,$k);
        }
         $k++;
       }
      $ppp=implode(',',$pp) ;
      return $ppp;
      }

//a function for random prime number generator
function random_primes()
{   
  // set the number of primes that you want to store
      $n=100;
  //we can't chooose pure randomly..coz their is infinite primes 
    
  $primes=explode(',',prime_up_to_n($n));
  //random key making by rand() function 
  $random_keys=rand(0,count($primes)-1); 
  //giving a random prime from primes array 
  return $primes[$random_keys]; 
 //but the best way to generate random primes is save all primes in a array in tabular form
}
//public key generator
function public_key($p,$q)
{
 //$p and $q should be random primes
 //array for storing coprime values
 $p_key=array();
 
   //you can store coprimes as much as you want for randomize 
 for ($i=2; $i < 104 ; $i++) 
 { 
   if (gcd(($p-1)*($q-1),$i)==1) 
  {
   array_push($p_key,$i);
  }
 }
   //making random key for accessing random element's value of array
   $r_key=rand(0,count($p_key)-1);
   //returning random value according to RSA algorithm use
   return $p_key[$r_key];
}
//private key generator
function private_key($p,$q,$public_key)
{
  // p and q are randomly generated prime numbers 
 // public_key is public key generated by public key function 
  $private_key=array();
  $s=($p-1)*($q-1);
  $i=1;
  for (; ; ) 
  { 
   //satisfying conditions given in RSA algorithm
   if (($i*$public_key)%$s==1) 
   {
     array_push($private_key,$i);
     break;
   }
    $i++;
  }
   //returning private key value
  return $private_key[0]; 
}

//fast exponential counting
function exp_count($c, $n, $d)
{
            

            if ($d % 2 == 0) $g = 1; else $g = $c;

            for ($i = 1; $i <= $d / 2; $i++)
            {
                $f = $c * $c % $n;
                $g = $f * $g % $n;
            }
            return $g;

}
//main RSA Cryptography function 
function RSA_Encrypt($data,$N,$public_key)
{  
  $enc_val=array();
  $ascii_val=str_split($data);
  for ($i=0; $i < count($ascii_val); $i++) 
  { 
    $enc_val[$i]=exp_count(ord($ascii_val[$i]),$N,$public_key);
  } 
  $acc=implode('-',$enc_val);
  
  return $acc;
}
//decryption of RSA Encryption
function RSA_decrypt($enc_data,$N,$private_key)
{
 if(preg_match("/-/", $enc_data))
 {
 $ascii_val=explode("-",$enc_data);
 $arr_val=array();
 for ($i=0; $i < count($ascii_val); $i++) 
  { 
    $arr_val[$i]=chr(exp_count($ascii_val[$i],$N,$private_key));
     
  }
  $r=implode("", $arr_val);
  return $r;
  } 
}

//testing
$data='hitesh';
echo 'actual data is='.$data.'
';
$p=random_primes(); $q=random_primes();
echo 'primes is='. $p."-".$q."
";
echo 'n is='.$N=$p*$q."
";
echo 'public key is='.$pp=public_key($p,$q)."
";
$enc=RSA_Encrypt($data,$N,$pp);
echo 'ET='.$enc."
";
$pri=private_key($p,$q,$pp);
echo 'private key is='.$pri.'
';
echo 'PT='.RSA_decrypt('1488-2737-261-2735-2399-1488',2911,1767);

RSA Encryption Application- RSA Decryption Application-