Today we will write a program to implement RSA algorithm in C programming language, so let’s first understand what is RSA algorithm.
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.
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
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!
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.
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?