Writeup: The Riddler’s Cipher Delight - ApoorvCTF (Crypto)

Challenge Description

"The Riddler never settles for a single puzzle... why should you? Layers of encryption guard the flag, each hiding some secret. Break through them one by one and prove that even the Riddler's cleverest traps can be unraveled."

We are given a Python script enc.py that encrypts a flag using RSA with a suspiciously small public exponent.

Source Code Analysis

from Crypto.Util.number import *

e = 3

while True:
    p = getPrime(1024)
    q = getPrime(1024)
    N = p * q
    phi = (p - 1) * (q - 1)
    if GCD(phi, e) == 1:
        break

d = inverse(e, phi)

with open("flag.txt", "rb") as f:
    m = bytes_to_long(f.read())

assert m < N

c = pow(m, e, N)

The script generates a standard 2048-bit RSA modulus from two 1024-bit primes and encrypts the flag. The given parameters are:

Identifying the Vulnerability

The public exponent e = 3 is dangerously small. In RSA, encryption computes:

c = m^e mod N

When e is very small and the plaintext message m is relatively short, a critical condition arises:

m³ < N

When this holds, the modular reduction in c = m³ mod N never actually activates — the ciphertext c is simply m³ computed over the integers. This means we can recover the plaintext by computing the exact integer cube root of c, completely bypassing the need to factor N.

Solution

The attack is straightforward: compute the integer cube root of the ciphertext using Newton's method for arbitrary-precision integer root extraction.

def iroot(n, k):
    """Integer k-th root via Newton's method"""
    if n == 0:
        return 0, True
    x = 1 << ((n.bit_length() + k - 1) // k)
    while True:
        y = ((k - 1) * x + n // (x ** (k - 1))) // k
        if y >= x:
            break
        x = y
    return x, x ** k == n

N = 17520886769422446781402845171452766678392945055507226042115591127790949038926405961588057901152880775198538951363849458511296788407527886190154759113620716962246342938913740398465525503895457929394994569820769711534794538522137993456194572001467194513826600891537022249206765745867423270603572791751504625621683522248065102814089587644651305112722919320696919194544558237008950904152753314856531469392976852299194227815343105809059455186267184706498969875531092067425496067267400027976328334687257293407409892934030446988318349271430705178690957392508571214791220858911022252486038830213798547638612103672306741523579
e = 3
c = 5959848254333830910624523071067197529743942832931749422613446095759596470869632698744448445022974243192082623200541274049999046045462632699888118125553180389758240097512080800465269924123706310996597928101365256237876736940573969864179631586328876422479408805381027940806738410297399027560825960052951200511768291312433697743253773594534719688371211151318607767527029263892621127356788516738086153844247429662752321125

m, is_exact = iroot(c, 3)
assert is_exact  # Confirms m^3 == c exactly (no modular wrap)

flag = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print(flag)

The cube root is exact on the first attempt — no need to search through c + k*N offsets. This confirms that m³ < N and the modular reduction was never triggered.

Flag

apoorvctf{3ncrypt1ng_w1th_RSA_c4n_b3_4_d4ng3r0us_cl1ff_83}

Key Takeaways

1. Never use e = 3 without padding. Small exponents make RSA trivially breakable when the plaintext is short relative to the modulus. The standard minimum is e = 65537.
2. Always use OAEP padding. PKCS#1 OAEP adds randomized padding that ensures m^e always exceeds N, preventing cube root and related attacks.
3. Textbook RSA is insecure. This challenge demonstrates why raw RSA (without padding) should never be used in practice — even with proper key sizes, the scheme crumbles with a bad exponent choice.