Farm was a 42 point challenge on CryptoCTF 2022. I missed the CTF and was only able to download this challenge before the servers went down.

Solution

We’re given a ciphertext that’s encoded in what appears to be base64. Taking a look at the keygen function, we see

def keygen(l):
    key = [F[randint(1, 63)] for _ in range(l)] 
    key = prod(key) # Optimization the key length :D
    return key

So the keygen samples elements from the finite field \(\mathbb{F}_{2^6}\) and multiplies them together to form a supposedly larger key. However, multiplication of two field elements just produces another one; in \(\mathbb{F}_{2^6}\) there are only 63 possible keys excluding 0. The keyspace is tiny, so we can just brute force each character in the plaintext character by character with every possible key until we get one that decodes to valid ASCII. The resulting code is super ugly and probably not the best approach, but works:

from sage.all import *
import string, base64, math

ALPHABET = string.printable[:62] + '\\='
F = list(GF(64))
ctext = b"805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj"

def solve(enc):
    candidates = []

    decoded = None
    for key in F[1:]:
        plain = ""
        i = 0
        while i < len(ctext):
            old_i = i
            for char in ALPHABET:
                if encrypt_char(char, key) == chr(ctext[i]):
                    plain += char
                    i += 1
                    break

            if old_i == i:
                break

        candidates += [plain]
    

    for cand in candidates:
        try:
            decoded = base64.b64decode(cand)
            if b"CCTF{" in decoded:
                break
        except:
            continue


    return decoded

def maptofarm(c):
    assert c in ALPHABET
    return F[ALPHABET.index(c)]

def invert(k):
    assert k in F:
    return ALPHABET[F.in]

def encrypt_char(m, key):
    pkey = key**5 + key**3 + key**2 + 1
    return ALPHABET[F.index(pkey * maptofarm(m))]

def keygen(l):
    key = [F[randint(1, 63)] for _ in range(l)] 
    key = prod(key) # Optimization the key length :D
    return key

if __name__ == "__main__":
    res = solve(ctext)
    print(res)

Running it produces the flag CCTF{EnCrYp7I0n_4nD_5u8STitUtIn9_iN_Fi3Ld!}.