RSA Encryption

Why RSA matters

• TLS certificates. The vast majority of HTTPS certificates issued through 2026 are still RSA-2048 — every browser maintains a root store with hundreds of RSA roots from CAs like DigiCert, Let's Encrypt, Sectigo, GoDaddy. Visit any major site and your browser verifies an RSA chain.
• S/MIME and email signing. Outlook, Apple Mail, Thunderbird signing and encryption uses X.509 certs with RSA keys (typically 2048 or 4096 bit). Corporate email crypto is dominated by RSA because deployment predated mass ECC adoption.
• Code signing. Windows Authenticode, Apple notarization, Java jarsigner, npm package signing — almost all use RSA. The signed-binary infrastructure of every major OS depends on RSA.
• JWT and OAuth. Most JSON Web Tokens use RS256 (RSA-PKCS1-v1_5 with SHA-256) or RS512. JWKS endpoints publish RSA public keys. OIDC providers like Auth0, Okta, Microsoft Entra default to RSA.
• SSH host keys. Servers often advertise RSA host keys alongside Ed25519. Until ~2020, RSA was the only universally-supported SSH key type for client authentication.
• Hardware tokens. Smart cards, YubiKeys (PIV slots), and TPM-bound credentials store RSA private keys. PKCS#11 hardware module APIs are RSA-first by historical inertia.
• Document signing. Adobe PDF signatures, ETSI eIDAS qualified signatures, DocuSign — all RSA in the dominant deployments. EU regulations explicitly enumerate RSA-2048+ as acceptable algorithms.

Protocol walkthrough with concrete numbers

Toy example. Pick small primes p = 61, q = 53.

• Compute modulus. n = p × q = 61 × 53 = 3233.
• Compute totient. φ(n) = (p-1)(q-1) = 60 × 52 = 3120.
• Pick public exponent. e = 17 (coprime to 3120).
• Compute private exponent. d = 17^(-1) mod 3120 = 2753 (extended Euclidean: 17 × 2753 = 46801 = 15 × 3120 + 1).
• Public key: (n=3233, e=17). Private key: (n=3233, d=2753).
• Encrypt m = 65. c = 65^17 mod 3233 = 2790.
• Decrypt c = 2790. m = 2790^2753 mod 3233 = 65. Round-trip recovered.
• Real-world keys. A 2048-bit RSA key has p, q each ~1024 bits — primes around 10^308. Generation finds them via random odd candidates filtered through trial division then Miller-Rabin (typically 40+ rounds for 2^-80 false-positive rate).

Encryption vs signing — they are not symmetric

RSA is unusual in that the same primitive supports both encryption and digital signatures, but the modes are different.

• Encryption (RSA-OAEP). Public key encrypts; private key decrypts. Always pad with OAEP — never raw m^e mod n. The plaintext m must be smaller than n; RSA is too slow to encrypt bulk data, so it encrypts a randomly-generated AES key (a hybrid encryption scheme), and AES does the actual data encryption.
• Signing (RSA-PSS). Private key signs; public key verifies. Use PSS (Probabilistic Signature Scheme) padding, not legacy PKCS#1 v1.5. PSS adds randomness so signing the same message twice produces different signatures, preventing some structural attacks.
• Hybrid encryption. A typical TLS-pre-1.3 RSA handshake: client generates random 48-byte premaster secret, encrypts it with server's RSA-OAEP public key, sends 256-byte ciphertext. Server decrypts to recover premaster, both sides derive AES keys. Note: this lacks forward secrecy — if the server's RSA key is later stolen, all recorded sessions decrypt. This is why TLS 1.3 dropped RSA key exchange entirely.
• Signing in TLS. TLS 1.3 still uses RSA (RSA-PSS) for server certificate signatures — the server proves possession of the private key by signing the handshake transcript. RSA signing is not deprecated; only RSA key encryption is.

Performance optimizations and CRT

