Playfair, Vigenère and Hill ciphers

"""The Vigenere cipher and its autokey variant, and what a repeating key does to the index of coincidence."""
from collections import Counter

UPPER = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
PASSAGE = (
    "When the first heavy rain reached the coast, the old bridge by the station was closed, "
    "and every bus on the morning route had to wait. The driver of the last bus told his "
    "passengers about his grandfather, who built fishing boats in a village south of the river "
    "and never once let water into a hull. He described how the wood was chosen, how the planks "
    "were bent over a slow fire and how the seams were packed with cotton and oil. By the time "
    "the bridge opened again, the children at the back could name every part of a boat, and "
    "nobody on the bus minded the delay. Their parents had missed the start of work, but they "
    "agreed that it was the most useful hour the route had ever given them. That evening, a few "
    "of them walked down to the river to watch the boats come in."
)


def letters(text):
    return [UPPER.index(ch) for ch in text.upper() if ch in UPPER]


def vigenere(text, key, sign=1):
    """Letter i moves by key letter i mod len(key); sign=-1 decrypts."""
    k = letters(key)
    return "".join(UPPER[(p + sign * k[i % len(k)]) % 26] for i, p in enumerate(letters(text)))


def autokey_encrypt(text, primer):
    """The primer shifts the first letters; after it, each plaintext letter shifts a later one."""
    p = letters(text)
    k = letters(primer) + p
    return "".join(UPPER[(x + k[i]) % 26] for i, x in enumerate(p))


def autokey_decrypt(text, primer):
    k = letters(primer)
    out = []
    for i, c in enumerate(letters(text)):
        out.append((c - k[i]) % 26)
        k.append(out[-1])  # each recovered letter becomes key material
    return "".join(UPPER[x] for x in out)


def index_of_coincidence(text):
    counts = Counter(letters(text))
    n = sum(counts.values())
    return sum(f * (f - 1) for f in counts.values()) / (n * (n - 1))


secret = vigenere("MEETATTHEGATE", "STORM")
print("Vigenere, key STORM:   ", secret, "->", vigenere(secret, "STORM", -1))
secret = autokey_encrypt("MEETATTHEGATE", "THUNDER")
print("autokey, primer THUNDER:", secret, "->", autokey_decrypt(secret, "THUNDER"))

ciphertext = vigenere(PASSAGE, "MONSOON")
print(f"index of coincidence, the passage:        {index_of_coincidence(PASSAGE):.4f}")
print(f"index of coincidence, Vigenere MONSOON:   {index_of_coincidence(ciphertext):.4f}")
print(f"index of coincidence, autokey THUNDER:    {index_of_coincidence(autokey_encrypt(PASSAGE, 'THUNDER')):.4f}")
print("first 35 letters under MONSOON:", ciphertext[:35])

Vigenere, key STORM:    EXSKMLMVVSSMS -> MEETATTHEGATE
autokey, primer THUNDER: FLYGDXKTIKTTX -> MEETATTHEGATE
index of coincidence, the passage:        0.0692
index of coincidence, Vigenere MONSOON:   0.0483
index of coincidence, autokey THUNDER:    0.0394
first 35 letters under MONSOON: IVRFHVRRWEKHVRMJLJOWADSNUVSQFVRUCOF

"""Finding a Vigenere key's length, then the key, on the lesson's passage encrypted under MONSOON."""
from collections import Counter

UPPER = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
ENGLISH = [8.04, 1.54, 3.06, 3.99, 12.51, 2.30, 1.96, 5.49, 7.26, 0.16, 0.67, 4.14, 2.53,
           7.09, 7.60, 2.00, 0.11, 6.12, 6.54, 9.25, 2.71, 0.99, 1.92, 0.19, 1.73, 0.09]  # Handbook, Figure 7.5
PASSAGE = (
    "When the first heavy rain reached the coast, the old bridge by the station was closed, "
    "and every bus on the morning route had to wait. The driver of the last bus told his "
    "passengers about his grandfather, who built fishing boats in a village south of the river "
    "and never once let water into a hull. He described how the wood was chosen, how the planks "
    "were bent over a slow fire and how the seams were packed with cotton and oil. By the time "
    "the bridge opened again, the children at the back could name every part of a boat, and "
    "nobody on the bus minded the delay. Their parents had missed the start of work, but they "
    "agreed that it was the most useful hour the route had ever given them. That evening, a few "
    "of them walked down to the river to watch the boats come in."
)


