Textbook RSA
NEVER USE DIRECTLYRSA in its raw form: real primes, real modular exponentiation, real key generation β but no padding. See exactly why determinism makes textbook RSA completely insecure.
Step 1 β Generate RSA Key Parameters
Generate real prime numbers p and q, then compute all RSA parameters step by step. Use small primes (~32-bit) for visual clarity, or 2048-bit for real cryptographic strength.
Step 2 β Encrypt and Decrypt
Encrypt: c = me mod n | Decrypt: m = cd mod n
Determinism Demonstration
Encrypt the same message twice. The ciphertext is always identical β a fatal flaw.
Why Textbook RSA Is Broken
- Deterministic: Same plaintext always β same ciphertext. Attacker can build an encryption oracle and test known messages.
- Homomorphic weakness: cβ Β· cβ mod n = Enc(mβ Β· mβ) β ciphertexts can be multiplied to produce the encryption of the product.
- Small message space: Low-entropy messages (like symmetric keys) are vulnerable to brute-force with an encryption oracle.
- No ciphertext integrity: Any integer is a valid ciphertext β malleability attacks are trivial.
RSA-OAEP: Secure Encryption
RECOMMENDEDRSA-OAEP (Optimal Asymmetric Encryption Padding) adds randomization and domain separation to make RSA encryption semantically secure. Specified in RFC 8017 (PKCS#1 v2.2), Section 7.1.
Generate RSA Keys via WebCrypto
Real 2048-bit and 4096-bit RSA key pairs generated using the browser's WebCrypto API. NIST SP 800-57 recommends 2048-bit minimum; 3072-bit or 4096-bit for long-term security.
RSA-2048
~112-bit classical security (NIST level 3)
RSA-4096
~140-bit classical security (NIST level 4)
Encrypt with RSA-OAEP-SHA-256
The plaintext is padded with OAEP before RSA encryption. Each encryption uses a fresh random seed.
Randomization β Same Plaintext, Different Ciphertexts
Unlike textbook RSA, OAEP uses a random seed. Encrypt the same message twice and compare β ciphertexts are always different, providing IND-CPA security.
OAEP Padding Structure
OAEP encodes the message using two MGF1 mask operations with a random seed, providing non-determinism and all-or-nothing decoding.
Decrypt
RSA-PSS: Secure Signatures
RECOMMENDEDRSA-PSS (Probabilistic Signature Scheme) adds a random salt to each signature, making it provably secure in the random oracle model. Specified in RFC 8017 Β§8.1.
Generate Key and Sign
Sign a message with RSA-PSS-SHA-256. Each signature uses a fresh random salt (sLen = 32 bytes).
Verify Signature
Test signature verification with correct and tampered messages.
PSS Padding Structure
PSS encodes the message hash with a random salt. The salt makes signatures non-deterministic and provides tight security reduction.
PSS vs PKCS#1 v1.5 Signatures
Why PSS is the provably secure choice.
| Property | PKCS#1 v1.5 (RSASSA-PKCS1-v1_5) | PSS (RSASSA-PSS) β |
|---|---|---|
| Randomization | Deterministic | Probabilistic (random salt) |
| Security proof | No tight reduction known | Tight reduction to RSA inversion |
| Signature malleability | Potentially malleable | Non-malleable by design |
| NIST recommendation | Legacy β not recommended for new systems | Recommended (FIPS 186-5) |
| TLS 1.3 | PKCS#1 v1.5 signatures still allowed | PSS signatures preferred |
Small Exponent Attack β HΓ₯stad Broadcast
PADDING IS NON-NEGOTIABLEIf the same unpadded message m is sent to three recipients all using e=3, an attacker who intercepts all three ciphertexts can recover m using the Chinese Remainder Theorem and integer cube root β no private key needed.
Setup β Three Recipients, e=3
Generate three independent RSA keys each with e=3 and distinct small moduli. These represent three servers all using textbook RSA with a small public exponent.
Broadcast Same Message Unpadded
Encrypt the same message to all three recipients with no padding: cα΅’ = mΒ³ mod nα΅’. The attacker intercepts all three ciphertexts.
Attack β CRT Reconstruction + Cube Root
Since m < nα΅’ for all i, we have mΒ³ < nβΒ·nβΒ·nβ. The Chinese Remainder Theorem gives us exactly M = mΒ³. Then the integer cube root of M reveals m directly.
Why OAEP Destroys This Attack
- Randomization: With OAEP, each recipient receives a different padded message. Even with the same underlying plaintext, the padded m values differ, so mΒ³ values are not related by CRT.
- Structure: The OAEP padding expands the message to fill the full modulus, so m is always close to n in size β mΒ³ mod n wraps around the modulus multiple times.
- Minimum key size: NIST SP 800-57 recommends e=65537 for all production RSA. Small e values (e=3, e=17) must only ever be used with proper padding.
Bleichenbacher PKCS#1 v1.5 Oracle
PKCS#1 v1.5 ENCRYPTION = AVOIDBleichenbacher (1998) showed that a single-bit padding oracle β "is this ciphertext PKCS#1 v1.5 conformant?" β is enough to decrypt any RSA ciphertext via adaptive chosen-ciphertext queries. This broke SSL/TLS RSA key exchange and is still discovered in the wild today (ROBOT, 2017).
PKCS#1 v1.5 Encryption Padding Structure
A PKCS#1 v1.5 conformant encryption block has a specific structure. The oracle leaks only one bit: whether the decryption starts with 0x00 0x02.
"Conformant" means: EM[0] == 0x00 AND EM[1] == 0x02.
This is equivalent to: m β [2B, 3Bβ1] where B = 28(kβ2), k = modulus byte length.
Setup β Small RSA for Demonstration
Generate a small RSA key (128-bit modulus, 16 bytes) to make the attack completable in the browser. In practice, Bleichenbacher's 1998 attack targeted 512-bit SSL server keys.
The Padding Oracle
The oracle accepts a ciphertext and returns only "conformant" or "not conformant." In real attacks, this oracle was exposed via error messages in TLS handshakes.
Execute Bleichenbacher Attack
The attack multiplies c by se mod n, where varying s shifts the decryption. Each conformant result constrains the interval [a, b] containing m.
Why TLS 1.3 Removed RSA Key Exchange Entirely
- No forward secrecy: RSA key exchange uses the server's long-term private key to wrap the session key. Compromise of the private key retroactively decrypts all past traffic.
- Bleichenbacher variants: ROBOT (2017) found 8 major TLS implementations still vulnerable 19 years after the original paper. The oracle is hard to eliminate from real implementations.
- TLS 1.3 fix: RSA key exchange (RSA_PSK, RSA) removed. Only ephemeral Diffie-Hellman (ECDHE) allowed β provides forward secrecy by design.
- PKCS#1 v1.5 encryption: RFC 8017 explicitly marks RSA-PKCS1_V1_5 encryption as legacy. Use RSA-OAEP for any new RSA encryption.
RSA vs ECC vs Post-Quantum
QUANTUM-VULNERABLERSA security rests on the integer factorization problem. Shor's algorithm (1994) factors integers in polynomial time on a quantum computer, breaking all RSA key sizes. NIST's PQC standardization is complete β migration should begin now.
Algorithm Comparison (2026 NIST Recommendations)
| Algorithm | Key Size | Ciphertext / Sig Size | Classical Security | Post-Quantum Security | Status |
|---|---|---|---|---|---|
| RSA-2048 | 2048-bit (256 B public) | 256 B | ~112-bit | β Broken (Shor) | LEGACY |
| RSA-4096 | 4096-bit (512 B public) | 512 B | ~140-bit | β Broken (Shor) | LEGACY |
| ECDH P-256 | 64 B (32 B compressed) | 64 B shared secret | ~128-bit | β Broken (Shor) | TRANSITION |
| X25519 | 32 B | 32 B shared secret | ~128-bit | β Broken (Shor) | TRANSITION |
| ML-KEM-768 (Kyber) | 1184 B public key | 1088 B ciphertext | > 180-bit | β ~168-bit (NIST L3) | RECOMMENDED |
| ML-DSA-65 (Dilithium) | 1952 B public key | 3309 B signature | > 180-bit | β ~168-bit (NIST L3) | RECOMMENDED |
Sources: NIST SP 800-57 Part 1 Rev. 5; FIPS 203 (ML-KEM); FIPS 204 (ML-DSA); NIST PQC Round 3 Report.
Public Key Size Comparison
RSA key sizes dwarf modern alternatives β post-quantum keys are larger than ECC but far smaller than RSA at equivalent security.
Bar lengths scaled to ML-KEM-768 (1184 B) = 100%. RSA-4096 has the same bar width as ML-KEM-768 but provides no post-quantum security.
Shor's Algorithm β Why RSA Will Break
- Classical factoring: Best classical algorithm (GNFS) runs in sub-exponential time β 264 operations for RSA-2048. Secure against classical computers.
- Shor's algorithm: Reduces factoring to order-finding in polynomial time. Requires a fault-tolerant quantum computer with ~4,000 logical qubits for RSA-2048.
- 2026 timeline: No quantum computer currently capable of breaking RSA-2048. But "harvest now, decrypt later" β adversaries store encrypted traffic today to decrypt with future hardware.
- Migration urgency: NIST published FIPS 203/204/205 in August 2024. Systems with >10-year security requirements should migrate now.