Geekly Articles each Day

At once I will say that this topic is interesting only from the point of view of the history of cryptography, the described cipher is of little use for protecting information in the modern world. But, nevertheless, the algorithms described in the topic can be useful at specialized Olympiads.

Blaise Viginer in the 17th century offered a rather interesting encryption method. The cipher key is a special phrase. This phrase, repeated many times, is written over the encrypted text. Each letter of a secret message is obtained by shifting each letter of the source text by a certain number given by the letter of the key phrase (the letter A does not give a shift, the letter B - a shift by one position, B - by two, etc.).

For example, try to encrypt the word "SECRET" using the key phrase "ABC". The letter C does not move, the first letter E moves one position, turning into F, the letter K moves two positions, turning into M. Continuing to encrypt the message, we end up with â€śSJMRZHFâ€ť.

For three centuries, this cipher was considered virtually unbreakable. The first attempts to break this cipher were made in the 19th century. All these attempts were based on determining the length of the key phrase. If we know its length, then we can break the entire encrypted text into fragments, each of which is encoded by the same shift. In our example, the letters C, P are encoded with a zero shift, E, E are encoded with a shift of one, K, T are encoded with a shift of 2. If the text is long enough, we can apply frequency analysis and thereby, reveal the original message. It turns out that the solution to this cipher is reduced to finding the length of the key phrase.

')

Now we consider two methods for finding this length. The first method was proposed by Friedrich Kasitsky. The basis of the Kasitsky method is the search for bigrams. In the case when in the encrypted message the same digram is repeated at a distance that is a multiple of the length of the key phrase, it will be encountered at the same positions and in the encrypted text. Having found these distances and, having received all its dividers, we will receive a set of candidate numbers for the length of a key phrase.

Let us try to decipher the following text using Kasitsky's method: The cipher text contains three repeating MA bigrams (positions 16 and 26), YOU (positions 44 and 49) and HX (positions 57 and 62). The MA digram is repeated at a distance of 10 positions, and the TY and HX digram at a distance of 5 positions. Most likely the position is the length of the key sequence is equal to 5. The considered method requires some luck, because â€śrandomâ€ť bigrams may appear in the text. Their probability is much lower than that of the "regular" ones, but in small texts they can complicate the interpretation significantly.

Before finally deciphering the text, we will consider another method for determining the key length proposed by Friedman. The essence of the method in the cyclical shift of the message. Messages thus received are recorded under the original ciphertext and the number of matching letters in the top and bottom lines is counted. Based on these numbers, so-called is calculated. index of matches, equal to the ratio of the number of matches to the full length of the message. For Russian texts, the coincidence index is about 6%, but for random texts this index is 1/32, i.e. about 3%. The Friedmann method is based on this fact. Text is written with a shift of 1, 2, 3, etc. positions and for each shift is calculated index of matches. Cyclic shifting our message we get:

Shift Matches Index

2 0 0.000

3 5 0.068

4 2 0.027

5 8 0.110 (!)

6 1 0.014

7 1 0.014

8 2 0.027

With a shift of 5, the index increases dramatically, therefore the length of the keyword is most likely equal to 5. It is quite simple to understand why the index increases sharply. In the case when all characters are shifted to the same position, the coincidence index is the same as that of the source text. In the case when we calculate the index for the Viginer cipher, we in all cases (except where the shift length is equal to the key length) compare the actual random text.

Having determined the key length, we can, using the letter frequency table, find out that a well-known children's poem was encrypted:

Our Tanya cries loudly:

Dropped the ball in the river.

Tanya, Tanya, do not cry,

The ball will not sink in the river!

The authorâ€™s surname â€śBartoâ€ť was taken as the password.

I hope you found something new in this article. And, I hope, you use the gained knowledge exclusively for the good.

Blaise Viginer in the 17th century offered a rather interesting encryption method. The cipher key is a special phrase. This phrase, repeated many times, is written over the encrypted text. Each letter of a secret message is obtained by shifting each letter of the source text by a certain number given by the letter of the key phrase (the letter A does not give a shift, the letter B - a shift by one position, B - by two, etc.).

For example, try to encrypt the word "SECRET" using the key phrase "ABC". The letter C does not move, the first letter E moves one position, turning into F, the letter K moves two positions, turning into M. Continuing to encrypt the message, we end up with â€śSJMRZHFâ€ť.

For three centuries, this cipher was considered virtually unbreakable. The first attempts to break this cipher were made in the 19th century. All these attempts were based on determining the length of the key phrase. If we know its length, then we can break the entire encrypted text into fragments, each of which is encoded by the same shift. In our example, the letters C, P are encoded with a zero shift, E, E are encoded with a shift of one, K, T are encoded with a shift of 2. If the text is long enough, we can apply frequency analysis and thereby, reveal the original message. It turns out that the solution to this cipher is reduced to finding the length of the key phrase.

')

Now we consider two methods for finding this length. The first method was proposed by Friedrich Kasitsky. The basis of the Kasitsky method is the search for bigrams. In the case when in the encrypted message the same digram is repeated at a distance that is a multiple of the length of the key phrase, it will be encountered at the same positions and in the encrypted text. Having found these distances and, having received all its dividers, we will receive a set of candidate numbers for the length of a key phrase.

Let us try to decipher the following text using Kasitsky's method: The cipher text contains three repeating MA bigrams (positions 16 and 26), YOU (positions 44 and 49) and HX (positions 57 and 62). The MA digram is repeated at a distance of 10 positions, and the TY and HX digram at a distance of 5 positions. Most likely the position is the length of the key sequence is equal to 5. The considered method requires some luck, because â€śrandomâ€ť bigrams may appear in the text. Their probability is much lower than that of the "regular" ones, but in small texts they can complicate the interpretation significantly.

Before finally deciphering the text, we will consider another method for determining the key length proposed by Friedman. The essence of the method in the cyclical shift of the message. Messages thus received are recorded under the original ciphertext and the number of matching letters in the top and bottom lines is counted. Based on these numbers, so-called is calculated. index of matches, equal to the ratio of the number of matches to the full length of the message. For Russian texts, the coincidence index is about 6%, but for random texts this index is 1/32, i.e. about 3%. The Friedmann method is based on this fact. Text is written with a shift of 1, 2, 3, etc. positions and for each shift is calculated index of matches. Cyclic shifting our message we get:

Shift Matches Index

2 0 0.000

3 5 0.068

4 2 0.027

5 8 0.110 (!)

6 1 0.014

7 1 0.014

8 2 0.027

With a shift of 5, the index increases dramatically, therefore the length of the keyword is most likely equal to 5. It is quite simple to understand why the index increases sharply. In the case when all characters are shifted to the same position, the coincidence index is the same as that of the source text. In the case when we calculate the index for the Viginer cipher, we in all cases (except where the shift length is equal to the key length) compare the actual random text.

Having determined the key length, we can, using the letter frequency table, find out that a well-known children's poem was encrypted:

Our Tanya cries loudly:

Dropped the ball in the river.

Tanya, Tanya, do not cry,

The ball will not sink in the river!

The authorâ€™s surname â€śBartoâ€ť was taken as the password.

I hope you found something new in this article. And, I hope, you use the gained knowledge exclusively for the good.

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