def vigenere(text, key, sign=1):
    p = [UPPER.index(ch) for ch in text.upper() if ch in UPPER]
    k = [UPPER.index(ch) for ch in key]
    return "".join(UPPER[(x + sign * k[i % len(k)]) % 26] for i, x in enumerate(p))


def index_of_coincidence(text):
    counts = Counter(text)
    n = len(text)
    return sum(f * (f - 1) for f in counts.values()) / (n * (n - 1))


def best_shift(column):
    """The Caesar key of one column: the shift whose decryption is closest to English (chi-squared)."""
    def score(s):
        counts = Counter(UPPER[(UPPER.index(ch) - s) % 26] for ch in column)
        n = len(column)
        return sum((counts[ch] - n * f / 100) ** 2 / (n * f / 100) for ch, f in zip(UPPER, ENGLISH))
    return min(range(26), key=lambda s: (score(s), s))


ciphertext = vigenere(PASSAGE, "MONSOON")
print("letters:", len(ciphertext), f"  index of coincidence of the whole ciphertext: {index_of_coincidence(ciphertext):.4f}")

# Kasiski: the distances between repeated three-letter sequences, and the factors they share.
seen, distances = {}, []
for i in range(len(ciphertext) - 2):
    triple = ciphertext[i:i + 3]
    if triple in seen:
        distances.append(i - seen[triple])
    seen[triple] = i
factors = Counter(f for d in distances for f in range(2, 13) if d % f == 0)
print(f"{len(distances)} repeat distances; the factors 2 to 12 they share, most common first:")
print("  " + ", ".join(f"{f}: {n}" for f, n in factors.most_common(6)))

# The index of coincidence of every t-th letter, averaged over the t columns.
means = {}
for t in range(1, 13):
    columns = [ciphertext[i::t] for i in range(t)]
    means[t] = sum(index_of_coincidence(c) for c in columns) / t
    print(f"  key length {t:2}: mean column index {means[t]:.4f}{'  <- English-like' if means[t] > 0.06 else ''}")

# The first English-like length is the key's length, and each of its columns is a Caesar cipher: solve it by chi-squared.
length = min((t for t in means if means[t] > 0.06), default=max(means, key=means.get))
key = "".join(UPPER[best_shift(ciphertext[i::length])] for i in range(length))
print("key found:", key)
print("plaintext:", vigenere(ciphertext, key, -1)[:40], "...")

letters: 605   index of coincidence of the whole ciphertext: 0.0483
65 repeat distances; the factors 2 to 12 they share, most common first:
  7: 48, 2: 29, 3: 19, 4: 16, 5: 13, 8: 10
  key length  1: mean column index 0.0483
  key length  2: mean column index 0.0478
  key length  3: mean column index 0.0477
  key length  4: mean column index 0.0476
  key length  5: mean column index 0.0483
  key length  6: mean column index 0.0470
  key length  7: mean column index 0.0700  <- English-like
  key length  8: mean column index 0.0467
  key length  9: mean column index 0.0476
  key length 10: mean column index 0.0478
  key length 11: mean column index 0.0489
  key length 12: mean column index 0.0458
key found: MONSOON
plaintext: WHENTHEFIRSTHEAVYRAINREACHEDTHECOASTTHEO ...

"""How much ciphertext a Vigenere key needs: 20 random keys of each length, on the first 100 to 605 letters of the
passage. For each key length t from 1 to 12 the solver finds every column's Caesar key by chi-squared, then keeps the t
whose whole decryption is closest to English; a key found as two copies of a shorter one is shortened."""
import random

UPPER = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
ENGLISH = [8.04, 1.54, 3.06, 3.99, 12.51, 2.30, 1.96, 5.49, 7.26, 0.16, 0.67, 4.14, 2.53,
           7.09, 7.60, 2.00, 0.11, 6.12, 6.54, 9.25, 2.71, 0.99, 1.92, 0.19, 1.73, 0.09]  # Handbook, Figure 7.5
PASSAGE = (
    "When the first heavy rain reached the coast, the old bridge by the station was closed, "
    "and every bus on the morning route had to wait. The driver of the last bus told his "
    "passengers about his grandfather, who built fishing boats in a village south of the river "
    "and never once let water into a hull. He described how the wood was chosen, how the planks "
    "were bent over a slow fire and how the seams were packed with cotton and oil. By the time "
    "the bridge opened again, the children at the back could name every part of a boat, and "
    "nobody on the bus minded the delay. Their parents had missed the start of work, but they "
    "agreed that it was the most useful hour the route had ever given them. That evening, a few "
    "of them walked down to the river to watch the boats come in."
)
PLAIN = [UPPER.index(ch) for ch in PASSAGE.upper() if ch in UPPER]


