Encryption using the permutation method. Types and methods of ciphers. Permutation ciphers

The so-called route changes, based on some geometric figure. A segment of plaintext is written into such a figure along a certain trajectory. The ciphertext is the sequence obtained by writing the text along a different trajectory. For example, you can write a message in a rectangular table by choosing the following route: we will move horizontally, starting from the upper left corner, alternately from left to right and from right to left. We will copy the message along a different route: vertically, starting from the upper right corner and moving alternately from top to bottom and bottom to top.

Example (routing permutation)

Let's encrypt the phrase using the above method example of route permutation, using a 4x7 rectangular table:

P	R	And	m	e	R	m
n	T	at	R	w	R	A
O	th	P	e	R	e	With
And	To	V	O	n	A	T

The encrypted phrase looks like this:

mastaerreshrnoermiupvkitrpnoi

Reversing the steps described during decryption is not difficult.

A type of route permutation called vertical rearrangement. This system also uses a rectangular table in which the message is written in the usual way (in rows from left to right). The message is written vertically (from top to bottom), with the columns selected in the order determined numeric key.

Example (vertical rearrangement)

Let's encrypt the phrase Here is an example of a vertical permutation cipher, using a 6 x 7 rectangle and a numeric key (5,1,4,7,2,6,3).

Note that it is inappropriate to fill the last line of the rectangle with “non-working” letters, since this would give the enemy who received this cryptogram information about the length of the numeric key. Indeed, in this case the key length should be sought among the message length divisors.

Now, writing out the letters in the columns in the order indicated by the numeric key, we get the following cryptogram:

oreekrfiyamaaeotshrnsivevlrvirkpnpitot

When decrypting, first of all, you need to determine the number of long columns, that is, the number of letters in the last line of the rectangle. To do this, you need to divide the number of letters in the message by the length of the numeric key. It is clear that the remainder of the division will be the desired number. Once this number has been determined, the letters of the cryptogram can be placed in their proper places and the message will be read naturally.

In our example, 38=7x5+3, so the completed table has 3 long and 4 short columns.

More complex route permutations can use other geometric shapes and more “cunning” routes, as, for example, when going around a chessboard with a “knight’s move”, paths in some labyrinth, etc. Possible options depend on the imagination of the system compiler and, of course, the natural requirement for ease of use.

Substitution (replacement) ciphers are based on an algebraic operation called substitution. A permutation is a one-to-one mapping of a finite set M onto itself. The number N of elements of sets is called the degree of substitution. The number n of numbers actually moved by substitution is called the length of the substitution cycle.

Permutation ciphers is a cipher, the conversion from which is changed only order of occurrence characters of the source text, but do not change them themselves.

Weakness of replacement ciphers. If a certain character occurs frequently in an open message, then the corresponding character occurs with the same frequency in an encrypted message. For large amounts of text, this leads to successful cryptanalysis. Thus, it is impossible to encrypt sufficiently long messages using one key.

Networks (as an element of encryption) - any block cipher is a combination of the first two schemes. The use of the concept of “network” in block encryption consists in repeating the original operations multiple times (repetitions are cycles or rounds, and the operations themselves are layers). Some of the layers may contain keys. This allows:

1. Make the cipher easily complicated (by increasing the number of rounds)
2. Reduce code size
3. Unify the algorithmic encryption formula

The Feisil network (Feistel) is a method of constructing an encryption cycle in iterative encryption algorithms based on a shift register, with a feedback function depending on the round key (the optimal number of rounds is from 8 to 32)

DES – US federal encryption standard (1997-2001).

The architecture is a classic, balanced Faisil network with initial and final bit permutations of a general form. The key size is 56 bits. It is based on the international standard ISO 8372-87. The algorithm is designed to encrypt data in 64-bit blocks.

DES is a combination of two main methods:

1. Substitution
2. Rearrangement.

A single combination of these two methods is applied to the text.

DES has 16 rounds, meaning the same combination of methods is applied to the plaintext 16 times.

The key round is applied using the XOR operation

Source text=>Initial permutation=>Encryption * 16(<=Ключ) =>Final permutation => ciphertext

