Simple single permutation cipher. Vertical permutation cipher. Analysis of permutation ciphers

(see also )

Big influence The development of cryptography was influenced by the works of the American mathematician Claude Shannon that appeared in the mid-20th century. 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 Communication”.

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 the following can be identified as typical components: simple ciphers How 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 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 The permutation cipher is the "Scital" cipher. Usually the plaintext is divided into segments 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 itself. 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 fits into the diagram required sizes, then a hash mark is applied, 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

G	WITH	Left		On right	G	WITH
3	97	l, d, k, t, v, r, n	A	l, n, s, t, r, v, k, m	12	88
80	20	i, e, y, i, a, o	B	o, s, e, a, r, y	81	19
68	32	i, t, a, e, i, o	IN	o, a, i, s, s, n, l, r	60	40
78	22	r, y, a, i, e, o	G	o, a, p, l, i, v	69	31
72	28	r, i, y, a, i, e, o	D	e, a, i, o, n, y, p, v	68	32
19	81	m, i, l, d, t, r, n	E	n, t, r, s, l, v, m, i	12	88
83	17	r, e, i, a, y, o	AND	e, i, d, a, n	71	29
89	11	o, e, a, and	3	a, n, c, o, m, d	51	49
27	73	r, t, m, i, o, l, n	AND	s, n, c, i, e, m, k, h	25	75
55	45	b, v, e, o, a, i, s	TO	o, a, i, p, y, t, l, e	73	27
77	23	g, v, s, i, e, o, a	L	i, e, o, a, b, i, yu, y	75	25
80	20	i, s, a, i, e, o	M	i, e, o, y, a, n, p, s	73	27
55	45	d, b, n, o, a, i, e	N	o, a, i, e, s, n, y	80	20
11	89	r, p, k, v, t, n	ABOUT	c, s, t, r, i, d, n, m	15	85
65	35	in, with, y, a, i, e, o	P	o, p, e, a, y, i, l	68	32
55	45	i, k, t, a, p, o, e	R	a, e, o, i, u, i, s, n	80	20
69	31	s, t, v, a, e, i, o	WITH	t, k, o, i, e, b, s, n	32	68
57	43	h, y, i, a, e, o, s	T	o, a, e, i, b, v, r, s	63	37
15	85	p, t, k, d, n, m, r	U	t, p, s, d, n, y, w	16	84
70	30	n, a, e, o, and	F	and, e, o, a, e, o, a	81	19
90	10	y, e, o, a, s, and	X	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	Sh	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	E	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	I	c, 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. Alternation of vowels and consonants

	G	WITH	Total
G	6588	38310	44898
WITH	38296	16806	55102

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.

Cipher text:

D	IN			Y	T
	G	ABOUT	E	R	ABOUT
U	b	D		U	B
M	M	I	Y	R	P

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.

Let's make a table:

	1	2	3	4	5	6
1	X
2		X
3			X
4				X
5					X
6						X

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

Combinations of columns 1, 2 and 5, 2 are not possible, since a vowel cannot appear before a soft sign. The sequences of columns 2, 1 and 2, 5 are also impossible. Now from the third line it follows that 1, 5 and 5, 1 are impossible, since УУ is a bigram uncharacteristic for the Russian language. Next, two spaces in a row cannot be in the text, which means we put “X” in cells 3, 4 and 4, 3. Let’s turn to the third line again. If column 2 followed column 4, the word would begin with a soft sign. We put “X” in cell 4, 2. From the first line: the combination 4, 5 is impossible, and 3, 5 is also impossible. The result of our reasoning is presented in the table:

	1	2	3	4	5	6
1	X	X			X
2	X	X			X
3			X	X	X
4		X	X	X	X
5	X	X			X
6						X

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 an MP bigram in last line and the combination of 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

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

A cipher from which transformations change only the order of the symbols source text, but do not change them themselves, is called a permutation cipher

Let's consider a transformation from Silk, designed to encrypt a message with a length of characters. It can be represented using a table

