RSA

Pick two large random primes. Multiply them to get a modulus. Pick a small public exponent. Use number theory to compute a matching private exponent. Encryption is one modular exponentiation. Decryption is another. The security rests entirely on the fact that factoring the modulus back into its two primes is, with current methods, prohibitively expensive.

The rest of this page expands that paragraph. Each step is small. Together they produce one of the most consequential algorithms in computing history.

Key generation is six steps. Each step uses operations a calculator can handle, until the numbers get big.

1. Pick two distinct large primes, call them p and q. Real RSA uses primes around 1024 bits long.
2. Compute the modulus n = p × q. This becomes part of the public key.
3. Compute Euler's totient: φ(n) = (p-1)(q-1). This is the count of integers from 1 to n that share no factor with n.
4. Pick a public exponent e with 1 < e < φ(n) such that gcd(e, φ(n)) = 1. In practice everyone uses e = 65537.
5. Compute the private exponent d as the modular inverse of e modulo φ(n). That means (d × e) mod φ(n) = 1.
6. The public key is the pair (n, e). The private key is d (with n implied).

Throw away p, q, and φ(n) after generation. Anyone who recovers them can derive d from e in microseconds.

Once the keys exist, the operations are blindingly simple:

That is it. Two modular exponentiations. The same operation twice with different exponents. The clever part is that (me)d mod n = m always works, which is what Euler's theorem guarantees when the exponents are chosen the way we chose them.

The interactive below runs the full algorithm with small primes so the numbers fit in your head. Real RSA does the same operations on numbers thousands of digits long.

The correctness of RSA falls out of Euler's theorem, which states that for any integer m coprime to n, raising m to the φ(n) power and taking mod n always gives 1:

mφ(n) mod n = 1

We chose d so that e × d equals 1 plus some multiple of φ(n). Substitute that into the decryption:

cd mod n = (me)d mod n = med mod n = m1 + kφ(n) mod n = m × (mφ(n))k mod n = m × 1k = m

That is the whole proof of correctness. The 1977 paper extends it slightly to handle messages that share a factor with n (which essentially never happens for random m and random p, q), but the core argument is one line.

To compute d from the public key alone, an attacker would need φ(n). To get φ(n) from n, they would need to factor n into p and q. Integer factorization of large semiprimes is the hard problem at the bottom of RSA security.

The best-known classical algorithm is the General Number Field Sieve. Its running time grows sub-exponentially in the size of the modulus. The current record stands at RSA-250 (829 bits), factored in 2020 with about 2,700 core-years of computation. RSA-2048 is many orders of magnitude harder.

What we have described so far is "textbook RSA," and it is dangerously insecure when used directly. Two production-grade modifications are mandatory:

• Padding. Raw RSA leaks information: encrypting the same message twice produces the same ciphertext, small messages can be brute-forced, and there are mathematical relationships an attacker can exploit. Real systems wrap the plaintext in a random padding scheme like OAEP (Optimal Asymmetric Encryption Padding) for encryption or PSS (Probabilistic Signature Scheme) for signing. The older PKCS#1 v1.5 padding is still in use but has known weaknesses.
• Hybrid use. RSA can only encrypt a message smaller than the modulus. So real protocols never use RSA to encrypt a file. They use RSA to encrypt a fresh AES key, then encrypt the file with AES. See the Hybrid Encryption page for the full pattern.

The textbook version on this page is for learning. Production code never calls me mod n directly; it calls RSA_OAEP_encrypt(public_key, message), which handles padding, message size limits, and random IVs internally.