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 =Pe mod n
For decryption, D =Cd 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 = Pe mod n = 73 mod 33 = 343
mod 33 = 13.
Hence the ciphertext C = 13.
To check decryption we compute
D = Cd mod n = 137 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.