where is the number of the place in the ciphertext where the first letter of the original message falls under the selected transformation, the number of place for the second letter, etc. In top line The tables are written in order of numbers from 1 to 1, and at the bottom there are the same numbers, but in random order. This table is called degree substitution

Knowing the substitution that specifies the transformation, it is possible to carry out both encryption and decryption of the text. For example, if you use substitution for conversion

and the word is encrypted in accordance with it. Try to decrypt the message received as a result of the transformation using the above substitution.

As an exercise, the reader is invited to independently write out substitutions that specify transformations in the three described below

examples of permutation ciphers. The answers are located at the end of the section.

A reader familiar with the method of mathematical induction can easily verify that there are (read factorial) options for filling out the bottom row of the table (6). Thus, the number of different transformations of a permutation cipher designed to encrypt messages of length is less than or equal to (note that this number also includes a transformation option that leaves all the characters in their places!).

As the number increases, the value increases very quickly. Here is a table of values ​​for the first 10 natural numbers:

(see scan)

For large values, for an approximate calculation you can use the well-known Stirling formula

An example of a silent encryption system designed to encrypt messages of length is a cipher in which the set of all degree substitutions is taken as the set of keys and the corresponding cipher transformations are specified as described above. The number of keys in such a cipher is

For practical use, such a cipher is not convenient, since large values I have to work with long tables.

Permutation ciphers using some geometric figure have become widespread. Transformations from this cipher consist in the fact that the original text is entered into the figure along one “route”, and then written out from it along the other. This cipher is called a route permutation. For example, you can enter Original message into a rectangular table by choosing the following route: horizontally, starting from the left top corner alternately from left to right and from right to left. We will write out the message along a different route: vertically, starting from the upper right corner and moving alternately from top to bottom and bottom to top.

Let's encrypt, for example, in the specified way phrase:

using size rectangle

(see scan)

The encrypted phrase looks like this:

Theoretically, the routes could be much more sophisticated, but the obfuscation of the routes makes such ciphers difficult to use.

Below are descriptions of three types of permutation ciphers encountered in Olympiad problems.

Cipher "Scitala". One of the very first encryption devices was the staff ("Scital"), which was used during the war of Sparta against Athens in the 5th century BC. e. It was a cylinder on which a narrow papyrus tape (without gaps or overlaps) was wound turn by turn, and then the text necessary for transmission was written on this tape along its axis. The tape was unwound from the cylinder and sent to the recipient, who, having a cylinder of exactly the same diameter, wound the tape around it and read the message. It is clear that this encryption method rearranges the letters of the message.

The Scital cipher, as can be seen from the solution to Problem 2.1, implements no more permutations as before - message length). Indeed, this cipher, as is easy to see, is equivalent to the following routing permutation cipher: a message is written line by line into a table consisting of columns, after which the letters are written down in columns. The number of table columns involved cannot exceed the message length.

There are also clean physical limitations, imposed by the implementation of the Scital cipher. It is natural to assume that the diameter of the rod should not exceed 10 centimeters. With a line height of 1 centimeter, no more than 32 letters will fit on one turn of such a rod. Thus, the number of permutations implemented by Scytala is unlikely to exceed 32.

Code "Rotary grille". To use the cipher, called a rotary hash, a stencil is made from a rectangular sheet of checkered paper the size of the squares. The number of cells is cut out in the stencil so that when applied to Blank sheet four papers of the same size possible ways its cuts completely cover the entire area of ​​the sheet.

The letters of the message are sequentially entered into the cutouts of the stencil (line by line, in each line from left to right) at each of its four possible positions in advance in the prescribed manner.

Let us explain the encryption process with an example. Let the grid shown in Fig. be used as a key. 1.

Let's encrypt text using it

Having placed a grid on a sheet of paper, we enter the first 15 (according to the number

cutouts) of the message letters: Removing the grille, we will see the text shown in Fig. 2. Rotate the grill 180°. New, not yet filled cells will appear in the windows. We enter the following 15 letters into them. The result will be the entry shown in Fig. 3. Then we turn the lattice over to the other side and encrypt the rest of the text in the same way (Fig. 4, 5).

