Tool to decrypt/encrypt with Hill cipher, a ciphering system similar to affine cipher but using a coefficient matrix instead of 2 affine coefficients (gradient).

Hill Cipher - dCode

Tag(s) : Poly-Alphabetic Cipher

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!

A suggestion ? a feedback ? a bug ? an idea ? *Write to dCode*!

Hill Cipher is a polyalphabetic cipher created by extending the Affine cipher, using linear algebra and modular arithmetic via a numeric matrix that serves as an encryption and decryption key.

Hill cipher encryption uses an alphabet and a square matrix $ M $ of size $ n $ made up of integers numbers and called encryption matrix.

__Example:__ Encrypt the plain text `DCODE` with the latin alphabet `ABCDEFGHIJKLMNOPQRSTUVWXYZ` and the matrix $ M $ (size $ n=2 $): $$ M = \begin{bmatrix} 2 & 3 \\ 5 & 7 \end{bmatrix} $$

Split the text into $ n $-grams. Complete any final incomplete ngrams with random letters if necessary.

__Example:__ The matrix $ M $ is a 2x2 matrix, `DCODE`, split in 2-grams, becomes `DC,OD,EZ` (`Z` letter has been added to complete the last bigram)

Substitute the letters of the plain message by a value: their rank in the alphabet starting from $ 0 $.

__Example:__ The alphabet `ABCDEFGHIJKLMNOPQRSTUVWXYZ` leads to `A=0,B=1,…,Z=25`.

Groups of letters `DC`, `OD`, `EZ` become the groups of values `(3,2)`, `(14,3)`, `(4,25)`

It is possible (but not recommended) to use `ZABCDEFGHIJKLMNOPQRSTUVWXY` in order to get `A=1,B=2,…Y=25,Z=0`.

For each group of values $ P $ of the plain text (mathematically equivalent to a vector of size $ n $), compute the multiplication">matrix product: $$ M.P \equiv C \mod 26 $$ where $ C $ is the calculated vector (a group) of ciphered values and $ 26 $ the alphabet length.

__Example:__ $$ \begin{bmatrix} 2 & 3 \\ 5 & 7 \end{bmatrix} \cdot \begin{bmatrix} 3 \\ 2 \end{bmatrix} \equiv \begin{bmatrix} 12 \\ 3 \end{bmatrix} \mod 26 $$

From cipher values $ C $, retrieve cipher letters of the same rank in the alphabet.

__Example:__ $ 12 $ is equal to `M` and $ 3 $ is equal to `D`.

And so on, `DCODEZ` is encrypted `MDLNFN`.

Hill cipher decryption needs the matrix and the alphabet used. Decryption involves matrix computations such as matrix inversion, and arithmetic calculations such as modular inverse.

To decrypt hill ciphertext, compute the matrix inverse modulo 26 (where 26 is the alphabet length), requiring the matrix to be invertible.

__Example:__ Using the example matrix, compute the inverse matrix (modulo 26) : $$ \begin{bmatrix} 2 & 3 \\ 5 & 7 \end{bmatrix}^{-1} \equiv \begin{bmatrix} -7 & 3 \\ 5 & -2 \end{bmatrix} \equiv \begin{bmatrix} 19 & 3 \\ 5 & 24 \end{bmatrix} \mod 26 $$

Decryption consists in encrypting the ciphertext with the inverse matrix.

Note that not all matrices can be adapted to hill cipher. The determinant of the matrix has to be coprime with 26.

The determinant of the Hill matrix must be prime with 26 to ensure that the matrix is invertible modulo 26 (the value 26 comes from the length of the Latin alphabet having 26 letters).

This ensures that each modular multiplication operation remains one-to-one (each input vector/ngram corresponds to a single encrypted vector/ngram and vice versa).

If this were not the case, several different vectors/ngrams could be encrypted in the same way, which would make decryption ambiguous and difficult to perform reliably.

For a 2x2 matrix, the 4 numbers $ \{ a,b,c,d \} $ must satisfy the condition that $ ad-bc $ is coprime with 26.

The ciphered message has a small index of coincidence and similar ngrams can be coded using the same letters.

Any reference to an actual hill or mountain is a clue.

Sometimes the groups of letters are left visible (all of length n = 2, 3 or 4) which suggests that the matrix is of size n.

dCode proposes to bruteforce test around 6000 combinations of 2x2 matrices (with digits between 1 and 9) and alphabets.

For matrices containing numbers $ >= 10 $ or larger size matrices, computation times become exponentially longer.

Hill is already a variant of Affine cipher. Few variants, except the use of large size matrices.

Hill cipher has been created in 1929 by Lester S. Hill

dCode retains ownership of the "Hill Cipher" source code. Except explicit open source licence (indicated Creative Commons / free), the "Hill Cipher" algorithm, the applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, breaker, translator), or the "Hill Cipher" functions (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and all data download, script, or API access for "Hill Cipher" are not public, same for offline use on PC, mobile, tablet, iPhone or Android app!

Reminder : dCode is free to use.

The copy-paste of the page "Hill Cipher" or any of its results, is allowed (even for commercial purposes) as long as you cite dCode!

Exporting results as a .csv or .txt file is free by clicking on the *export* icon

Cite as source (bibliography):

*Hill Cipher* on dCode.fr [online website], retrieved on 2023-09-23,

- Hill Decoder
- Hill Encoder
- Matrix Inversion
- What is the Hill cipher? (Definition)
- How to encrypt using Hill cipher?
- How to decrypt Hill cipher?
- Why must the determinant of the Hill matrix be coprime with 26?
- How to recognize Hill ciphertext?
- How to decipher Hill without the key matrix?
- What are the variants of the Hill cipher?
- When was the Hill cipher invented?

hill,cipher,affine,modulo,matrix,lester,inverse,determinant

https://www.dcode.fr/hill-cipher

© 2023 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.

Feedback