Corrupt-Key-1 — RSA Key Recovery via FactorDB

Analysis

Examining the corrupted key reveals: Modulus (n) intact at 1024-bit, public exponent e = 65537 intact. Private exponent (d), prime2 (q), and all CRT parameters are zeroed out. Prime1 (p) has partial data followed by zeros.

Without p and q, d cannot be computed from (n, e) — this is the entire security of RSA. The only option: factorize n.

Solution: FactorDB

1024-bit RSA is considered weak. The modulus was already factored in FactorDB (status: FF — fully factored).

p = 107258024031135001609...25503110781
q = 120985208645981987572...47051090363
assert p * q == n

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
key = RSA.construct((n, e, d, p, q))

cipher = PKCS1_v1_5.new(key)
plaintext = cipher.decrypt(ciphertext, None)

Key Insights

• RSA security relies entirely on factorization difficulty
• 1024-bit RSA is no longer secure
• Public databases like FactorDB are extremely powerful in CTFs
• Private keys cannot be partially fixed

Flag