The purpose of the initial permutation is to evenly distribute adjacent bits across blocks.

The same function can be used to encrypt and decrypt, but the keys are used in reverse order.

DES provides 4 types of work:

1. ECB-electronic cipher pad. Plaintext is processed in 64-bit blocks, encrypted with one key
2. CBC - block chain. Eliminates the disadvantage of the first mode. The input value of the encryption algorithm is set equal to the XOR difference between the current plaintext block and the ciphertext block obtained at the previous step. Thus, all blocks of the original text are connected (text=>ciphertext=>XOR=>text=>ciphertext)
3. CFB – ciphertext feedback. The algorithm is converted into a stream cipher, that is, each character can be encrypted and immediately transmitted to the recipient
4. OFB – output feedback. A portion of the ciphertext is fed into the shift register. For each encryption session, a new initial state of the register is used.

Four modes are believed to be sufficient to use DES in almost any area for which the algorithm is suitable

The hardware implementation of the algorithm on a separate chip makes it possible to achieve high encryption speeds with small device dimensions.

AES is the US federal encryption standard currently in use.

AES is an advanced encryption standard.

Requirements:

1. The cipher must be block
2. The cipher must have a block length of 128 bits
3. The cipher must support keys of length 128, 192, 256 bits

The algorithm is an unconventional block cipher because it does not use a Feishtel network for cryptotransformations.

The algorithm represents each block of encoded data as a two-dimensional byte array of size 4x4, 4x6 or 4x8, depending on the set block length.

The algorithm consists of a certain number of rounds (from 10 to 14 - this depends on the block size and key length).

GOST 28147089 – Russian standard for data encryption and data protection.

The algorithm is designed for hardware and software implementation, satisfies the necessary cryptographic requirements and does not impose restrictions on the degree of secrecy of the protected information.

The algorithm implements encryption of 64-bit data blocks using a 256-bit key consisting of eight 32-bit subkeys.

At each i-th round, the K i-th subkey is used.

GOST 28147-89 encryption algorithms have the advantages of other algorithms for symmetric systems and surpass them in their capabilities.

At each i-th round of the GOST algorithm, the following operations are performed:

L i =R i -1 , R i =L i -1 (plus circle)f(R i -1 , K i)

After completing these 32 operations, the implementation of the encryption algorithm will be completed.

The advantage of GOST is the presence of protection against the imposition of false data (imitation insertion mode), as well as the same encryption cycle in all 4 modes (algorithms) of GOST.

High cryptographic strength is ensured due to the large key length (256 bits) and 32 conversion rounds.

The standard includes modes (algorithms):

1. Easy replacement mode
2. Gamma mode
3. Gamma mode with feedback
4. Simulation insert generation mode

Asymmetric encryption algorithms.

In asymmetric encryption algorithms (or public key cryptography), one key (public) is used for encrypted information, and another (secret) is used for decryption.

These keys are different and cannot be derived from one another.

Information exchange scheme:

1. The recipient calculates the public and private keys; the secret key is kept secret, but the public key is made available (informs the sender, a group of network users, publishes)
2. The sender, using the recipient's public key, encrypts the message that is sent to the recipient
3. The recipient receives the message and decrypts it using his private key

Using an asymmetric encryption method

The use of such ciphers became possible thanks to K. Shannon, who proposed constructing a cipher in such a way that its solution would be equivalent to solving a mathematical problem that requires performing volumes of calculations that exceed the capabilities of modern computers (for example, operations with large prime numbers and their products; finding the value of the product P =x*y)

RSA data encryption cryptosystem.

Currently, the most developed method of cryptographic information protection with a known key is RSA, named after the initial letters of the names of its inventors (Rivest, Shamir, Adleman)

To use RSA algorithms, you must first generate a public and private key by following these steps:

1. Choose two very large prime numbers p and q and define n as the result of multiplying p by q (n=p*q)
2. Choose a large random number d. This number must be coprime to m, the result of multiplication (p-1)(q-1)
3. Determine a number e for which the following relation is true (e*d)mod(m)=1 or e=(1mod(m))/d
4. The public key will be the numbers e,n, and the secret key will be the numbers d,n

