TOP secret!

Introduction

In this post, I’ll walk you through solving a fun cryptography CTF challenge I tackled recently in the Dreamhack plataform. It’s a clever combo of RSA encryption and a Vigenère cipher. The key insight? Not everything is as secure as it seems—especially when secrets are tiny.

In this challenge we get a public RSA key (N and e=5) and two ciphertexts: enc1 (Vigenère-encrypted FLAG) and enc2 (RSA-encrypted 4-byte key). No flag file or server interaction needed—just pure analysis.

By the end, you’ll see how to think through hybrid ciphers: break it down, spot weaknesses, and exploit them step by step. Let’s dive in!

The Challenge Setup

The provided Python code generates the challenge like this:

• A random 4-byte key is created (key = random.randbytes(4)).
• The FLAG (e.g., from open("flag", "rb").read()) is encrypted with a Vigenère cipher using the key. Vigenère here is a simple stream cipher: for each byte msg[i], compute (msg[i] + key[i % 4]) % 256. The result is converted to a long integer (enc1 = bytes_to_long(encrypted_bytes)).
• The key (as an integer) is then RSA-encrypted: enc2 = pow(key_long, 5, N), where N is a 2048-bit modulus from two 1024-bit primes (p and q), and e=5.
• Outputs: e=5, N (huge number), enc1 (FLAG ciphertext), enc2 (key ciphertext).

Sample values (from my instance):

• e = 5
• N = 24778450034785355796150191255487074823099958164427517612668815658468206009158475774203229828058652831641389747402272728790787685762568229069520469756247804941312947307153713830371750706901868389560472732254665749033734649996443767231968425511092244591774647092925931126950380935008196052393893271837275626174525444417778170526468251066473481105512939105882134615031671691748551289394109269703632798650982887859648332846094423809290782207835604174269463315884480062803289020119565250762542625596177768616201281918850432872639983965071018579891448754659608103400036049016809640134053891855019010729470727777892901808607
• enc1 = 25889043021335548821260878832004378483521260681242675042883194031946048423533693101234288009087668042920762024679407711250775447692855635834947612028253548739678779
• enc2 = 332075826660041992234163956636404156206918624

So the goal: is to recover the FLAG from enc1 using the key hidden in enc2.

Step-by-Step Thinking: How I Approached It

Step 1: Understand the Ciphers (Break Down the Code)

• Vigenère Part: This is XOR-like but addition mod 256: enc_byte = (plain_byte + key_byte) % 256. The key repeats every 4 bytes and the decryption is trivial: plain_byte = (enc_byte - key_byte) % 256.
• RSA Part: Standard textbook RSA with e=5 (small exponent). Normally, we’d need to factor N (2048-bit, impossible in time) or find d (private key). But the plaintext is the 4-byte key (< 2³² ≈ 4.3 billion), so key^5 is tiny: < 2¹⁶⁰ (about 48 digits). N is ~617 digits, so enc2 = key^5 mod N = key^5 exactly—no wrap-around! This means we can recover the key by computing the integer 5th root of enc2.
• Key Insight: The small key size is the vulnerability. No need to factor N or use Coppersmith’s attack—direct root extraction works because the math “leaks” the plaintext.

Why think this way? Always estimate sizes: log2(enc2) ≈ 138 bits (from its value), so 5th root ≈ 138/5 ≈ 27.6 bits (< 2²⁸, well under 2³²). Feasible to brute-force or search.

Step 2: Verify Assumptions (Size Checks and Modular Arithmetic)

• Confirm key^5 < N: enc2 has 42 digits; N has 617.
• Vigenère output: enc1 is a long from bytes, so convert back to bytes: length ≈ bit_length(enc1)/8 ≈ 31 bytes (short FLAG, typical for CTFs).
• Edge cases: FLAG might have leading zeros (handled by big-endian byte conversion). Key is exactly 4 bytes, padded if needed.

If assumptions fail? Test with small numbers: e.g., key=123, enc2=123^5=2717383423 (small), root works.

Step 3: Plan the Attack

1. Extract key: Find integer k where k^5 = enc2 (binary search for efficiency, since k < 2³²).
2. Convert k to 4 bytes (big-endian).
3. Convert enc1 to bytes.
4. Decrypt byte-by-byte: Subtract repeating key mod 256.
5. Output as string (expect ASCII flag like ctf{...}).

