RSA & public-key cryptography

Symmetric cryptography has a bootstrapping problem: to encrypt securely, both sides need the same secret key — but how do you get that key to the other side without an eavesdropper intercepting it first?

Public-key (asymmetric) cryptography, introduced conceptually by Diffie and Hellman in 1976 and made practical by Rivest, Shamir, and Adleman with RSA in 1977, solves this with two mathematically linked keys: a public key anyone can know, and a private key only the owner holds. Data encrypted with the public key can only be decrypted with the matching private key.

RSA's security rests on a simple asymmetry: multiplying two large prime numbers is easy, but factoring their product back into the original primes is computationally hard for classical computers when the numbers are large enough (2048 bits or more, today).

Key generation picks two large random primes p and q, computes n = p × q, and derives a public exponent e and private exponent d such that they're mathematically inverse under modular arithmetic tied to n. The public key is (n, e); the private key is (n, d). Encryption raises the message to the power e mod n; decryption raises the ciphertext to the power d mod n.

In practice, RSA is rarely used to encrypt bulk data directly — it's slow and has strict size limits. Instead it's typically used to encrypt a short symmetric key (key transport) or to produce digital signatures, with AES doing the heavy lifting on the actual data.

Real RSA uses primes hundreds of digits long, but the same arithmetic works identically with small ones — which is why this toy example (the one most textbooks use) is worth stepping through by hand.

Take p = 61 and q = 53. Then n = 3233 and φ(n) = 60 × 52 = 3120. Pick e = 17 (it shares no common factors with 3120). Solving 17d ≡ 1 (mod 3120) gives d = 2753 — that's the whole key pair: public key (3233, 17), private key (3233, 2753).

Encrypting the message M = 65 gives C = 65¹⁷ mod 3233 = 2790. Decrypting runs it back: 2790²⁷⁵³ mod 3233 = 65. The same modulus, two different exponents, one direction easy without the private key and the other only possible with it.

Solving "17d ≡ 1 (mod 3120)" isn't guesswork — it's a standard computation called the extended Euclidean algorithm, which finds the modular inverse of e directly. Run backward, the ordinary Euclidean algorithm (repeated division to find a greatest common divisor) leaves behind a trail of remainders; the extended version tracks coefficients alongside those remainders and, because e and φ(n) were chosen to be coprime, that trail terminates in exactly the d you need. It's fast — logarithmic in the size of the numbers — which is what makes key generation practical even for 2048-bit primes.

Almost every RSA key you'll encounter uses the public exponent e = 65537, and the reason is a genuine engineering trade-off rather than convention. Written in binary, 65537 is 10000000000000001 — only two bits are set — and the square-and-multiply algorithm used for modular exponentiation does one multiplication per bit and one extra squaring per set bit, so a sparse exponent like this makes encryption and signature verification (both of which use e) noticeably faster than a dense one would.

Smaller exponents like e = 3 are even faster, but they reopen exactly the kind of low-exponent attacks covered below — 65537 is small enough to stay fast and large enough to close off the simplest ones. It also happens to be a Fermat prime (2¹⁶ + 1), which guarantees it's coprime with φ(n) for essentially any RSA modulus, simplifying key generation.

Encryption and signing use identical RSA arithmetic with the public and private key's roles reversed. To encrypt, anyone raises a message to the public exponent; to sign, the key-holder raises a (hashed) message to their private exponent — something only they can do. To decrypt, the key-holder raises the ciphertext to their private exponent; to verify a signature, anyone raises it to the public exponent and checks the result matches the message's hash.

In practice, following the hash-then-sign pattern from the hashing module, RSA never signs a raw message directly — it signs a padded hash digest (via RSA-PSS, covered in the padding module), for exactly the same reasons raw RSA encryption is unsafe.

The requirement "n = p × q for two large primes" is doing more work than it looks like. Both directions of getting it wrong break RSA completely, for different reasons.

Using a single prime as the modulus (n = p, with no q at all) breaks it immediately: φ(n) for a prime is just n − 1, computable on the spot with no factoring whatsoever, since the modulus's primality is already public. An attacker skips straight to finding d — the entire security argument evaporates, because "hard to factor n" was never a barrier to begin with.

Using many small primes multiplied together (n = p₁ × p₂ × ⋯ × p₃₀, say) breaks it the opposite way: n is trivially factorable by algorithms tuned for exactly this shape, like Pollard's rho or the elliptic curve method, which are fast whenever n has small factors — even if n itself is a large number. RSA's security specifically depends on n having no small factors at all, which is precisely what two similarly-sized large primes guarantees and a product of many small ones doesn't.

RSA's math is sound; most real-world breaks come from how it's deployed. Three patterns recur across decades of RSA vulnerabilities, and none of them require factoring anything.

Every attack on RSA either tries to factor n directly or tries to find a shortcut that avoids factoring. The best known classical factoring algorithm, the General Number Field Sieve (GNFS), has sub-exponential running time — hard enough that factoring a 2048-bit RSA modulus is considered infeasible with any classical computer for the foreseeable future.

This is precisely the assumption that Shor's algorithm breaks on a sufficiently large quantum computer — see the quantum threat module for why RSA is on every PQC migration roadmap.