• Chinese Remainder Theorem (CRT). Production RSA implementations don't compute c^d mod n directly. They split into c^d_p mod p and c^d_q mod q (where d_p = d mod (p-1), d_q = d mod (q-1)) and combine with CRT. Each modular exponentiation is half the bit width, and the combined cost is ~4x faster than direct.
• Sliding-window exponentiation. Square-and-multiply with precomputed odd powers reduces multiplications from 1.5n to ~1.2n per bit of exponent. Modern OpenSSL uses 5-bit windows.
• Montgomery multiplication. Avoids expensive division by replacing mod n with mod 2^k operations. Critical for both speed and constant-time guarantees.
• Constant-time blinding. Multiply ciphertext by r^e mod n before decryption (random r), then divide by r after. Prevents timing attacks (Brumley-Boneh 2003) by randomizing the working values that flow through the ladder.
• RSA-CRT fault attack. If a single bit-flip happens during CRT decryption, the attacker can compute gcd(c^d - bad_result, n) to recover one of the prime factors. Mitigation: verify the signature (or re-encrypt the result) before returning.

Choosing parameters safely

• Key size. NIST SP 800-57 deprecated 1024-bit RSA in 2013. 2048-bit is acceptable through 2030 for most uses. 3072-bit gives 128-bit equivalent security and is recommended for new long-term keys. 4096-bit is paranoid but inexpensive for occasional signing operations (CA root keys are typically 4096).
• Prime quality. p and q must be true primes (not Carmichael numbers); pass at least 40 Miller-Rabin rounds. Difference |p - q| should be ≥ 2^(n/4 - 100) bits to defeat Fermat factorization. Avoid primes where p-1 or q-1 has only small factors (Pollard p-1 attack).
• Padding. Always OAEP for encryption. Never use textbook RSA, never PKCS#1 v1.5 for new code (Bleichenbacher attacks survive 25+ years of patches — ROBOT 2017, Marvin 2024).
• Exponent e = 65537. The universal default. e=3 has been attacked when used without proper padding (Coppersmith). Larger e adds no security.
• Don't share moduli. Two parties using the same n with different e, d is catastrophic — anyone who knows two (e, d) pairs can factor n. This was a real bug in DROWN-class incidents.

Common misconceptions

• "Encryption uses public key" — full picture. True for the literal RSA primitive, but in practice RSA encrypts a symmetric key, not the data itself. Saying "RSA encrypts your file" is misleading; AES-256 encrypts the file, RSA encrypts the AES key.
• "256-bit RSA is secure." No. 256-bit RSA factors in seconds on a laptop. RSA key sizes need to be ≥ 2048 bits. A 256-bit key is roughly the size of a single AES block.
• "Naive m^e mod n is safe." Textbook RSA without padding is broken in dozens of ways: deterministic, malleable, vulnerable to broadcast attacks, susceptible to chosen-ciphertext, low-exponent attacks for small e. OAEP is mandatory.
• "RSA is dead." Far from it — billions of devices, certs, and signatures still run RSA. New deployments often pick ECC, but RSA's installed base will outlast many of us.
• "Quantum-safe." Shor's algorithm factors integers in polynomial time on a quantum computer with enough logical qubits (~6000+ for 2048-bit). NIST is standardizing post-quantum signature schemes (ML-DSA / Dilithium, SLH-DSA / SPHINCS+) to replace RSA-PSS.
• "Bigger primes = more secure linearly." Factoring effort grows sub-exponentially in key size: doubling from 2048 to 4096 adds only ~16 bits of strength but quadruples signing cost. Beyond 4096 you should switch algorithm classes (ECC, post-quantum) rather than scaling RSA further.

Performance numbers (3 GHz x86_64)

• RSA-2048. Sign ~1.5 ms; verify ~30 microseconds (e=65537); key generation ~50–200 ms.
• RSA-3072. Sign ~5 ms; verify ~70 microseconds; key generation ~300 ms–1 s.
• RSA-4096. Sign ~10 ms; verify ~120 microseconds; key generation ~500 ms–2 s.
• Ed25519 (for comparison). Sign ~50 microseconds; verify ~150 microseconds; key generation ~30 microseconds. Ed25519 signing is 30x faster, key generation is ~10000x faster.
• Memory. RSA-2048 public keys are 256 bytes plus encoding overhead (PEM ~450 bytes). Ed25519 keys are 32 bytes plus encoding (PEM ~110 bytes).