RSA Encryption Explained

The Most Famous Algorithm in History

RSA, named after its creators Rivest, Shamir, and Adleman, was published in 1977 and became the first practical public-key cryptosystem the world had ever seen. For decades, RSA was the absolute backbone of internet security, powering everything from HTTPS certificates to email encryption and VPN tunnels.

RSA works by leveraging a beautifully simple mathematical asymmetry: multiplying two enormous prime numbers together is trivially easy for a computer, but factoring the resulting product back into its two original primes is computationally devastating. A modern RSA key uses primes so large that the resulting product is 2048 or 4096 bits long, creating a number with over 600 digits.

The public key is derived from the product of the two primes (the modulus N) and a public exponent (typically 65537). The private key is mathematically computed using the Extended Euclidean Algorithm applied to Euler's totient of N. Anyone can encrypt a message using the public key, but only the holder of the private key can reverse the modular exponentiation to recover the plaintext.

Despite its historical dominance, RSA is falling out of favor. Its key sizes are enormous compared to elliptic curve alternatives (a 256-bit ECC key provides equivalent security to a 3072-bit RSA key). RSA is also significantly slower for key generation and signing. Most critically, Shor's algorithm running on a sufficiently powerful quantum computer would factor RSA keys in polynomial time, rendering the entire system obsolete.

Everyday Example

Imagine you publicly announce two massive numbers and challenge anyone in the world to figure out which two secret numbers you multiplied together to get them. Finding two factors of a small number like 15 (3 × 5) is trivial. But finding the two factors of a 600-digit number is like trying to find a specific grain of sand on every beach on Earth simultaneously. That mathematical impossibility is what protects your data.

The Deep Mathematics

Key generation selects two large primes p and q, computing N = p × q and φ(N) = (p-1)(q-1). The public exponent e is chosen such that gcd(e, φ(N)) = 1. The private exponent d is computed via the modular inverse d ≡ e^(-1) (mod φ(N)). Encryption computes c ≡ m^e (mod N). Decryption recovers m ≡ c^d (mod N). The security guarantee rests entirely on the computational intractability of factoring N back into p and q using classical algorithms like the General Number Field Sieve, which operates in sub-exponential time L(1/3, (64/9)^(1/3)).