Key creation is highlighted in red.

Asymmetric cryptosystems based on elliptic curves.

Based on elliptic curves E, it is possible to implement not only cryptographic algorithms for asymmetric encryption, but also to generate a shared secret key for symmetric encryption.

Cryptosystems based on elliptic curves allow the use of significantly smaller key sizes compared to other cryptographic algorithms while maintaining the same level of cryptographic strength.

For the above implementations, elliptic curves over Galois fields GF(p) with a finite number p of elements of two types are used:

1. Elliptic curve over a finite field of type E(GF(p)), where p is some prime number
2. Elliptic curve over a finite field of type E(GF(2m)), where p=2m

Example: Asymmetric encryption algorithm based on elliptic curves ECES (Elliptic Curve Encryption Scheme)

ElGamal algorithm.

The ElGamal system is a public key cryptosystem based on the logarithm problem. This algorithm is used for both encryption and digital signature.

The set of system parameters includes a prime number p and an integer g, the powers of which modulo p generate a large number of elements Z p

Replacement methods.

A substitution cipher replaces some characters with others, but preserves their order in the message.

4 types of replacement (substitution):

1. Mono-alphabetic. Formula = Y i =k 1 X i +k 2 (modN), where Y i is the i-character of the alphabet, k 1, k 2 are constants, X i is the i-character of the plaintext, N is the length of the alphabet used.

Example. Replacement - plaintext, Key - Key

1. Homophonic substitution - substitution of one plaintext character matches several ciphertext characters. This method is used to distort the statistical properties of ciphertext. Table substitution is used. The values ​​are used one by one from the column.

1. Polyalphabetic substitution is the use of several alphabets. The alphabet changes at every encryption step. A stepwise replacement of letters according to the table is used.
2. Polygram replacement - formed from one alphabet using special rules. The cipher is located in a matrix, and the plaintext is divided into pairs of symbols XiXi+1

Permutation ciphers.

The difference between a permutation cipher is that only the order of characters of similar text is changed, but they themselves are not changed.

Example. Text "Load oranges in barrels Brothers Karamazov"

Ciphertext “Ptr_aezguionl_byseit_kramchaizryamaak_a__v____oi”

along different paths of a geometric figure.

The simplest example of a permutation is permutation with fixed period d. In this method, the message is divided into blocks according to d characters and the same permutation is performed in each block. The rule by which the permutation is performed is a key and can be specified by some permutation of the first d natural numbers. As a result, the letters of the message themselves do not change, but are transmitted in a different order.

For example, for d=6, you can take 436215 as the permutation key. This means that in each block of 6 characters, the fourth character goes to first place, the third to second, the sixth to third, etc. Suppose you need to encrypt the following text:

The number of characters in the original message is 24, therefore, the message must be divided into 4 blocks. The result of encryption using the permutation 436215 will be the message

OETET_TLSKDISHR_YAFNAVOI

Theoretically, if a block consists of d characters, then the number of possible permutations d!=1*2*...*(d-1)*d . In the last example d=6, therefore, the number of permutations is 6!=1*2*3*4*5*6=720. Thus, if an adversary intercepted the encrypted message in the example above, it would take him no more than 720 attempts to resolve the original message (assuming the block size is known to the adversary).

To increase cryptographic strength, two or more permutations with different periods can be sequentially applied to the encrypted message.

Another example of permutation methods is table rearrangement. In this method, the source text is written along the rows of a table and reads it along the columns of the same table. The sequence of filling rows and reading columns can be any and is specified by a key.

Let's look at an example. Let the encoding table have 4 columns and 3 rows (block size is 3*4=12 characters). Let's encrypt the following text:

The number of characters in the original message is 24, therefore, the message must be divided into 2 blocks. Let's write each block in its own table line by line (Table 2.9).

Table 2.9.

Encryption using table permutation method
1 block	E	T
E	ABOUT	E	TO
E		WITH	D
L
2 block		I	Sh
AND	F	T	R
IN	A	Sh	2 block

N

Then we will read each block from the table sequentially column by column:

ETTTE OKD SLYAFA RNSHOIVYA

You can read the columns not sequentially, but, for example, like this: third, second, first, fourth:

OKDTE ETT SLSHOI RNYAFAVYA

In this case, the order in which the columns are read will be the key. If message size

is not a multiple of the block size, you can supplement the message with some symbols that do not affect the meaning, for example, spaces. However, this is not recommended, since it gives the enemy, in case of interception of the cryptogram, information about the size of the permutation table used (block length). After determining the block length, the adversary can find the key length (number of table columns) among the block length divisors.

Let's see how to encrypt and decrypt a message that is not a multiple of the size of the permutation table. Let's encrypt the word

CHANGE

The number of characters in the original message is 9. Let's write the message into the table line by line (Table 2.10), and leave the last three cells empty.

Then we will read from the table sequentially by columns:

PMAEERNEC If To decrypt, first determine the number of complete columns, that is, the number of characters in the last line. For this they divide

There are other permutation methods that can be implemented in software and hardware. For example, when transmitting data written in binary form, it is convenient to use a hardware unit that shuffles the bits of the original n-bit message in a certain way using appropriate electrical wiring. So, if we take the block size to be eight bits, we can, for example, use a permutation block such as

Transposition encryption is that plaintext characters are rearranged according to a certain rule within a certain block of this text. Consider a permutation designed to encrypt a message of length n characters. It can be represented with using a table

Where i 1 – the number of the ciphertext location where the first letter of the plaintext falls during the selected transformation, i 2 - the number of the place for the second letter, etc. In the top line of the table the numbers from 1 to n, and at the bottom are the same numbers, but in random order. This table is called a degree permutation n.

Knowing the permutation that specifies the transformation, it is possible to carry out both encryption and decryption of the text. In this case, the permutation table itself serves as the encryption key.

Number of different transformations of a permutation cipher designed to encrypt messages of length n, less than or equal n! (n factorial). Note that this number also includes a conversion option that leaves all the characters in their places.

With increasing numbers n meaning n! grows very quickly. For use in practice, such a cipher is not convenient, since for large values n I have to work with long tables. Therefore, ciphers that use not the permutation table itself, but a certain rule that generates this table, have become widespread. Let's look at a few examples of such ciphers.

Scytala permutation cipher. It is known that in the 5th century BC the rulers of Sparta, the most warlike of the Greek states, had a well-developed system of secret military communications and encrypted their messages using wandered the first simplest cryptographic device that implements the simple permutation method.

Encryption was performed as follows. A strip of parchment was wound in a spiral (turn to turn) on a cylindrical rod, which was called a skitala, and several lines of message text were written on it along the rod (Fig. 1.2). Then a strip of parchment with written text was removed from the rod. The letters on this strip turned out to be located chaotically.

Rice. 1.2. Scytala code

The same result can be obtained if the letters of the message are written in a ring, not in a row, but through a certain number of positions until the entire text is exhausted. Message " GO"When placed around the circumference of the rod, three letters each gives the ciphertext: " NUTAPESA_TY".

To decrypt such a ciphertext, you need not only to know the encryption rule, but also to have a key in the form of a rod of a certain diameter. Knowing only the type of cipher, but not having the key, deciphering the message was not easy.

Encryption tables. Since the beginning of the Renaissance (late 14th century), cryptography began to revive. The permutation ciphers developed at that time used encryption tables, which, in essence, set the rules for permuting letters in a message.

The keys used in encryption tables are:

table size;

word or phrase specifying a permutation;

features of the table structure.

One of the most primitive table permutation ciphers is simple permutation, for which the key is the size of the table. This encryption method is similar to the scytal cipher. For example, the message " TERMINATOR ARRIVES ON THE SEVENTH AT MIDNIGHT"is written into the table one by one column by column. The result of filling a table of 5 rows and 7 columns is shown in Fig. 1.3.

After filling the table with the message text, the contents of the table are read row by row to form the ciphertext. If the ciphertext is written in groups of five letters, the result is an encrypted message: " TNPVE GLEAR ADONR TIEV OMOBT MPCHIR YSOOO".

