AntInLoop

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>

---

Related Algorithms