rsa_briefing.enc

Challenge Description

We're handed an "RSA encrypted" classified briefing. The file contains: - A plaintext intelligence briefing about asset NIGHTINGALE - An encrypted addendum with parameters: e = 3, n (1024-bit), c

Analysis

Standard RSA encryption: c = m^e mod n

With e = 3 and no padding, if the plaintext m is small enough that m³ < n, then the modular reduction mod n is a no-op: m³ mod n = m³ exactly.

Check: c is only 859 bits. n is 1024 bits. If c = m³ exactly, then m = cbrt(c) with no remainder.

from sympy import integer_nthroot

m, exact = integer_nthroot(c, 3)
print(exact)   # True: no remainder, no factoring needed

exact = True confirms it. Convert the integer back to bytes:

flag = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode('ascii')
# DEADROP{cube_root_attack_e3_classic}

Full Solve

import re
from sympy import integer_nthroot

with open('rsa_briefing.enc') as f:
    raw = f.read()

e = int(re.search(r'^e = (\d+)', raw, re.M).group(1))
n = int(re.search(r'^n = (\d+)', raw, re.M).group(1))
c = int(re.search(r'^c = (\d+)', raw, re.M).group(1))

m, exact = integer_nthroot(c, e)
assert exact, "m^3 >= n, would need Hastad broadcast attack"
print(m.to_bytes((m.bit_length() + 7) // 8, 'big').decode())

Why No Padding Is Fatal

RSA-PKCS#1 and OAEP padding exist specifically to prevent this. Padding randomises m before encryption, ensuring m_padded fills most of the key space and m_padded^e wraps around mod n regardless of e. Without it:

e=3, small m → m^3 < n → trivial cube root
e=3, same message sent to 3 recipients → Hastad's broadcast attack (CRT combines the three ciphertexts to get m^3 over the integers)
e=3, related messages → Franklin-Reiter related message attack

The fix is always the same: use proper padding (OAEP). The choice of e is a secondary concern.

Flag

DEADROP{cube_root_attack_e3_classic}