Scribd
Upload
16 views7 pages

RSA Encryption and Decryption Code

This document outlines a C program that implements the RSA algorithm for data encryption and decryption. It includes functions for checking prime numbers, calculating the greatest common divisor, and performing encryption and decryption using public and private keys. The program prompts the user for prime numbers p and q, generates keys, and allows the user to encrypt and decrypt a message.

Uploaded by

moral.work19
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
16 views7 pages

RSA Encryption and Decryption Code

This document outlines a C program that implements the RSA algorithm for data encryption and decryption. It includes functions for checking prime numbers, calculating the greatest common divisor, and performing encryption and decryption using public and private keys. The program prompts the user for prime numbers p and q, generates keys, and allows the user to encrypt and decrypt a message.

Uploaded by

moral.work19
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Data Encryption and Decryption using RSA Algorithm

Program:
#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;
}

Output:
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

Common questions

Powered by AI

Modular exponentiation is the operation used to encrypt and decrypt messages in RSA. A message is encrypted by raising it to the power of 'e' (the public exponent) and taking modulo 'n'. For decryption, the cipher is raised to the power of 'd' (the private exponent) and then taken modulo 'n'. This method is suitable because it allows for the use of large integers, ensuring security. The operations themselves are hard to reverse due to the nature of the modular arithmetic, making the RSA encryption secure against direct decryption without the private key.

Prime numbers are crucial in RSA encryption because they are used to generate the public and private keys. Specifically, two distinct prime numbers, p and q, are multiplied to produce n. The difficulty of factoring this large number n back into its prime factors is the basis of RSA's security. The primes also determine lambda_n, which is the product of (p-1) and (q-1), used in calculating the public exponent 'e' and private exponent 'd'. This ensures that only those with the private key (derived from these primes) can decrypt messages encrypted with the public key.

The greatest common divisor (GCD) is vital for RSA security as it ensures that the chosen public key exponent 'e' is suitable for encryption operations. Specifically, 'e' must be coprime with lambda_n, meaning gcd(e, lambda_n) = 1, to ensure that an inverse 'd' can exist. This condition guarantees that a decipherable private key can be derived and prevents unintended simplifications or cancelations in the encryption and decryption processes, maintaining the integrity and security of the keys.

In RSA, the totient, specifically lambda_n, plays a crucial role in both key generation and encryption/decryption processes. It is computed as the product of (p-1) and (q-1) if p and q are the primes used to compute n. The totient gives the number of integers up to n that are coprime with n, and it's used to determine the modular relationships necessary for selecting 'e' and computing 'd'. The totient ensures that the keys generated allow reversible encryption and decryption processes.

The 'pomod' function in the RSA program is designed to perform modular exponentiation efficiently. It takes three parameters 'a', 'b', and 'm', calculating (a^b) % m using a method known as exponentiation by squaring. This method is crucial in encryption and decryption as it handles the large numbers resulting from raising integers to the powers used in RSA securely and quickly. Modular exponentiation is a cornerstone of RSA as it ensures both processes are feasible even for large numbers.

The Euclidean algorithm is significant in RSA encryption because it is used to compute the greatest common divisor (GCD) of two numbers, which is essential in determining a suitable public exponent 'e'. The algorithm ensures that 'e' is coprime with (p-1)(q-1), making sure there is a modular inverse. This coprime requirement is crucial for the formation of valid keys and for the mathematical operations that enable RSA encryption and decryption.

Modular arithmetic contributes to RSA's strength by allowing calculations to work with very large numbers in a manageable way, specifically when using key sizes that ensure security. It makes reversing the encryption without the decryption key computationally infeasible due to the properties of prime factorization and the discrete logarithm problem within modular systems. This enables RSA to utilize large keys that are resistant to factorization attacks, hence ensuring high security levels while maintaining the practicality of encryption and decryption processes.

The value 'e' in RSA encryption is selected as a small odd integer that is coprime with lambda_n (the totient of n). A common choice for 'e' is 65537 as it ensures efficient encryption and computational simplicity. The constraints are that 'e' must be greater than 1 and less than lambda_n, with gcd(e, lambda_n) = 1, ensuring that it has an inverse 'd' which can be used for decryption. These constraints ensure that 'e' can encrypt messages properly, while 'd' used during decryption is valid.

The multiplicative inverse, represented by the private key 'd', is essential in RSA as it allows for decryption of messages encrypted using the corresponding public key 'e'. It satisfies the relation (e * d) % lambda_n = 1. This property ensures that any message encrypted using 'e' can be decrypted using 'd', completing the circle of secure communication. The existence of this inverse is what makes RSA a two-way encryption algorithm, facilitating both safe message delivery and privacy preservation.

The RSA algorithm ensures message security through the use of key pairs consisting of a public key (n and e) and a private key (n and d). The public key is used for encryption, while the private key is used for decryption. The values of e and d are chosen such that (e * d) % lambda_n = 1, meaning d is the modular multiplicative inverse of e mod lambda_n. As a result, only the private key can reverse the encryption done by the public key, ensuring that only the intended recipient can decrypt the message.

You might also like