Hill Cipher: The Mathematics of Matrix Encryption

What if you could crack an encrypted military message by guessing just nine letters? The Hill cipher—invented in 1929 by mathematician Lester S. Hill—is elegant, mathematically beautiful, and fatally flawed. It was the first practical polygraphic cipher, encrypting multiple letters at once using matrix multiplication.

This post explains how it works, why it's broken, and provides working code in Python, Go, and C to both use and break it.

What is the Hill Cipher?

The Hill cipher encrypts blocks of letters by treating them as vectors and multiplying them by a key matrix. Unlike simple substitution ciphers that replace one letter at a time, the Hill cipher encrypts multiple letters simultaneously, making frequency analysis much harder.

Basic idea:

Key matrix × Plaintext vector = Ciphertext vector (mod n)

For a 3×3 key matrix encrypting "CAT":

[k₀₀ k₀₁ k₀₂]   [C]   [?]
[k₁₀ k₁₁ k₁₂] × [A] = [?] (mod 26)
[k₂₀ k₂₁ k₂₂]   [T]   [?]

History

Lester S. Hill was a mathematics professor at Hunter College in New York. He published the cipher in 1929 in The American Mathematical Monthly under the title "Cryptography in an Algebraic Alphabet."

Hill's innovation was applying linear algebra to cryptography. While the mathematics was sound, the cipher never saw widespread use because:

1. Matrix calculations by hand are tedious and error-prone
2. Computing the inverse matrix (for decryption) is even harder
3. It's vulnerable to known-plaintext attacks

However, the Hill cipher remains important for education—it demonstrates how linear algebra applies to cryptography and introduces concepts used in modern systems like AES (which uses matrix operations in its MixColumns step).

Prerequisites

Before diving into the details, let's clarify some terms and concepts used throughout this article.

Terminology: Cipher vs Encryption

• Cipher: An algorithm for transforming plaintext into ciphertext. The Hill cipher, Caesar cipher, and AES are all ciphers—they define how to scramble data.
• Encryption: The process of applying a cipher to transform plaintext into ciphertext.
• Decryption: The reverse process—recovering plaintext from ciphertext using the cipher and key.

GCD (Greatest Common Divisor)

The Greatest Common Divisor of two numbers is the largest positive integer that divides both evenly.

Examples:

• gcd(12, 8) = 4 (both divisible by 4, but not by anything larger)
• gcd(15, 26) = 1 (no common factors other than 1—we call these "coprime")
• gcd(13, 26) = 13 (26 = 2 × 13, so they share factor 13)

Why GCD matters for Hill cipher: A key matrix is valid only if gcd(determinant, 26) = 1. This ensures the matrix has a modular inverse, which is required for decryption.

Modular Arithmetic

The expression "a mod n" means the remainder when a is divided by n. For example:

• 31 mod 26 = 5 (because 31 = 1×26 + 5)
• 216 mod 26 = 8 (because 216 = 8×26 + 8)
• -4 mod 26 = 22 (negative numbers wrap around: -4 + 26 = 22)

Note on negative numbers: Determinants can be negative (e.g., -4187), but this is perfectly fine. When we take mod 26, we always get a positive result between 0 and 25. For example: -4187 mod 26 = 25.

Reference Matrix for Verification

Throughout this article, we use the following 3×3 key matrix for all mathematical examples:

    [6  24  1]
K = [13 16 10]
    [20 17 15]

This matrix has determinant 441, which equals 25 (mod 26). Since gcd(25, 26) = 1, it's a valid Hill cipher key. You can use this same matrix with the code examples below to verify that all calculations match what's shown in this article.

How Encryption Works

Step 1: Convert Letters to Numbers

Assign each letter a number (A=0, B=1, ..., Z=25):

A  B  C  D  E  F  G  H  I  J  K  L  M
0  1  2  3  4  5  6  7  8  9  10 11 12

N  O  P  Q  R  S  T  U  V  W  X  Y  Z
13 14 15 16 17 18 19 20 21 22 23 24 25

Step 2: Group into Vectors

For a 3×3 key matrix, group plaintext into 3-letter blocks:

"ATTACKATDAWN" → "ATT" "ACK" "ATD" "AWN"
                   ↓     ↓     ↓     ↓
                 [0]   [0]   [0]   [0]
                 [19]  [2]   [19]  [22]
                 [19]  [10]  [3]   [13]

If the message length isn't divisible by the block size, pad with X's (the common convention for a 26-letter alphabet). If using an extended alphabet that includes spaces, punctuation, or other characters, you can pad with spaces instead—the Hill cipher works with any alphabet size.

Step 3: Matrix Multiplication

Multiply each plaintext vector by the key matrix, then take mod 26:

Example with key matrix K:

    [6  24  1]
K = [13 16 10]
    [20 17 15]

Encrypting "CAT" = [2, 0, 19]:

[6  24 1 ]   [2 ]   [6×2  + 24×0 + 1×19 ]   [31 ]   [5 ]
[13 16 10] × [0 ] = [13×2 + 16×0 + 10×19] = [216] = [8 ] (mod 26)
[20 17 15]   [19]   [20×2 + 17×0 + 15×19]   [325]   [13]

Result: [5, 8, 13] = "FIN"

So "CAT" encrypts to "FIN".

How Decryption Works

To decrypt, multiply the ciphertext vector by the inverse of the key matrix (mod 26):

K⁻¹ × Ciphertext vector = Plaintext vector (mod 26)

The inverse matrix K⁻¹ satisfies: K × K⁻¹ = I (identity matrix)

For the key matrix above, the inverse (mod 26) is:

      [8  5  10]
K⁻¹ = [21 8  21]
      [21 12 8 ]

Decrypting "FIN" = [5, 8, 13]:

[8  5  10]   [5 ]   [8×5  + 5×8  + 10×13]   [210]   [2 ]
[21 8  21] × [8 ] = [21×5 + 8×8  + 21×13] = [442] = [0 ] (mod 26)
[21 12 8 ]   [13]   [21×5 + 12×8 + 8×13 ]   [305]   [19]

Result: [2, 0, 19] = "CAT"

The Key Matrix Requirements

Not every matrix can be a Hill cipher key. The matrix must be invertible modulo n (where n is the alphabet size, typically 26).

Requirements for a Valid Key Matrix:

1. Must be square (n×n)
2. Determinant must not be zero
3. gcd(determinant, alphabet_size) = 1

The third requirement is crucial. For mod 26:

• Valid determinants: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 (coprime to 26)
• Invalid determinants: 0, 2, 4, 6, 8, 10, 12, 13, 14, 16, 18, 20, 22, 24 (share factors with 26)

Simple rule: Valid determinants are odd numbers except 13, because 26 = 2 × 13. Any multiple of 2 or 13 shares a factor with 26.

Why? If gcd(det, n) ≠ 1, the determinant has no modular multiplicative inverse, so the matrix has no inverse mod n.

The Mystery: How to Generate Valid Matrices

