Ciphers

Hill

Hill sends blocks through a key matrix. Pick an alphabet and the arithmetic follows.
IDhill24 / 75classical · polygraphic
Cipher / Polygraphic

Hill

Letter blocks times a key matrix, mod 26.

Keyspace
157,248
Decode
same options back
Works on
The alphabet, A-Z unless set, in blocks of 2 or 3, X or its last symbol pads the last, the rest dropped
Family
1 in polygraphic
required 1 / 2

Options

keystring
required
4 or 9 symbols of the alphabet, the 2×2 or 3×3 matrix row by row, its determinant coprime with the alphabet length
alphabetstring
default ABCDEFGHIJKLMNOPQRSTUVWXYZ
At least 2 distinct symbols in order, the first one 0, its length the modulus

Access

Createcreate("hill")
CLIciphers encode hill 'ACT CAT' --key GYBNQKURP
Tryplayground with the sample above

Hill turns blocks of symbols into numbers, then multiplies them by a key matrix. Lester Hill published it in 1929. Linear algebra in a puzzle. Nobody asked for it.

By default, A is 0 and the arithmetic uses mod 26. Every letter in a block feeds every letter of the result. Change one plaintext letter and the whole block changes. Caesar could never.

ts
const hill = create("hill");

hill.encode("HELP", { key: "DDCF" }).text; // "HIAT"
hill.decode("HIAT", { key: "DDCF" }).text; // "HELP"
hill.encode("ACT CAT", { key: "GYBNQKURP" }).text; // "POHFIN"

These are Wikipedia's examples. The space in ACT CAT doesn't stop a block.

The key

key spells the matrix row by row. Four symbols make a 2×2 matrix, nine make a 3×3. The key uses the same alphabet as the text. DDCF gives this matrix with the default alphabet:

text
3 3
2 5

Not every matrix works. Decoding needs an inverse matrix. That exists only when the determinant shares no factor with the alphabet's length. No inverse, no way back.

For A to Z, the modulus is 26, or 2 × 13. A determinant with a factor 2 or 13 won't work. ABCD has determinant 24 mod 26, so it's rejected.

For a 25 symbol alphabet, determinants divisible by 5 fail. FAAF has determinant 0 mod 25. The error names the modulus: has determinant 0 mod 25, which shares a factor with 25.

With A to Z, there are 157,248 valid keys at 2×2. At 3×3, there are about 1.6 trillion. Those counts don't apply to other alphabets.

Blocks and padding

Encoding drops anything outside the alphabet. Output uses the alphabet's own symbols, without spaces. A short last block gets an X if the alphabet has one. Otherwise, it gets the alphabet's last symbol.

ts
const hill = create("hill");

hill.encode("HEL", { key: "DDCF" }).text; // "HIYH"
hill.decode("HIYH", { key: "DDCF" }).text; // "HELX"

Decode keeps the padding, just like Playfair. Padding or a real X? Only the sender knows.

What can the alphabet do?

Pass alphabet as symbols in order. The first symbol is 0, and the alphabet's length sets the modulus. It needs at least two symbols. Each must be unique, and whitespace isn't allowed. An invalid alphabet raises an InvalidOptionError naming alphabet.

Digits, a 25 letter square, or A counted as 1 all fit here. That's a lot of puzzle arithmetic without writing another matrix routine.

Digits mod 9

The alphabet 012345678 makes the arithmetic mod 9. A four digit key makes a 2×2 matrix. A nine digit key makes a 3×3 matrix.

ts
const hill = create("hill");

hill.encode("3141567", { key: "2113", alphabet: "012345678" }).text; // "76077544"
hill.decode("7607 7544", { key: "2113", alphabet: "012345678" }).text; // "31415678"

The trailing 8 is padding. It's the alphabet's last symbol, because there's no X. And 9 doesn't belong in this alphabet. Mod 9 has its limits.

The result's options include the alphabet: { key: "2113", alphabet: "012345678" }. The CLI takes it too:

shell
ciphers encode hill 3141567 --key 2113 --alphabet 012345678

That prints 76077544.

25 letters without J

A puzzle square may leave out J. Use the same alphabet for Hill:

ts
const hill = create("hill");

hill.encode("HELP", { key: "DDCF", alphabet: "ABCDEFGHIKLMNOPQRSTUVWXYZ" }).text; // "IKXQ"

That's arithmetic mod 25. But 25 isn't prime. A determinant divisible by 5 still has no inverse.

A counted as 1

Put Z first, and A lands at 1. There's no separate flag to remember.

ts
const hill = create("hill");

hill.encode("HELP", { key: "CCBE", alphabet: "ZABCDEFGHIJKLMNOPQRSTUVWXY" }).text; // "MOFZ"

Here CCBE gives Wikipedia's matrix 3 3 / 2 5. Rotating the alphabet does the counting.

What does decoding refuse?

Decode skips whitespace, but refuses other symbols outside the alphabet. It raises a CipherError naming the character, code point, and position. For example:

text
Invalid Hill ciphertext: "9" (U+0039) at character 4 isn't in the alphabet

With the default alphabet, poh fin decodes fine. POH-FIN doesn't: the hyphen isn't in the alphabet. Ciphertext that doesn't split into whole blocks also raises a CipherError.

When the alphabet has only one case, letters match the other case too. Output still uses the alphabet's own symbols. But ı never counts as I.

Spotting one

What gives an A to Z Hill away? Letters only, with a count divisible by 2 or 3. Letter counts can look as flat as Vigenère's. A J is another clue.

The 5×5 squares of Playfair and Bifid can't make a J. Hill doesn't care. guess names Hill on those signals, but never above medium. A Vigenère with its spaces gone looks the same in a histogram.

It's also linear all the way down. For an n×n key, n² known plaintext letters and their ciphertext give a linear system. Four letters of crib usually do it for a 2×2. That's the whole security story.