RSA algorithm explanation and implementation in java

RSA Algorithm

RSA stangs for Rivest Shamir Adleman  named after Ron Rivest, Adi Shamir and Len Adleman who invented it in 1977. RSA is an asymmetric cryptographic algorithm used by modern computers to encrypt and decrypt messages. Asymmetric means that there are two different keys: one is public key and the other is private key. This is also called public key cryptography, because one of them can be given to everyone. The other key must be kept private.

The RSA cryptosystem is the most widely used public key cryptography algorithm in the world. It can be used to encrypt a message without the need to exchange a secret key separately. For example, Party A can send an encrypted message to party B without any prior exchange of secret keys. A just uses B's public key to encrypt the message and B decrypts it using the private key, which only he knows. RSA can also be used to sign a message, so A can sign a message using their private key and B can verify it using A's public key.

From data security perspective, our encrypted data is secured till our private key is secured.

A practical key generation approach:

1. Generate two large random primes, p and q, of approximately equal size.

2. Compute n = pq and (phi) φ = (p-1) (q-1).

3. Choose an integer e, 1 < e < phi, such that gcd(e, phi) = 1(e should be co-prime with phi).

4. Compute the secret exponent d, 1 < d < phi, such that

                                   d * e mod phi=1

This is the most crucial step of the process. Basically, we can solve this in two ways:

By reorganizing above equation,

                                   d = mod inverse (e, phi)

By using Extended Euclidean Algorithm.

Keep all the values d, p, q and phi secret except e which is public key.

Finally,

                                  Public key = (n, e)

                                  Private key = (n, d)

For encryption, C =P^e   mod n

For decryption, D =C^d  mod  n

  where P is the text to be encrypted

  C is the encrypted text which we can utilize for our purpose.

  D is the decrypted text.

e.g.

A very simple example of RSA encryption is

1. Select primes p=11, q=3.

2.  n = pq = 11*3 = 33

     phi = (p-1)(q-1)= 10*2 = 20

3. Choose  e=3

   Check gcd (e, phi) = gcd(3, 20) = 1 (i.e. 3 and 20 have no common   factors )

4. Compute d such that d * e mod phi=1.

    In our case, d is 7.

5. Public key = (n, e) = (33, 3)

    Private key = (n, d) = (33, 7).

Now say we want to encrypt the message P = 7,

C = P^e mod n = 7³ mod 33 = 343 mod 33 = 13.

Hence the ciphertext C = 13.

To check decryption we compute

D = C^d mod n = 13⁷ mod 33 = 7.

A simple implementation of RSA Algorithm in Java is given below:

import java.io.*;

import java.util.Random;

import java.math.BigInteger;

public class myRSA1

{

int  primegen()         //generates prime numbers

{

int  i,j,num,size=1000,index=0,c,r,r1;

Random ran = new Random();

int arr []=new int[size];

r1=ran.nextInt(2000);

for(i=100;i<r1;i++)

{

num=i;

c=0;

for(j=2;j<=num/2;j++)

{

 if(num%j==0)

 c++;

}

if(c==0)

arr[index++]=num;

}

r= ran.nextInt(index);   //returns a random prime number

return arr[r];

}

long gcd(long a, long b)  //calculates greatest common divisor

{

    long t;

    while(b != 0)

{

     t = a;

     a = b;

     b = t%b;

}

     return a;

}

long cale(long b)   //calculates and returns e

 {

long a,g;

Random ran = new Random();

do

{

a= ran.nextInt((int)b/2);

g= gcd(a,b);

}

while(g!=1);

return a;

}

long solve(long phi, long e) //extended Eucledian Algorithm to find d

{

    long x1= 1, y1= 0, x2 = 0, y2 = 1, d1=phi,d2=e,k;

     long lastx,lasty,lastd;

     do

{

      k = d1/ d2;

      lastx=x1-(x2*k);

      lasty=y1-(y2*k);

      lastd=d1-(d2*k);

       

      x1=x2;

     x2=lastx;

     y1=y2;

     y2=lasty;

     d1=d2;

     d2=lastd;

     }

   while (lastd!= 1);

   return lasty;

 }

BigInteger[] encrypt(String str,long e,long n)  //Encrypts String

{

int i,l,ch;

char c;

BigInteger charpow,t1,t2,t3;

l=str.length();

BigInteger arr[]=new BigInteger[l];

t2=BigInteger.valueOf(e);    //converting long to BigInteger

t3=BigInteger.valueOf(n);

for(i=0;i<l;i++)

{

c=str.charAt(i);

ch=(int)c;

t1=BigInteger.valueOf(ch);  //Converting Biginteger to integer

charpow=t1.modPow(t2,t3);

arr[i]=charpow;

}

System.out.println("Encrypted string");

for(i=0;i<l;i++)

System.out.print(arr[i]);

System.out.println("");

return arr;

}

void decrypt(BigInteger arr[],long d,long n)   //Decrypts String

{

int l=arr.length,i;

char ch;

BigInteger res,res1,t2,t1;

String str="";

t1=BigInteger.valueOf(d);

t2=BigInteger.valueOf(n);

for(i=0;i<l;i++)

{

res=arr[i];

res1=res.modPow(t1,t2);

ch=(char)(res1.intValue());     //Converting Biginteger to integer

str=str+ch;

}

System.out.println("Decrypted string="+str);

}

public static void main (String[] args) throws IOException

 {

long p,q,initd,d,e, n,phi;

String s;

myRSA1 rsa = new myRSA1();

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

p=rsa.primegen();

q=rsa.primegen();

n=p*q;

phi=(p-1)*(q-1);

e=rsa.cale(phi);

initd=rsa.solve(phi,e);

if(initd>phi)

d=initd%phi;

else

d=initd+phi;

System.out.println("Enter string");

s=br.readLine();

BigInteger ans[]=rsa.encrypt(s,e,n);

rsa.decrypt(ans,d,n);

}

}

Above program uses Random class and Biginteger class for prime number generation and calculation of various other values. After calculation of all values, we convert the characters of string to be encrypted to their corresponding ASCII value and then encrypt them.

The strength of RSA algorithm lies in the size of prime numbers.

For fast execution, we took very small digits, One can increase their size and encrypt the text as per their needs. Any question or query regarding program or algorithm can be asked in comment section. Suggestions or improvements are welcomed.