Here's the natural question: How do you mathematically construct a valid key matrix?

The Naive Approach (Generate and Check)

The simplest method:

1. Fill a matrix with random numbers (0 to n-1)
2. Calculate the determinant
3. Check if gcd(det, n) = 1
4. If not, try again

This works but feels unsatisfying—it's trial and error, not mathematics.

The Mathematical Approach

There are several ways to construct valid matrices directly:

Method 1: Start with det = 1

Matrices with determinant 1 are always invertible. You can build them using:

Elementary matrices with det = 1:

• Row swap matrices (det = -1, use two swaps for det = 1)
• Row addition matrices (det = 1)
• Diagonal matrices with product of diagonals = 1

Example: Multiply two elementary "row addition" matrices (each has det = 1):

[1 0 0]   [1 0 0]   [1 0 0]
[2 1 0] × [0 1 0] = [2 1 0]  (det = 1)
[0 0 1]   [3 0 1]   [3 0 1]

Method 2: Triangular Matrices

Upper or lower triangular matrices have determinant = product of diagonal elements.

To get det coprime to 26, make all diagonal elements coprime to 26:

[1 5 7]
[0 3 9]   det = 1 × 3 × 5 = 15, gcd(15, 26) = 1 ✓
[0 0 5]

Then apply row operations to make it look random.

Method 3: Extended Euclidean Algorithm

The key insight is that finding the modular inverse requires the Extended Euclidean Algorithm (EEA).

For integers a and n, the EEA finds x such that:

a × x ≡ 1 (mod n)

This only exists when gcd(a, n) = 1.

The EEA also tells you immediately if an inverse exists—no need for brute-force searching.

Computing the Matrix Inverse (mod n)

To find K⁻¹ mod n:

1. Calculate the determinant of K
2. Find the modular inverse of the determinant using EEA
3. Calculate the adjugate matrix (transpose of cofactor matrix)
4. Multiply adjugate by the modular inverse of determinant
5. Take mod n of all elements (handling negatives correctly)

K⁻¹ = det(K)⁻¹ × adj(K) (mod n)

Security Analysis

The Hill cipher is not secure by modern standards. Here are all the known cryptanalysis techniques:

1. Known-Plaintext Attack

Difficulty: Trivial (if plaintext is available)

If an attacker knows n plaintext-ciphertext pairs (where n is the matrix size), they can solve for the key matrix using linear algebra.

For a 3×3 matrix, knowing 3 plaintext blocks and their ciphertexts gives 9 equations with 9 unknowns—solvable by Gaussian elimination.

The math:

If K × P = C (mod n)
Then K = C × P⁻¹ (mod n)

Where P is a matrix formed from known plaintext blocks (as columns), and C is the corresponding ciphertext matrix.

How do attackers get known plaintext?

The attacker doesn't magically know what the encrypted message says. They obtain plaintext through:

1. Predictable message formats - Military protocols often require standard headers, signatures, or classifications
2. Intelligence from other sources - Captured documents, spies, or protocol manuals reveal message templates
3. Educated guessing (cribs) - Testing common phrases like "ATTACK", "URGENT", "WEATHER REPORT"
4. Forcing known plaintext - Trick the enemy into encrypting something predictable (e.g., plant a mine and wait for the location report)
5. Re-encrypted messages - The same message sent with different keys

Historical example: Bletchley Park broke Enigma partly because German weather reports always started with "WETTER" (weather), and lazy operators sent "NOTHING TO REPORT" repeatedly. These predictable phrases—called cribs—gave codebreakers the known plaintext they needed.

The code examples below demonstrate this attack: an attacker who guesses (correctly) that messages start with "BEGINREPORT" (a standard military message header) can recover the entire key and decrypt all future messages.

Important caveat: The matrix P formed from known plaintext blocks must be invertible (mod 26). If the first 3 blocks happen to form a non-invertible matrix, the attacker simply tries different combinations of known blocks until finding one that works. With enough known plaintext, a working combination is virtually guaranteed.

Worked Example: Breaking a 2×2 Hill Cipher

Let's walk through the attack step by step using a 2×2 key (smaller for easier hand calculation).

Setup: Unknown key matrix K encrypts messages. Attacker intercepts ciphertext and guesses some plaintext.

Known plaintext-ciphertext pairs (attacker obtained these through cribs):

• "AT" → "FL" (letters: [0, 19] → [5, 17])
• "HI" → "TC" (letters: [7, 8] → [19, 2])

Step 1: Build the plaintext and ciphertext matrices

Each column is one block:

P = [0  7 ]    C = [5  19]
    [19 8 ]        [17 2 ]

Step 2: Verify P is invertible

det(P) = (0)(8) - (7)(19) = -133 ≡ 23 (mod 26)
gcd(23, 26) = 1 ✓  (invertible!)

Step 3: Find P⁻¹ (mod 26)

First, find 23⁻¹ mod 26. We need x where 23x ≡ 1 (mod 26).
Testing: 23 × 17 = 391 = 15×26 + 1, so 23⁻¹ = 17

Adjugate of P (swap diagonal, negate off-diagonal):

adj(P) = [8   -7 ]
         [-19  0 ]

Multiply by determinant inverse:

P⁻¹ = 17 × adj(P) (mod 26)
    = [17×8    17×(-7) ] mod 26
      [17×(-19) 17×0   ]
    = [136  -119] mod 26
      [-323   0 ]
    = [6  11]
      [15  0]

Step 4: Recover the key: K = C × P⁻¹ (mod 26)

K = [5  19] × [6  11] mod 26
    [17  2]   [15  0]

K₀₀ = 5×6 + 19×15 = 315 ≡ 3 (mod 26)
K₀₁ = 5×11 + 19×0 = 55 ≡ 3 (mod 26)
K₁₀ = 17×6 + 2×15 = 132 ≡ 2 (mod 26)
K₁₁ = 17×11 + 2×0 = 187 ≡ 5 (mod 26)

K = [3 3]
    [2 5]

The attacker has recovered the secret key. They can now decrypt any message encrypted with this key.

Verification: Let's confirm by encrypting "AT" with the recovered key:

[3 3] × [0 ] = [0 + 57 ] = [57] ≡ [5 ] = "FL" ✓
[2 5]   [19]   [0 + 95]   [95]   [17]

2. Ciphertext-Only Attack: Frequency Analysis

Difficulty: Moderate (requires sufficient ciphertext)

Even without known plaintext, the Hill cipher can be broken using statistical analysis.

Why frequency analysis still works:

The Hill cipher hides single-letter frequencies—"E" doesn't always become the same ciphertext letter. However, it operates on fixed-size blocks, and each block is encrypted independently. This means:

• For a 2×2 key: digraph (2-letter) frequencies are preserved
• For a 3×3 key: trigraph (3-letter) frequencies are preserved

English frequency data attackers exploit:

The attack:

