The private key, d, is calculated as follows:
d * e = 1 mod λ(n)
The process of encryption is as follows:
c = me mod n
Overall the characters.
The procedure for deciphering all the characters unfolds in the subsequent manner:
m = cd mod n
Example:
Develop a C program that prompts the user to input two prime numbers. Subsequently, implement the RSA algorithm to encode and decode a message.
Solution for the problem:
RSA Cryptography
- Request two prime numbers from the user and verify them.
- Put the prime numbers in different variables.
- Determine n = pq .
- Calculate (n) = (p - 1)(q - 1) after the above step.
- Select a random number e that is close to being prime to both n and 1 e n .
- Determine d = e-1 mod n .
- Print out the private and public keys .
- Request a message from the user and then save it in a variable.
- Use the public key to encrypt the message.
- Using the private key , decrypt the message.
- Print the message , both encrypted and decrypted .
Let's explore two examples of the RSA Algorithm implemented in C.
- RSA Algorithm Using Basic Methodology
- Extended RSA Algorithm Implementation
Approach 1
RSA Algorithm Using Simple Approach
The RSA technique is applied in this process. This form of public key cryptography utilizes a pair of distinct yet interrelated keys, commonly referred to as asymmetric encryption and decryption mechanism. Furthermore, having access to one key does not simplify the comprehension of how the other key safeguards itself.
The RSA encryption method leverages the principle that the multiplication of two significant prime numbers produces a straightforward outcome. Nevertheless, possessing knowledge of just one prime number does not allow for an accurate deduction of the other prime or the original numbers from their product.
Source Code
Here is the source code of a C program that implements the RSA algorithm. The program has been compiled and run successfully on a Linux operating system. Additionally, the program's output is provided below.
#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("ENTER FIRST PRIME NUMBER: ");
scanf("%ld", &p);
flag = prime(p);
if (flag == 0 || p == 1)
{
printf("WRONG INPUT\n");
exit(1);
}
printf("ENTER ANOTHER PRIME NUMBER: ");
scanf("%ld", &q);
flag = prime(q);
if (flag == 0 || q == 1 || p == q)
{
printf("WRONG INPUT\n");
exit(1);
}
printf("ENTER MESSAGE: ");
scanf(" %[^\n]s", msg);
for (i = 0; i < strlen(msg); 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("%ld\t%ld\n", e[i], d[i]);
encrypt();
decrypt();
return 0;
}
int prime(long int pr)
{
int i;
if (pr == 1)
return 0;
for (i = 2; i <= sqrt(pr); 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", (char)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", (char)m[i]);
}
Cases of Runtime Testing
In this scenario, we input the pair of prime numbers "5" and "17", and proceed to encode and decode a message using the RSA algorithm.
ENTER FIRST PRIME NUMBER: 5
ENTER ANOTHER PRIME NUMBER: 17
ENTER MESSAGE: Jitendra
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:
I?j?x??a
THE DECRYPTED MESSAGE IS:
Jitendra
Approach 2:
Additional RSA Algorithm Programming
In this procedure, we retain certain interim information in a temporary array which will be utilized at a subsequent stage in the decryption process.
Methods applied
int isPrime(int) -
This function checks if a given number is a prime number or not.
int gcd(int, int) -
The function returns the greatest common divisor of two numbers.
int totient(int, int) -
The function returns the totient of an integer.
int randome(int) -
This function returns a random integer that is less than the provided input value.
int private_key(int, int) -
The private key is returned by this function.
long pomod(long, long, long) -
This function calculates the modular exponentiation of a given number.
char encrypt(char , long, long) -
The message is encrypted using this feature.
char decrypt(char , long, long) -
The message is decrypted using this function.
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 value of e must be more than 1 and less than 108.
As a result, (i * e) % λ(n) = 1, (65 * 5) % 108 = 1
N has a value of 133.
The value of λ(n) is 108.
e has a value of 5.
d has a value of 65.
Source Code
The following C source code demonstrates the implementation of the RSA algorithm. It has been compiled and run successfully on a Linux environment. The program's output is shown below.
/*
* RSA algorithm implementation in C
*/
#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 procedure that requires the message, the public key, and an integer n which is the sum of p and q. Using the public key, the function encrypts the message and then returns the result.
*/
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 procedure that requires the cypher text, the private key, and an integer n, which is the sum of the values of p and q. The function uses the private key to decode the cypher text and then returns the message that has been decrypted.
*/
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;
}
Output:
Cases of Runtime Testing
In this scenario, we input the pair of prime numbers "5" and "13", followed by encoding and decoding a message utilizing the RSA method.
Enter the value of p: 5
Enter the value of q: 13
The number e should be less than 48
and greater than 1.
Thus, (i * e) % lambda_n = 1, (29 * 5) % 48 = 1
The value of n is 65
The value of lambda_n is 48
The value of e is 5
The value of d is 29
Enter the message: mango
m -> ,
a ->
n ->
g ->&
o ->
The encrypted message is:
,&
, -> ,
->
-> -
& ->&
-> .
The original message was:
, -&.
Program Description
- The user will be prompted to provide two prime numbers before this program uses the RSA technique to encrypt and decrypt a communication.
- The program will determine whether or not the values of p and q are prime after accepting their values.
- The program will determine the values of n, lambda_n, e, and d based on the aforementioned hypothesis if they are prime .
- After that, the message will be encrypted, and then decoded.
Note: Given that the character set implementation in C is so limited, many characters are lost during the encryption and decryption processes , making Approach 2 (Additional program) an imperfect implementation for large values of n (p * q) . As a result, as a workaround, all the intermediate calculations for this program should be performed on a long long int type array.
Advantages and Disadvantages of RSA Algorithm
There exist a range of benefits and drawbacks associated with the RSA Algorithm. Here are some primary advantages and disadvantages of the RSA Algorithm:
Advantages:
Security:
The RSA encryption method is commonly employed for ensuring secure transmission of data, known for its high level of security.
Public-key cryptography:
The RSA encryption method requires distinct keys for encryption and decryption due to its nature as a public-key cryptography technique. Information is encrypted with the public key and decrypted with the private key.
Key conversation:
A confidential key can be securely shared between two entities using the RSA method without transmitting the key directly through the network.
Electronic signatures:
A message sender has the ability to digitally sign a message by employing their private key, and the recipient can authenticate the signature by utilizing the sender's public key in the RSA method for digital signatures.
Disadvantages:
Poor processing rate:
When dealing with large volumes of data, the RSA algorithm demonstrates slower performance compared to other encryption methods.
Extra-large keys:
Utilizing extensive key sizes is essential for ensuring the security of the RSA algorithm, requiring increased computational capabilities and storage capacity.
Attacks through side-channel are susceptible:
The RSA algorithm is vulnerable to side-channel attacks, enabling malicious actors to acquire the private key through leaked information from sources like power consumption, electromagnetic emissions, and timing evaluation.
Limited application in some cases:
Because of its inadequate processing speed, the RSA algorithm may not be suitable for certain scenarios where there is a continuous need to encrypt and decrypt large amounts of data.