def chi_squared(counts):
    n = sum(counts)
    return sum((counts[i] - n * ENGLISH[i] / 100) ** 2 / (n * ENGLISH[i] / 100) for i in range(26))


def solve(cipher, max_len=12):
    best = None
    for t in range(1, max_len + 1):
        shifts, total = [], [0] * 26
        for j in range(t):
            counts = [0] * 26
            for c in cipher[j::t]:
                counts[c] += 1
            # Decrypting with shift s turns ciphertext letter (p + s) into p.
            s = min(range(26), key=lambda s: (chi_squared([counts[(p + s) % 26] for p in range(26)]), s))
            shifts.append(s)
            for p in range(26):
                total[p] += counts[(p + s) % 26]
        score = chi_squared(total)
        if best is None or score < best[0] - 1e-9:
            best = (score, shifts)
    key = best[1]
    for p in range(1, len(key) + 1):  # shorten a key that is a shorter key repeated
        if len(key) % p == 0 and key == key[:p] * (len(key) // p):
            return key[:p]


rng = random.Random(2026)
print("letters | key length 4 | 6 | 8 | 10 (keys recovered exactly, of 20)")
for n in (100, 200, 400, 605):
    row = []
    for m in (4, 6, 8, 10):
        found = 0
        for _ in range(20):
            key = [rng.randrange(26) for _ in range(m)]
            cipher = [(p + key[i % m]) % 26 for i, p in enumerate(PLAIN[:n])]
            found += solve(cipher) == key
        row.append(found)
    print(f"{n:7} | " + " | ".join(f"{x:2}" for x in row))

letters | key length 4 | 6 | 8 | 10 (keys recovered exactly, of 20)
    100 | 19 | 20 | 18 |  0
    200 | 20 | 20 | 20 | 20
    400 | 20 | 20 | 20 | 20
    605 | 20 | 20 | 20 | 20

// A review check for "encryption" by XOR with a short repeating key, the Vigenere cipher on bytes. For every period t
// from 1 to 16 it splits the output into t columns (every t-th byte) and measures how often two bytes of a column are
// equal, as a multiple of the rate for random bytes (1.0). A column XORed with one key byte keeps the shape of its text,
// so at the key's length the columns score as high as text does; random-looking output stays near 1.0 at every period.
// Failing the check proves a leak; passing it proves nothing about a cipher.

const PASSAGE =
  'When the first heavy rain reached the coast, the old bridge by the station was closed, ' +
  'and every bus on the morning route had to wait. The driver of the last bus told his ' +
  'passengers about his grandfather, who built fishing boats in a village south of the river ' +
  'and never once let water into a hull. He described how the wood was chosen, how the planks ' +
  'were bent over a slow fire and how the seams were packed with cotton and oil. By the time ' +
  'the bridge opened again, the children at the back could name every part of a boat, and ' +
  'nobody on the bus minded the delay. Their parents had missed the start of work, but they ' +
  'agreed that it was the most useful hour the route had ever given them. That evening, a few ' +
  'of them walked down to the river to watch the boats come in.';
const encode = (text) => new TextEncoder().encode(text);

/** How often two bytes of the array are equal, as a multiple of the rate for random bytes. */
function coincidenceRatio(bytes) {
  const counts = new Array(256).fill(0);
  for (const b of bytes) counts[b] += 1;
  let pairs = 0;
  for (const c of counts) pairs += c * (c - 1);
  return (pairs / (bytes.length * (bytes.length - 1))) * 256;
}

/** The mean ratio of the t columns, for every period t from 1 to 16. */
function columnProfile(bytes) {
  const means = [];
  for (let t = 1; t <= 16; t++) {
    let sum = 0;
    for (let j = 0; j < t; j++) sum += coincidenceRatio(bytes.filter((_, i) => i % t === j));
    means.push(sum / t);
  }
  return means;
}

/** The check a test suite runs on an encrypt function: no period may show columns at 3 times the random rate. */
function checkOutput(name, bytes) {
  const means = columnProfile(bytes);
  const top = Math.max(...means);
  if (top < 3) return console.log(`${name}: pass`); // random output varies a little, so only the verdict prints
  const period = means.findIndex((m) => m >= 0.8 * top) + 1; // the shortest period that scores like the best one
  console.log(`${name}: FAIL, period ${period}, columns at ${means[period - 1].toFixed(1)} times the random rate`);
}

// The weak sample: XOR with a fixed 8-byte key kept in the code, as such functions do. Never write a real key in code.
const DEMO_KEY = encode('demo-key');
const xorEncrypt = (data) => data.map((b, i) => b ^ DEMO_KEY[i % DEMO_KEY.length]);
const weak = xorEncrypt(encode(PASSAGE));
checkOutput('xorEncrypt, 8-byte key', weak);
console.log('  its mean column ratio at periods 1 to 16:', columnProfile(weak).map((m) => m.toFixed(1)).join(' '));
console.log('  the plaintext as a whole:', coincidenceRatio(encode(PASSAGE)).toFixed(1));

// The fix: AES-256-GCM through Web Crypto, with a fresh random key and a fresh random 96-bit nonce.
const key = await crypto.subtle.generateKey({ name: 'AES-GCM', length: 256 }, false, ['encrypt']);
const iv = crypto.getRandomValues(new Uint8Array(12));
const sealed = new Uint8Array(await crypto.subtle.encrypt({ name: 'AES-GCM', iv }, key, encode(PASSAGE)));
checkOutput(`aesGcmEncrypt (${sealed.length} bytes)`, sealed);

xorEncrypt, 8-byte key: FAIL, period 8, columns at 20.6 times the random rate
  its mean column ratio at periods 1 to 16: 7.5 9.5 7.4 13.0 7.4 9.4 7.3 20.6 7.6 9.4 7.3 12.8 7.3 9.5 7.1 20.4
  the plaintext as a whole: 20.4
aesGcmEncrypt (785 bytes): pass

"""The Playfair cipher on the GTU 3161606 practical, a doubled letter, and what it does to letter and pair counts."""
from collections import Counter

UPPER = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
PASSAGE = (
    "When the first heavy rain reached the coast, the old bridge by the station was closed, "
    "and every bus on the morning route had to wait. The driver of the last bus told his "
    "passengers about his grandfather, who built fishing boats in a village south of the river "
    "and never once let water into a hull. He described how the wood was chosen, how the planks "
    "were bent over a slow fire and how the seams were packed with cotton and oil. By the time "
    "the bridge opened again, the children at the back could name every part of a boat, and "
    "nobody on the bus minded the delay. Their parents had missed the start of work, but they "
    "agreed that it was the most useful hour the route had ever given them. That evening, a few "
    "of them walked down to the river to watch the boats come in."
)


def square(keyword):
    """5 x 5 letters: the keyword without repeats, then the rest of the alphabet; I and J share a cell."""
    cells = ""
    for ch in keyword.upper().replace("J", "I") + UPPER.replace("J", ""):
        if ch in UPPER and ch not in cells:
            cells += ch
    return [cells[r * 5:r * 5 + 5] for r in range(5)]


def pairs(text):
    """Letter pairs; an X goes between a doubled pair and after a lone last letter."""
    s = [ch for ch in text.upper().replace("J", "I") if ch in UPPER]
    out, i = [], 0
    while i < len(s):
        a = s[i]
        b = s[i + 1] if i + 1 < len(s) else "X"
        if a == b:
            out.append(a + "X")
            i += 1
        else:
            out.append(a + b)
            i += 2
    return out


def playfair(pair_list, keyword, step=1):
    """step=1 encrypts, step=-1 decrypts. Returns each pair's result and the rule that made it."""
    sq = square(keyword)
    where = {sq[r][c]: (r, c) for r in range(5) for c in range(5)}
    out = []
    for a, b in pair_list:
        (r1, c1), (r2, c2) = where[a], where[b]
        if r1 == r2:
            out.append((sq[r1][(c1 + step) % 5] + sq[r2][(c2 + step) % 5], "same row: one to the right"))
        elif c1 == c2:
            out.append((sq[(r1 + step) % 5][c1] + sq[(r2 + step) % 5][c2], "same column: one down"))
        else:
            out.append((sq[r1][c2] + sq[r2][c1], "rectangle: swap the columns"))
    return out


def coincidence(units):
    counts = Counter(units)
    n = len(units)
    return sum(f * (f - 1) for f in counts.values()) / (n * (n - 1))


print("square for MONARCHY:", " ".join(square("MONARCHY")))
for (pair, (result, rule)) in zip(pairs("ar mu hs ea"), playfair(pairs("ar mu hs ea"), "MONARCHY")):
    print(f"  {pair} -> {result}  ({rule})")
print("balloon is split as", " ".join(pairs("balloon")), "->", " ".join(r for r, _ in playfair(pairs("balloon"), "MONARCHY")))
back = playfair([r for r, _ in playfair(pairs("balloon"), "MONARCHY")], "MONARCHY", -1)
print("and decrypts to", " ".join(r for r, _ in back))

plain_pairs = pairs(PASSAGE)
cipher_pairs = [r for r, _ in playfair(plain_pairs, "MONARCHY")]
plain_letters, cipher_letters = list("".join(plain_pairs)), list("".join(cipher_pairs))
print(f"single letters, index of coincidence: {coincidence(plain_letters):.4f} -> {coincidence(cipher_letters):.4f}")
print(f"letter pairs, index of coincidence:   {coincidence(plain_pairs):.5f} -> {coincidence(cipher_pairs):.5f}"
      f"  (uniform pairs: {1 / 625:.5f})")

square for MONARCHY: MONAR CHYBD EFGIK LPQST UVWXZ
  AR -> RM  (same row: one to the right)
  MU -> CM  (same column: one down)
  HS -> BP  (rectangle: swap the columns)
  EA -> IM  (rectangle: swap the columns)
balloon is split as BA LX LO ON -> IB SU PM NA
and decrypts to BA LX LO ON
single letters, index of coincidence: 0.0677 -> 0.0504
letter pairs, index of coincidence:   0.01067 -> 0.01067  (uniform pairs: 0.00160)

"""The Hill cipher with the 3 x 3 key of the GTU 3161606 practical: both conventions, the inverse key and how many
2 x 2 keys can be inverted at all."""
from collections import Counter
from math import gcd

UPPER = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
PASSAGE = (
    "When the first heavy rain reached the coast, the old bridge by the station was closed, "
    "and every bus on the morning route had to wait. The driver of the last bus told his "
    "passengers about his grandfather, who built fishing boats in a village south of the river "
    "and never once let water into a hull. He described how the wood was chosen, how the planks "
    "were bent over a slow fire and how the seams were packed with cotton and oil. By the time "
    "the bridge opened again, the children at the back could name every part of a boat, and "
    "nobody on the bus minded the delay. Their parents had missed the start of work, but they "
    "agreed that it was the most useful hour the route had ever given them. That evening, a few "
    "of them walked down to the river to watch the boats come in."
)
K = [[17, 17, 5],
     [21, 18, 21],
     [2, 2, 19]]


def numbers(text):
    return [UPPER.index(ch) for ch in text.upper() if ch in UPPER]


def encrypt_rows(text, key):
    """C = P K mod 26, each block of n letters a row vector (the practical's convention)."""
    p, n = numbers(text), len(key)
    out = []
    for i in range(0, len(p), n):
        block = p[i:i + n]
        out += [sum(block[r] * key[r][c] for r in range(n)) % 26 for c in range(n)]
    return "".join(UPPER[x] for x in out)


def encrypt_columns(text, key):
    """C = K P mod 26, each block a column vector (the Handbook's Example 7.52)."""
    p, n = numbers(text), len(key)
    out = []
    for i in range(0, len(p), n):
        block = p[i:i + n]
        out += [sum(key[r][c] * block[c] for c in range(n)) % 26 for r in range(n)]
    return "".join(UPPER[x] for x in out)


def det3(m):
    (a, b, c), (d, e, f), (g, h, i) = m
    return a * (e * i - f * h) - b * (d * i - f * g) + c * (d * h - e * g)


def inverse3(m):
    """The inverse modulo 26: the adjugate times the inverse of the determinant."""
    d_inv = pow(det3(m) % 26, -1, 26)  # ValueError if the determinant shares a factor with 26
    def minor(r, c):
        rows = [row[:c] + row[c + 1:] for k, row in enumerate(m) if k != r]
        return rows[0][0] * rows[1][1] - rows[0][1] * rows[1][0]
    return [[d_inv * (-1) ** (r + c) * minor(c, r) % 26 for c in range(3)] for r in range(3)]


print("pay, rows (C = P K):", encrypt_rows("pay", K), "  columns (C = K P):", encrypt_columns("pay", K))
secret = encrypt_rows("paymoremoney", K)
print("paymoremoney ->", secret)
print("determinant:", det3(K), "=", det3(K) % 26, "mod 26, gcd with 26:", gcd(det3(K) % 26, 26))
K_inv = inverse3(K)
print("inverse key:", K_inv)
print("decrypted with it:", encrypt_rows(secret, K_inv))

letters = "".join(ch for ch in PASSAGE.upper() if ch in UPPER) + "X"  # 606 letters: whole blocks of three
for name, text in [("the passage", letters), ("under K", encrypt_rows(letters, K))]:
    counts = Counter(text)
    n = len(text)
    print(f"index of coincidence, {name}: {sum(f * (f - 1) for f in counts.values()) / (n * (n - 1)):.4f}")

count = sum(1 for a in range(26) for b in range(26) for c in range(26) for d in range(26)
            if gcd((a * d - b * c) % 26, 26) == 1)
print(f"invertible 2 x 2 keys: {count:,} of {26 ** 4:,}")

pay, rows (C = P K): RRL   columns (C = K P): LNS
paymoremoney -> RRLMWBKASPDH
determinant: -939 = 23 mod 26, gcd with 26: 1
inverse key: [[4, 9, 15], [15, 17, 6], [24, 0, 17]]
decrypted with it: PAYMOREMONEY
index of coincidence, the passage: 0.0689
index of coincidence, under K: 0.0391
invertible 2 x 2 keys: 157,248 of 456,976

"""Known plaintext against the Hill cipher: three known blocks give the whole 3 x 3 key, K = P^-1 C mod 26."""
from math import gcd

UPPER = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
SECRET_KEY = [[17, 17, 5], [21, 18, 21], [2, 2, 19]]  # the key the attacker does not know


def numbers(text):
    return [UPPER.index(ch) for ch in text.upper() if ch in UPPER]


def times(a, b):
    return [[sum(a[r][k] * b[k][c] for k in range(len(b))) % 26 for c in range(len(b[0]))] for r in range(len(a))]


def det3(m):
    (a, b, c), (d, e, f), (g, h, i) = m
    return a * (e * i - f * h) - b * (d * i - f * g) + c * (d * h - e * g)


def inverse3(m):
    d_inv = pow(det3(m) % 26, -1, 26)
    def minor(r, c):
        rows = [row[:c] + row[c + 1:] for k, row in enumerate(m) if k != r]
        return rows[0][0] * rows[1][1] - rows[0][1] * rows[1][0]
    return [[d_inv * (-1) ** (r + c) * minor(c, r) % 26 for c in range(3)] for r in range(3)]


def blocks(text):
    p = numbers(text)
    return [p[i:i + 3] for i in range(0, len(p) - len(p) % 3, 3)]


message = "Transfer the money to the river office before noon"  # the attacker sees only its ciphertext
ciphertext = times(blocks(message), SECRET_KEY)  # what the attacker records


def invertible_triple(known):
    """The first three blocks whose 3 x 3 matrix has an inverse modulo 26, or None."""
    for i in range(len(known)):
        for j in range(i + 1, len(known)):
            for k in range(j + 1, len(known)):
                if gcd(det3([known[i], known[j], known[k]]) % 26, 26) == 1:
                    return i, j, k
    return None


# Not every known start is enough: three of its blocks must make a matrix with an inverse modulo 26.
for start in ("Transfer the funds", "Transfer the money"):
    known = blocks(start)
    print(f"{start!r}: blocks {[''.join(UPPER[x] for x in b) for b in known]}, invertible triple: {invertible_triple(known)}")

# The attacker knows that the message starts "Transfer the money", and has its ciphertext.
known = blocks("Transfer the money")
i, j, k = invertible_triple(known)
P = [known[i], known[j], known[k]]
found = times(inverse3(P), [ciphertext[i], ciphertext[j], ciphertext[k]])  # K = P^-1 C
print(f"blocks {i}, {j} and {k}: determinant {det3(P) % 26} mod 26")
print("key found:", found, "  equal to the secret key:", found == SECRET_KEY)
print("whole message:", "".join(UPPER[x] for row in times(ciphertext, inverse3(found)) for x in row))

'Transfer the funds': blocks ['TRA', 'NSF', 'ERT', 'HEF', 'UND'], invertible triple: None
'Transfer the money': blocks ['TRA', 'NSF', 'ERT', 'HEM', 'ONE'], invertible triple: (0, 1, 3)
blocks 0, 1 and 3: determinant 3 mod 26
key found: [[17, 17, 5], [21, 18, 21], [2, 2, 19]]   equal to the secret key: True
whole message: TRANSFERTHEMONEYTOTHERIVEROFFICEBEFORENOON