1. Collect enough ciphertext (longer messages = better)
2. Count the frequency of each 3-letter ciphertext block
3. The most frequent ciphertext blocks likely correspond to "THE", "AND", "ING", etc.
4. Use these probable correspondences as "guessed" known plaintext
5. Apply the known-plaintext attack

This is essentially converting a ciphertext-only attack into a known-plaintext attack through statistical inference.

3. Brute Force Attack

Difficulty: Trivial for small keys, impractical for large keys

The keyspace for Hill cipher is finite and often surprisingly small.

Keyspace size:

For an n×n matrix over alphabet size m, the theoretical maximum is m^(n²) matrices, but only those with gcd(det, m) = 1 are valid keys.

The attack:

1. For each possible key matrix:
   • Decrypt the ciphertext
   • Check if result looks like English (letter frequencies, common words)
2. When a key produces readable text, you've found it

For 2×2 and 3×3 keys, this is completely practical on modern hardware. A laptop can test millions of keys per second.

Optimization: Use statistical measures like the Index of Coincidence or chi-squared test to automatically score how "English-like" each decryption attempt is, rather than manual inspection.

4. Chosen-Plaintext Attack

Difficulty: Trivial (if attacker can encrypt chosen messages)

If an attacker can trick the system into encrypting messages of their choice, breaking the cipher becomes even easier.

The attack:

1. Submit carefully chosen plaintexts that form an invertible matrix
2. For a 3×3 key, encrypt: "ABC", "DEF", "GHI" (or any invertible combination)
3. These encrypt to some ciphertext blocks
4. Apply the standard known-plaintext attack

Example setup for instant key recovery:

Plaintext matrix P:     Ciphertext matrix C:
[A B C]   [0 1 2]        [? ? ?]
[D E F] = [3 4 5]   →    [? ? ?]  (observed)
[G H I]   [6 7 8]        [? ? ?]

Key K = C × P⁻¹ (mod 26)

The matrix formed by "ABC/DEF/GHI" has determinant = 0, so it's not invertible. A clever attacker uses something like "ABC/DEG/HIJ" which is invertible.

5. Probable Word Attack (Crib Dragging)

Difficulty: Moderate

Even without confirmed known plaintext, attackers can guess that certain words appear somewhere in the message.

The attack:

1. Assume a common word like "THE" appears at position 0
2. If position 0 ciphertext is "XYZ", assume "THE" → "XYZ"
3. Need more pairs? Assume "THE" also appears at positions 3, 6, 9...
4. Test if a consistent key emerges
5. If not, try "THE" at position 1, 2, 3... and repeat

Why this works:

• Common words appear frequently in most messages
• Only one consistent key can produce the ciphertext
• Wrong guesses produce either no valid key or garbage decryption

Automation: This attack can be fully automated—try all common words at all positions, checking each combination for validity and readable output.

6. The Fundamental Weakness: Linearity

Why Hill cipher is inherently broken:

The Hill cipher is a linear transformation:

E(P₁ + P₂) = E(P₁) + E(P₂)
E(k × P) = k × E(P)

This linearity means:

• No confusion: The relationship between key and ciphertext is mathematically simple
• No diffusion across blocks: Each block is encrypted independently
• Algebraic structure preserved: Patterns in plaintext create exploitable patterns in ciphertext

Comparison with modern ciphers:

Modern ciphers like AES use:

• S-boxes: Non-linear substitution that breaks algebraic relationships
• Multiple rounds: Each round compounds the confusion
• Key mixing: Key material affects every bit of output
• Diffusion: One bit change affects ~50% of output bits

The Hill cipher has none of these properties, making it fundamentally unsuitable for security applications.

Summary: Attack Comparison

Bottom line: The Hill cipher provides obfuscation, not security. Any attacker with basic cryptanalysis knowledge can break it regardless of whether they have known plaintext.

Why It's Still Taught

Despite being thoroughly broken, the Hill cipher teaches valuable concepts:

• Matrix operations in modular arithmetic
• The importance of invertibility in cryptography
• How linear algebra applies to security
• The concept of block ciphers
• Why linearity is dangerous in cryptographic design
• The foundations that led to modern cipher development

Where You'll Encounter It Today

• CTF competitions - Hill cipher challenges appear regularly in capture-the-flag cryptography contests
• University courses - Linear algebra and introductory cryptography classes use it as an accessible hands-on example
• Technical interviews - Security and cryptography positions sometimes include Hill cipher problems
• Historical cryptanalysis - Understanding classical ciphers helps researchers analyze historical encrypted documents

Code Examples

The following implementations in Python, Go, and C are complete and runnable. All three are functionally identical—choose whichever language you prefer. Each one demonstrates key generation, encryption, decryption, and breaking the cipher via known-plaintext attack.

If you're here for the concepts rather than the code, feel free to skip to the Summary section.

Setup Instructions

Python

Requirements: Python 3.6+ with NumPy

# Install NumPy if you don't have it
pip install numpy

# Or with pip3 on some systems
pip3 install numpy

import numpy as np
from math import gcd

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    """Extended Euclidean Algorithm. Returns (gcd, x, y) where ax + by = gcd."""
    if a == 0:
        return b, 0, 1
    gcd_val, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd_val, x, y

def mod_inverse(a: int, m: int) -> int:
    """Find modular multiplicative inverse of a mod m."""
    g, x, _ = extended_gcd(a % m, m)
    if g != 1:
        raise ValueError(f"No modular inverse: gcd({a}, {m}) = {g}")
    return x % m

def matrix_mod_inverse(matrix: np.ndarray, mod: int) -> np.ndarray:
    """Calculate the modular inverse of a matrix."""
    # Calculate determinant
    det = int(round(np.linalg.det(matrix)))
    det = det % mod
    if det < 0:
        det += mod

    # Find modular inverse of determinant
    det_inv = mod_inverse(det, mod)

    # Calculate adjugate matrix (transpose of cofactor matrix)
    n = matrix.shape[0]
    adjugate = np.zeros((n, n), dtype=int)

    for i in range(n):
        for j in range(n):
            # Minor matrix (remove row i, column j)
            minor = np.delete(np.delete(matrix, i, axis=0), j, axis=1)
            # Cofactor with sign
            cofactor = ((-1) ** (i + j)) * int(round(np.linalg.det(minor)))
            # Adjugate is transpose of cofactor matrix
            adjugate[j, i] = cofactor

    # Multiply by modular inverse of determinant
    inverse = (det_inv * adjugate) % mod
    return inverse