The recipient of the message, having exactly the same hash, can easily read the original text by applying the hash to the ciphertext in order in four ways.

It can be proven that the number of possible stencils, that is, the number of keys in the lattice cipher, is (see Problem 1.1). This cipher is intended for messages of length The number of all permutations in a text of this length will be many times

greater than the number However, even with the size of the stencil, the number of possible gratings exceeds 4 billion.

A widely used variant of the routing permutation cipher is called the vertical rearrangement"(ball screw). It again uses a rectangle in which the message fits in the usual way(line by line from left to right). The letters are written vertically, and the columns are taken in the order determined by the key. Let, for example, this key be: (5,4,1,7,2,6,3), and with its help you need to encrypt the message:

Let's write the message in a rectangle, the columns of which are numbered according to the key:

(see scan)

Now, selecting the columns in the order specified by the key and writing the letters of each of them sequentially from top to bottom, we obtain the following cryptogram:

The number of ball screw keys is no more than where is the number of table columns. As a rule, much less than the length of the text (the message fits into several lines of letters), and, therefore, much less

Using the above Stirling formula for large numbers, try to estimate how many times the number of possible permutations by columns is less than the number of all permutations on a text of length that is a multiple of

In cases where the ball screw key is not recommended to be written down, it can be extracted from some easy-to-remember word or sentence. There are many ways to do this. The most common one is to assign numbers to the letters according to the usual alphabetical order letters For example, let the keyword be The letter A present in it is given the number 1. If a letter appears several times, then its occurrences are numbered sequentially from left to right. Therefore, the second occurrence of the letter A receives the number 2. Since there is no letter in this word, the letter B receives the number 3, and so on. The process continues until

until all letters receive numbers. Thus we get the following key:

Let's move on to the question of methods for breaking permutation ciphers. The problem that arises when recovering a message encrypted by Silk is not only that the number of possible keys is large, even with small text lengths. Even if it is possible to go through all the possible permutations, it is not always clear which of these options is true. For example, suppose we need to recover the original text from a cryptogram and we know nothing except that a permutation cipher was used. Which version of the “meaningful” source text is accepted as true: or A maybe Let’s give an example of an even more confusing situation. Suppose you want to recover a message using a cryptogram

the permutation obtained by the cipher. There are at least two options for the original message:

These options have exactly the opposite meaning, and under the existing conditions we have no way to determine which option is true.

Sometimes, due to the peculiarities of the cipher implementation, it is possible to obtain information about the transformation (permutation) used. Let's look at the Scital cipher from Problem 2.1. The question of the number of permutations implemented by Scytala has already been discussed above. There were no more than 32 of them. This number is small, so you can search through all the options. If the message is long enough, we will most likely receive a single readable version of the text. However, using information about the location of the lines left by the encoder, it is possible to determine the diameter of the rod, and therefore the resulting permutation of letters (see Problem 2.1).

In the example considered, the cipher operator inadvertently left traces on the papyrus that allow us to easily read the message. There are also other situations where the not very “competent” use of the cipher makes it easier to open the correspondence.

