According to definition in wikipedia
, in classical cryptography, the Hill cipher is a polygraphic substitution cipher based on linear algebra. Invented by Lester S. Hill in 1929, it was the first polygraphic cipher in which it was practical (though barely) to operate on more than three symbols at once. The explanation of cipher which is below the calculator assumes an elementary knowledge of matrices.
How does it work
First, symbols of used alphabet (alphabet as set of symbols, for example, alphabet in the above calculator includes space, comma and dot symbols) are encoded with digits, for example, symbol's order number in the set. Then we choose matrix of n x n size, which will be cipher's key. Text is divided into blocks of size n, and each block forms a vector of size n. Each vector is multiplied by key matrix of n x n. The result, vector of size n is block of encrypted text. Modular arithmetic is used, that is all operations (addition, subtraction, and multiplication) are done in the ring of integers, where modulus is m - the length of the alphabet. This allows us to force results to belong to the same alphabet.
Key is the matrix, however, it is convenient to use the key phrase, which is transformed to the digit representation and to the matrix. Obviously, to create matrix of n x n key phrase length should be square of integer, i.e. 4, 9, 16, etc..
Additional restrictions to the key are imposed by the need to decrypt encrypted text :)
And, for this to happen, we need to have modular inverse of the key matrix in
- ring of integers modulo m.
Indeed, if source vector B is multiplied by matrix A to get vector C, then to restore vector B from vector C (decrypt text) one need to multiply it by modular inverse of matrix.
Thus the have the following restrictions:
Determinant of the matrix should not be equal to zero, and, additionally, determinant of the matrix should have modular multiplicative inverse.
The latter is imposed by the formula
where operation of division is substituted by the operation of multiplication by modular multiplicative inverse.
In order to have modular multiplicative inverse, determinant and modulo (length of the alphabet) should be coprime integers, refer to Modular Multiplicative Inverse
. To increase the probability of this, the alphabet is expanded so its length becomes prime integer. That is why the English alphabet in the calculator above is expanded with space, comma and dot up to 29 symbols, 29 is prime integer.
Not every key phrase is qualified to be the key, however, there are still more than enough.