def text_to_vector(text: str, alphabet: str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ") -> list[int]:
    """Convert text to list of numbers."""
    return [alphabet.index(c.upper()) for c in text if c.upper() in alphabet]

def vector_to_text(vector: list[int], alphabet: str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ") -> str:
    """Convert list of numbers to text."""
    return ''.join(alphabet[i % len(alphabet)] for i in vector)

def hill_encrypt(plaintext: str, key_matrix: np.ndarray,
                 alphabet: str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ") -> str:
    """Encrypt plaintext using Hill cipher."""
    mod = len(alphabet)
    n = key_matrix.shape[0]

    # Convert to numbers and pad if necessary
    numbers = text_to_vector(plaintext, alphabet)
    while len(numbers) % n != 0:
        numbers.append(alphabet.index('X'))

    # Encrypt each block
    ciphertext = []
    for i in range(0, len(numbers), n):
        block = np.array(numbers[i:i+n])
        encrypted = np.dot(key_matrix, block) % mod
        ciphertext.extend(encrypted.tolist())

    return vector_to_text(ciphertext, alphabet)

def hill_decrypt(ciphertext: str, key_matrix: np.ndarray,
                 alphabet: str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ") -> str:
    """Decrypt ciphertext using Hill cipher."""
    mod = len(alphabet)
    inverse_matrix = matrix_mod_inverse(key_matrix, mod)

    # Convert to numbers
    numbers = text_to_vector(ciphertext, alphabet)
    n = key_matrix.shape[0]

    # Decrypt each block
    plaintext = []
    for i in range(0, len(numbers), n):
        block = np.array(numbers[i:i+n])
        decrypted = np.dot(inverse_matrix, block) % mod
        plaintext.extend(decrypted.tolist())

    return vector_to_text(plaintext, alphabet)

def generate_valid_key(n: int, mod: int = 26) -> np.ndarray:
    """Generate a valid n×n key matrix for Hill cipher."""
    while True:
        # Generate random matrix
        matrix = np.random.randint(0, mod, (n, n))
        det = int(round(np.linalg.det(matrix))) % mod
        if det < 0:
            det += mod
        # Check if determinant is coprime to mod
        if gcd(det, mod) == 1:
            return matrix

def is_valid_key(matrix: np.ndarray, mod: int = 26) -> bool:
    """Check if a matrix is valid for Hill cipher."""
    det = int(round(np.linalg.det(matrix))) % mod
    if det < 0:
        det += mod
    return gcd(det, mod) == 1

def break_cipher(known_plaintext: list[str], known_ciphertext: list[str],
                 block_size: int = 3, mod: int = 26) -> np.ndarray:
    """
    Break Hill cipher using known-plaintext attack.

    Args:
        known_plaintext: List of plaintext blocks (e.g., ["CAT", "DOG", "BAT"])
        known_ciphertext: Corresponding ciphertext blocks (e.g., ["FIN", "XYZ", "ABC"])
        block_size: Size of the key matrix (n for n×n)
        mod: Alphabet size (default 26)

    Returns:
        The recovered key matrix

    The attack works because:
        K × P = C (mod n)
        Therefore: K = C × P⁻¹ (mod n)
    """
    if len(known_plaintext) < block_size:
        raise ValueError(f"Need at least {block_size} known plaintext-ciphertext pairs")

    # Build plaintext matrix P (each column is a plaintext block)
    P = np.zeros((block_size, block_size), dtype=int)
    for j, pt in enumerate(known_plaintext[:block_size]):
        for i, char in enumerate(pt[:block_size]):
            P[i, j] = ord(char.upper()) - ord('A')

    # Build ciphertext matrix C (each column is a ciphertext block)
    C = np.zeros((block_size, block_size), dtype=int)
    for j, ct in enumerate(known_ciphertext[:block_size]):
        for i, char in enumerate(ct[:block_size]):
            C[i, j] = ord(char.upper()) - ord('A')

    # Check if P is invertible
    if not is_valid_key(P, mod):
        raise ValueError("Plaintext matrix is not invertible. Try different known pairs.")

    # Calculate K = C × P⁻¹ (mod n)
    P_inv = matrix_mod_inverse(P, mod)
    K = np.dot(C, P_inv) % mod

    return K


# ============ Example Usage ============

if __name__ == "__main__":
    print("=" * 60)
    print("HILL CIPHER DEMONSTRATION")
    print("=" * 60)

    # ============ Step 1: Generate a random valid key ============
    print("\n[STEP 1] Generating a random valid 3x3 key matrix...")
    print("-" * 60)

    key = generate_valid_key(3)
    det_raw = int(round(np.linalg.det(key)))
    det_mod = det_raw % 26
    if det_mod < 0:
        det_mod += 26

    print(f"Generated key matrix:\n{key}")
    print(f"\nDeterminant: {det_raw}")
    print(f"Determinant (mod 26): {det_mod}")
    print(f"Greatest Common Divisor of ({det_mod}, 26) = {gcd(det_mod, 26)}")
    print(f"Valid key (GCD must equal 1): {is_valid_key(key)}")

    # ============ Step 2: Encrypt ============
    print("\n" + "=" * 60)
    print("[STEP 2] Encryption")
    print("-" * 60)

    plaintext = "ATTACKATDAWN"
    ciphertext = hill_encrypt(plaintext, key)
    print(f"Plaintext:  '{plaintext}'")
    print(f"Ciphertext: '{ciphertext}'")

    # ============ Step 3: Decrypt ============
    print("\n" + "=" * 60)
    print("[STEP 3] Decryption")
    print("-" * 60)

    inverse = matrix_mod_inverse(key, 26)
    print(f"Inverse matrix (mod 26):\n{inverse}")

    decrypted = hill_decrypt(ciphertext, key)
    print(f"\nCiphertext: '{ciphertext}'")
    print(f"Decrypted:  '{decrypted}'")
    print(f"Matches original: {decrypted == plaintext}")

    # ============ Step 4: Breaking the cipher ============
    print("\n" + "=" * 60)
    print("[STEP 4] Known-Plaintext Attack (Breaking the Cipher)")
    print("-" * 60)

    # Scenario: Attacker intercepts an encrypted message.
    # From intelligence reports, they GUESS that military messages
    # always start with "BEGINREPORT" (a standard header).
    # They test this hypothesis...

    secret_message = "BEGINREPORTMEETATTHENORTHGATE"
    intercepted_ciphertext = hill_encrypt(secret_message, key)

    # Attacker assumes first 9 chars of ciphertext = encrypted "BEGINREPO"
    # They only need 3 blocks (9 chars) to break a 3x3 key
    known_pt = ["BEG", "INR", "EPO"]  # Their guess
    known_ct = [intercepted_ciphertext[i:i+3] for i in range(0, 9, 3)]

    print(f"Scenario: Attacker intercepts ciphertext and GUESSES the header")
    print(f"\nIntercepted ciphertext: '{intercepted_ciphertext}'")
    print(f"Attacker's guess: First 9 chars are encrypted 'BEGINREPO'")
    print(f"\nAssumed plaintext-ciphertext pairs:")
    for pt, ct in zip(known_pt, known_ct):
        print(f"  '{pt}' -> '{ct}'")

    # Break the cipher!
    try:
        recovered_key = break_cipher(known_pt, known_ct, block_size=3)
        print(f"\nRecovered key matrix:\n{recovered_key}")
        print(f"\nOriginal key matrix (for comparison):\n{key}")
        print(f"\nKeys match: {np.array_equal(recovered_key, key)}")

        # Now the attacker can decrypt the ENTIRE intercepted message!
        full_decrypted = hill_decrypt(intercepted_ciphertext, recovered_key)
        print(f"\n*** ATTACK SUCCESSFUL ***")
        print(f"Decrypted message: '{full_decrypted}'")
        print(f"\nThe attacker guessed 9 characters correctly and can now")
        print(f"decrypt ALL messages encrypted with this key!")
    except ValueError as e:
        print(f"Attack failed: {e}")

    print("\n" + "=" * 60)

Go (Golang)

Requirements: Go 1.18+ (uses generics-style code)

package main

import (
	"fmt"
	"math/rand"
	"strings"
	"time"
)

const alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

// extendedGCD returns gcd, x, y such that ax + by = gcd
func extendedGCD(a, b int) (int, int, int) {
	if a == 0 {
		return b, 0, 1
	}
	gcd, x1, y1 := extendedGCD(b%a, a)
	x := y1 - (b/a)*x1
	y := x1
	return gcd, x, y
}

// modInverse finds the modular multiplicative inverse of a mod m
func modInverse(a, m int) (int, error) {
	a = ((a % m) + m) % m
	gcd, x, _ := extendedGCD(a, m)
	if gcd != 1 {
		return 0, fmt.Errorf("no modular inverse: gcd(%d, %d) = %d", a, m, gcd)
	}
	return ((x % m) + m) % m, nil
}

// gcd calculates greatest common divisor
func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

// Matrix represents an n×n matrix
type Matrix [][]int

// NewMatrix creates a new n×n matrix
func NewMatrix(n int) Matrix {
	m := make(Matrix, n)
	for i := range m {
		m[i] = make([]int, n)
	}
	return m
}

// determinant2x2 calculates determinant of 2x2 matrix
func determinant2x2(m Matrix) int {
	return m[0][0]*m[1][1] - m[0][1]*m[1][0]
}

// determinant3x3 calculates determinant of 3x3 matrix
func determinant3x3(m Matrix) int {
	return m[0][0]*(m[1][1]*m[2][2]-m[1][2]*m[2][1]) -
		m[0][1]*(m[1][0]*m[2][2]-m[1][2]*m[2][0]) +
		m[0][2]*(m[1][0]*m[2][1]-m[1][1]*m[2][0])
}

// Determinant calculates the determinant of a matrix
func (m Matrix) Determinant() int {
	n := len(m)
	if n == 2 {
		return determinant2x2(m)
	}
	if n == 3 {
		return determinant3x3(m)
	}
	// For larger matrices, use cofactor expansion (recursive)
	det := 0
	for j := 0; j < n; j++ {
		minor := m.Minor(0, j)
		sign := 1
		if j%2 == 1 {
			sign = -1
		}
		det += sign * m[0][j] * minor.Determinant()
	}
	return det
}

// Minor returns the minor matrix (removing row i and column j)
func (m Matrix) Minor(row, col int) Matrix {
	n := len(m)
	minor := NewMatrix(n - 1)
	mi := 0
	for i := 0; i < n; i++ {
		if i == row {
			continue
		}
		mj := 0
		for j := 0; j < n; j++ {
			if j == col {
				continue
			}
			minor[mi][mj] = m[i][j]
			mj++
		}
		mi++
	}
	return minor
}

// Cofactor returns the cofactor matrix
func (m Matrix) Cofactor() Matrix {
	n := len(m)
	cof := NewMatrix(n)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			minor := m.Minor(i, j)
			sign := 1
			if (i+j)%2 == 1 {
				sign = -1
			}
			cof[i][j] = sign * minor.Determinant()
		}
	}
	return cof
}

// Transpose returns the transpose of the matrix
func (m Matrix) Transpose() Matrix {
	n := len(m)
	t := NewMatrix(n)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			t[j][i] = m[i][j]
		}
	}
	return t
}

