RSA algorithm in C

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.

---

Advantages:

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.

---

Disadvantages:

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.