RSA (Rivest-Shamir-Adleman) Algorithm is an asymmetric or public-key cryptography algorithm, meaning it operates using two distinct keys: a Public Key and a Private Key. The Public Key is used for encryption and is publicly accessible, while the Private Key handles decryption and must remain confidential. Developed by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977, RSA remains a cornerstone of secure digital communication.
How Asymmetric Cryptography Works
If Person A needs to securely send a message to Person B:
- Person A encrypts the message using Person B's Public Key.
- Person B decrypts the message using their Private Key.
Core Stages of the RSA Algorithm
The RSA Algorithm relies on large-number factorization and modular arithmetic for encryption/decryption. It involves three critical phases:
1. Key Generation
- Select two large primes (p, q): Kept secret.
- Compute n = p × q: Part of both Public and Private Keys.
- Calculate Euler’s Totient Φ(n):
[
Φ(n) = (p - 1) × (q - 1)
] Choose encryption exponent (e):
- (1 < e < Φ(n))
- (gcd(e, Φ(n)) = 1) (co-prime).
- Derive decryption exponent (d):
[
d ≡ e^{-1} \mod Φ(n)
]
Solved via the Extended Euclidean Algorithm or Fermat’s Little Theorem.
Resulting Keys:
- Public Key = (n, e)
- Private Key = (n, d)
2. Encryption
Convert plaintext M to numerical form, then encrypt using:
[
C = M^e \mod n
]
(C = ciphertext; e, n from Public Key)
3. Decryption
Recover original data with:
[
M = C^d \mod n
]
(d, n from Private Key)
Practical Example
Key Setup:
- Let (p = 1997), (q = 4003) → (n = 7,990,271)
- (Φ(n) = (1996) × (4002) = 7,987,992)
- Choose (e = 5) (co-prime with Φ(n))
- Compute (d = 1,596,269) (via modular inverse).
Encrypting "123":
[
C = 123^5 \mod 7,990,271 = 3,332,110
]
Decrypting:
[
M = 3,332,110^{1,596,269} \mod 7,990,271 = 123
]
Security Foundation
RSA’s strength hinges on the computational infeasibility of factoring large n into p and q. Even with known n and e, deriving d requires knowing Φ(n), which demands prime factorization—a task deemed intractable for 1024-bit or larger keys.
👉 Note: Compromised p and q expose d, breaking encryption.
Pros and Cons
| Advantages | Disadvantages |
|-----------------------------------------|------------------------------------------|
| ✅ High security | ❌ Slow for large data |
| ✅ Public-key convenience | ❌ Large key sizes (2048+ bits) |
| ✅ Secure key exchange | ❌ Vulnerable to side-channel attacks |
| ✅ Digital signatures | ❌ Quantum computing threat |
FAQs
1. Why is RSA called "asymmetric" cryptography?
It uses two keys: a public key for encryption and a private key for decryption.
2. What key length is secure today?
2048-bit or longer; 1024-bit is now considered vulnerable.
3. Can RSA be broken by quantum computers?
Yes—Shor’s Algorithm theoretically factors large n efficiently, compromising RSA.
4. Why must p and q be large primes?
Smaller primes simplify factorization, exposing Φ(n) and d.
5. Is RSA used in HTTPS?
Yes, for key exchange, though bulk encryption often uses faster symmetric algorithms like AES.
👉 Explore advanced cryptographic techniques for deeper insights.