The RSA Algorithm
1-Based on the idea that factorization of integers into their prime factors is hard.
★ n=p．q, where p and q are distinct primes
2-Proposed by Rivest, Shamir, and Adleman
in 1977 and a paper was published in The Communications of ACM in 1978
3-A public-key cryptosystem.
4-Bob chooses two primes p,q and compute n=pq
5-Bob chooses e with gcd(e,(p-1)(q-1))=
gcd(e, ψ(n))=1.
6-Bob solves de≡1 (mod ψ(n))
7-Bob makes (e,n) public and (p,q,d) secret
8-Alice encrypts M as C≡Me (mod n)
9-Bob decrypts by computing M≡Cd (mod n).
Example.
#include<iostream>
#include<conio.h>
#include<math.h>
using namespace std;
int prime(int a)
{
if (a==1)
return 1;
for(int i=2;i<=a/2;i++)
{
if (a%i==0)
{
return 0;
}
}
return 1;
}
int Multiply(int iNum1,int iNum2)
{
return iNum1*iNum2;
}
int FindE(int iNum)
{
int iCount;
iCount=2;
while(iCount<iNum)
{
if(iNum%iCount!=0)
return iCount;
iCount++;
}
return 0;
}
int FindD(int iNum1,int iNum2)
{
int a1,a2,a3,b1,b2,b3,t1,t2,t3,q;
a1=1;
a2=0;
a3=iNum1;
b1=0;
b2=1;
b3=iNum2;
while(b3!=1)
{
q=a3/b3;
t1=a1-(q*b1);
t2=a2-(q*b2);
t3=a3-(q*b3);
a1=b1;
a2=b2;
a3=b3;
b1=t1;
b2=t2;
b3=t3;
}
if(b2<0)
b2=b2+iNum1;
return b2;
}
int FindText(int iNum1,int iNum2,int iNum3)
{
int iCount,t;
iCount=1;
t=1;
while(iCount<=iNum2)
{
t=t*iNum1;
t=t%iNum3;
iCount++;
}
return (t%iNum3);
}
int plain(double a,double b,int c)
{
double z;
z =pow(a,b);
}
int main()
{
long int p,q,n,d,e,pi,pt,ct;
cout<<"-----IMPLEMENTATION OF R.S.A ALGORITHM-----";
cout<<endl<<endl<<"Enter a prime number :";
cin>>p;
cout<<"Enter another prime number :";
cin>>q;
if((prime(p))&&(prime(q)))
{
n=Multiply(p,q);
cout<<endl<<"/* Intermediate Catculations...";
cout<<endl<<"n :"<<n;
pi=Multiply(p-1,q-1);
cout<<endl<<"pi :"<<pi;
e=(FindE(pi));
cout<<endl<<"e :"<<e;
d=FindD(pi,e);
cout<<endl<<"d :"<<d;
cout<<"*/";
cout<<endl<<endl<<endl<<"----KEYS----";
cout<<endl<<"Public Key : ("<<e<<","<<n<<")";
cout<<endl<<"Private Key : ("<<d<<","<<n<<")";
cout<<endl<<endl<<endl<<"----ENCRYPTION----"<<endl;
cout<<"Enter the plain text : ";
cin>>pt;
ct=FindText(pt,e,n);
pt=FindText(ct,d,n);
cout<<"Cipher Text :"<<ct;
cout<<"Plain text"<<(FindText(ct,d,n))<<endl;
//cout<<"plain teeee"<<plain(ct,d,n);
}
else
{
cout<<"Error! Enter two prime numbers!";
}
getch();
return 0;
}
Output:
