Affine Cipher: Modular Multiplicative Inverses, Coprimality & Algebraic Cryptanalysis

1. Mathematical Formulation: Linear Congruences in ℤ₂₆

In previous lessons, we explored the Caesar cipher (pure addition: x + k) and the Atbash cipher (pure reflection: 25 - x). The Affine Cipher generalizes both into a single unified linear mathematical transformation.

Operating over the finite integer ring ℤ₂₆ = {0, 1, 2, ..., 25}, the Affine cipher combines modular multiplication and modular addition using a pair of secret integer keys (a, b):

Notice how the Affine cipher elegantly unifies previous ciphers as special cases:

When a = 1, the encryption function becomes E(x) = (x + b) mod 26, which is exactly the Caesar Cipher.

When a = 25 (since 25 ≡ -1 mod 26) and b = 25, the function becomes E(x) = (25 - x) mod 26, which is exactly the Atbash Cipher.

2. The Coprimality Rule: Why gcd(a, 26) = 1 is Mandatory

In elementary algebra, you can divide by any non-zero real number. In modular arithmetic over composite moduli like 26, division does not exist! Instead, we multiply by the modular multiplicative inverse a^(-1).

A number a possesses a modular multiplicative inverse modulo 26 if and only if a and 26 are coprime—meaning their Greatest Common Divisor is 1: gcd(a, 26) = 1.

What catastrophic failure happens if you choose an invalid key like a = 2, a = 4, or a = 13? Let us test a = 2 with b = 0:

3. Modular Multiplicative Inverses & Extended Euclidean Algorithm

The modular inverse a^(-1) is the unique integer satisfying the congruence:

a · a^(-1) ≡ 1 (mod 26)

To find a^(-1) computationally, we run the Extended Euclidean Algorithm on a and 26, solving Bézout’s identity: a · x + 26 · y = gcd(a, 26) = 1. The coefficient x (reduced modulo 26) is the modular inverse a^(-1).

Because there are only 12 valid coprime integers in ℤ₂₆, we can examine the complete, definitive inverse lookup table:

4. Step-by-Step Worked Trace Table: a = 5, b = 8

Let us encrypt the message "MATHEMATICS" using the key pair a = 5, b = 8.

From our inverse table, we know that 5^(-1) ≡ 21 (mod 26).

Encryption formula: y = (5x + 8) mod 26.

Decryption formula: x = 21(y - 8) mod 26.

5. Key Space Analysis: Euler’s Totient φ(26)

How large is the key space of the Affine cipher?

The number of coprime integers less than 26 is given by Euler’s Totient Function φ(n):

φ(26) = φ(2) × φ(13) = (2 - 1) × (13 - 1) = 1 × 12 = 12.

For each of these 12 choices of a, there are 26 independent choices for the additive shift parameter b (0 through 25).

Total Key Space Size: |K| = 12 × 26 = 312 keys.

Subtracting the trivial identity key (a = 1, b = 0) which leaves text unchanged, there are exactly 311 active transformations. By modern standards, 312 keys is trivially vulnerable: a modern computer tests all 312 keys in under 500 microseconds.

6. Cryptanalysis: The Two-Point Algebraic Attack

Because the Affine cipher is monoalphabetic, it preserves character frequencies. Furthermore, because the algorithm is strictly linear, discovering just two letters of plaintext completely breaks the entire cipher!

Suppose an intelligence analyst discovers that plaintext letter p₁ encrypts to c₁, and plaintext letter p₂ encrypts to c₂. We establish a system of two linear congruences in two unknowns (a, b):

In natural English, the letters "E" (p₁ = 4) and "T" (p₂ = 19) are the two most common. Their difference is Δp = 4 - 19 = -15 ≡ 11 (mod 26).

Because gcd(11, 26) = 1, the difference is guaranteed to be invertible! An analyst simply identifies the two most frequent characters in the ciphertext, assumes they correspond to E and T, and instantly solves for the secret key pair (a, b).

7. Complete Python Implementation & Automated Cracker

Here is a production-grade, standalone Python script containing full Affine encryption/decryption, Extended Euclidean modular inversion, the two-point algebraic solver, and an automated Chi-Square brute-force cracking engine:

8. Practice Challenge: The Gauss Number Theory Dispatch

Put your cryptanalysis skills to the test with this historical quotation encoded using an unknown Affine key pair (a, b):

Can you identify the secret multiplier a and additive shift b to read the famous mathematical declaration?

Clue: Notice the high frequency of the 3-letter word "GAF", which frequently represents "THE" in English! You can test your deduction in the live CipherVerse Affine Solver below.

9. Interactive Affine Cipher Workbench

Ready to explore linear congruences, coprimality checks, and automated inverse calculation hands-on? The CipherVerse Affine Cipher Tool validates your keys in real time and handles all modular reductions automatically.

Everything executes inside your client-side browser with 100% privacy and zero external server transmission.