RSA algorithm in C easy implementation

Today we will write a program to implement RSA algorithm in C programming language, so let’s first understand what is RSA algorithm.

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

Now let’s write a program to implement the RSA Algorithm in C programming language.

Program to implement RSA Algorithm in C:

 

#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

More knowledge:

https://proprogramming.org/c-program-to-implement-coppersmith-freivalds-algorithm/

Let me know in comments if you have suggestions or any confusion regarding implementation of RSA algorithm in C programming language.

4 thoughts on “RSA algorithm in C easy implementation”

  1. gcc rsa4.cpp
    rsa4.cpp: In function ‘int main()’:
    rsa4.cpp:34:18: warning: NULL used in arithmetic [-Wpointer-arith]
    for(i=0;msg[i]!=NULL;i++)
    ^~~~
    /tmp/ccn55de1.o: In function `__gnu_cxx::__enable_if<std::__is_integer::__value, double>::__type std::sqrt(long)’:
    rsa4.cpp:(.text._ZSt4sqrtIlEN9__gnu_cxx11__enable_ifIXsrSt12__is_integerIT_E7__valueEdE6__typeES3_[_ZSt4sqrtIlEN9__gnu_cxx11__enable_ifIXsrSt12__is_integerIT_E7__valueEdE6__typeES3_]+0x13): undefined reference to `sqrt’
    collect2: error: ld returned 1 exit status

    Reply
    • add “using namespace std;” under the includes, or add “std::” before the sqrt function: you need to specify that sqrt is part of the standard (std) library!

      Reply
      • This is unnecessary and furthermore results in a compiler error. Simply compile using:
        gcc ProgramName.c -lm
        and sqrt won’t cause a problem. This is because sqrt is part of the math library, not the standard library.

        Reply
  2. When I enter the string it gives;
    Exception thrown at 0x7C21D4EC (ucrtbased.dll) in Dec.exe: 0xC0000005: Access violation writing location 0x00F5B000. Do you know why?

    Reply

Leave a Comment