The Hill encryption algorithm (Menu Crypt/Decrypt \ Symmetric (classic))
The Hill encryption algorithm was invented in 1929 by Lester Hill. It was one of the first methods to make use of mathematical techniques (linear algebra), and it was hoped that this would raise the level of security.
The Hill encryption algorithm requires a key and cleartext. Also the key may only consists of the characters of the cleartext alphabet (see Text Options dialog). Additionally the key is a quadratic matrix: this means it has the same number of rows and columns. This number is called the dimension of the matrix. The key is entered in the Key for Hill cipher dialog.
The plaintext is divided into blocks of equal size (one block consists of as many characters as the key has rows).
The last block sometimes has too few characters: In this case the last block is padded to have the length of the matrix dimension -- by default its filled up with the first character of the used alphabet (this character is not necessarily the one with the smallest ASCII value, e.g. in the case when the alphabet is defined as "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789").
From a mathematics point of view, the Hill encryption algorithm is based on matrix multiplication with the matrix A=(a[i,j]) for i and j between 1 and n. In the course of this the plaintext, the encrypted text and the key are all interpreted as numbers (for example, A=0, B=1, C=2 etc.), and the interpretation depends on the sequence of the characters to be encrypted in the Text Options dialog. If the key has dimension n x n, then a block of the encrypted text v[1]... v[n] is obtained from a block of plaintext k[1]... k[n] by applying the following formula:
v[j] = sum for i from 1 to n of k[i] * a[i,j], for j between 1 and n.
If a plaintext has been encrypted with matrix A, then the encrypted text is decrypted with the inverse matrix to the encryption matrix A modulo number of characters to be encrypted.
Hence not all combinations of any characters coild be used as keys. It makes no sense allowing a matrix that is not invertible (a matrix for which no inverse matrix exists) to be the key as decryption is then not possible. Therefore the program will reject such a key. Since, especially with keys of greater dimension, it is difficult to guess a key which corresponds to an invertible matrix (see the table below on this point) the Random key pushbutton in the Key for Hill cipher dialog enables you to have a key which corresponds to an invertible matrix generated automatically.
In this way, the Hill encryption algorithm is a linear transformation of the plaintext. Hence it is possible to work out the key using a Known Plaintext attack. CrypTool contains a tool which enables a Known Plaintext attack to be performed on the Hill encryption algorithm.
An example of the Hill encryption algorithm and of a Known Plaintext attack will be found in the Examples chapter.
Empirical calculation of the number of invertible matrices modulo of different numbers:
Examples for different alphabet sizes:
Modulus 10: only numbers are encrypted.
Modulus 26: only upper or lower case letters are encrypted.
Modulus 52: only upper and lower case letters are encrypted.
Modulus 62: only upper and lower case letters and numbers are encrypted.
Modulus 71: only upper and lower case letters, numbers and punctuation characters are encrypted.
Dimension: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Modulus 4 | 51% | 38% | 33% | 31% | 30% | 30% | 29% | 29% | 29% | 28% |
Modulus 5 | 81% | 77% | 76% | 76% | 76% | 76% | 76% | 76% | 76% | 76% |
Modulus 6 | 34% | 22% | 19% | 17% | 17% | 17% | 16% | 16% | 16% | 16% |
Modulus 7 | 86% | 84% | 84% | 84% | 84% | 84% | 84% | 84% | 84% | 84% |
Modulus 10 | 40% | 29% | 25% | 24% | 23% | 23% | 22% | 22% | 22% | 22% |
Modulus 26 | 46% | 34% | 30% | 28% | 27% | 27% | 27% | 26% | 26% | 26% |
Modulus 35 | 69% | 64% | 64% | 64% | 64% | 64% | 64% | 64% | 64% | 64% |
Modulus 36 | 33% | 22% | 19% | 17% | 16% | 17% | 16% | 16% | 16% | 16% |
Modulus 52 | 46% | 35% | 30% | 29% | 28% | 27% | 27% | 27% | 26% | 27% |
Modulus 62 | 49% | 36% | 32% | 30% | 29% | 28% | 28% | 29% | 27% | 27% |
Modulus 71 | 99% | 99% | 99% | 99% | 99% | 99% | 99% | 99% | 99% | 99% |
These values suggest that the number of invertible matrices depends on the number of divisors of the modulus. Prime numbers have only two divisors and a high percentage of the matrices are invertible. Moreover, the number of invertible matrices appears to become smaller as the dimension increases.