// ModInverse calculates the modular inverse of the matrix
func (m Matrix) ModInverse(mod int) (Matrix, error) {
	det := m.Determinant()
	det = ((det % mod) + mod) % mod

	detInv, err := modInverse(det, mod)
	if err != nil {
		return nil, err
	}

	// Adjugate = transpose of cofactor matrix
	adjugate := m.Cofactor().Transpose()

	// Multiply by modular inverse of determinant
	n := len(m)
	inverse := NewMatrix(n)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			inverse[i][j] = ((adjugate[i][j]*detInv)%mod + mod) % mod
		}
	}
	return inverse, nil
}

// IsValid checks if the matrix is valid for Hill cipher
func (m Matrix) IsValid(mod int) bool {
	det := m.Determinant()
	det = ((det % mod) + mod) % mod
	return gcd(det, mod) == 1
}

// Multiply multiplies matrix by a vector
func (m Matrix) Multiply(v []int, mod int) []int {
	n := len(m)
	result := make([]int, n)
	for i := 0; i < n; i++ {
		sum := 0
		for j := 0; j < n; j++ {
			sum += m[i][j] * v[j]
		}
		result[i] = ((sum % mod) + mod) % mod
	}
	return result
}

// textToNumbers converts text to numbers
func textToNumbers(text string) []int {
	text = strings.ToUpper(text)
	nums := make([]int, 0)
	for _, c := range text {
		idx := strings.IndexRune(alphabet, c)
		if idx >= 0 {
			nums = append(nums, idx)
		}
	}
	return nums
}

// numbersToText converts numbers to text
func numbersToText(nums []int) string {
	result := make([]byte, len(nums))
	for i, n := range nums {
		result[i] = alphabet[n%26]
	}
	return string(result)
}

// HillEncrypt encrypts plaintext using the Hill cipher
func HillEncrypt(plaintext string, key Matrix) string {
	mod := 26
	n := len(key)
	nums := textToNumbers(plaintext)

	// Pad if necessary
	for len(nums)%n != 0 {
		nums = append(nums, 23) // 'X'
	}

	// Encrypt each block
	result := make([]int, 0)
	for i := 0; i < len(nums); i += n {
		block := nums[i : i+n]
		encrypted := key.Multiply(block, mod)
		result = append(result, encrypted...)
	}

	return numbersToText(result)
}

// HillDecrypt decrypts ciphertext using the Hill cipher
func HillDecrypt(ciphertext string, key Matrix) (string, error) {
	mod := 26
	inverse, err := key.ModInverse(mod)
	if err != nil {
		return "", err
	}

	n := len(key)
	nums := textToNumbers(ciphertext)

	// Decrypt each block
	result := make([]int, 0)
	for i := 0; i < len(nums); i += n {
		block := nums[i : i+n]
		decrypted := inverse.Multiply(block, mod)
		result = append(result, decrypted...)
	}

	return numbersToText(result), nil
}

// GenerateValidKey generates a random valid key matrix
func GenerateValidKey(n, mod int) Matrix {
	rand.Seed(time.Now().UnixNano())
	for {
		m := NewMatrix(n)
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				m[i][j] = rand.Intn(mod)
			}
		}
		if m.IsValid(mod) {
			return m
		}
	}
}

// BreakCipher performs a known-plaintext attack to recover the key
// knownPT and knownCT are slices of strings (e.g., ["CAT", "DOG", "BAT"])
func BreakCipher(knownPT, knownCT []string, blockSize, mod int) (Matrix, error) {
	if len(knownPT) < blockSize || len(knownCT) < blockSize {
		return nil, fmt.Errorf("need at least %d known pairs", blockSize)
	}

	// Build plaintext matrix P (columns are plaintext blocks)
	P := NewMatrix(blockSize)
	for j := 0; j < blockSize; j++ {
		pt := strings.ToUpper(knownPT[j])
		for i := 0; i < blockSize && i < len(pt); i++ {
			P[i][j] = int(pt[i] - 'A')
		}
	}

	// Build ciphertext matrix C (columns are ciphertext blocks)
	C := NewMatrix(blockSize)
	for j := 0; j < blockSize; j++ {
		ct := strings.ToUpper(knownCT[j])
		for i := 0; i < blockSize && i < len(ct); i++ {
			C[i][j] = int(ct[i] - 'A')
		}
	}

	// Check if P is invertible
	if !P.IsValid(mod) {
		return nil, fmt.Errorf("plaintext matrix not invertible, try different pairs")
	}

	// Calculate K = C × P⁻¹ (mod n)
	PInv, err := P.ModInverse(mod)
	if err != nil {
		return nil, err
	}

	// Matrix multiplication: K = C × PInv
	K := NewMatrix(blockSize)
	for i := 0; i < blockSize; i++ {
		for j := 0; j < blockSize; j++ {
			sum := 0
			for k := 0; k < blockSize; k++ {
				sum += C[i][k] * PInv[k][j]
			}
			K[i][j] = ((sum % mod) + mod) % mod
		}
	}

	return K, nil
}

func main() {
	fmt.Println("============================================================")
	fmt.Println("HILL CIPHER DEMONSTRATION")
	fmt.Println("============================================================")

	// ============ Step 1: Generate a random valid key ============
	fmt.Println("\n[STEP 1] Generating a random valid 3x3 key matrix...")
	fmt.Println("------------------------------------------------------------")

	key := GenerateValidKey(3, 26)
	det := key.Determinant()
	detMod := ((det % 26) + 26) % 26

	fmt.Println("Generated key matrix:")
	for _, row := range key {
		fmt.Println(row)
	}
	fmt.Printf("\nDeterminant: %d\n", det)
	fmt.Printf("Determinant (mod 26): %d\n", detMod)
	fmt.Printf("Greatest Common Divisor of (%d, 26) = %d\n", detMod, gcd(detMod, 26))
	fmt.Printf("Valid key (GCD must equal 1): %v\n", key.IsValid(26))

	// ============ Step 2: Encrypt ============
	fmt.Println("\n============================================================")
	fmt.Println("[STEP 2] Encryption")
	fmt.Println("------------------------------------------------------------")

	plaintext := "ATTACKATDAWN"
	ciphertext := HillEncrypt(plaintext, key)
	fmt.Printf("Plaintext:  '%s'\n", plaintext)
	fmt.Printf("Ciphertext: '%s'\n", ciphertext)

	// ============ Step 3: Decrypt ============
	fmt.Println("\n============================================================")
	fmt.Println("[STEP 3] Decryption")
	fmt.Println("------------------------------------------------------------")

	inverse, _ := key.ModInverse(26)
	fmt.Println("Inverse matrix (mod 26):")
	for _, row := range inverse {
		fmt.Println(row)
	}

	decrypted, _ := HillDecrypt(ciphertext, key)
	fmt.Printf("\nCiphertext: '%s'\n", ciphertext)
	fmt.Printf("Decrypted:  '%s'\n", decrypted)
	fmt.Printf("Matches original: %v\n", decrypted == plaintext)

	// ============ Step 4: Breaking the cipher ============
	fmt.Println("\n============================================================")
	fmt.Println("[STEP 4] Known-Plaintext Attack (Breaking the Cipher)")
	fmt.Println("------------------------------------------------------------")

	// Scenario: Attacker intercepts ciphertext and GUESSES the header
	secretMessage := "BEGINREPORTMEETATTHENORTHGATE"
	interceptedCiphertext := HillEncrypt(secretMessage, key)

	// Attacker guesses first 9 chars are encrypted "BEGINREPO"
	knownPT := []string{"BEG", "INR", "EPO"}
	knownCT := []string{
		interceptedCiphertext[0:3],
		interceptedCiphertext[3:6],
		interceptedCiphertext[6:9],
	}

	fmt.Println("Scenario: Attacker intercepts ciphertext and GUESSES the header")
	fmt.Printf("\nIntercepted ciphertext: '%s'\n", interceptedCiphertext)
	fmt.Println("Attacker's guess: First 9 chars are encrypted 'BEGINREPO'")
	fmt.Println("\nAssumed plaintext-ciphertext pairs:")
	for i := 0; i < 3; i++ {
		fmt.Printf("  '%s' -> '%s'\n", knownPT[i], knownCT[i])
	}

	// Break the cipher!
	recoveredKey, err := BreakCipher(knownPT, knownCT, 3, 26)
	if err != nil {
		fmt.Printf("Attack failed: %v\n", err)
	} else {
		fmt.Println("\nRecovered key matrix:")
		for _, row := range recoveredKey {
			fmt.Println(row)
		}

		fmt.Println("\nOriginal key matrix (for comparison):")
		for _, row := range key {
			fmt.Println(row)
		}

		// Now the attacker can decrypt the ENTIRE message!
		fullDecrypted, _ := HillDecrypt(interceptedCiphertext, recoveredKey)
		fmt.Println("\n*** ATTACK SUCCESSFUL ***")
		fmt.Printf("Decrypted message: '%s'\n", fullDecrypted)
		fmt.Println("\nThe attacker guessed 9 characters correctly and can now")
		fmt.Println("decrypt ALL messages encrypted with this key!")
	}

	fmt.Println("\n============================================================")
}

C

Requirements: GCC or Clang, compiles on Linux and macOS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

#define ALPHABET_SIZE 26

// Extended Euclidean Algorithm
// Returns gcd, and sets *x, *y such that ax + by = gcd
int extended_gcd(int a, int b, int *x, int *y) {
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }
    int x1, y1;
    int gcd = extended_gcd(b % a, a, &x1, &y1);
    *x = y1 - (b / a) * x1;
    *y = x1;
    return gcd;
}

// Find modular multiplicative inverse of a mod m
// Returns -1 if no inverse exists
int mod_inverse(int a, int m) {
    a = ((a % m) + m) % m;
    int x, y;
    int gcd = extended_gcd(a, m, &x, &y);
    if (gcd != 1) {
        return -1;  // No inverse
    }
    return ((x % m) + m) % m;
}

// GCD function
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// Positive modulo (handles negative numbers)
int pos_mod(int a, int m) {
    return ((a % m) + m) % m;
}