Problem 5.2 contains an example of text encrypted by a ball screw. By convention, spaces between words were omitted when writing text into the table. Therefore, we conclude that all columns containing a space in the last line must appear at the end of the text. Thus, the columns are divided into two groups (containing 6 letters, and

A similar situation arises with the “incomplete” use of the lattice cipher (see Problem 4.1). Let there be a lattice of size and a message of length k encrypted using it, containing no spaces. Unfilled k spaces in the grille, provided that k correspond to the cutouts in the fourth position of the grille. Based on such information, there is a sharp decrease in the number of admissible lattices (there will be them. The reader is invited to independently calculate the number of admissible lattices at

Using the example of solving Problem 5.2, we will demonstrate another approach to breaking vertical permutation ciphers - linguistic. It is based on the fact that in natural languages ​​some combinations of letters occur very often, others much less frequently, and many do not occur at all (for example -

We will select the order of the columns one after another so that in all lines of these columns we get “readable” text segments. In the given solution to the problem, text recovery begins with selecting a chain of three columns of the first group, containing a combination in the last line, since it is natural to assume that the message ends with a period. Next, columns are selected that continue sections of text in other lines, etc.

Combination of linguistic method taking into account additional information can quite quickly lead to the message being opened.

To conclude the story about permutation ciphers, we present a story with the encrypted autograph of A. S. Pushkin, described in V. Kaverin’s novel “The Fulfillment of Desires.”

The main character of the novel, a history student Trubachevsky, who was working in the archives of his teacher, Academician S.I. Bauer, found in one of the secret drawers of Pushkin's bureau a fragment of the unfinished X chapter of Eugene Onegin. It was a half-sheet of thick bluish paper folded in half with a watermark dated 1829. The following was written on the sheet.

(see scan)

(see scan)

Without special effort Trubachevsky read the manuscript and did not understand anything. He rewrote it, it turned out to be incoherent nonsense, in which one line, which barely began a thought, is interrupted by another, and that by a third, even more meaningless and incoherent. He tried to break the manuscript into stanzas, but again it didn’t work. I began to look for rhymes - as if there were no rhymes, although all this bears little resemblance to blank verse. I calculated the line - iambic tetrameter, the meter in which “Eugene Onegin” was written.

Trubachevsky excitedly took up the manuscript, tried to read it, skipping one line at a time, then two, then three, hoping to accidentally guess the secret sequence in which the lines were written. Nothing worked for him. Then he began to read the third line after the first, the fifth after the third, the eighth after the fifth, assuming that the gaps should increase in arithmetic progression. All the same! Desperate, he abandoned this idea. However, she did not give him peace either at the lecture or on the tram... Like a chess player playing in his head, he not only knew every line by heart, he saw it in ten combinations at once.

Time has passed. One day, when he was looking at the light spots of the windows of a train approaching the platform, with some inner vision he

I saw the entire manuscript in front of me - and with such extraordinary clarity, as only happens in a dream.

Permutation ciphers

This method consists in the fact that the characters of the encrypted text are rearranged according to certain rules within the encrypted block of characters, i.e. transformations lead to a change only in the order of the characters in the original message. Let's look at some of the most common varieties of this method - simple, table-complicated, and route-complex permutations.

Encryption simple rearrangement (vertical rearrangement) is carried out as follows:

1) selected keyword with non-repeating characters;

2) the encrypted text is written in consecutive lines under the keyword symbols;

3) the ciphertext is written out in columns in the sequence in which the letters of the key are located in the alphabet (or in the order of numbers in a natural series, if the key is digital).

As an illustration, here is an example of encryption using a simple rearrangement of the message: “BE CAREFUL WITH YOUR REPRESENTATIVE OF THE PHOENIX COMPANY.” In this case we apply digital key 5 – 8 – 1 – 3 – 7 – 4 – 6 – 2. In the source text, a letter is used instead of spaces A.

B	U	D	b	T	E	A	ABOUT
WITH	T	ABOUT	R	ABOUT	AND	N	Y
A	WITH	A	P	R	E	D	WITH
T	A	IN	AND	T	E	L	E
M	A	F	AND	R	M	Y	A
F	E	N	AND	TO	WITH	A	A

By writing the text in columns and grouping characters by five, we get the encrypted text in the form:

DO VF NOYSE LRP IIEZH EEMSB S TMF NDLY TOPT RKUTS A E .

Decryption is performed in the following order:

1) count the number of characters in the ciphertext and divide by the number of characters in the key;

2) write down the keyword and under its signs in the appropriate sequence write down the ciphertext symbols in the quantity determined above;

3) read the source text according to the rows of the table.

The number of keys is no more than m!, where m is the number of table columns.

The weakness of encryption by simple permutation is due to the fact that with a large length of the encrypted text, patterns of key symbols may appear in the ciphertext. To eliminate this drawback, you can change the key after encrypting a certain number of characters. By changing the key frequently enough, the strength of encryption can be significantly increased. At the same time, however, the organization of the encryption and decryption process becomes more complicated.

