Here you will learn about RSA algorithm in C and C++.
RSA Algorithm is used to encrypt and decrypt data in modern computer systems and other electronic devices. RSA algorithm is an asymmetric cryptographic algorithm as it creates 2 different keys for the purpose of encryption and decryption. It is public key cryptography as one of the keys involved is made public. RSA stands for Ron Rivest, Adi Shamir and Leonard Adleman who first publicly described it in 1978.
RSA makes use of prime numbers (arbitrary large numbers) to function. The public key is made available publicly (means to everyone) and only the person having the private key with them can decrypt the original message.
Working of RSA Algorithm
RSA involves use of public and private key for its operation. The keys are generated using the following steps:-
- Two prime numbers are selected as p and q
- n = pq which is the modulus of both the keys.
- Calculate totient = (p-1)(q-1)
- Choose e such that e > 1 and coprime to totient which means gcd (e, totient) must be equal to 1, e is the public key
- Choose d such that it satisfies the equation de = 1 + k (totient), d is the private key not known to everyone.
- Cipher text is calculated using the equation c = m^e mod n where m is the message.
- With the help of c and d we decrypt message using equation m = c^d mod n where d is the private key.
Note: If we take the two prime numbers very large it enhances security but requires implementation of Exponentiation by squaring algorithm and square and multiply algorithm for effective encryption and decryption. For simplicity the program is designed with relatively small prime numbers.
Below is the implementation of this algorithm in C and C++.
Program for RSA Algorithm in C
//Program for RSA asymmetric cryptographic algorithm
//for demonstration values are relatively small compared to practical application
#include<stdio.h>
#include<math.h>
//to find gcd
int gcd(int a, int h)
{
int temp;
while(1)
{
temp = a%h;
if(temp==0)
return h;
a = h;
h = temp;
}
}
int main()
{
//2 random prime numbers
double p = 3;
double q = 7;
double n=p*q;
double count;
double totient = (p-1)*(q-1);
//public key
//e stands for encrypt
double e=2;
//for checking co-prime which satisfies e>1
while(e<totient){
count = gcd(e,totient);
if(count==1)
break;
else
e++;
}
//private key
//d stands for decrypt
double d;
//k can be any arbitrary value
double k = 2;
//choosing d such that it satisfies d*e = 1 + k * totient
d = (1 + (k*totient))/e;
double msg = 12;
double c = pow(msg,e);
double m = pow(c,d);
c=fmod(c,n);
m=fmod(m,n);
printf("Message data = %lf",msg);
printf("\np = %lf",p);
printf("\nq = %lf",q);
printf("\nn = pq = %lf",n);
printf("\ntotient = %lf",totient);
printf("\ne = %lf",e);
printf("\nd = %lf",d);
printf("\nEncrypted data = %lf",c);
printf("\nOriginal Message Sent = %lf",m);
return 0;
}
Program for RSA Algorithm in C++
//Program for RSA asymmetric cryptographic algorithm
//for demonstration values are relatively small compared to practical application
#include<iostream>
#include<math.h>
using namespace std;
//to find gcd
int gcd(int a, int h)
{
int temp;
while(1)
{
temp = a%h;
if(temp==0)
return h;
a = h;
h = temp;
}
}
int main()
{
//2 random prime numbers
double p = 3;
double q = 7;
double n=p*q;
double count;
double totient = (p-1)*(q-1);
//public key
//e stands for encrypt
double e=2;
//for checking co-prime which satisfies e>1
while(e<totient){
count = gcd(e,totient);
if(count==1)
break;
else
e++;
}
//private key
//d stands for decrypt
double d;
//k can be any arbitrary value
double k = 2;
//choosing d such that it satisfies d*e = 1 + k * totient
d = (1 + (k*totient))/e;
double msg = 12;
double c = pow(msg,e);
double m = pow(c,d);
c=fmod(c,n);
m=fmod(m,n);
cout<<"Message data = "<<msg;
cout<<"\n"<<"p = "<<p;
cout<<"\n"<<"q = "<<q;
cout<<"\n"<<"n = pq = "<<n;
cout<<"\n"<<"totient = "<<totient;
cout<<"\n"<<"e = "<<e;
cout<<"\n"<<"d = "<<d;
cout<<"\n"<<"Encrypted data = "<<c;
cout<<"\n"<<"Original Message sent = "<<m;
return 0;
}
Output
This article is submitted by Rahul Maheshwari. You can connect with him on facebook.
Comment below if you have any queries related to above program for rsa algorithm in C and C++.
Thanks for this tutorial!
I’m a bit confused, the code for encryption and decryption is all together. I think the “double m” is the variable where the decrypted message is stored, but it needs “pow(c,d)” and the variable “c” needs the message “msg” because of “c= pow(msg,e)”. If I am right, how can this be possible?
In fact, the code works correctly with current values of ‘p’ e ‘q’, but if assign other values decrypt is wrong.
I’m not understand a utility of ‘k’, too.
It is because if you use large values in p, q and e then the values you will get from them will be very large which cannot be stored in even long long int datatype.
This code does not work. Anything other than “12” will return false decryptions.
You have to choose value of e and d in such a may that satisfies conditions mentioned in above article. Read the conditions properly.
I confirm that anything other than “12” will return false decryptions.
The code is fine but here e is incremented in every iteration until the while condition is satisfied which to me doesn’t look appealing. I suggest you to randomly choose e such that ( e <(p-q)(q-1) ) and check for the condition and then increment e.
Very clear and concise! Thanks!
Hey really appreciate the tutorial you have set for RSA encryption. It is very useful for people like me who is just getting started in the field. However I have a small doubt, what happens when I want to increase key length to 1024 bits (pq = 128 bytes). How would i store the key and implement mathematical functions on it since the there is not a single self sufficient variable that would be able to store this long key. I am sure I will have to take it to binary operations and use arrays, but I am not experienced as much and would really help me if you could just show me a place to start 🙂
Thanks for this beautiful piece of code.
I am trying to implement RSA and Blum Blum Shub algorithm to generate cryptographically secure pseuderandom bit stream.
Can you please explain me how to handle lagre primes in C.
I need to choose p,q such large that it will be 128 bits.
Thanking You!
Thanks for this tutorial!
Not ran the code but how can you decrypt (7) before it has been fully encrypted (6)?
Change:
double c = pow(msg,e);
double m = pow(c,d);
c=fmod(c,n);
m=fmod(m,n);
To:
double c = pow(msg,e);
c=fmod(c,n);
double m = pow(c,d);
m=fmod(m,n);
It does not work for random primes assigned to p and q. Only works for current values of p and q.
i think the issue lies in k because it’s fixed 2 to find k you need to satisfy that d and k both integers
in the relation (d*e-1)mod(tontient)=0 .. d*e+k*tontient=1 where both d and k integers solve this by doing gcd(d,tontient) and using the equations to manipulate to reach linear equation x*e+y*tontient=1 then you can use those x,y values for k and d
amazing code good job i like it
To be fair, your code is quite simple and easy to understand. It is nice to play and fiddle around with and to test how RSA works. But you can’t use it for an actual implementation of RSA since you wouldn’t be able to store numbers in the range of typical RSA public keys (n is somewhere between 2000 and 3000 bits).
And there are a few minor flaws in your code. First of all, I wouldn’t use the type double for values which are supposed to be integers, since integers are more precise than doubles when dealing with integers.
The next thing is that your way of computing the private key d is wrong. The formula e*d = 1 + k * totient is correct but I think you misunderstood what it implies. k is arbitrary and should not be set to a fixed number like you did. What this formula actually means is
e*d = 1 + k * totient = 1 mod(totient).
Thus d is the modular multiplicative inverse of e mod(totient) an can be calculated with the extended euclidian algorithm.
The last flaw I spotted is your way of choosing e. e is supposed to be a random integer between 1 and n where n is p*q, but you are in fact not choosing it randomly but with a clear system. e will always be the smallest number which is coprime to (p-1)*(q-1). If your implementation of RSA gets public , everyone could derive some of the factors of (p-1)*(q-1) from e which would make RSA immediately less secure.
My last point: The totient doesn’t need to be (p-1)*(q-1) but only the lowest common multiple of (p-1) and (q-1). However, thats not too crucial.
How to compute e*d = 1 + k * totient = 1 mod(totient) correctly by keeping the code simple?
As a mathematician and programmer, I can confidently tell you that this is not RSA! There are a number of sites with this same code (possibly copies of this?), but it’s utterly incorrect. RSA is an algorithm that works with integers mod m. It cannot be implemented using floating points numbers (double) – or, at least, not reasonably, since the “divisions” that occur in RSA refer to multiplicative inverses in modular arithmetic – which is very different from divisions of floating point numbers (and there is absolutely no gain from using floating point numbers – RSA requires the exact representation of any number from 0 up to the modulus – clearly a job for integral types). If we overlook this catastrophic problem, there’s some other problems too, any of which suffices to make this not an implementation of RSA.
First: d cannot be chosen as (1 + (k * totient)) / e for any k – if you insist upon doing it the hard way, you need to choose k to be the least non-negative integer for which this quotient is an integer. Choosing k to be the least one such that e divides 1 + k * totient, then dividing by e will give you the multiplicative inverse of e mod totient and I guess would be the simplest way to do it, but the way that every sane implementation of RSA is going to do it is to use the extended euclidean algorithm.
Second: This implementation treats fmod(pow(msg,e), n) as the ciphertext, except it computes the decrypted text using pow(msg,e) – that is, the “decryption” algorithm is using an intermediate computation of the encryption algorithm, rather than the ciphertext. A decryption algorithm is supposed to take the ciphertext back to the plaintext (i.e. it should take 3 as an input and return 12 – this takes 12^e as the input, and basically just raises it to the power of 1/e, with some modular arithmetic obfuscating the true nature of the code).
I would really recommend deleting this post – it’s seems to me quite dangerous to publicly post an incorrect cryptographic algorithm, and even short of that problem, this post will surely confuse anyone seeking to learn about RSA because, if they look at the details, they will find that this is all wrong.
Just looking at this line: c=fmod(c,n);
We can see that there are so many flaws here: how can c be computed using the private key??