RSA algorithm
Aim
To implement data encryption and decryption using the RSA algorithm in C, demonstrating
how a plaintext message can be securely encrypted with a public key and decrypted with a
private key.
About RSA Algorithm
The RSA algorithm, developed in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman,
is one of the most widely used public-key cryptosystems for secure data transmission. It is based
on the mathematical difficulty of factoring large prime numbers. RSA enables both encryption
(securing data) and digital signatures (authenticating identity).
Core Principles
Asymmetric Cryptography: RSA uses two keys — a public key for encryption and a
private key for decryption. Unlike symmetric systems, the keys are not identical.
Mathematical Foundation: Security relies on the computational infeasibility of
factoring a large integer (n), which is the product of two large primes.
Modular Arithmetic: Encryption and decryption are performed using modular
exponentiation, ensuring that even large numbers can be handled efficiently.
Applications
Secure Communication: Protects sensitive data during transmission.
Digital Signatures: Ensures authenticity and integrity of messages.
Key Exchange: Forms the basis for secure session key distribution in protocols like
SSL/TLS.
Strengths and Limitations
Strengths: Strong security, widely adopted, supports both encryption and authentication.
Limitations: Computationally intensive, slower than symmetric algorithms, requires
careful choice of key sizes (typically 2048 bits or more for modern security).
Algorithm
1. Key Generation
o Choose two large prime numbers (p) and (q).
o Compute (n = p \cdot q).
o Compute (\phi(n) = (p-1)(q-1)).
o Choose an integer (e) such that (1 < e < \phi(n)) and gcd((e, \phi(n))) = 1.
o
Compute (d) such that (d \cdot e \equiv 1 \ (\text{mod } \phi(n))).
o
Public key = ((e, n)), Private key = ((d, n)).
2. Encryption
o Ciphertext (C = M^e \ (\text{mod } n)), where (M) is the plaintext.
3. Decryption
o Plaintext (M = C^d \ (\text{mod } n)).
Step-by-Step Procedure
1. Input two prime numbers (p) and (q).
2. Compute (n) and (\phi(n)).
3. Select encryption key (e).
4. Compute decryption key (d).
5. Input plaintext message (M).
6. Encrypt using (C = M^e \ (\text{mod } n)).
7. Decrypt using (M = C^d \ (\text{mod } n)).
8. Display results.
C Program
#include <stdio.h>
#include <math.h>
// Function to compute gcd
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to compute modular exponentiation
long long modExp(long long base, long long exp, long long mod) {
long long result = 1;
base = base % mod;
while (exp > 0) {
if (exp % 2 == 1) // If exp is odd
result = (result * base) % mod;
exp = exp / 2;
base = (base * base) % mod;
}
return result;
}
int main() {
long long p, q, n, phi, e, d, message, encrypted, decrypted;
// Step 1: Input prime numbers
printf("Enter two prime numbers (p and q): ");
scanf("%lld %lld", &p, &q);
// Step 2: Compute n and phi
n = p * q;
phi = (p - 1) * (q - 1);
// Step 3: Choose e such that gcd(e, phi) = 1
for (e = 2; e < phi; e++) {
if (gcd(e, phi) == 1)
break;
}
// Step 4: Compute d (multiplicative inverse of e mod phi)
for (d = 2; d < phi; d++) {
if ((d * e) % phi == 1)
break;
}
printf("Public Key: (e=%lld, n=%lld)\n", e, n);
printf("Private Key: (d=%lld, n=%lld)\n", d, n);
// Step 5: Input message
printf("Enter message (numeric form < %lld): ", n);
scanf("%lld", &message);
// Step 6: Encrypt
encrypted = modExp(message, e, n);
printf("Encrypted message: %lld\n", encrypted);
// Step 7: Decrypt
decrypted = modExp(encrypted, d, n);
printf("Decrypted message: %lld\n", decrypted);
return 0;
}
Sample Outputs
Output Set 1
Enter two prime numbers (p and q): 17 11
Public Key: (e=7, n=187)
Private Key: (d=23, n=187)
Enter message (numeric form < 187): 88
Encrypted message: 11
Decrypted message: 88
Output Set 2
Enter two prime numbers (p and q): 13 19
Public Key: (e=2, n=247)
Private Key: (d=122, n=247)
Enter message (numeric form < 247): 123
Encrypted message: 33
Decrypted message: 123