Rice. 1.3. Filling an encryption table with 5 rows and 7 columns

Naturally, the sender and recipient of the message must agree in advance on a shared key in the form of a table size. It should be noted that combining ciphertext letters into 5-letter groups is not included in the cipher key and is carried out for the convenience of writing nonsense text. When decrypting, the steps are performed in reverse order.

An encryption method called single permutation by key. This method differs from the previous one in that the table columns are rearranged by a keyword, phrase, or set of numbers the length of the table row.

Let's use, for example, the word " PELICAN", and let's take the message text from the previous example. Figure 1.4 shows two tables filled with the message text and a keyword, with the left table corresponding to the filling before the rearrangement, and the right table to the filling after the rearrangement.

Rice. 1.4. Encryption tables filled with keyword and message text

The top row of the left table contains the key, and the numbers under the key letters are determined according to the natural order of the corresponding key letters in the alphabet. If there were identical letters in the key, they would be numbered from left to right. In the right table, the columns are rearranged according to the ordered numbers of the key letters.

When reading the contents of the right table row by row and writing the ciphertext in groups of five letters, we get the encrypted message: " GNVEP LTOOA DRNEV TEIO RPOTM BCHMOR SOYYI".

To provide additional privacy, you can re-encrypt a message that has already been encrypted. This encryption method is called double permutation. In case of double permutation of columns and rows, the permutations of tables are defined separately for columns and separately for rows. First, the text of the message is written into the table, and then the columns and then the rows are rearranged one by one. When decrypting, the order of permutations should be reversed.

An example of performing encryption using the double permutation method is shown in Fig. 1.5. If you read the ciphertext from the right table line by line in blocks of four letters, you will get the following: " TYUAE OOGM RLIP OSV".

Rice. 1.5. An example of performing encryption using the double permutation method

The key to the double permutation cipher is the sequence of column numbers and row numbers of the source table (in our example, the sequences are 4132 and 3142, respectively).

The number of double permutation options increases rapidly as the table size increases:

for a 3x3 table there are 36 options;

for a 4x4 table 576 options;

for a 5x5 table there are 14400 options.

Encryption using magic squares. In the Middle Ages, magic squares were also used for encryption by permutation. . Magic squares are called square tables with consecutive natural numbers inscribed in their cells, starting from 1, which add up to the same number for each column, each row and each diagonal.

The encrypted text was entered into magic squares in accordance with the numbering of their cells. If you then write out the contents of such a table line by line, you will get a ciphertext formed by rearranging the letters of the original message.

An example of a magic square and filling it with the message " I'M ARRIVING ON THE EIGHTH" is shown in Fig. 1.6.

Rice. 1.6. Example of a 4x4 magic square and filling it with a message

The ciphertext obtained by reading the contents of the right table row by row has a completely mysterious appearance: " OIRM EOSYU VTA LGOP".

The number of magic squares increases rapidly as the size of the square increases. There is only one magic square of size 3x3 (if you do not take into account its rotations). The number of 4x4 magic squares is already 880, and the number of 5x5 magic squares is about 250,000.

Magic squares of medium and large sizes could serve as a good basis for providing the encryption needs of that time, since it is almost impossible to manually try all the options for such a cipher.

(see also )

The work of the American mathematician Claude Shannon, which appeared in the mid-20th century, had a great influence on the development of cryptography. These works laid the foundations of information theory, and also developed a mathematical apparatus for research in many areas of science related to information. Moreover, it is generally accepted that information theory as a science was born in 1948 after the publication of K. Shannon’s work “Mathematical Theory of Communications”.

In his work “The Theory of Communication in Secret Systems,” Claude Shannon summarized the experience accumulated before him in the development of ciphers. It turned out that even in very complex ciphers such simple ciphers as substitution ciphers, permutation ciphers or combinations thereof.

The primary characteristic by which ciphers are classified is the type of transformation performed on the plaintext during encryption. If fragments of plaintext (individual letters or groups of letters) are replaced by some of their equivalents in the ciphertext, then the corresponding cipher belongs to the class replacement ciphers. If the letters of the plaintext during encryption only change places with each other, then we are dealing with permutation cipher. In order to increase the reliability of encryption, the ciphertext obtained using a certain cipher can be encrypted again using a different cipher.

