Hill cipher
This calculator uses Hill cipher to encrypt/decrypt a block of text.
According to the 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.
Hill cipher
How does it work
First, symbols of the used alphabet (alphabet as a set of symbols, for example, the 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 a matrix of n x n size, which will be the 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 the key matrix of n x n. The result, vector of size n, is a block of encrypted text. Modular arithmetic is used; that is, all operations (addition, subtraction, and multiplication) are done in the ring of integers, where the 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 into the digit representation and matrix. In order to create a n x n size matrix, keyphrase length should be square of an integer, i.e., 4, 9, 16.
Additional restrictions to the key are imposed by the need to decrypt encrypted text :)
And, for this to happen, we need to have a modular inverse of the key matrix in - ring of integers modulo m.
If source vector B is multiplied by matrix A to get vector C, then to restore vector B from vector C (decrypt text), one needs to multiply it by the modular inverse of the matrix.
Thus they have the following restrictions:
The determinant of the matrix should not be equal to zero, and, additionally, the determinant of the matrix should have a modular multiplicative inverse.
The formula imposes the latter
.
where the operation of multiplication substitutes the operation of division by the modular multiplicative inverse.
In order to have a modular multiplicative inverse, determinant and modulo (length of the alphabet) should be coprime integers, refer to Modular Multiplicative Inverse Calculator. In order to increase the probability of this, the alphabet is expanded, so its length becomes the 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 a prime integer.
Not every key phrase is qualified to be the key; however, there are still more than enough.
Comments