📜 ⬆️ ⬇️

Cryptanalysis of the Vigenere cipher

First of all, let us assume that the adversary is certain that the ciphertext was obtained either with a mono-alphabetic substitution, or with the help of the Vigener cipher. To find out which of these two methods was used, you can conduct a simple test. If a mono-alpha numeric substitution was used, the statistical indicators of the cipher text will not differ from the corresponding indicators of the language in which the open text is written. If there is only one message for analysis, the exact coincidence of statistical indicators may not be obtained. But if the statistics accurately enough repeat the statistics of plain plaintext, it can be assumed that a mono-alphabetic substitution was used.

If, on the contrary, everything indicates that the Vigenère cipher was used, then, as we shall see later, the success of further text analysis depends on whether the length of the keyword can be determined. The solution to this problem is based on the following peculiarity of this cipher: if the initial characters of two identical plaintext sequences are from each other at a distance multiple of the key length, these sequences will be represented by the same sequences in the ciphertext. For example, even if the plaintext contains two identical sequences of characters (a word or a combination of them), then if they are encrypted using the same key fragment, we will get the same sequences of ciphertext characters. The analyst, having at his disposal only cipher text, will find a repeating sequence of characters with an offset to K (a multiple of the key length) of characters.

Further analysis is based on another feature of this cipher. If a keyword has a length of N, then the cipher essentially consists of N mono-alphabetic permutation ciphers. For example, when using the keyword deceptive letters that are on the 1st, 10th, 19th, etc. positions are encrypted with the same mono-alphabetic cipher. This makes it possible to use the known characteristics of the frequency distributions of the letters of the plaintext to hack each mono-alphabetic cipher separately.

Periodicities in the key line can be avoided by using a non-periodic sequence of the same length as the message itself for the key line. Vizhener proposed an approach called the system with automatic key selection, when the sequence of a key string is obtained as a result of a concatenation of a keyword with plain text itself. For the example under consideration, we obtain the following.
key: deceptivewearediscoveredsav
plain text: wearediscoveredsaveyourself

However, this scheme is also vulnerable. Since the values ​​of the frequency of the distribution of letters will be the same in the key line and in the plaintext, statistical methods can be applied in this case as well. Then, for example, the symbol encrypted with the key symbol b, will occur with a frequency equal to the product of the frequencies of these symbols. It is these patterns that allow success in analyzing ciphertext.

The best defense against such cryptanalysis methods is to choose a keyword that is equal in length to the plaintext, but different from the plaintext in statistical indicators. Such a system was proposed by AT & T engineer Gilbert Vernam in 1918. His system operates not with letters, but binary numbers. Briefly, it can be expressed by the formula:


Thus, the cipher text is generated by bitwise performing the XOR operation on the plaintext and the key. Due to the properties of this operation, it is enough to perform a similar operation to decrypt:


The essence of this technology is the key selection method. Vernam proposed to use a looped ribbon, which means a cyclical repetition of the key word, so that his system actually assumed work, albeit with a very long, but still repetitive key. Despite the fact that such a scheme, due to the very long key length, considerably complicates the task of cryptanalysis, the scheme can nevertheless be hacked by having a sufficiently long fragment of ciphertext, known or probably known pieces of plaintext, or both at once.

Army Corps Officer Joseph Mauborgne proposed such improvements in the Vernam encryption scheme that made this scheme extremely reliable. Moborn proposed to abandon repetitions, and randomly generate a key equal in length to the length of the message. Such a scheme, called tape disposable (or schemes with a disposable notebook), can not be cracked. As a result of its use, the output is a random sequence that does not have a statistical relationship with cleartext. Since in this case, the ciphertext does not give any information about the plaintext, there is no way to crack the code.

The complexity of the practical application of this method lies in the fact that both the sender and the recipient must have the same random key and be able to protect it from unauthorized persons. Therefore, despite all the advantages of the Vernama cipher over other ciphers, in practice it is seldom used.

Source: https://habr.com/ru/post/104771/

All Articles