RSA Algorithm — Public Key Cryptography

RSA, published in 1977 by Rivest, Shamir, and Adleman, solved the key distribution problem that had plagued cryptography since its inception. The mathematical foundation: multiplying two large primes p and q is easy (milliseconds), but factoring their product n = p×q is computationally infeasible for large enough primes. This asymmetry — easy to compute one direction, hard to reverse — is the trapdoor that makes public key cryptography possible.

RSA secures every HTTPS connection, every SSH session, every S/MIME email, every code signing certificate. Understanding RSA is understanding the mathematical foundation of internet security. It is also a masterclass in applied number theory: Euler's totient, modular exponentiation, the extended Euclidean algorithm, and Fermat's little theorem all play essential roles.

Key Generation

Generate two large primes p, q. Compute n = p×q and φ(n) = (p-1)(q-1). Choose public exponent e (usually 65537). Compute private key d = e⁻¹ mod φ(n) using extended Euclidean. Public key: (n, e). Private key: (n, d).

import random
from math import gcd

def is_prime_miller_rabin(n, k=10):
    if n < 2: return False
    if n == 2 or n == 3: return True
    if n % 2 == 0: return False
    r, d = 0, n - 1
    while d % 2 == 0: r += 1; d //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1: continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1: break
        else: return False
    return True

def generate_prime(bits=512):
    while True:
        p = random.getrandbits(bits) | (1 << bits-1) | 1
        if is_prime_miller_rabin(p): return p

def extended_gcd(a, b):
    if b == 0: return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def rsa_keygen(bits=512):
    p, q = generate_prime(bits//2), generate_prime(bits//2)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 65537  # standard public exponent
    _, d, _ = extended_gcd(e, phi)
    d %= phi
    return (n, e), (n, d)  # (public_key, private_key)

pub, priv = rsa_keygen(bits=512)
print(f'Public key (n, e): n={str(pub[0])[:30]}..., e={pub[1]}')
print(f'Private key (n, d): n=..., d={str(priv[1])[:30]}...')

Encryption and Decryption

RSA encryption: c = m^e mod n. Decryption: m = c^d mod n. Security rests on the fact that computing d from e and n requires factoring n — computationally infeasible for 2048+ bit keys.

def rsa_encrypt(message: int, public_key: tuple) -> int:
    n, e = public_key
    return pow(message, e, n)  # Python's pow(b, e, m) uses fast modexp

def rsa_decrypt(ciphertext: int, private_key: tuple) -> int:
    n, d = private_key
    return pow(ciphertext, d, n)

# Demo with small numbers (real RSA uses 2048+ bit keys)
p, q = 61, 53
n = p * q          # 3233
phi = (p-1)*(q-1)  # 3120
e = 17             # public exponent (gcd(17, 3120) = 1)
# d = 17^-1 mod 3120 = 2753
d = pow(e, -1, phi)  # Python 3.8+ supports modular inverse directly
pub = (n, e)
priv = (n, d)

msg = 65  # ASCII 'A'
ct = rsa_encrypt(msg, pub)
pt = rsa_decrypt(ct, priv)
print(f'Message: {msg}')
print(f'Encrypted: {ct}')
print(f'Decrypted: {pt}')

Why e=65537?

The standard public exponent 65537 (2^16 + 1) is chosen because: (1) it is prime, so gcd(e, φ(n))=1 for most φ(n); (2) it has only two set bits in binary (10000000000000001), so modular exponentiation with e requires exactly 17 squarings and 1 multiplication — very fast; (3) small enough to make encryption fast, large enough to avoid small-exponent attacks that affect e=3.

RSA Security Status and Key Sizes

RSA security depends on the hardness of integer factorisation. Current recommendations: - 1024-bit: Broken (NIST deprecated 2010). Do not use. - 2048-bit: Secure through ~2030 per NIST. Current minimum. - 3072-bit: Secure through ~2040. - 4096-bit: Conservative long-term choice.

Shor's algorithm on a quantum computer can factor n in polynomial time, breaking RSA completely. Post-quantum cryptography (CRYSTALS-Kyber, CRYSTALS-Dilithium — NIST standardised 2024) is the response. Migration to post-quantum algorithms is actively underway in major infrastructure.

Frequently Asked Questions