RSA is an algorithm for public-key cryptography that is based on the presumed difficulty of factoring large integers, the factoring problem. RSA stands for Ron Rivest, Adi Shamir and Leonard Adleman, who first publicly described it in 1977. Clifford Cocks, an English mathematician, had developed an equivalent system in 1973, but it was classified until 1997. A user of RSA creates and then publishes the product of two large prime numbers, along with an auxiliary value, as their public key. The prime factors must be kept secret. Anyone can use the public key to encrypt a message, but with currently published methods, if the public key is large enough, only someone with knowledge of the prime factors can feasibly decode the message.Whether breaking RSA encryption is as hard as factoring is an open question known as the RSA problem. Below is the C program to demonstrate the algorthm (using small prime numbers, not suitable for real life application)
#include<iostream.h>
#include<math.h>
#include<string.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
void
keygen(void);
void ran(void);
void man(void);
void
encrypt(void);
void
decrypt(void);
int
sqrmul(int,int,int);
int invr1(int,int);
int
invr(int,int);
int prime(int);
int gcd(int,int);
void main()
{
int chk;
do
{
printf("\n-------------------------------------------\n");
printf("\n*MAIN
MENU*");
printf("\n");
printf("\t \t \t \n *PROGRAM TO DEMONSTRATE RSA
CIPHER
SYSTEM*");
printf("\n--------------------------------------------\n");
printf("\n Press 1 to
ENCRYPT:");
printf("\n Press 2 to
DECRYPT:");
printf("\n Press 3 to GENERATE
KEY:");
printf("\n Press 4 to EXIT:");
printf("\n Please enter your
choice......");
scanf("%d",&chk);
printf("\n");
switch(chk)
{
case 1:
encrypt();
break;
case 2:
decrypt();
break;
case 3:
keygen();
break;
case 4:
break;
default:
printf("\n You have enter a
wrong choice!!!!!!!!\n");
break;
}
}
while(chk!=4);
}
void encrypt()
{
char pln[100];
int len,e,n,tm;
printf("\n Enter the plain text:");
cin.getline(pln,'\100');
printf("\n Enter the public key
(e,n):");
scanf("%d %d",&e,&n);
len=strlen(pln);
printf("\n The cipher text
is:");
for(int i=0;i<len;i++)
{
tm=pln[i];
printf("%d ",sqrmul(tm,e,n));
}
printf("\n Length of cipher text is:
%d",len);
getche();
}
void decrypt()
{
int
cip[50],e,n1,l;
printf("\n
Enter the lenth:");
scanf("%d",&l);
printf("\n
Enter d and n:");
scanf("%d
%d",&e,&n1);
printf("\n
Enter the cipher text:");
for(int
i=0;i<l;i++)
scanf("%d",&cip[i]);
printf("\n
The decoded message is: ");
for(int
j=0;j<l;j++)
{
printf("%c",sqrmul(cip[j],e,n1));
}
getche();
}
void keygen()
{
int ch;
do
{
printf("\n\n");
printf("\nKEY GENERATOR FOR
RSA");
printf("\nPress 1 for random
selection");
printf("\nPress 2 for manual
selection");
printf("\nPress 3 to return to main
menu\n\t\t");
scanf("%d",&ch);
switch(ch)
{
case 1:
ran();
break;
case 2:
man();
break;
case 3:
break;
default:
printf("\n Wrong
choice:");
}
}while(ch!=3);
}
void man(void)
{
int
u,i,ar[1000],k=0,p,q,ph,n,e;
printf("\n
Enter the upper limit:");
scanf("%d",&u);
printf("\n
You can choose any two primes from the following prime(s):\n");
for(i=2;i<=u;i++)
{
if(prime(i)==1)
{
ar[k]=i;
printf("\t%d(%d)",ar[k],k);
k++;
}
}
printf("\n");
printf("\n
Enter two numbers between 0 and %d
:",k-1);
scanf("%d
%d",&p,&q);
printf("\n");
printf("\n
Your choice of p and q is:%d %d",ar[p],ar[q]);
ph=(ar[p]-1)*(ar[q]-1);
n=(ar[p])*(ar[q]);
printf("\n");
printf("\n
phi(%d) is: %d",ar[p]*ar[q],ph);
int z=0;
printf("\n");
printf("\n
You can choose any one number for 'e':\n");
for(i=2;i<ph;i++)
{
if(gcd(i,ph)==1)
{
ar[z]=i;
printf("\t%d(%d)",ar[z],z);
z++;
}
}
printf("\n");
printf("\n
Enter one number between 0 and %d
:",z-1);
scanf("%d",&e);
printf("\n");
printf("\n
Your choice of e is:%d",ar[e]);
printf("\n");
printf("\n
You have chosen the public key:(%d,%d)",ar[e],n);
printf("\n");
printf("\n
Private key is: (%d,%d)",invr(ar[e],ph),n);
printf("\n
Press any key............");
getche();
}
void ran()
{
int
u,i,ar[400],k=0,p,q,ph,n,e;
printf("\n
Enter the upper limit:");
scanf("%d",&u);
printf("\n p
and q will be seleted automatically from the list below:\n");
printf("\n");
for(i=2;i<=u;i++)
{
if(prime(i)==1)
{
ar[k]=i;
printf("\t%d",ar[k]);
k++;
}
}
printf("\n");
p=rand()%k;
do
{
q=rand()%k;
}while(q==p);
printf("\n");
printf("\n
Selected value p and q is:%d %d",ar[p],ar[q]);
printf("\n");
ph=((ar[p]-1)*(ar[q]-1));
n=(ar[p])*(ar[q]);
printf("\n");
printf("\n
phi(%d) is: %d",n,ph);
printf("\n");
int z=0;
printf("\n");
printf("\n e
will be seleted automatically from the list below :\n");
printf("\n");
for(i=2;i<ph;i++)
{
if(gcd(i,ph)==1)
{
ar[z]=i;
printf("\t%d",ar[z]);
z++;
}
}
printf("\n");
e=rand()%z;
printf("\n");
printf("\n
Selected e is:%d",ar[e]);
printf("\n");
printf("\n
The public key:(%d,%d)",ar[e],n);
printf("\n");
printf("\n
Private key is: (%d,%d)",invr(ar[e],ph),n);
printf("\n
Press any key.........");
getche();
}
int prime(int n)
{
int i,rem,k=0;
for(i=2;i<=sqrt(n);i++)
{
rem=n%i;
if(rem==0)
{
k++;
}
}
if(k>0)
return 0;
else
return 1;
}
int gcd(int a,int
b)
{
int x,y,rem;
x=abs(a);
y=abs(b);
if(x<y)
{
int tmp=y;
y=x;
x=tmp;
}
do
{
rem=x%y;
x=y;
y=rem;
} while(rem!=0);
if(x==1)
return 1;
else
return 0;
}
int sqrmul(int
p,int e,int n)
{
unsigned long int rem,q,a[20],i=19,mod;
while(q!=1)
{
rem=e%2;
q=(e-rem)/2;
e=q;
a[i]=rem;
i--;
}
a[i]=1;
long int k=0,tmp;
for(int
j=i;j<20;j++)
{
if(k==0)
{
mod=p%n;
tmp=mod;
}
else
{
if(a[j]==1)
{
mod=(tmp*tmp*p)%n;
tmp=mod;
}
else
{
mod=(tmp*tmp)%n;
tmp=mod;
}
}
k++;
}
return(tmp);
}
int invr(int
a,int b)
{
long int
temp=0,inv;
do
{
inv=a*temp-1;
++temp;
}
while(inv%b!=0);
return (temp-1);
}
int invr1(int
e,int n)
{
long int
temp=0,inv;
do
{
inv=e*temp-1;
++temp;
}
while(inv%n!=0);
return(temp-1);
}
