RSA algorithm in C
0 275
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.
Share:
Comments
Waiting for your comments