The Hill cipher

The Hill cipher encrypts blocks of letters by multiplying them by a matrix of numbers. Lester Hill described it in 1929, and it was the first cipher where algebra, not just shuffling alphabets, did the scrambling. Each ciphertext letter depends on every letter in its block, which defeats single-letter frequency counting. It has one fatal flaw. Everything is linear, so a handful of known letters give away the key.

Try it

Nothing you type here leaves your browser.

Enter 4 numbers for a 2×2 key, or 9 for a 3×3, row by row. The tool refuses a matrix with no inverse and explains why. Short messages are padded with X.

How it works

Turn the letters into numbers, A = 0 to Z = 25. Cut the message into blocks of n letters and write each block as a column of n numbers. The key is an n×n matrix K, and the ciphertext block is K times the plaintext block, with every result reduced modulo 26. Take the key [3 3; 2 5] and the message HELP, in two blocks, HE and LP:

The first block: 3×7 + 3×4 = 33, and 33 mod 26 = 7, which is H. Then 2×7 + 5×4 = 34, and 34 mod 26 = 8, which is I. So HE becomes HI. The second block LP (11, 15) gives 78 and 97, which are 0 and 19 modulo 26, so AT. The ciphertext is HIAT. Notice that HE came out as HI. The H stayed put by accident, not by design, and the second letter changed because it depends on both input letters.

Decrypting needs the inverse matrix

To undo the multiplication you multiply by the matrix inverse of K, modulo 26. For a 2×2 key [a b; c d] the inverse is (1/det) × [d −b; −c a], where det = ad − bc and 1/det is the number that gives 1 when multiplied by det modulo 26. For [3 3; 2 5] the determinant is 15 − 6 = 9, its inverse modulo 26 is 3 (9 × 3 = 27 = 26 + 1), and the inverse matrix is [15 17; 20 9]. Multiply HI by it and HE comes back.

That's where the key rule comes from. The determinant must have no common factor with 26, meaning it's odd and not a multiple of 13. Otherwise no inverse exists and the message can't be read back. It's the same reason the affine cipher restricts its multiplier to twelve values. The Hill cipher is a cousin of Playfair, which also encrypts several letters at once.

How many keys?

A 2×2 matrix has 26⁴ = 456,976 possible fillings, and 157,248 of them are invertible modulo 26 and so usable as keys. A 3×3 matrix has 26⁹ = 5,429,503,678,976 fillings and 1,634,038,189,056 usable keys, about 1.6 × 10¹². Those counts come from counting the invertible matrices separately modulo 2 and modulo 13 and multiplying. It's a long way from the 4 × 10²⁶ keys of simple substitution, but a Hill cipher works on blocks and spreads each letter across several outputs, so no key-length analysis applies.

Where it comes from

Lester S. Hill, an American mathematician, published "Cryptography in an Algebraic Alphabet" in The American Mathematical Monthly in 1929, followed by a second paper in 1931. He also patented a mechanical version, built with gears and chains, that multiplied by a 6×6 matrix. It didn't sell. The Hill cipher stands out as the first polygraphic cipher where it was practical to work on more than three letters at a time, and for bringing linear algebra into cryptography. It was never widely used for real secrets, which isn't surprising once you see how easily it breaks. Matrix multiplication lives on as one step in the mixing layer of modern ciphers such as AES (its "MixColumns" step).

Why it breaks: everything is linear

The key is a matrix, and a matrix equation is easy to solve. If you know a few plaintext letters and the ciphertext they became, you can work out the key. Suppose you know the message started with HELP and the ciphertext began HIAT, with a 2×2 key. Put the plaintext blocks side by side as columns of a matrix P = [7 11; 4 15] and the ciphertext blocks as columns of C = [7 0; 8 19]. The key satisfies K × P = C, so K = C × P⁻¹. Computing that modulo 26 gives [3 3; 2 5], the key. The tool's library does it in a few lines, and the project's tests recover the key from exactly this example. In general, n blocks of known plaintext, that is n² letters, give the key of an n×n Hill cipher. Four letters crack a 2×2 key, nine a 3×3, twenty-five a 5×5.

Without known plaintext it's harder, since you have to guess the block size and search. But short keys are tiny searches. A 2×2 key can be tried exhaustively, and 157,248 candidates cost a computer nothing. Digraph and trigraph statistics leak too, and the frequency analysis tool shows the pair counts of a ciphertext. The Hill cipher is a lesson in why a mathematically elegant cipher isn't necessarily a strong one. A cipher has to be non-linear somewhere, and AES gets that from its S-boxes, the part Hill's cipher lacks.

The code

// Hill cipher: cut the message into blocks of n letters, treat each block as a column of numbers, and multiply by the key matrix mod 26.
// `m` is the n x n key matrix as a flat array, row by row.
function hill(text, m, n) {
  var nums = text.toUpperCase().replace(/[^A-Z]/g, '').split('').map(function (c) { return c.charCodeAt(0) - 65; });
  while (nums.length % n) nums.push(23);                                // pad with X
  var out = '';
  for (var b = 0; b < nums.length; b += n)
    for (var r = 0; r < n; r++) {
      var sum = 0;
      for (var c = 0; c < n; c++) sum += m[r * n + c] * nums[b + c];
      out += String.fromCharCode(65 + sum % 26);
    }
  return out;
}

// For a 2 x 2 key [a b; c d] the decrypting matrix is (1/det) * [d -b; -c a], where 1/det is the inverse of the determinant mod 26.
function hillInverse2(m) {
  var det = ((m[0] * m[3] - m[1] * m[2]) % 26 + 26) % 26, inv = 0;
  for (var i = 1; i < 26; i++) if (det * i % 26 === 1) inv = i;
  if (!inv) return null;                                                // determinant shares a factor with 26: no inverse
  return [m[3] * inv, -m[1] * inv, -m[2] * inv, m[0] * inv].map(function (x) { return ((x % 26) + 26) % 26; });
}

Common questions