RSA with C
RSA
RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem that is widely used for secure data transmission.
p,q are distinct primes.
n = p*q
phi = (p-1)*(q-1)
e is such that
1 < e < phi and is coprime to phi.
d = modInverse(e)
Public Key pair (n,e)
Private Key pair (n,d)
Encryption
For Padded Plaintext message ‘m’
c(m) = m^e mod n
c(m) = pow(m,e) % n
Decryption
m(c) = c^d mod n
m(c) = pow(c,d) % n
RSA in C
rsa.h file :
Encrypt function
encrypt which takes 3 arguments
1st argument the message to encrypt of type char*
2nd and 3rd argument the index values for p,q of type integer
returns an integer array of the same size of the message.
Decrypt function
decrypt which takes 3 arguments
1st argument is the encrypted integer array
2nd and 3rd argument the index values for p,q of type integer
The same values used to encrypt the plaintext message.
It returns a char array, the decrypted message .
rsa.h Header file
#define ll long long
// #define ld long double
#ifndef RSA_H
#define RSA_H
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
// prime numbers array for random values of p,q
int prime_list[400] = {11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777};
// the enc array which will have the encrypted numbers of the message
int enc[1000]={0};
unsigned ll p,q,n,phi,e,track,c,m,d;
char msg[1000];
// 1 < e < phi
void gcd(){
int t,a,b;
a = e;
b = phi;
while(1){
t = a%b;
if(!t){
track = b;
return;
}
a = b;
b = t;
}
}
// the power function which will help to keep the number in range of mod
ll power(ll x, ll y, ll mod)
{
ll res = 1;
while (y > 0)
{
if (y & 1)
res = res*x % mod;
y = y>>1;
x = x*x % mod;
}
return res;
}
// computing the values and keys which will be required for encryption
// and decryption
void pre(ll v1, ll v2){
p = prime_list[v1];
q = prime_list[v2];
n = p*q;
phi = (p-1)*(q-1);
e = 7;
// 1 < e < phi
while(e<phi){
gcd();
if(track==1)
break;
else
e++;
}
// 1 < e < phi
}
// mod Inverse function to calculate the value of d, for decryption
ll modInverse(ll a, ll m)
{
ll m0 = m;
ll y = 0, x = 1;
if (m == 1)
return 0;
while (a > 1) {
int q = a / m;
int t = m;
m = a % m, a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0)
x += m0;
return x;
}
// public key pair (n,e)
// private key pair (n,d)
// encryption function
int* encrypt(char *s, ll v1, ll v2){
strcpy(msg, s);
pre(v1, v2);
for(int i=0; msg[i] != 0; ++i){
int msg_letter;
msg_letter = (int)msg[i];
// m = pow(m, e) % n
enc[i] = power(msg_letter, e, n);
}
return enc;
}
// decryption function
char* decrypt(int *a, ll v1, ll v2){
pre(v1, v2);
d = modInverse(e,phi);
char *dec_msg;
int size;
for(size=0; a[size] != 0; ++size);
dec_msg = (char*)malloc((size+1) * sizeof(char));
for(int i=0; i < size; ++i){
// m = pow(c,d) % n
m = power(a[i], d, n);
dec_msg[i] = (char)(long)m;
}
dec_msg[size] = '\0';
return dec_msg;
}
#endif
APPLICATION
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include "rsa.h"
#define ll long long
int main(){
char *s = "This is a Sample Message";
printf("Sample Message to Encrypt : %s\n",s);
srand(time(0));
unsigned ll v1, v2;
// generating two random numbers in the range of 0->400
v1 = rand() % 400;
do{
v2 = rand() % 400;
}while(v1 == v2);// checking for v1 != v2
int *a = encrypt(s, v1, v2);
// encryption of plaintext message.
printf("\nEncrypted array\n");
for(int i=0; a[i] != 0;++i){
printf("%d, ", a[i]);
}
// decryption of the encrypted array to get the plaintext message 'm'
char *d = decrypt(a, v1, v2);
printf("\n\nDecrypted Message : %s\n",d);
return 0;
}
OUTPUT
Sample Message to Encrypt : This is a Sample Message
Encrypted array
2804921, 420449, 4929558, 2472507, 1556470, 4929558, 2472507, 1556470, 1195619, 1556470, 4898031, 1195619, 1279340, 2174968, 1035401, 5248057, 1556470, 1482633, 5248057, 2472507, 2472507, 1195619, 3230331, 5248057,
Decrypted Message : This is a Sample Message