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.
Standardmäßig ist der Prompt ausgewählt, der zuerst die Quelle prüft. Sie können zu einem direkten Befehl wechseln oder eine lokale Kopie herunterladen.
Quelldateien prüfen
Lesen Sie SKILL.md und alle von SkillsMP angezeigten Begleitdateien, bevor Sie sich für eine Installation entscheiden.
Mit Codex oder Claude installieren Kopieren Sie diesen Prompt, fügen Sie ihn in Codex, Claude oder einen anderen Assistant ein und lassen Sie die Skill-Seite prüfen und installieren.
Ein direkter Befehl überspringt den Prüf-Prompt. Prüfen Sie die Quelle, bevor Sie ihn ausführen.
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.
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.
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)
from sympy import factorint
n = 0x... # small modulus
factors = factorint(n)
p, q = list(factors.keys())
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.
from gmpy2 import isqrt, is_square
deffermat_factor(n):
a = isqrt(n) + 1whileTrue:
b2 = a * a - n
if is_square(b2):
b = isqrt(b2)
return (a + b, a - b)
a += 1
1.3 Pollard's p-1
Works when p-1 has only small prime factors (B-smooth).
from gmpy2 import gcd
defpollard_p1(n, B=2**20):
a = 2for j inrange(2, B):
a = pow(a, j, n)
d = gcd(a - 1, n)
if1 < d < n:
return d
returnNone
1.4 Batch GCD (Multiple n share a factor)
from math import gcd
from functools import reduce
defbatch_gcd(moduli):
"""Find shared factors among multiple RSA moduli."""
product = reduce(lambda a, b: a * b, moduli)
results = {}
for i, n inenumerate(moduli):
remainder = product // n
g = gcd(n, remainder)
if g != 1and g != n:
results[i] = (g, n // g)
return results
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.
from gmpy2 import iroot
c = 0x... # ciphertext
e = 3
m, exact = iroot(c, e)
if exact:
print(f"Plaintext: {bytes.fromhex(hex(m)[2:])}")
2.2 Hastad Broadcast Attack
Same message encrypted with same small e under different moduli (n₁, n₂, ..., nₑ).
from sympy.ntheory.modular import crt
from gmpy2 import iroot
# e = 3, three ciphertexts under three different n
n_list = [n1, n2, n3]
c_list = [c1, c2, c3]
# CRT: find x such that x ≡ ci (mod ni) for all i
r, M = crt(n_list, c_list)
m, exact = iroot(r, 3)
assert exact
2.3 Related Message Attack (Franklin-Reiter)
Two messages related by a known linear function: m₂ = a·m₁ + b. Same n and e.
# SageMathdeffranklin_reiter(n, e, c1, c2, a, b):
R.<x> = PolynomialRing(Zmod(n))
f1 = x^e - c1
f2 = (a*x + b)^e - c2
return Integer(n - gcd(f1, f2).coefficients()[0])
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.
defwiener_attack(e, n):
"""Recover d when d is small via continued fractions."""
cf = continued_fraction(e, n)
convergents = get_convergents(cf)
for k, d in convergents:
if k == 0:
continue
phi_candidate = (e * d - 1) // k
# phi(n) = n - p - q + 1 → p + q = n - phi + 1
s = n - phi_candidate + 1# p, q are roots of x^2 - s*x + n = 0
discriminant = s * s - 4 * n
if discriminant >= 0:
from gmpy2 import isqrt, is_square
if is_square(discriminant):
return d
returnNonedefcontinued_fraction(a, b):
cf = []
while b:
cf.append(a // b)
a, b = b, a % b
return cf
defget_convergents(cf):
convergents = []
h_prev, h_curr = 0, 1
k_prev, k_curr = 1, 0for a in cf:
h_prev, h_curr = h_curr, a * h_curr + h_prev
k_prev, k_curr = k_curr, a * k_curr + k_prev
convergents.append((h_curr, k_curr))
return convergents
3.2 Boneh-Durfee Attack (Lattice-Based)
Extends Wiener: works when d < n^0.292. Uses lattice reduction (LLL/BKZ).
Known portion of plaintext, unknown part is small.
# SageMath
n = ...
e = 3
c = ...
known_prefix = b"flag{" + b"\x00" * 27# known prefix, unknown suffix
known_int = int.from_bytes(known_prefix, 'big')
R.<x> = PolynomialRing(Zmod(n))
f = (known_int + x)^e - c
roots = f.small_roots(X=2^(27*8), beta=1.0)
if roots:
m = known_int + int(roots[0])
print(bytes.fromhex(hex(m)[2:]))
4.2 Partial Key Exposure
Known MSB or LSB of p → recover full p via Coppersmith.
# SageMath — known MSB of p
p_msb = ... # known upper bits of p
R.<x> = PolynomialRing(Zmod(n))
f = p_msb + x
roots = f.small_roots(X=2^unknown_bits, beta=0.5)
if roots:
p = p_msb + int(roots[0])
q = n // p
5. COMMON MODULUS ATTACK
Two ciphertexts of same message under same n but different e₁, e₂ where gcd(e₁, e₂) = 1.
from gmpy2 import gcd, invert
defcommon_modulus(n, e1, e2, c1, c2):
"""Recover m when same message encrypted with two different e under same n."""assert gcd(e1, e2) == 1
_, s1, s2 = extended_gcd(e1, e2) # s1*e1 + s2*e2 = 1if s1 < 0:
c1 = invert(c1, n)
s1 = -s1
if s2 < 0:
c2 = invert(c2, n)
s2 = -s2
m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
return m
defextended_gcd(a, b):
if a == 0:
return b, 0, 1
g, x, y = extended_gcd(b % a, a)
return g, y - (b // a) * x, x
6. ORACLE ATTACKS
6.1 LSB Oracle (Parity Oracle)
An oracle reveals whether decrypted message is even or odd.
from gmpy2 import mpz
deflsb_oracle_attack(n, e, c, oracle_func):
"""Decrypt using LSB (parity) oracle. oracle_func(c) returns m%2."""from fractions import Fraction
lo, hi = Fraction(0), Fraction(n)
for _ inrange(n.bit_length()):
c = (c * pow(2, e, n)) % n # multiply plaintext by 2if oracle_func(c) == 0:
hi = (lo + hi) / 2else:
lo = (lo + hi) / 2returnint(hi)
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):
defrsa_crt_fault(n, e, correct_sig, faulty_sig, msg):
"""Factor n from one correct and one faulty CRT signature."""from math import gcd
diff = pow(correct_sig, e, n) - pow(faulty_sig, e, n)
p = gcd(diff % n, n)
if1 < p < n:
q = n // p
return p, q
returnNone# Even simpler: only faulty signature needed if message is knowndefrsa_crt_fault_simple(n, e, faulty_sig, msg):
p = gcd(pow(faulty_sig, e, n) - msg, n)
if1 < p < n:
return p, n // p
returnNone
8. DECISION TREE
RSA challenge — what information do you have?
│
├─ Have n and it's small (< 512 bits)?
│ └─ Factor directly: factordb.com → yafu → msieve
│
├─ Have multiple n values?
│ └─ Batch GCD — shared factors?
│ ├─ Yes → factor all that share factors
│ └─ No → analyze each n individually
│
├─ Know e?
│ ├─ e = 3 (or small)?
│ │ ├─ Single ciphertext, small message → cube root
│ │ ├─ Multiple ciphertexts, different n → Hastad broadcast
│ │ ├─ Two related messages → Franklin-Reiter
│ │ └─ Partial plaintext known → Coppersmith
│ │
│ ├─ e is very large?
│ │ └─ d is likely small → Wiener → Boneh-Durfee
│ │
│ └─ Same n, two different e values?
│ └─ Common modulus attack (Bezout coefficients)
│
├─ Know partial factorization info?
│ ├─ Know some bits of p → Coppersmith partial key
│ ├─ p-1 is B-smooth → Pollard p-1
│ └─ p ≈ q (close primes) → Fermat factorization
│
├─ Have an oracle?
│ ├─ Parity oracle (LSB) → LSB oracle attack
│ ├─ Padding validity oracle (PKCS#1 v1.5) → Bleichenbacher
│ └─ OAEP oracle → Manger's attack
│
├─ Have faulty signature?
│ └─ RSA-CRT fault → factor n from faulty sig
│
├─ Know e·d relationship?
│ └─ e·d ≡ 1 mod φ(n) → factor n from (e,d,n)
│
└─ None of the above?
├─ Check factordb for known factorization
├─ Try Pollard rho for medium-size n
├─ Look for implementation flaws (weak PRNG for key generation)
└─ Consider side-channel if physical access available
