RSA Cryptosystem

RSA Cryptosystem

RSA (Rivest–Shamir–Adleman, 1977) is the most widely deployed public-key cryptosystem. Its security rests on the integer factorization problem — factoring large numbers is believed to be computationally infeasible.

Key Generation

1. Choose two distinct primes $p$ and $q$
2. Compute $n = p \cdot q$ (the modulus)
3. Compute $\varphi(n) = (p-1)(q-1)$ (Euler's totient)
4. Choose $e$ coprime to $\varphi(n)$ (the public exponent; common choice: $e = 65537$)
5. Compute $d \equiv e^{-1} \pmod{\varphi(n)}$ (the private exponent)

Public key: $(e, n)$ · Private key: $(d, n)$

Encryption and Decryption

$\text{encrypt}(m) = m^e \bmod n$ $\text{decrypt}(c) = c^d \bmod n$

Why It Works

By Euler's theorem: $m^{\varphi(n)} \equiv 1 \pmod{n}$, so:

$c^d = (m^e)^d = m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k \equiv m \pmod{n}$

Classic Example

$p = 61$, $q = 53$, $e = 17$:

• $n = 3233$
• $\varphi(n) = 3120$
• $d = 17^{-1} \bmod 3120 = 2753$

Encrypt 42: $42^{17} \bmod 3233 = 2557$ Decrypt 2557: $2557^{2753} \bmod 3233 = 42$

Your Task

Implement:

• rsa_keypair(p, q, e) → (n, e, d)
• rsa_encrypt(m, e, n) — returns $m^e \bmod n$
• rsa_decrypt(c, d, n) — returns $c^d \bmod n$

Use Python's built-in pow(base, exp, mod) for efficient modular exponentiation.