This challenge looks like a normal hybrid cryptosystem: RSA protects an AES key, and AES protects the flag. But the way the AES key is generated introduces a structure that completely breaks the security. The attack is a neat combination of RSA’s multiplicative property and a meet-in-the-middle strategy.
class RSAGen:
def __init__(self, bits):
self.bits = bits
def keygen(self):
p = getPrime(self.bits//2)
q = getPrime(self.bits//2)
self.n = p*q
self.e = 0x10001
phi = (p-1)*(q-1)
self.d = pow(self.e, -1, phi)
return (self.n, self.e), (p, q, phi, self.d)
def encrypt(self, m):
return pow(m, self.e, self.n)
def decrypt(self, c):
return pow(c, self.d, self.n)
This is a totally standard 1024-bit RSA implementation:
We are only given the public key (n, e), not p, q, d, and we will not factor n at all.
class AESGen:
def __init__(self, size):
key1 = randint(1 << size, 1 << (size+1))
key2 = randint(1 << size, 1 << (size+1))
self.k = key1 * key2
assert 40 <= self.k.bit_length() <= 42
self.KEY = sha256(str(self.k).encode()).digest()
def encrypt(self, m):
cipher = AES.new(self.KEY, AES.MODE_ECB)
enc_secret = cipher.encrypt(pad(m, 16))
return enc_secret
Here, the AES key is derived in an unusual way:
key1, key2 are chosen uniformly from
[2^{20}, 2^{21}], so about a million possibilities each.k = key1 * key2 is a 40–42 bit integer.KEY = SHA256(str(k)), a 256-bit key.
So the true security of the AES key is bounded by ~40–42 bits of entropy in k,
not by 256 bits.
def main():
rsa = RSAGen(1024)
aes = AESGen(20)
pubkey, _ = rsa.keygen()
enc_aes_key = l2b(rsa.encrypt(aes.k))
enc_secret = aes.encrypt(FLAG)
with open('output.txt', 'w') as f:
f.write("Bob :: Hi Alice, here is my public key:\n")
f.write(f"({pubkey[0]}, {pubkey[1]})\n")
f.write("Alice :: Hi Bob, here is my encrypted AES key, don't forget to sha256-hash it!\n")
f.write(f"Encrypted AES Key = {enc_aes_key.hex()}\n")
f.write("Bob :: Got it, here is the encrypted secret you requested:\n")
f.write(f"Encrypted Secret = {enc_secret.hex()}")
The challenge gives us:
Encrypted AES Key = RSA(k) = k^e mod n,Encrypted Secret = AES_KEY(FLAG).We want to recover FLAG without factoring n.
RSA is multiplicatively homomorphic:
Enc(m₁) · Enc(m₂) ≡ (m₁^e mod n) (m₂^e mod n) ≡ (m₁ m₂)^e mod n ≡ Enc(m₁ m₂) (mod n)
In our case:
k = key1 · key2
c = Enc(k) = k^e mod n = (key1 · key2)^e mod n = key1^e · key2^e mod n
Let:
Then the observed ciphertext c satisfies:
c ≡ A · B (mod n).
Rearranging:
B ≡ c · A^{-1} (mod n).
If we know A for some candidate key1, we can compute the corresponding B. If this B equals key2^e mod n for some valid key2, we have found the pair (key1, key2).
k is a 40–42 bit integer, so the naive search space is about:
2^{40} to 2^{42} ≈ 10^{12} possibilities.
For each candidate k, we would check whether k^e mod n = c. That’s too large for a typical CTF.
Instead, we know:
That suggests a meet-in-the-middle approach:
Time complexity becomes roughly:
O(2^{20}) + O(2^{20}) ≈ O(2^{21})
Instead of O(2^{40}). This is easily feasible.
table[v] = k2.table,
retrieve k₂ = table[B_target].At this point, we have found a pair (key1, key2) such that:
key1^e · key2^e ≡ c (mod n) ⇒ (key1·key2)^e ≡ c (mod n).
So k = key1 · key2 is the correct AES pre-key.
KEY = sha256(str(k).encode()).digest()FLAG.d, nor do we factor n.
The attack purely uses the public key, the ciphertext c = RSA(k), and the fact that
k lies in a small, structured subset of integers.
Below is a self-contained Python script that:
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from hashlib import sha256
# ====== Given RSA public key and ciphertexts ======
n = 72741423208033405403492275698762968936514657314823442485453559870105200118330405900858299998747406127848670334407387228444029070060538220448699667905891284937839901536444798774307744865631349770845980738192442639071823803272283670943732769371979418893953521892212745135191661138195973757608889180051128601323
e = 65537
enc_aes_key_hex = "4da0230d2b8b46e3a7065f32c46df019739cc002a208cc37767a82c3e94edfc3440fa4b24a32274e35d5ddceaa33505c4f2a57281c3a5d6d4db3a0dbdbb30dbf373241319ce4a7fdd1780b6bafc86e37d283c9f9787c567434e2fc29c988fb05fd411fe4453ea40eb45fc41a423839b485e238dd2530fba284e9b07a0bba6546"
enc_secret_hex = "ce8f36aa844ab00319bcd4f86460a10d77492c060b2c2a91615f4cd1f2d0702e76b68f1ec0f11d15704ba52c5dacc60018d5ed87368464acd030ce6230efdbff7b18cba72ccaa9455a6fe6021b908dd1"
c = int(enc_aes_key_hex, 16)
# ====== key1, key2 range ======
LOW = 1 << 20
HIGH = 1 << 21 # randint upper bound is inclusive in original code
print(f"[+] Searching key1, key2 in [{LOW}, {HIGH}]")
# ====== Step 1: Build table for key2^e mod n ======
print("[+] Building table for key2^e mod n ...")
val_to_key2 = {}
for k2 in range(LOW, HIGH + 1):
v = pow(k2, e, n)
val_to_key2[v] = k2
print("[+] Table built. Entries:", len(val_to_key2))
# ====== Step 2: Loop over key1 and match ======
print("[+] Searching for matching key1, key2 ...")
found = False
key1 = key2 = None
for k1 in range(LOW, HIGH + 1):
A = pow(k1, e, n)
invA = pow(A, -1, n) # modular inverse of A mod n
target = (c * invA) % n # should equal key2^e mod n
if target in val_to_key2:
key1 = k1
key2 = val_to_key2[target]
found = True
print("[+] Found candidate!")
print(" key1 =", key1)
print(" key2 =", key2)
break
if not found:
print("[-] No key pair found in range?!")
exit(1)
k = key1 * key2
print("[+] k =", k)
print("[+] bit_length(k) =", k.bit_length())
# ====== Step 3: Derive AES key and decrypt flag ======
KEY = sha256(str(k).encode()).digest()
cipher = AES.new(KEY, AES.MODE_ECB)
plaintext = unpad(cipher.decrypt(bytes.fromhex(enc_secret_hex)), 16)
print("[+] FLAG:", plaintext)
k: ~2^{40–42} candidates (too large).k = key1 * key2:
This is completely feasible in a typical CTF environment, even in pure Python.
In a real system, k should be a uniformly random value with at least 128 bits of entropy,
and the RSA layer should be used in a well-studied KEM–DEM construction, not with ad-hoc key generation.