The **RSA algorithm** is a very fast algorithm for encryption and decryption. It is used in many applications like **encryption** and **decryption** of messages. The algorithm is based on the idea that if we know the public and private keys, then we can encrypt and decrypt messages. An **RSA** user creates two large prime numbers, p and q, and computes **n = pq**. Then they computes the **totient** function, **λ(n) = (p – 1)(q – 1)**. Choosing **e** as a relatively prime number to **λ(n) and 1 < e < λ(n)** they release **e** as the public key.

Then they computes the private key, **d**, as follows:

**d * e = 1 mod λ(n)**

Encrytion is done as follows:

**c = m ^{e} mod n**

over all the characters.

Decryption is done as follows:

**m = c ^{d} mod n**

over all the characters.

Write a C program that will ask the user to enter two prime numbers and then encrypt and decrypt a message using the RSA algorithm.

1. Ask the user to enter two prime numbers and validate them.

2. Store the prime numbers in variables.

3. Compute **n = pq**.

4. Compute **λ(n) = (p – 1)(q – 1)**.

5. Choose a random number e as a relatively prime number to **λ(n)** and **1 < e < λ(n)**.

6. Compute **d = e ^{-1} mod λ(n)**.

7. Print the public and private keys.

8. Ask the user to enter a message and store it in a variable.

9. Encrypt the message using the public key.

10. Decrypt the message using the private key.

11. Print the encrypted and decrypted message.

Let’s look at the RSA Algorithm in C with two examples.

In this approach, we implement the RSA algorithm. This is a type of Public Key encryption or Asymmetric encryption/decryption algorithm, that uses two different but related keys. Plus knowing the one key will not help figure out the other is the key protection.

The RSA algorithm uses the fact that it’s easy to multiply two large prime numbers together and get a product. But you can’t take that product and reasonably guess the two original numbers, or guess one of the original primes if only the other is known.

Here is source code of the C Program to Implement the RSA Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C program to Implement the RSA Algorithm`

`*/`

`#include<stdio.h>`

`#include<conio.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();

void main()

`{`

printf("\nENTER FIRST PRIME NUMBER\n");

scanf("%d", &p);

flag = prime(p);

if (flag == 0)

`{`

printf("\nWRONG INPUT\n");

getch();

exit(1);

`}`

printf("\nENTER ANOTHER PRIME NUMBER\n");

scanf("%d", &q);

flag = prime(q);

if (flag == 0 || p == q)

`{`

printf("\nWRONG INPUT\n");

getch();

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();

`}`

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]);

`}`

In this case, we enter two prime numbers “7” and “19” and then use the RSA algorithm to encrypt and decrypt a message.

$ gcc RSA.c $ ./a.out ENTER FIRST PRIME NUMBER: 7 ENTER ANOTHER PRIME NUMBER: 19 ENTER MESSAGE: Dharmendra POSSIBLE VALUES OF e AND d ARE 5 65 11 59 13 25 17 89 23 47 29 41 31 7 37 73 41 29 THE ENCRYPTED MESSAGE IS =’a…º¢É½…a THE DECRYPTED MESSAGE IS Dharmendra

In this approach we use a temp array to store some intermediate values to be later used in decrypt function.

**Methods used:**

**int isPrime(int)**– This function checks if the number is prime or not.**int gcd(int, int)**– This function returns the greatest common divisor of two numbers.**int totient(int, int)**– This function returns the totient of a number.**int randome(int)**– This function returns a random number less than the given number.**int private_key(int, int)**– This function returns the private key.**long pomod(long, long, long)**– This function returns the modular exponentiation of a number.**char *encrypt(char *, long, long)**– This function encrypts the message.**char *decrypt(char *, long, long)**– This function decrypts the message.

**Example:**

Enter the value of p: 7

Enter the value of q: 19

**n = pq** = 7 * 19 = 133

**λ(n) = (p – 1)(q – 1)** = λ(n) = (7 – 1)(19 – 1) = 108

The number **e** should be less than 108 and greater than 1.

Thus, **(i * e) % λ(n) = 1**, (65 * 5) % 108 = 1

The value of **n** is 133

The value of **λ(n)** is 108

The value of **e** is 5

The value of **d** is 65

Here is source code of the C Program to Implement the RSA Algorithm. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C program to Implement the RSA Algorithm`

`*/`

`#include <math.h>`

`#include <stdio.h>`

`#include <stdlib.h>`

`#include <string.h>`

int isPrime(int n)

`{`

int i;

for (i = 2; i <= sqrt(n); i++)

`{`

if (n % i == 0)

`{`

return 0;

`}`

`}`

return 1;

`}`