To obtain and remember a numeric key, there are various methods. One of the most common is to assign numbers to letters according to the alphabetical order of the letters. Let's take, for example, the word PERMANENT. The letter A present in it receives No. 1. If a letter appears more than once, its occurrences are numbered sequentially from left to right. Therefore, the second occurrence of the letter A gets #2. There is no letter B in this word, then the letter B receives No. 3, etc.:

P	E	R	E	WITH	T	A	N	ABOUT	IN	TO	A

Making it more difficult to rearrange a table lies in the fact that to record the characters of the encrypted text, a special table is used, into which some complicating elements are introduced. The complication is that a certain number of table cells are not used (they are empty in the figure). The number and location of unused elements is additional key encryption. Encrypted text in blocks of m x n – s elements (m x n– table dimensions, s– number of unused elements) is recorded in the table. Further encryption is similar to simple permutation.

B	U	D		b	T	E	A	ABOUT	WITH
	T	ABOUT	R	ABOUT	AND	N		Y	A
WITH	A	ABOUT	R	E	D	WITH	T		A
IN	AND		T	E	L	E	M	A	F
AND		R	M	Y	A	F	E	N	AND
TO	WITH	A	A	A		A	A	A	A

The encrypted text will look like this: DOPR BSWIK RRTM OY N ENSEF UT I SS AF I HOE EE T ME TJ DL.

During decryption, the ciphertext characters are written in table columns in a sequence of key characters, skipping unused elements. The source text is read line by line. By varying the size of the table, the sequence of key characters, and the number and location of unused elements, you can obtain the required strength of the ciphertext.

Another option is cipher "Rotating grid" . intended for messages of length 4mk. Take a stencil measuring 2m*2k cells, cut out m*k cells so that when applied to a sheet of paper of the same size 4 different ways(rotating 90°) its cutouts completely cover the entire area of ​​the sheet. The letters of the message are sequentially entered into the stencil cutouts in rows, in each row from left to right, in each of its 4 possible positions in a predetermined order. The number of possible stencils, i.e. the number of keys in this cipher is 4 mk (with a stencil size of 8*8, the number of options exceeds 4 billion).

Very high encryption strength can be achieved complicating rearrangements along routes like Hamiltonian ones. In this case, the vertices of a certain hypercube are used to record the characters of the ciphertext, and the characters of the ciphertext are read along Hamilton routes, and several different routes are used. For example, consider encryption using Hamilton routes with n = 3. The structure and three routes are shown in Fig. 7, and an example of encryption is in Fig. 8. volumetric (multidimensional) permutation. In 1992 - 94 the idea of ​​using volumetric permutation to encrypt plaintext received further development. An improved permutation scheme based on the Rubik's cube principle, in which, along with the plaintext, the permutations are also functional elements the encryption algorithm itself formed the basis of the Rubicon system. It uses a three-dimensional cube and a tetrahedron as prototypes of spatial multidimensional structures, based on volumetric transformations of which permutations are carried out.

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	ABOUT
T	E	TO	WITH
T		D	L
2 block
I		Sh	AND
F	R	ABOUT	IN
A	N	AND	I

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 RNYAFAIVA

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 any 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

To decrypt, first determine the number of complete columns, that is, the number of characters in the last line. For this they divide message size(in our example – 9) by the number of columns or key size (in the example – 4). The remainder of the division will be the number of complete columns: 9 mod 4 = 1. Therefore, in our example there was 1 full column and three short ones. Now you can put the letters of the message in their places and decipher the message. Since the encryption key was the number 1234 (the columns were read sequentially), then when decrypting, the first three characters (PMA) are written in the first column of the permutation table, the next two (EE) - in the second column, the next two (RN) - in the third, and the last two (EK) - in the fourth. After filling the table, we read the rows and receive the initial message CHANGE.

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 in a certain way by appropriate wiring, bits of the original n-bit message. So, if we take the block size to be eight bits, we can, for example, use a permutation block such as

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 changes can be used by others geometric figures and more “tricky” routes, such as 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.