Rice. 6.1.

All possible such compositions of various ciphers lead to the third class of ciphers, which are usually called composition ciphers. Note that a composition cipher may not be included in either the class of substitution ciphers or the class of permutation ciphers (Fig. 6.1).

6.3 Permutation ciphers

A permutation cipher, as its name suggests, transforms the permutation of letters in plaintext. A typical example of a permutation cipher is the Scital cipher. Typically, plaintext is divided into segments of equal length and each segment is encrypted independently. Let, for example, the length of the segments be equal to and be a one-to-one mapping of the set into yourself. Then the permutation cipher works like this: a piece of plaintext is converted into a piece of ciphertext.

A classic example of such a cipher is a system using a card with holes - grille, which, when applied to a sheet of paper, leaves only some parts of it exposed. When encrypted, the letters of the message fit into these holes. When decrypted, the message is fit into a diagram of the required dimensions, then a grid is superimposed, after which only the letters of the plaintext are visible.

Other permutation cipher options are also possible, such as columnar and double permutation ciphers.

6.3.1 Column permutation cipher

During decryption, the letters of the ciphertext are written in columns according to the sequence of key numbers, after which the original text is read in rows. To make it easier to remember the key, the table columns are rearranged by keyword or phrase, all characters of which are assigned numbers determined by the order of the corresponding letters in the alphabet.

When solving tasks for cryptanalysis of permutation ciphers, it is necessary to restore the initial order of the letters of the text. To do this, character compatibility analysis is used, which a compatibility table can help with (see).

Table 6.1.

Combination of Russian letters	TO	G		Left	Combination of Russian letters	TO
3	97	On right	IN	l, d, k, t, v, r, n	12	88
80	20	l, n, s, t, r, v, k, m	i, e, y, i, a, o	B	81	19
68	32	o, s, e, a, r, y	R	i, t, a, e, i, o	60	40
78	22	o, a, i, s, s, n, l, r	Combination of Russian letters	r, y, a, i, e, o	69	31
72	28	o, a, p, l, i, v	WITH	r, i, y, a, i, e, o	68	32
19	81	e, a, i, o, n, y, p, v	ABOUT	m, i, l, d, t, r, n	12	88
83	17	n, t, r, s, l, v, m, i	r, e, i, a, y, o	AND	71	29
89	11	e, i, d, a, n	3	o, e, a, and	51	49
27	73	a, n, c, o, m, d	Sh	r, t, m, i, o, l, n	25	75
55	45	s, n, c, i, e, m, k, h	E	b, v, e, o, a, i, s	73	27
77	23	o, a, i, p, y, t, l, e	D	g, v, s, i, e, o, a	75	25
80	20	i, e, o, a, b, i, yu, y	i, s, a, i, e, o	M	73	27
55	45	i, e, o, y, a, n, p, s	A	d, b, n, o, a, i, e	80	20
11	89	o, a, i, e, s, n, y	T	r, p, k, v, t, n	15	85
65	35	c, s, t, r, i, d, n, m	in, with, y, a, i, e, o	P	68	32
55	45	o, p, e, a, y, i, l	F	i, k, t, a, p, o, e	80	20
69	31	a, e, o, i, u, i, s, n	TO	s, t, v, a, e, i, o	32	68
57	43	t, k, o, i, e, b, s, n	E	h, y, i, a, e, o, s	63	37
15	85	o, a, e, i, b, v, r, s	p, t, k, d, n, m, r	U	16	84
70	30	t, p, s, d, n, y, w	AND	n, a, e, o, and	81	19
90	10	and, e, o, a, e, o, a	y, e, o, a, s, and	o, i, s, n, v, p, r	43	57
69	31	e, yu, n, a, and	C	i, e, a, s	93	7
82	18	e, a, y, i, o	H	e, i, t, n	66	34
67	33	b, y, s, e, o, a, i, v	I	e, i, n, a, o, l	68	32
84	16	e, b, a, i, y	SCH	e, i, a	97	3
0	100	m, r, t, s, b, c, n	Y	L, x, e, m, i, v, s, n	56	44
0	100	n, s, t, l	b	n, k, v, p, s, e, o, and	24	76
14	86	s, s, m, l, d, t, r, n	1 block	n, t, r, s, k	0	100
58	42	b, o, a, i, l, y	YU	d, t, sch, c, n, p	11	89
43	57	o, n, r, l, a, i, s	2 block	v, s, t, p, d, k, m, l	16	84