int gcd(int a, int b)

`{`

if (a == 0)

`{`

return b;

`}`

return gcd(b % a, a);

`}`

int totient(int p, int q)

`{`

return (p - 1) * (q - 1);

`}`

int randome(int lambda_n)

`{`

printf("\nThe number e should be less than %d\n and greater than 1.",

lambda_n);

for (int i = 2; i < lambda_n; i++)

`{`

if (gcd(i, lambda_n) == 1)

`{`

return i;

`}`

`}`

return -1;

`}`

int private_key(int e, int lambda_n)

`{`

for (int i = 1; i < lambda_n; i++)

`{`

if ((i * e) % lambda_n == 1)

`{`

printf("\nThus, (i * e) %% lambda_n = 1, (%d * %d) %% %d = 1", i, e,

lambda_n);

return i;

`}`

`}`

return -1;

`}`

long pomod(long a, long b, long m)

`{`

long x = 1, y = a;

while (b > 0)

`{`

if (b % 2 == 1)

`{`

x = (x * y) % m;

`}`

y = (y * y) % m;

b /= 2;

`}`

return x % m;

`}`

`/* Encryption`

`* A function which takes the message, the public key and a number n which is the`

`* product of p and q. The function encrypts the message using the public key`

`* and returns the encrypted message.`

`*/`

char *encrypt(char *message, long e, long n)

`{`

long i;

long len = strlen(message);

char *cipher = (char *)malloc(len * sizeof(char));

for (i = 0; i < len; i++)

`{`

cipher[i] = pomod(message[i], e, n);

printf("\n%c -> %c", message[i], cipher[i]);

`}`

return cipher;

`}`

`/* Decryption`

`* A function which takes the cipher text, the private key and a number n which`

`* is he product of p and q. The function decrypts the cipher text using the`

`* private key and returns the decrypted message.`

`*/`

char *decrypt(char *cipher, long d, long n)

`{`

long i;

long len = strlen(cipher);

char *message = (char *)malloc(len * sizeof(char));

for (i = 0; i < len; i++)

`{`

`// message[i] = (long) pow(cipher[i], d) % n;`

message[i] = pomod(cipher[i], d, n);

printf("\n%c -> %c", cipher[i], message[i]);

`}`

return message;

`}`

int main()

`{`

int p, q, lambda_n;

long n, e, d;

char *message;

char *cipher;

printf("\nEnter the value of p: ");

scanf("%d", &p);

printf("\nEnter the value of q: ");

scanf("%d", &q);

if (isPrime(p) && isPrime(q))

`{`

n = p * q;

lambda_n = totient(p, q);

e = randome(lambda_n);

d = private_key(e, lambda_n);

printf("\nThe value of n is %ld", n);

printf("\nThe value of lambda_n is %d", lambda_n);

printf("\nThe value of e is %ld", e);

printf("\nThe value of d is %ld", d);

printf("\nEnter the message: ");

message = (char *)malloc(sizeof(char) * 100);

scanf("%s", message);

cipher = encrypt(message, e, n);

puts("\nThe encrypted message is: ");

printf("%s", cipher);

message = decrypt(cipher, d, n);

puts("\nThe original message was: ");

printf("%s", message);

`}`

`else`

`{`

printf("\nThe value of p and q should be prime.");

`}`

return 0;

`}`

1. This program will ask the user to enter two prime numbers and then encrypt and decrypt a message using the RSA algorithm.

2. After accepting the values of **p** and **q**, the program will check if the values are prime or not.

3. If they are prime, the program will calculate the value of **n**, **lambda_n**, **e** and **d** using the above mentioned theory.

4. After this, the message will be encrypted and decrypted.

In this case, we enter two prime numbers “7” and “19” and then use the RSA algorithm to encrypt and decrypt a message.

Enter the value of p: 7 Enter the value of q: 19 The number e should be less than 108 and greater than 1. Thus, (i * e) % lambda_n = 1, (65 * 5) % 108 = 1 The value of n is 133 The value of lambda_n is 108 The value of e is 5 The value of d is 65 Enter the message: apple a -> p -> ? p -> ? l -> ! e -> The encrypted message is: ??! -> a ? -> p ? -> p ! -> l -> e The original message was: apple

**Note:**

**Method 2** (Additional program) is not a perfect implementation for large value of **n (p * q)**, as the character set implementation in C is very small, during the encryption and decryption process, many characters are lost. Therefore, for this program to work correctly for large values, as a workaround, all the intermediate calculation should be done on a long long int type array.

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Apply for C Internship
- Watch Advanced C Programming Videos
- Check C Books
- Practice Computer Science MCQs
- Practice BCA MCQs