AFFINE-HILL
Challenge
Many classical ciphers are inherently vulnerable to known-plaintext attacks. Unfortunately, your obstinate friend claimed that his original Affine-Hill Cipher, inspired by the Affine Cipher and Hill Cipher, is invulnerable to such attacks. He posed a challenge to anyone that claims he's wrong.
Can you break his cipher by recovering the keywords?
Files given: encrypt.py, output.txt
Understanding the cipher
They give you the thing and you just undo it. encrypt.py encrypts one known plaintext string twice, once under each of two secret keywords, and hands us both ciphertexts:
alphabet = "abcdefghijklmnopqrstuvwxyz0123456789-" # l = 38 symbols
m = 4 # block size
def enc_affine_hill(pt, m, K, b):
pt_vecs = [ split pt into length-m chunks, each mapped to a vector of alphabet indices ]
for pt_vec in pt_vecs:
ct_vec = (pt_vec * K + b) % l
Each 4-character block of plaintext is a row vector p over Z/38, encrypted as:
K is a secret 4×4 matrix and b a secret 1×4 offset. It's a Hill cipher with an affine shift bolted on. Both are derived from a "keyword" (the keyword's characters become the matrix rows, plus 4 trailing characters for b), and two independent keywords produce ct1 and ct2 from the same plaintext.
output.txt gives the padded plaintext plus both ciphertexts:
Padded plaintext: b3w4reofbugs1ntheab0vec0de-ih4ve0nlyprov3ditc0rrectnottr13dit--- Ciphertext with key 1: x3etd0vgd7z9v6bld4ba7p94s0acp-bvfjjfywypdkzuwsgah4shanrdaop4 Ciphertext with key 2: odbewk453xyc3210-mlqxley8loydmzgy0k6ok4i9qjcwx42om5au1-hqqkr
The vulnerability
This is a known-plaintext attack against an affine transform. We already have plaintext/ciphertext block pairs, so all that's left is getting enough of them to solve for K and b.
Each block gives one linear equation, c = p·K + b. Augmenting every plaintext vector with a trailing 1 turns this into one matrix equation:
K is 4×4 and b is 1×4, so [K; b] is a 5×4 unknown. Stack 5 augmented plaintext rows into P and the matching ciphertext rows into C:
As long as 5 of the augmented plaintext blocks form an invertible matrix mod 38, inverting it recovers K and b directly with no brute force needed. Since alphabet has length 38 (2 times 19, composite, not prime), invertibility mod 38 isn't guaranteed for every window, so the script slides across the available blocks until it finds one that inverts cleanly.
Once K and b are recovered, decoding them back into alphabet characters reconstructs the original keyword, which is what the challenge actually asks for.
Solution
from sympy import Matrix
from sympy.matrices.exceptions import NonInvertibleMatrixError
from math import ceil
alphabet = "abcdefghijklmnopqrstuvwxyz0123456789-"
l = len(alphabet)
m = 4
pt = "b3w4reofbugs1ntheab0vec0de-ih4ve0nlyprov3ditc0rrectnottr13dit"
ct1 = "x3etd0vgd7z9v6bld4ba7p94s0acp-bvfjjfywypdkzuwsgah4shanrdaop4"
ct2 = "odbewk453xyc3210-mlqxley8loydmzgy0k6ok4i9qjcwx42om5au1-hqqkr"
def pad(s, m):
n = len(s)
return s + "-" * (m * ceil(n / m) - n)
def to_blocks(s, m):
s = pad(s, m)
return [[alphabet.index(c) for c in s[m*i:m*(i+1)]] for i in range(len(s) // m)]
def recover_key(pt_blocks, ct_blocks, m, l):
need = m + 1 # 5 rows needed to solve for a 5x4 unknown ([K; b])
for start in range(len(pt_blocks) - need + 1):
P = Matrix([pt_blocks[start + i] + [1] for i in range(need)])
C = Matrix([ct_blocks[start + i] for i in range(need)])
try:
P_inv = P.inv_mod(l) # only works if this 5x5 window is invertible mod 38
except (NonInvertibleMatrixError, ValueError):
continue
Kb = (P_inv * C) % l
return Kb[:m, :], Kb[m, :] # split back into K (4x4) and b (1x4)
raise RuntimeError("no invertible block window found")
pt_blocks = to_blocks(pt, m)
for name, ct in [("key 1", ct1), ("key 2", ct2)]:
ct_blocks = to_blocks(ct, m)
K, b = recover_key(pt_blocks[:len(ct_blocks)], ct_blocks, m, l)
keyword = "".join(alphabet[x] for row in K.tolist() for x in row) + "".join(alphabet[x] for x in b)
print(f"{name}: {keyword}")