Time complexity: Binary search is O(log(2³²)) = 32 steps, instant.

Step 4: Handle Potential Pitfalls (Debugging Mindset)

• Float precision for roots? Use integer binary search first; fallback to enc2 ** (1/5) and check nearby integers.
• Imports: Needs pycryptodome for long_to_bytes.
• Verification: Always check k^5 == enc2 post-recovery.

Implementation: The Solver Code

Here’s the full Python solver. It’s standalone, and includes comments for clarity. Run with Python 3 (e.g., py -3 solver.py on Windows).

# solver.py - RSA-Vigenère CTF Solver
# Hardcoded values from the challenge

enc1 = 25889043021335548821260878832004378483521260681242675042883194031946048423533693101234288009087668042920762024679407711250775447692855635834947612028253548739678779
enc2 = 332075826660041992234163956636404156206918624
N = 24778450034785355796150191255487074823099958164427517612668815658468206009158475774203229828058652831641389747402272728790787685762568229069520469756247804941312947307153713830371750706901868389560472732254665749033734649996443767231968425511092244591774647092925931126950380935008196052393893271837275626174525444417778170526468251066473481105512939105882134615031671691748551289394109269703632798650982887859648332846094423809290782207835604174269463315884480062803289020119565250762542625596177768616201281918850432872639983965071018579891448754659608103400036049016809640134053891855019010729470727777892901808607
e = 5

def find_fifth_root(n):
    """Binary search for k where k^e == n (e=5, k < 2^32)."""
    low = 0
    high = 2**32  # Max 4-byte key
    while low <= high:
        mid = (low + high) // 2
        pow_mid = mid ** 5
        if pow_mid == n:
            return mid
        elif pow_mid < n:
            low = mid + 1
        else:
            high = mid - 1
    # Fallback: Float approx + nearby check (handles precision quirks)
    approx = int(n ** (1 / 5) + 0.5)
    for candidate in range(max(0, approx - 10), approx + 11):
        if candidate ** 5 == n:
            return candidate
    raise ValueError(f"No exact 5th root for {n}!")

# Step 1: Recover key (5th root of enc2)
key_long = find_fifth_root(enc2)
print(f"Recovered key (int): {key_long}")

# Step 2: To 4 bytes (fallback if no Crypto lib)
try:
    from Crypto.Util.number import long_to_bytes
    key_bytes = long_to_bytes(key_long, 4)
except ImportError:
    key_bytes = key_long.to_bytes(4, 'big')
print(f"Key bytes (hex): {key_bytes.hex()}")

# Step 3: enc1 to bytes
byte_length = (enc1.bit_length() + 7) // 8
enc_bytes = enc1.to_bytes(byte_length, 'big')
print(f"Enc bytes length: {len(enc_bytes)}")

# Step 4: Decrypt Vigenère
dec_bytes = bytearray()
key_len = len(key_bytes)  # 4
for i in range(len(enc_bytes)):
    dec_byte = (enc_bytes[i] - key_bytes[i % key_len]) % 256
    dec_bytes.append(dec_byte)

flag = bytes(dec_bytes)
print(f"FLAG (bytes): {flag}")

# Decode if ASCII
try:
    print(f"FLAG (str): {flag.decode('ascii')}")
except UnicodeDecodeError:
    print("Non-ASCII; check bytes.")

# Verify
print(f"Verify (key^5 == enc2): {key_long ** 5 == enc2}")

What I Learned: Crypto CTF Takeaways

• Size Matters: Small plaintexts + small exponents = leaks. Always check if m^e < N.

• Hybrid Attacks: Separate the ciphers—solve the easy one (Vigenère) after unlocking the hard one (RSA via weakness).

• Tools: Binary search > brute-force for roots. Python’s bigints handle everything natively.

• Common Pitfalls: Float roots can be imprecise for large numbers; stick to integers. Test assumptions with toy examples.

• Tip: Install pycryptodome (pip install pycryptodome) for utils, but know fallbacks—CTFs run on minimal envs.

This challenge served as an excellent reminder that cryptography is about analyzing entire systems, not just isolated algorithms. Coming from a web CTF background, this systems-thinking approach was initially challenging to adapt to, but it was incredibly rewarding to work through the problem and achieve a successful solution.