// 3x3 Matrix type
typedef struct {
    int data[3][3];
} Matrix3x3;

// Calculate determinant of 3x3 matrix
int determinant_3x3(Matrix3x3 *m) {
    return m->data[0][0] * (m->data[1][1] * m->data[2][2] - m->data[1][2] * m->data[2][1])
         - m->data[0][1] * (m->data[1][0] * m->data[2][2] - m->data[1][2] * m->data[2][0])
         + m->data[0][2] * (m->data[1][0] * m->data[2][1] - m->data[1][1] * m->data[2][0]);
}

// Check if matrix is valid for Hill cipher
int is_valid_key(Matrix3x3 *m, int mod) {
    int det = pos_mod(determinant_3x3(m), mod);
    return gcd(det, mod) == 1;
}

// Calculate cofactor matrix
void cofactor_matrix(Matrix3x3 *m, Matrix3x3 *cof) {
    cof->data[0][0] = m->data[1][1] * m->data[2][2] - m->data[1][2] * m->data[2][1];
    cof->data[0][1] = -(m->data[1][0] * m->data[2][2] - m->data[1][2] * m->data[2][0]);
    cof->data[0][2] = m->data[1][0] * m->data[2][1] - m->data[1][1] * m->data[2][0];

    cof->data[1][0] = -(m->data[0][1] * m->data[2][2] - m->data[0][2] * m->data[2][1]);
    cof->data[1][1] = m->data[0][0] * m->data[2][2] - m->data[0][2] * m->data[2][0];
    cof->data[1][2] = -(m->data[0][0] * m->data[2][1] - m->data[0][1] * m->data[2][0]);

    cof->data[2][0] = m->data[0][1] * m->data[1][2] - m->data[0][2] * m->data[1][1];
    cof->data[2][1] = -(m->data[0][0] * m->data[1][2] - m->data[0][2] * m->data[1][0]);
    cof->data[2][2] = m->data[0][0] * m->data[1][1] - m->data[0][1] * m->data[1][0];
}

// Transpose matrix
void transpose(Matrix3x3 *m, Matrix3x3 *t) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            t->data[j][i] = m->data[i][j];
        }
    }
}

// Calculate modular inverse of matrix
// Returns 0 on success, -1 on failure
int matrix_mod_inverse(Matrix3x3 *m, int mod, Matrix3x3 *inverse) {
    int det = pos_mod(determinant_3x3(m), mod);
    int det_inv = mod_inverse(det, mod);

    if (det_inv == -1) {
        return -1;  // No inverse
    }

    // Calculate adjugate (transpose of cofactor)
    Matrix3x3 cofactor, adjugate;
    cofactor_matrix(m, &cofactor);
    transpose(&cofactor, &adjugate);

    // Multiply by modular inverse of determinant
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            inverse->data[i][j] = pos_mod(adjugate.data[i][j] * det_inv, mod);
        }
    }

    return 0;
}

// Multiply matrix by vector
void matrix_multiply_vector(Matrix3x3 *m, int *v, int *result, int mod) {
    for (int i = 0; i < 3; i++) {
        int sum = 0;
        for (int j = 0; j < 3; j++) {
            sum += m->data[i][j] * v[j];
        }
        result[i] = pos_mod(sum, mod);
    }
}

// Convert character to number (A=0, B=1, ..., Z=25)
int char_to_num(char c) {
    return toupper(c) - 'A';
}

// Convert number to character
char num_to_char(int n) {
    return 'A' + (n % 26);
}

// Hill cipher encrypt
void hill_encrypt(const char *plaintext, Matrix3x3 *key, char *ciphertext) {
    int len = strlen(plaintext);
    int padded_len = len;

    // Calculate padded length (multiple of 3)
    if (len % 3 != 0) {
        padded_len = len + (3 - len % 3);
    }

    // Convert plaintext to numbers with padding
    int *nums = malloc(padded_len * sizeof(int));
    int j = 0;
    for (int i = 0; i < len; i++) {
        if (isalpha(plaintext[i])) {
            nums[j++] = char_to_num(plaintext[i]);
        }
    }
    // Pad with X (23)
    while (j < padded_len) {
        nums[j++] = 23;
    }

    // Encrypt each block
    int ct_idx = 0;
    for (int i = 0; i < padded_len; i += 3) {
        int block[3] = {nums[i], nums[i+1], nums[i+2]};
        int encrypted[3];
        matrix_multiply_vector(key, block, encrypted, 26);
        ciphertext[ct_idx++] = num_to_char(encrypted[0]);
        ciphertext[ct_idx++] = num_to_char(encrypted[1]);
        ciphertext[ct_idx++] = num_to_char(encrypted[2]);
    }
    ciphertext[ct_idx] = '\0';

    free(nums);
}

// Hill cipher decrypt
int hill_decrypt(const char *ciphertext, Matrix3x3 *key, char *plaintext) {
    Matrix3x3 inverse;
    if (matrix_mod_inverse(key, 26, &inverse) != 0) {
        return -1;  // Key not invertible
    }

    int len = strlen(ciphertext);

    // Convert ciphertext to numbers
    int *nums = malloc(len * sizeof(int));
    int j = 0;
    for (int i = 0; i < len; i++) {
        if (isalpha(ciphertext[i])) {
            nums[j++] = char_to_num(ciphertext[i]);
        }
    }
    int num_len = j;

    // Decrypt each block
    int pt_idx = 0;
    for (int i = 0; i < num_len; i += 3) {
        int block[3] = {nums[i], nums[i+1], nums[i+2]};
        int decrypted[3];
        matrix_multiply_vector(&inverse, block, decrypted, 26);
        plaintext[pt_idx++] = num_to_char(decrypted[0]);
        plaintext[pt_idx++] = num_to_char(decrypted[1]);
        plaintext[pt_idx++] = num_to_char(decrypted[2]);
    }
    plaintext[pt_idx] = '\0';

    free(nums);
    return 0;
}

// Generate a random valid key matrix
void generate_valid_key(Matrix3x3 *key, int mod) {
    srand(time(NULL));
    do {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                key->data[i][j] = rand() % mod;
            }
        }
    } while (!is_valid_key(key, mod));
}

