Program to implement RSA algorithm in C

What is RSA Algorithm?

RSA is one of the first practical public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem. RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1977.

Example of RSA Algorithm:

  • Choose p = 3 and q = 11
  • Compute n = p * q = 3 * 11 = 33
  • Compute φ(n) = (p – 1) * (q – 1) = 2 * 10 = 20
  • Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7
  • Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 3 [(3 * 7) % 20 = 1]
  • Public key is (e, n) => (7, 33)
  • Private key is (d, n) => (3, 33)
  • The encryption of m = 2 is c = 27 % 33 = 29
  • The decryption of c = 29 is m = 293 % 33 = 2

 

C program to implement RSA Algorithm:

 

#include<stdio.h> 
#include<stdlib.h> 
#include<math.h> 
#include<string.h> 

long int p,q,n,t,flag,e[100],d[100],temp[100],j,m[100],en[100],i; 
char msg[100]; 
int prime(long int); 
void ce(); 
long int cd(long int); 
void encrypt(); 
void decrypt(); 
int main() 
{ 
	printf("\nENTER FIRST PRIME NUMBER\n"); 
	scanf("%ld",&p); 
	flag=prime(p); 
	if(flag==0) 
	{ 
		printf("\nWRONG INPUT\n"); 
		exit(1); 
	} 
	printf("\nENTER ANOTHER PRIME NUMBER\n"); 
	scanf("%ld",&q); 
	flag=prime(q); 
	if(flag==0||p==q) 
	{ 
		printf("\nWRONG INPUT\n"); 
		exit(1); 
	} 
	printf("\nENTER MESSAGE\n"); 
	fflush(stdin); 
	scanf("%s",msg); 
	for(i=0;msg[i]!=NULL;i++) 
		m[i]=msg[i]; 
	n=p*q; 
	t=(p-1)*(q-1); 
	ce(); 
	printf("\nPOSSIBLE VALUES OF e AND d ARE\n"); 
	for(i=0;i<j-1;i++) 
		printf("\n%ld\t%ld",e[i],d[i]); 
	encrypt(); 
	decrypt(); 
	return 0; 
}
 
int prime(long int pr) 
{ 
	int i; 
	j=sqrt(pr); 
	for(i=2;i<=j;i++) 
	{ 
		if(pr%i==0) 
			return 0; 
	} 
	return 1; 
}
 
void ce() 
{ 
	int k; 
	k=0; 
	for(i=2;i<t;i++) 
        {
            if(t%i==0)
                continue;
                flag=prime(i);
            if(flag==1&&i!=p&&i!=q)
            {
                e[k]=i; flag=cd(e[k]);
                if(flag>0) 
		{ 
			d[k]=flag; 
			k++; 
		} 
		if(k==99) 
			break; 
		} 
	} 
}
 
long int cd(long int x) 
{ 
	long int k=1; 
	while(1) 
	{ 
		k=k+t; 
		if(k%x==0) 
			return(k/x); 
	} 
} 

void encrypt() 
{ 
	long int pt,ct,key=e[0],k,len; 
	i=0; 
	len=strlen(msg); 
	while(i!=len) 
	{ 
		pt=m[i]; 
		pt=pt-96; 
		k=1; 
		for(j=0;j<key;j++) 
		{ 
			k=k*pt; 
			k=k%n; 
		} 
		temp[i]=k; 
		ct=k+96; 
		en[i]=ct; 
		i++; 
	} 
	en[i]=-1; 
	printf("\nTHE ENCRYPTED MESSAGE IS\n"); 
	for(i=0;en[i]!=-1;i++) 
		printf("%c",en[i]); 
} 

void decrypt() 
{ 
	long int pt,ct,key=d[0],k; 
	i=0; 
	while(en[i]!=-1) 
	{ 
		ct=temp[i]; 
		k=1; 
		for(j=0;j<key;j++) 
		{ 
			k=k*ct; 
			k=k%n; 
		} 
		pt=k+96; 
		m[i]=pt; 
		i++; 
	} 
	m[i]=-1; 
	printf("\nTHE DECRYPTED MESSAGE IS\n"); 
	for(i=0;m[i]!=-1;i++) 
		printf("%c",m[i]); 
}

Sample Output:

 

ENTER FIRST PRIME NUMBER
5

ENTER ANOTHER PRIME NUMBER
7

ENTER MESSAGE
proprogramming

POSSIBLE VALUES OF e AND d ARE

11	11
13	13
17	17
THE ENCRYPTED MESSAGE IS
kbokbo|ba{{dn|
THE DECRYPTED MESSAGE IS
proprogramming

Leave a Reply