Hill Cipher

Encrypting several letters at once

Caesar and Vigenère change one letter at a time, so letter frequencies leak through. The Playfair cipher works on pairs. In 1929 Lester Hill went further: treat a block of m letters as a vector and multiply it by an m × m key matrix, modulo 26. Every ciphertext letter then depends on every letter of its block.

Encryption

Number the letters A = 0, B = 1, …, Z = 25. Cut the plaintext into blocks of m letters (pad the last block with X). For each block p:

c = K · p   (mod 26)

Example: K = [[3, 3], [2, 5]] (key letters DDCF), plaintext HELP.

HELP becomes HIAT. Each ciphertext letter mixes both letters of its block, so the same letter can encrypt differently depending on its neighbour: the E in HE becomes I, but the E in ME (12, 4) becomes S, because ME encrypts to WS.

Some books use row vectors, c = p · K. That is the same cipher with the key matrix transposed.

Decryption needs the inverse matrix

To undo the multiplication we need K⁻¹ mod 26:

1. Determinant: det K = 3·5 − 3·2 = 9.
2. Inverse of the determinant mod 26, using the extended Euclidean algorithm: 9 × 3 = 27 ≡ 1, so det⁻¹ = 3.
3. Adjugate: for a 2 × 2 matrix, swap the diagonal and negate the other two: adj K = [[5, −3], [−2, 3]] ≡ [[5, 23], [24, 3]].
4. K⁻¹ = det⁻¹ · adj K mod 26 = 3 · [[5, 23], [24, 3]] = [[15, 69], [72, 9]] ≡ [[15, 17], [20, 9]].

Then p = K⁻¹ · c mod 26 gives HELP back. For a 3 × 3 key, the adjugate is the transposed matrix of cofactors (signed 2 × 2 determinants). The model computes it for the key GYBNQKURP, whose inverse is [[8, 5, 10], [21, 8, 21], [21, 12, 8]].

Which keys work?

K has an inverse mod 26 only if gcd(det K, 26) = 1: the determinant must be odd and not a multiple of 13. Otherwise different plaintexts collide and decryption is impossible. Of all 456,976 possible 2 × 2 matrices, 157,248 are usable keys.

How secure is it?

The Hill cipher spreads each letter over its whole block (good diffusion), and a 3 × 3 key hides single-letter and pair frequencies well. But it is linear. If an attacker knows m plaintext blocks and their ciphertexts, stacking them as matrices gives C = K · P, so K = C · P⁻¹ mod 26. That is a few lines of algebra, not a search. Modern ciphers such as AES and DES mix linear steps with non-linear S-boxes for exactly this reason.

Code

def to_nums(s): return [ord(c) - 65 for c in s]
def to_text(v): return ''.join(chr(x + 65) for x in v)

def mat_vec(K, v):
    return [sum(k * x for k, x in zip(row, v)) % 26 for row in K]

def hill(K, text):
    n = len(K)
    text = text.upper() + 'X' * (-len(text) % n)    # pad to a multiple of n
    nums = to_nums(text)
    out = []
    for i in range(0, len(nums), n):
        out += mat_vec(K, nums[i:i + n])
    return to_text(out)

def inverse_2x2(K):
    (a, b), (c, d) = K
    det = (a * d - b * c) % 26
    det_inv = pow(det, -1, 26)          # ValueError if gcd(det, 26) != 1
    return [[det_inv * d % 26, det_inv * -b % 26],
            [det_inv * -c % 26, det_inv * a % 26]]

K = [[3, 3], [2, 5]]
c = hill(K, 'HELP')
print(c)                                # HIAT
print(inverse_2x2(K))                   # [[15, 17], [20, 9]]
print(hill(inverse_2x2(K), c))          # HELP

#include <iostream>
#include <string>
#include <vector>
using namespace std;
using Mat = vector<vector<int>>;

string hill(const Mat &K, string text) {
    int n = K.size();
    while (text.size() % n) text += 'X';          // pad to a multiple of n
    string out;
    for (size_t i = 0; i < text.size(); i += n)
        for (int r = 0; r < n; r++) {
            int sum = 0;
            for (int k = 0; k < n; k++) sum += K[r][k] * (text[i + k] - 'A');
            out += char('A' + sum % 26);
        }
    return out;
}

int main() {
    Mat K = {{3, 3}, {2, 5}};
    Mat Kinv = {{15, 17}, {20, 9}};
    string c = hill(K, "HELP");
    cout << c << "\n";                 // HIAT
    cout << hill(Kinv, c) << "\n";     // HELP
}

Common mistakes

• Choosing a key without checking the determinant. If gcd(det, 26) ≠ 1, nothing can be decrypted.
• Dividing by the determinant. There is no division mod 26. Multiply by the modular inverse of the determinant.
• Forgetting to reduce negative numbers. −3 mod 26 is 23, not −3.
• Mixing up row and column conventions. K · p and p · K use transposed keys. Pick one and stick with it.
• Forgetting the padding. The last block must be full: add X (and remove it after decrypting).