Suspicious Caesar (crypto)

PUBLISHED ON 21/12/2020 — EDITED ON 11/12/2023 — 247CTF, INFOSEC


A new challenge appeared on the site and here is my little write-up.

As it happens this was again sweet, sweet first blood!


We RSA encrypted the flag, but forgot to save the private key. Is it possible to recover the flag without it?

The code

The challenge provides a source code for the encryption

#!/usr/bin/env python3
from Crypto.Util.number import getStrongPrime
from fractions import gcd
from secret import flag

def get_key(e=65537, bit_length=2048):
    while True:
        p = getStrongPrime(bit_length, e=e)
        q = getStrongPrime(bit_length, e=e)
        if gcd(e, (p - 1) * (q - 1)) == 1:
            return e, p * q

def encrypt(e, n, m):
    return [((ord(c) ** e) % n) for c in m]

e, n = get_key()

print("Generated key:")

print("Encrypted flag:")
print(encrypt(e, n, flag))

Included is also the output of the script suspicious_caesar_cipher.out. Unfortunately running the script quickly reveals, that the secret library is missing, so we can’t just execute the script and win.


To exploit the problem, we will modify the existing code.

We know e, n, encription algorythm and encrypted flag data from the output file. So we can reuse the available data and encryption algorythm to encrypt all the possible singlecharacters and then check the encrypted data against them.

#!/usr/bin/env python3

# Read the provided output file and define a list of possible characters
filename = "suspicious_caesar_cipher.out"
possible_chars = "0123456789abcdef{}CTF"

# encrypt function taken from provided script
def encrypt(e, n, m):
    return [((ord(c) ** e) % n) for c in m]

# Read all the data from the provided output file (e, n, encrypted flag)
with open(filename) as f:
    content = f.readlines()

e = int(content[1])
n = int(content[2])

encrypted_data = content[4].replace("L","").replace("[","").replace("]","").replace("\n","")
encrypted_data = encrypted_data.split(', ')
enc_data = list(map(int, encrypted_data))

# Create a dictionary (translation table) by encrypting all possible characters
code_table = {}
for c in possible_chars:
    crypted = int(encrypt(e, n, c)[0])
    code_table[crypted] = c

# Check each entry in encrypted flag for corresponding char in code_table
for i in encrypted_data:
    print(code_table.get(int(i)), end = '')