StringMash.com

Hill cipher

Multiply blocks of letters by a matrix, and take what's left after 26.

Conversion
14 characters
Updates as you type
Key GYBNQKURP

Show the steps
  1. Number the letters from A = 0 to Z = 25.
  2. The key as a 3 × 3 matrix: [6 24 1] [13 16 10] [20 17 15]
  3. Cut the message into blocks of 3.
  4. ATT is [0 19 19]. Multiply: 6×0 + 24×19 + 1×19, 13×0 + 16×19 + 10×19, 20×0 + 17×19 + 15×19 gives [475 494 608], which mod 26 is [7 0 10]: HAK
  5. ACK is [0 2 10]. Multiply: 6×0 + 24×2 + 1×10, 13×0 + 16×2 + 10×10, 20×0 + 17×2 + 15×10 gives [58 132 184], which mod 26 is [6 2 2]: GCC
  6. ATD is [0 19 3]. Multiply: 6×0 + 24×19 + 1×3, 13×0 + 16×19 + 10×3, 20×0 + 17×19 + 15×3 gives [459 334 368], which mod 26 is [17 22 4]: RWE
  7. AWN is [0 22 13]. Multiply: 6×0 + 24×22 + 1×13, 13×0 + 16×22 + 10×13, 20×0 + 17×22 + 15×13 gives [541 482 569], which mod 26 is [21 14 23]: VOX

Using the Hill tool

Type in the Key matrix box and the cipher rebuilds as you type. Four values make a 2x2 and nine make a 3x3, and they can be digits from 0 to 25 or letters where A is 0. GYBNQKURP and 6 24 1 13 16 10 20 17 15 are the same key.

Swap the boxes to decode with the same matrix. Not every matrix can be undone. When one can't, the tool says so and names the determinant.

Blocks, not letters

The text is cut into blocks as wide as the matrix. Each block becomes a column of numbers, gets multiplied by the matrix, and every result is reduced modulo 26 back into a letter.

A 3x3 key means every output letter depends on three input letters at once. Change one letter of the plaintext and three letters of the ciphertext move. That's what defeats the frequency counting that breaks Caesar and affine, because no single ciphertext letter stands for a single plaintext one.

Blocks have to be full, so a short tail is padded with X. Decoding gives the padding back, and you trim it yourself.

Why some keys are rejected

Decoding multiplies by the matrix inverse, worked out modulo 26 rather than over the real numbers. That inverse exists only when the determinant shares no factor with 26.

26 is 2 times 13, so a determinant that is even, or a multiple of 13, or zero, has no inverse and the key is a one-way door. It's the same restriction the affine cipher runs into with its multiplier, for the same arithmetic reason.

The tool checks before it encodes and shows an error for a key you couldn't decode with.

Lester Hill, 1929

Lester S. Hill published it in The American Mathematical Monthly in 1929, under the title "Cryptography in an Algebraic Alphabet". It was the first polygraphic cipher that could practically work on more than three letters at once, and the first to treat a message as a vector.

He also designed the hardware. In 1929 Hill and Louis Weisner, a colleague at Hunter College, filed a patent for a device that did a 6x6 multiplication modulo 26 with gears and chains, because doing it by hand is slower than the message is worth. They tried to sell it to the military, the banks and the telegraph company, and nothing came of it.

It saw little real use. During the Second World War it enciphered three-letter radio call signs and not much else, and the cipher collapses against a known-plaintext attack. Guess or learn nine plaintext letters and their ciphertext, and you solve for the whole 3x3 key with school algebra.

Related conversions

Playfair had the same goal 75 years earlier, enciphering pairs of letters so that single-letter frequencies say nothing, and it does it with a grid rather than arithmetic.

Affine is the one-letter version of the same idea, multiplying and adding modulo 26. Hill is that formula with a matrix in place of the multiplier.

Questions

What is the Hill cipher?

A cipher from 1929 that treats blocks of letters as vectors and multiplies them by a key matrix modulo 26. It was the first polygraphic cipher that could practically work on more than three letters at once.

Why won't my key work?

Its determinant shares a factor with 26, so the matrix has no inverse modulo 26 and the message could never be decoded. Change one value and try again.

How do I write the key?

Four values for a 2x2 or nine for a 3x3, read left to right along each row. Digits from 0 to 25, or letters where A is 0 and Z is 25.

How is the Hill cipher broken?

With known plaintext. If you know nine plaintext letters and the ciphertext they produced, a 3x3 key falls out of a system of linear equations.

Sources

Written, edited and reviewed by .

Added . Last updated and reviewed . What's new