// Break cipher using known-plaintext attack
// Returns 0 on success, -1 on failure
int break_cipher(const char *known_pt[], const char *known_ct[],
                 int num_pairs, Matrix3x3 *recovered_key, int mod) {
    if (num_pairs < 3) {
        return -1;  // Need at least 3 pairs for 3x3 matrix
    }

    // Build plaintext matrix P (columns are plaintext blocks)
    Matrix3x3 P = {{{0}}};
    for (int j = 0; j < 3; j++) {
        for (int i = 0; i < 3 && known_pt[j][i] != '\0'; i++) {
            P.data[i][j] = char_to_num(known_pt[j][i]);
        }
    }

    // Build ciphertext matrix C (columns are ciphertext blocks)
    Matrix3x3 C = {{{0}}};
    for (int j = 0; j < 3; j++) {
        for (int i = 0; i < 3 && known_ct[j][i] != '\0'; i++) {
            C.data[i][j] = char_to_num(known_ct[j][i]);
        }
    }

    // Check if P is invertible
    if (!is_valid_key(&P, mod)) {
        return -1;  // Plaintext matrix not invertible
    }

    // Calculate P_inv
    Matrix3x3 P_inv;
    if (matrix_mod_inverse(&P, mod, &P_inv) != 0) {
        return -1;
    }

    // Calculate K = C × P_inv (mod n)
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            int sum = 0;
            for (int k = 0; k < 3; k++) {
                sum += C.data[i][k] * P_inv.data[k][j];
            }
            recovered_key->data[i][j] = pos_mod(sum, mod);
        }
    }

    return 0;
}

// Print matrix
void print_matrix(Matrix3x3 *m) {
    for (int i = 0; i < 3; i++) {
        printf("[%3d %3d %3d]\n", m->data[i][0], m->data[i][1], m->data[i][2]);
    }
}

int main() {
    printf("============================================================\n");
    printf("HILL CIPHER DEMONSTRATION\n");
    printf("============================================================\n");

    // ============ Step 1: Generate a random valid key ============
    printf("\n[STEP 1] Generating a random valid 3x3 key matrix...\n");
    printf("------------------------------------------------------------\n");

    Matrix3x3 key;
    generate_valid_key(&key, 26);
    int det_raw = determinant_3x3(&key);
    int det_mod = pos_mod(det_raw, 26);

    printf("Generated key matrix:\n");
    print_matrix(&key);
    printf("\nDeterminant: %d\n", det_raw);
    printf("Determinant (mod 26): %d\n", det_mod);
    printf("Greatest Common Divisor of (%d, 26) = %d\n", det_mod, gcd(det_mod, 26));
    printf("Valid key (GCD must equal 1): %s\n", is_valid_key(&key, 26) ? "true" : "false");

    // ============ Step 2: Encrypt ============
    printf("\n============================================================\n");
    printf("[STEP 2] Encryption\n");
    printf("------------------------------------------------------------\n");

    const char *plaintext = "ATTACKATDAWN";
    char ciphertext[100];
    char decrypted[100];

    hill_encrypt(plaintext, &key, ciphertext);
    printf("Plaintext:  '%s'\n", plaintext);
    printf("Ciphertext: '%s'\n", ciphertext);

    // ============ Step 3: Decrypt ============
    printf("\n============================================================\n");
    printf("[STEP 3] Decryption\n");
    printf("------------------------------------------------------------\n");

    Matrix3x3 inverse;
    matrix_mod_inverse(&key, 26, &inverse);
    printf("Inverse matrix (mod 26):\n");
    print_matrix(&inverse);

    hill_decrypt(ciphertext, &key, decrypted);
    printf("\nCiphertext: '%s'\n", ciphertext);
    printf("Decrypted:  '%s'\n", decrypted);
    printf("Matches original: %s\n", strcmp(decrypted, plaintext) == 0 ? "true" : "false");

    // ============ Step 4: Breaking the cipher ============
    printf("\n============================================================\n");
    printf("[STEP 4] Known-Plaintext Attack (Breaking the Cipher)\n");
    printf("------------------------------------------------------------\n");

    // Scenario: Attacker intercepts ciphertext and GUESSES the header
    char intercepted_ciphertext[50];
    hill_encrypt("BEGINREPORTMEETATTHENORTHGATE", &key, intercepted_ciphertext);

    // Attacker guesses first 9 chars are encrypted "BEGINREPO"
    const char *known_pt[] = {"BEG", "INR", "EPO"};
    char known_ct_0[4], known_ct_1[4], known_ct_2[4];

    strncpy(known_ct_0, intercepted_ciphertext + 0, 3); known_ct_0[3] = '\0';
    strncpy(known_ct_1, intercepted_ciphertext + 3, 3); known_ct_1[3] = '\0';
    strncpy(known_ct_2, intercepted_ciphertext + 6, 3); known_ct_2[3] = '\0';

    const char *known_ct[] = {known_ct_0, known_ct_1, known_ct_2};

    printf("Scenario: Attacker intercepts ciphertext and GUESSES the header\n");
    printf("\nIntercepted ciphertext: '%s'\n", intercepted_ciphertext);
    printf("Attacker's guess: First 9 chars are encrypted 'BEGINREPO'\n");
    printf("\nAssumed plaintext-ciphertext pairs:\n");
    for (int i = 0; i < 3; i++) {
        printf("  '%s' -> '%s'\n", known_pt[i], known_ct[i]);
    }

    // Break the cipher!
    Matrix3x3 recovered;
    if (break_cipher(known_pt, known_ct, 3, &recovered, 26) == 0) {
        printf("\nRecovered key matrix:\n");
        print_matrix(&recovered);

        printf("\nOriginal key matrix (for comparison):\n");
        print_matrix(&key);

        // Now the attacker can decrypt the ENTIRE message!
        char full_decrypted[50];
        hill_decrypt(intercepted_ciphertext, &recovered, full_decrypted);

        printf("\n*** ATTACK SUCCESSFUL ***\n");
        printf("Decrypted message: '%s'\n", full_decrypted);
        printf("\nThe attacker guessed 9 characters correctly and can now\n");
        printf("decrypt ALL messages encrypted with this key!\n");
    } else {
        printf("Attack failed!\n");
    }

    printf("\n============================================================\n");

    return 0;
}

Compile and run:

# Linux / macOS
gcc -o hill_cipher hill_cipher.c -lm
./hill_cipher

Summary

The Hill cipher demonstrates how linear algebra applies to cryptography:

1. Encryption = Matrix multiplication (mod n)
2. Decryption = Multiplication by the inverse matrix (mod n)
3. Key validity = gcd(determinant, alphabet_size) must equal 1
4. Finding the inverse = Extended Euclidean Algorithm + adjugate matrix

While broken by modern standards, the Hill cipher teaches fundamental concepts that appear in modern cryptography—including AES, which uses matrix operations in finite fields.

The mystery of generating valid matrices isn't a mystery at all: it's just number theory. Use the Extended Euclidean Algorithm to verify (or find) the modular inverse, and you'll always know if your matrix works.

References

1. Hill, L. S. (1929). Cryptography in an Algebraic Alphabet. The American Mathematical Monthly, 36(6), 306-312.
2. Hill, L. S. (1931). Concerning Certain Linear Transformation Apparatus of Cryptography. The American Mathematical Monthly, 38(3), 135-154.
3. Menezes, A., van Oorschot, P., & Vanstone, S. (1996). Handbook of Applied Cryptography. CRC Press. Chapter 7: Block Ciphers
4. Stinson, D. R. (2005). Cryptography: Theory and Practice (3rd ed.). Chapman & Hall/CRC.
5. Textos Científicos - Criptosistema Hill (Spanish resource from ~2006)