RSA Public-Key Cryptography Algorithm
RSA is an asymmetric public-key cryptosystem built on Euler's Theorem and the hardness of factoring n = p * q, using modular exponentiation for encryption, decryption, and digital signatures.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
RSA Public-Key Cryptography Algorithm
RSA (Rivest–Shamir–Adleman, 1977) is the most famous public-key cryptosystem. Its security rests on the asymmetry between multiplying two large primes $p \cdot q = n$ (instant) and factoring $n$ back into $p$ and $q$ (infeasible for 2048-bit $n$).
How It Works
1. Key Generation:
- Pick two distinct primes $p, q$ and compute $n = p \cdot q$ and $\varphi(n) = (p - 1)(q - 1)$.
- Choose public exponent $e$ coprime to $\varphi(n)$ (commonly $e = 65537$).
- Compute private exponent $d = e^{-1} \bmod \varphi(n)$ via Extended Euclid.
- Public key: $(e, n)$ | Private key: $(d, n)$.
2. Encryption: $c = m^e \bmod n$.
3. Decryption: $m = c^d \bmod n$ (works by Euler's Theorem: $c^d \equiv m^{ed} \equiv m^{1 + k\varphi(n)} \equiv m \pmod n$!).
---
Practice Problems
Intermediate
1. Toy RSA Key Generation, Encryption & Decryption
Implement RSA key generation (e, d, n), encryption, and decryption using Extended Euclid and Fast Exponentiation.
Approach: Compute phi = (p - 1) * (q - 1), d = modInv(e, phi), cipher = modPow(msg, e, n), and recover msg = modPow(cipher, d, n).
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
long long extGcd(long long a, long long b, long long& x, long long& y) {
if (b == 0) { x = 1; y = 0; return a; }
long long x1 = 0, y1 = 0;
long long g = extGcd(b, a % b, x1, y1);
x = y1; y = x1 - (a / b) * y1;
return g;
}
long long modPow(long long a, long long e, long long m) {
long long res = 1;
for (a %= m; e > 0; e >>= 1, a = a * a % m)
if (e & 1) res = res * a % m;
return res;
}
int main() {
long long p = 61, q = 53;
long long n = p * q; // 3233
long long phi = (p - 1) * (q - 1); // 3120
long long e = 17, x = 0, y = 0;
extGcd(e, phi, x, y);
long long d = (x % phi + phi) % phi; // 2753
long long msg = 65;
long long cipher = modPow(msg, e, n);
long long plain = modPow(cipher, d, n);
std::cout << "cipher=" << cipher << " decrypted=" << plain << "\n"; // cipher=2790 decrypted=65
return 0;
}
</details>
---