RSA algorithm in C

# RSA algorithm in C

72

RSA (Rivest-Shamir-Adleman) is a widely used asymmetric encryption algorithm in cryptography.

## Introduction

RSA involves generating a public-private key pair, where the public key is used for encryption and the private key for decryption.

The keys are generated using large prime numbers.

Key Generation:

Choose two distinct prime numbers, p and q.

Calculate n = p * q. This is used as the modulus for both the public and private keys.

Calculate φ(n) = (p-1)(q-1), where φ is Euler's totient function.

Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. This will be the public exponent.

Calculate d such that d * e ≡ 1 (mod φ(n)). d is the private exponent.

Encryption:

To encrypt a message m:

Compute c ≡ m^e (mod n). Here, c is the ciphertext.

Decryption:

To decrypt the ciphertext c:

Compute m ≡ c^d (mod n). Here, m is the plaintext.

Security: RSA is considered secure due to the difficulty of factoring large numbers.

Asymmetry: Its asymmetric nature provides separate keys for encryption and decryption.

Versatility: It can be used for both encryption and digital signatures.

Standards: RSA is widely standardized and implemented, making it interoperable across different systems.

Computational Intensity: RSA operations, especially key generation and decryption, can be computationally intensive, especially for large key sizes.

Key Management: Asymmetric algorithms like RSA require careful key management, including key storage and distribution.

Key Size: As computing power increases, larger key sizes are needed to maintain security, which can increase computational overhead.

Vulnerability to Quantum Computing: RSA is vulnerable to attacks by quantum computers due to its reliance on integer factorization.

Example:

```// Sample code for RSA encryption and decryption
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

// Function to calculate GCD
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}

// Function to calculate modular exponentiation
long long int mod_exp(long long int base, long long int exp, long long int mod) {
long long int result = 1;
while (exp > 0) {
if (exp % 2 == 1)
result = (result * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return result;
}

// Function to generate keys
void generate_keys(int p, int q, int *e, int *d, int *n) {
int phil= (p - 1) * (q - 1);
*n = p * q;
*e = 2;
while (gcd(*e, phil)!= 1) {
(*e)++;
}
*d = 2;
while ((*e * *d) % phil!= 1) {
(*d)++;
}
}

// Function to encrypt message
long long int encrypt(int m, int e, int n) {
return mod_exp(m, e, n);
}

// Function to decrypt message
long long int decrypt(long long int c, int d, int n) {
return mod_exp(c, d, n);
}

int main() {
int p = 61, q = 53; // Example prime numbers
int e, d, n;
generate_keys(p, q, &e, &d, &n);

int message = 123; // Example message to encrypt
printf("Original message: %d\n", message);

long long int encrypted = encrypt(message, e, n);
printf("Encrypted message: %lld\n", encrypted);

long long int decrypted = decrypt(encrypted, d, n);
printf("Decrypted message: %lld\n", decrypted);

return 0;
}

```

Output:

```Original message: 123
Encrypted message: 2868
Decrypted message: 123```

This program generates RSA keys, encrypts a message, and then decrypts it. However, this is a simplistic implementation and may not be suitable for production use.

Share:

## SEMRush FREE Trial – PRO Account for 14 Days

FREE Pro Account worth \$99.95 for 14 Days.

## Get a .COM for just \$6.98

Secure Domain for a Mini Price