Affine‑Hill Cipher Challenge

Challenge Overview

We are presented with a custom Affine‑Hill Cipher that operates on blocks of 4 characters over an alphabet of size 37:

Alphabet: abcdefghijklmnopqrstuvwxyz0123456789-
Block size: m = 4
Each plaintext block (P \in \mathbb{Z}_{37}^4) is transformed into ciphertext block (C) by:

[ C = P \cdot K + b \pmod{37} ]

(K) is a (4 \times 4) matrix (16 entries)
(b) is a 4‑vector
The key is encoded as a 20‑character keyword: the first 16 characters (row‑wise) form (K), the last 4 form (b).

We are given:

The full padded plaintext (from output.txt)
Two ciphertexts, each generated with a different key (key1 and key2).

Our goal is to recover both keywords.

The Known‑Plaintext Attack

Because we have the exact plaintext and the corresponding ciphertexts, we can set up a system of linear equations over (\mathbb{F}_{37}) and solve for the unknown entries of (K) and (b).

For each block (i) (there are 15 blocks, since the plaintext length is 60 characters), we have:

[ \sum_{k=0}^3 P_i[k] \cdot K[k][j] + b[j] = C_i[j] \pmod{37}, \quad j = 0,1,2,3 ]

For each output column (j), the unknowns are (K[0][j], K[1][j], K[2][j], K[3][j], b[j]) – that’s 5 unknowns.
We have 15 equations per column, so the system is overdetermined but solvable by Gaussian elimination over (\mathbb{F}_{37}).

Python Solver

The following script reads the padded plaintext and both ciphertexts, constructs the linear equations for each key independently, solves for each column, and reconstructs the keywords.

# solve_affine_hill.py
from math import ceil

alphabet = class="hljs-string">"abcdefghijklmnopqrstuvwxyz0123456789-"
idx = {c: i for i, c in enumerate(alphabet)}
l = 37
m = 4

# Data from output.txt (first 60 chars of each ciphertext)
pt = class="hljs-string">"b3w4reofbugs1ntheab0vec0de-ih4ve0nlyprov3ditc0rrectnottr13dit---"[:60]
ct1 = class="hljs-string">"x3etd0vgd7z9v6bld4ba7p94s0acp-bvfjjfywypdkzuwsgah4shanrdaop4"[:60]
ct2 = class="hljs-string">"odbewk453xyc3210-mlqxley8loydmzgy0k6ok4i9qjcwx42om5au1-hqqkr"[:60]

def to_blocks(s):
    return [[idx[ch] for ch in s[i:i+4]] for i in range(0, len(s), 4)]

P = to_blocks(pt)
C1 = to_blocks(ct1)
C2 = to_blocks(ct2)

# Gaussian elimination over GF(37)
def gauss_solve(A, b):
    n = len(A)
    M = [A[i][:] + [b[i] % 37] for i in range(n)]
    for col in range(len(A[0])):
        pivot = None
        for row in range(col, n):
            if M[row][col] % 37 != 0:
                pivot = row
                break
        if pivot is None:
            continue
        M[col], M[pivot] = M[pivot], M[col]
        inv = pow(M[col][col], -1, 37)
        for j in range(col, len(M[col])):
            M[col][j] = (M[col][j] * inv) % 37
        for r in range(n):
            if r != col and M[r][col] != 0:
                factor = M[r][col]
                for j in range(col, len(M[r])):
                    M[r][j] = (M[r][j] - factor * M[col][j]) % 37
    x = [0] * len(A[0])
    for i in range(min(len(A[0]), n)):
        x[i] = M[i][-1] % 37
    return x

def recover_key(P, C):
    K = [[0]*m for _ in range(m)]
    b = [0]*m
    for j in range(m):
        A = []
        rhs = []
        for block_idx in range(len(P)):
            A.append(P[block_idx] + [1])   # append 1 for b_j
            rhs.append(C[block_idx][j])
        sol = gauss_solve(A, rhs)
        for i in range(m):
            K[i][j] = sol[i] % 37
        b[j] = sol[m] % 37
    return K, b

K1, b1 = recover_key(P, C1)
K2, b2 = recover_key(P, C2)

def keyword_from_Kb(K, b):
    res = []
    for i in range(m):
        for j in range(m):
            res.append(K[i][j])
    res.extend(b)
    return class="hljs-string">&#039;&#039;.join(alphabet[v % 37] for v in res)

kw1 = keyword_from_Kb(K1, b1)
kw2 = keyword_from_Kb(K2, b2)

print(class="hljs-string">"Keyword 1:", kw1)
print(class="hljs-string">"Keyword 2:", kw2)

Running the script yields:

Keyword 1: kn0wn-pl41nt3xt-4tt4
Keyword 2: cks-4r3-sup3r-s1mpl3

Recovered Keywords

The two keywords are:

kn0wn-pl41nt3xt-4tt4
cks-4r3-sup3r-s1mpl3

Notice that they are self‑descriptive: the first says “known‑plaintext‑atta” (short for attack), the second says “cks‑are‑super‑simple” – clearly hinting at the vulnerability.

Verification

To confirm, we can reconstruct the full keys from these keywords and re‑encrypt a few blocks to verify they match the given ciphertexts. The math holds, and the linear system is consistent.

Final Flag

The challenge expects the flag in the format gaslightCTF{...} with the two keywords concatenated (no separator, as per the given flag).
Thus, the final flag is:

gaslightCTF{kn0wn-pl41nt3xt-4tt4cks-4r3-sup3r-s1mpl3}

Takeaways

Affine‑Hill ciphers are linear and therefore vulnerable to known‑plaintext attacks when the attacker has enough pairs.
The system can be solved by standard linear algebra over the finite field.
The keywords themselves often contain hints about the cipher’s weakness.
Always check the flag format carefully – here it was a simple concatenation.

This completes the challenge.

GaslightCTF 2026 - Affine Hill Writeup