Hill
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
Options
Access
- Create
create("hill") - CLI
ciphers 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.
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:
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.
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.
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:
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:
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.
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:
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.