You got the key to this room?

Challenge Description

You've gained shell access to a quarantined WHAMazon fulfillment node. Buried in their home directory is a Python script and some leftover output. It looks like they were trying to recover a private RSA key fragment and decrypt an internal payload. They didn't finish.

Flag: Raptor{H4lf_0f_N0thiNg_iS_StiLL_H4lf_0F_S0m3thinG}

The Problem

We're given:

n: the RSA modulus
e = 65537: the public exponent (standard)
ciphertext: the encrypted message
partial_d: the private exponent with the last 4 hex characters missing (????)

RSA decryption is m = c^d mod n. We have everything except those 4 missing hex digits of d. CyberChef and dcode.fr can handle standard RSA, but neither will help here, they need a complete key. Since the gap is only 4 hex digits, that's 0x0000 to 0xFFFF: exactly 65,536 possibilities. That's well within brute force range.

The Script

n = 80550153770908870461211679984102584345730019695398818939574910170576443900985943461378573452403260225393899983946914455473552562677308851821047959254135840747168129085690789273544120991474023343924995995760920776019626396242236880333039088126543835688317002169793571794254870439210372791051737961447974514397
e = 65537
ciphertext = 23427690145058979158878379395939850632597943895239191083896884363828698954379797414126438829564451794251190486868562912682796235811729538417613250134005670039832426453894147501487415922546508730967366179652212388643121615470167126444264486857644131595791781298101747244058598877453951008537409760452127164420
partial_d = "a26590e8e191d8ef978b64c9f5092d9775f6ef07fd9e01acc4f20543dec403a755a576a4838947ce691a6bf2ffe39e39cbd4c606e0990c4daa7a52dbecb744e205fe23a95077c8d073ce60493d82224cc70c6bfb26c89c980005e8faf9448a1349f16d6c2908cb2f922e4deba91e0743a112d382b7631ed9c18151a547c"

for missing in range(0x10000):  # 65536 candidates: 0x0000 to 0xffff
    if missing % 1000 == 0:
        print(f"Trying: {missing}/65536...", end='\r')

    full_d_hex = partial_d + format(missing, '04x')  # append candidate as zero-padded hex
    d = int(full_d_hex, 16)

    m = pow(ciphertext, d, n)  # RSA decrypt: m = c^d mod n
    m_bytes = m.to_bytes((m.bit_length() + 7) // 8, 'big')

    try:
        text = m_bytes.decode('ascii')
        if 'Raptor{' in text or (len(text) > 10 and all(32 <= ord(c) <= 126 for c in text)):
            print(f"\nMissing hex: {format(missing, '04x')}")
            print(f"Decrypted: {text}")
            break
    except UnicodeDecodeError:
        pass

What the script is doing, step by step:

1. Iterating all 65,536 candidates. The missing suffix is 4 hex characters, 16 bits, so range(0x10000) covers every possible value. format(missing, '04x') formats each integer as a zero-padded 4-character hex string and appends it to partial_d to reconstruct a candidate full key.

2. RSA decryption. pow(ciphertext, d, n) is Python's built-in modular exponentiation, this computes c^d mod n efficiently even for the enormous numbers involved. This is raw textbook RSA with no padding, exactly as the notes warned.

3. Converting the result to bytes. m.to_bytes((m.bit_length() + 7) // 8, 'big') converts the decrypted integer into a big-endian byte string. The (bit_length + 7) // 8 expression calculates the minimum number of bytes needed to hold the value.

4. Checking for valid plaintext. We try to decode the bytes as ASCII, then check whether the result either contains Raptor{ (the known flag format, our crib) or looks like general printable ASCII (length > 10, all characters in the printable range 32-126). Any wrong key will produce garbage bytes that fail both checks. The correct key produces our flag.

Output

Trying: 26000/65536...

Missing hex: 6741
Decrypted: Raptor{H4lf_0f_N0thiNg_iS_StiLL_H4lf_0F_S0m3thinG}

The missing suffix was 6741, found at iteration 26,000 out of a possible 65,536.

Key Takeaways

This challenge demonstrates that partial key recovery can be enough. A partial private exponent leak might seem survivable, after all, most of the key is still unknown, but if the unknown portion is small enough to brute force, the entire key is compromised. The relationship between key size and attack feasibility is why 4 missing hex digits (16 bits of entropy) is catastrophic while the full 2048-bit key would be untouchable.

The known flag format Raptor{ acted as a crib again, exactly like in Crypto 1, when you know any property of the expected plaintext, you can turn decryption into a verification step and brute force becomes viable.