Automatic analysis, Hill encryption method (Menu Analysis \ Symmetric Encryption (classic) \ Known Plaintext)
A Known Plaintext attack is available for the Hill encryption algorithm. This means that it is necessary to enter not just the text encrypted by the Hill encryption algorithm but also the same text in plaintext form. CrypTool then works out the key with which the plaintext was encrypted.
As mentioned above, both the plaintext and the encrypted text must be known to the automatic analysis function. One of the texts must be available in the active window prior to calling the function for automatic analysis of the Hill encryption algorithm, and the other text must be entered in the Hill cipher Analysis dialog.
The analysis functions as follows: CrypTool assumes that the key has the dimension n
x n
(from the range chosen in the Hill cipher Analysis dialog. The plaintext and the encrypted text are now divided into blocks of length n
. The matrices K
(plaintext) and V
(encrypted text) are constructed from n
blocks of plaintext and the corresponding blocks of the encrypted text. Clearly, V
= K
* A
, where A
is the key. If K
is invertible, then the key can be calculated through simple matrix multiplication modulo 26 (number of letters): inverse(K
) * V
= A
. If K
is not invertible, then another possible combination of blocks is tried out.
Example of searching a combination of blocks
The plaintext goes: | ABCDXY . |
The encrypted text is: | STONLC . |
The key length is: | 2. |
First of all CrypTool tries to find the key using the following matrices.
K: | AB | V: | ST |
CD | ON |
Matrix K
is not invertible. Therefore it would not be possible to find the key if the plaintext were ABCD
and the encrypted text STON
. However, as there is another block in the example, the next possible combination of blocks is now formed, producing these matrices:
K: | AB | V: | ST |
XY | LC |
As this matrix K
is invertible, the product of the inverse matrix of K
and matrix V
is calculated, and immediately one obtains the key of dimension 2 x 2:
A: | TE |
ST |
This key is then displayed in the Key for Hill cipher dialog.
With this plaintext and this encrypted text, the last possible combination of blocks would be:
K: | CD | V: | ON |
XY | LC |
In this example, it was not necessary to construct this last combination as the key had already been discovered from the previous combination of blocks.
If the key is not found after trying all possible combinations of blocks, the next dimension is tried. If the key can still not be found, an appropriate message is displayed.
In the Examples chapter there is an example of an attack on the encryption algorithm.
Conditions which the document must satisfy for a successful attack
The key will normally be found if the document
is not too short (though it must contain at least as many characters as the length of the key),
and does not consist of one and the same sequence of characters (or character sequences whose characters are the same distance apart).
The second condition means that, for example, it may not be possible to work out the key for plaintext ABAB
. This is true also for the plaintext sequence ABCD
, as the distance between the letters in the first block (AB
) is the same length as the distance between the letters in the second block (CD
), i.e. one character.
The two above conditions are normally satisfied if the plaintext consists of words from a natural language, for example, the word "HILLCIPHER".
However, it may occasionally still be possible to find the key even with a short text as long as it satisfies the second condition.