RSA attack playbook for CTF and real-world cryptanalysis. Use when given RSA parameters (n, e, c) and need to recover plaintext by exploiting weak keys, small exponents, shared factors, or padding oracles.

SKILL: RSA Attack Techniques — Expert Cryptanalysis Playbook AI LOAD INSTRUCTION : Expert RSA attack techniques for CTF and authorized security assessments. Covers factorization attacks, small exponent exploits, lattice based approaches (Wiener/Boneh Durfee/Coppersmith), broadcast attacks, common modulus, padding oracles, and fault attacks. Base models often suggest attacks that don't match the given parameters or miss the correct attack selection based on what's known. 0. RELATED ROUTING [lattice crypto attacks](../lattice crypto attacks/SKILL.md) for deep lattice theory behind Coppersmith/Boneh Durfee [hash attack techniques](../hash attack techniques/SKILL.md) when RSA signature forgery involves hash weaknesses [symmetric cipher attacks](../symmetric cipher attacks/SKILL.md) when RSA protects a symmetric key (hybrid encryption) Advanced Reference Also load [RSA ATTACK CATALOG.md](./RSA ATTACK CATALOG.md) when you need: Detailed SageMath/Python implementation for each attack Step by step mathematical derivation Edge cases and failure conditions per attack Quick attack selection Given / Observable Attack Tool Small n (< 512 bits) Direct factorization factordb, yafu, msieve e = 3, small message Cube root gmpy2.iroot Multiple (n, c) same small e Hastad broadcast CRT + iroot Very large e or very small d Wiener / Boneh Durfee SageMath, RsaCtfTool Partial p knowledge Coppersmith small roots SageMath Same n, different e Common modulus Extended GCD Multiple n values Batch GCD (shared factor) Python/SageMath Padding error oracle Bleichenbacher Custom script LSB parity oracle LSB oracle attack Custom script Fault in CRT computation RSA CRT fault Single faulty signature 1. FACTORIZATION ATTACKS 1.1 Direct Factorization (Small n) When : n < ~512 bits, or known to be in factordb. 1.2 Fermat's Factorization Works when p and q are close together: p q is small. 1.3 Pollard's p 1 Works when p 1 has only small prime factors (B smooth). 1.4 Batch GCD (Multiple n share a factor) 2. SMALL EXPONENT ATTACKS 2.1 Cube Root Attack (e = 3, small m) If m^e < n (no modular reduction occurred), simply take the e th root. 2.2 Hastad Broadcast Attack Same message encrypted with same small e under different moduli (n₁, n₂, ..., nₑ). 2.3 Related Message Attack (Franklin Reiter) Two messages related by a known linear function: m₂ = a·m₁ + b. Same n and e. 3. LARGE e / SMALL d ATTACKS 3.1 Wiener's Attack (Continued Fractions) When d < n^(1/4) / 3, the continued fraction expansion of e/n reveals d. 3.2 Boneh Durfee Attack (Lattice Based) Extends Wiener: works when d < n^0.292. Uses lattice reduction (LLL/BKZ). Use SageMath implementation — see [lattice crypto attacks](../lattice crypto attacks/SKILL.md) for theory. 4. COPPERSMITH'S METHOD 4.1 Stereotyped Message Known portion of plaintext, unknown part is small. 4.2 Partial Key Exposure Known MSB or LSB of p → recover full p via Coppersmith. 5. COMMON MODULUS ATTACK Two ciphertexts of same message under same n but different e₁, e₂ where gcd(e₁, e₂) = 1. 6. ORACLE ATTACKS 6.1 LSB Oracle (Parity Oracle) An oracle reveals whether decrypted message is even or odd. 6.2 Bleichenbacher (PKCS 1 v1.5 Padding Oracle) Given a padding validity oracle (valid/invalid PKCS 1 v1.5), iteratively narrow down the plaintext range. Complexity : O(2^16) oracle queries per byte on average. Target : TLS implementations returning different errors for valid/invalid padding. 6.3 Manger's Attack (PKCS 1 OAEP) Similar to Bleichenbacher but for OAEP padding. Exploits oracle that distinguishes whether the first byte after unpadding is 0x00. 7. RSA CRT FAULT ATTACK If RSA CRT signing produces a faulty signature (fault in one CRT half): 8. DECISION TREE 9. TOOLS Tool Purpose Usage RsaCtfTool Automated RSA attack suite python3 RsaCtfTool.py publickey pub.pem uncipherfile flag.enc SageMath Mathematical computation Coppersmith, lattice attacks, polynomial arithmetic factordb.com Online factor database Check if n is already factored yafu Fast factorization (SIQS/GNFS) yafu "factor(n)" msieve GNFS factorization Large n factorization gmpy2 Fast Python integer library iroot , invert , gcd pycryptodome RSA primitives Key construction from factors RsaCtfTool Quick Commands Decrypt After Factoring

rsa-attack-techniques