When analyzing the compatibility of letters with each other, one should keep in mind the dependence of the appearance of letters in plain text on a significant number of preceding letters. To analyze these patterns, the concept of conditional probability is used.

The question of the dependence of the letters of the alphabet in plaintext on previous letters was systematically studied by the famous Russian mathematician A.A. Markov (1856-1922). He proved that the occurrences of letters in plaintext cannot be considered independent of each other. In this regard, A.A. Markov noted another stable pattern of open texts associated with the alternation of vowels and consonants. He calculated the frequency of occurrence of vowel-vowel bigrams ( g, g), vowel-consonant ( g, s), consonant-vowel ( s, g), consonant-consonant ( s, s) in Russian text with a length of characters. The calculation results are shown in the following table:

Table 6.2.

	Combination of Russian letters	TO	Alternation of vowels and consonants
Combination of Russian letters	6588	38310	44898
TO	38296	16806	55102

Total Example 6.2

The plaintext, keeping spaces between words, was recorded in a table. The beginning was in the first line, the text was written from left to right, moving from line to the next, encryption consisted of rearranging the columns. Find the plaintext.

WITH	R			Y	E
	Combination of Russian letters	T	ABOUT	F	T
p, t, k, d, n, m, r	b	WITH		p, t, k, d, n, m, r	i, e, y, i, a, o
i, s, a, i, e, o	i, s, a, i, e, o	2 block	Y	F	in, with, y, a, i, e, o

Cipher text: Solution.

Let's assign numbers to the columns in the order they appear. Our task is to find an order of columns in which the text will make sense.

	1	2	3	4	5	6
1	Let's make a table:
2		Let's make a table:
3			Let's make a table:
4				Let's make a table:
5					Let's make a table:
6						Let's make a table:

X

A cell (, ) in this table means that the column number follows the column number . We mark impossible cases with an "X".

	1	2	3	4	5	6
1	Let's make a table:	Let's make a table:			Let's make a table:
2	Let's make a table:	Let's make a table:			Let's make a table:
3			Let's make a table:	Let's make a table:	Let's make a table:
4		Let's make a table:	Let's make a table:	Let's make a table:	Let's make a table:
5	Let's make a table:	Let's make a table:			Let's make a table:
6						Let's make a table:

So, after column 6, column 5 must necessarily follow. But then we put an “X” in cell 6, 2 and we get: column 2 follows column 3. Next, we crossed out 5, 1 and 2, 1, therefore, we need to check the options: . ..6532... and...65432... . But (4, 3) was crossed out earlier. So, the remaining options for the arrangement of columns are:

• 1, 6, 5, 3, 2, 4
• 6, 5, 3, 2, 4, 1
• 4, 1, 6, 5, 3, 2
• 1, 4, 6, 5, 3, 2

Let's write 6, 5, 3, 2 columns in a row:

6	5	3	2
T	s	-	V
O	R	O	G
b	at	d	b
P	R	I	m

Trying to put column 1 before column 6 will result in the bigram MP in the last row and the combination DTY in the first. The remaining options are: 653241, 146532.

Answer: 653241 - key, plain text: you\_on\_the road\_be\_stubborn (line from a song popular in the 1970s).

Let's give another example of cryptanalysis of a column permutation cipher.

Example 6.3 Decipher: SVPOOSLUYYST\_EDPSOKOKAIZO

Cipher text: The text contains 25 characters, which allows it to be written in a 5x5 square matrix. It is known that encryption was carried out column by column, therefore, decryption should be carried out by changing the order of the columns.