Affine Cipher — a tiny 312-key space that known-plaintext or brute force both break instantly

Each letter is mapped x -> a*x + b mod 26 for fixed key integers (a,b), with a restricted to values coprime with 26 — a linear (not merely rotational) generalization of the shift cipher, and one whose entire keyspace is small enough to just try.

The signal that betrays it

- The challenge or its source literally computes something of the shape (a*x + b) % 26 (or % m for a non-English alphabet size) per character — that multiplicative term on x is the tell that distinguishes it from a plain Caesar/Substitution & Shift Cipher — recovered by letter-frequency, not by algebra, where only b (the shift) varies and a is implicitly 1. - Key material is handed over (or must be recovered) as a *pair* (a, b), not a single shift value or a full 26-letter permutation table. - Decryption in any writeup or source talks about a "modular inverse" of a — that vocabulary alone is a strong tell for affine, since shift ciphers never need one (inverse of 1 is trivial) and full substitution ciphers have no algebraic inverse to speak of at all. - Ciphertext still passes basic frequency-analysis sanity checks (letter frequency histogram is a permuted-and-scaled version of the plaintext language's), because the map is still a fixed bijection on the 26 letters — same class of weakness as any monoalphabetic scheme, just with algebraic structure on top.

Path 1 — known-plaintext (fastest when you have a crib)

two known plaintext/ciphertext letter pairs (x1,y1), (x2,y2) give two linear equations y1 = a*x1+b, y2 = a*x2+b mod 26. Subtract to isolate a:

`` a = (y1 - y2) * inverse(x1 - x2, 26) mod 26 b = (y1 - a*x1) mod 26 ``

This only works if x1 - x2 is invertible mod 26, i.e. gcd(x1-x2, 26) == 1. If your two known letters happen to differ by an even number or by 13 (e.g. both letters are 13 apart, or the difference is 2, 4, 6…), the inverse doesn't exist for that pair — the fix is not a smarter formula, it's picking a different pair of known letters whose positions differ by an odd, non-multiple-of-13 amount. With any crib of 3+ letters this is a non-issue: just try another pair of positions.

Path 2 — ciphertext-only, bounded brute force

a must be coprime with 26, so it can only be one of {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25} — exactly 12 values — and b ranges freely over all 26 residues. That's 12 * 26 = 312 total keys, small enough to brute-force exhaustively in well under a second: decrypt under every one of the 312 (a,b) pairs and score each candidate plaintext (English letter-frequency chi-squared, dictionary-word count, or just "does it contain a legible crib/flag-shaped string") to pick the winner. No cryptanalytic cleverness needed — the keyspace is simply too small to matter.

Computing the modular inverse of `a` (needed for both decryption and Path 1): extended Euclidean algorithm, or in Python pow(a, -1, 26). Decryption is then x = a_inv * (y - b) mod 26.

What does NOT work

- Treating it as a plain shift cipher and only brute-forcing 26 values of b. If a != 1 this silently produces garbage for every one of the 26 shift guesses — the multiplicative term changes the mapping in a way no pure rotation can undo. The symptom is "brute force found nothing readable"; the fix is recognizing the a*x term and switching to the 312-key search, not brute-forcing harder on the wrong model. - Assuming any integer 0-25 is a valid `a`. Exactly 14 of the 26 residues (the even numbers and multiples of 13) are non-invertible mod 26 and are never valid affine keys — if a known-plaintext solve or a brute-force loop ever produces one of those as a candidate a, that's a bug in the attack code, not a real key, and should be filtered out (or simply skipped) rather than debugged as if the plaintext recovery were failing. - Reusing a known-plaintext pair whose positions aren't coprime-compatible. Solving Path 1's equations with a pair where gcd(x1-x2,26) != 1 doesn't raise an obviously wrong answer in every implementation — depending on how the modular inverse is computed it can throw, hang, or (worse) silently return one of several equally "valid"-looking wrong roots. Always verify the recovered (a,b) actually reproduces the ciphertext at a third known letter before trusting it.

Related: Substitution & Shift Cipher — recovered by letter-frequency, not by algebra Vigenere Cipher — Kasiski / Index-of-Coincidence Key-Length Recovery