Vertical permutation method. Substitution (substitution) and permutation ciphers

Block ciphers

Due to the fact that the clear text of the message usually has an arbitrary length, sometimes quite large, it is divided into smaller blocks of a fixed length. The texts of these blocks are encrypted separately and independently of each other.

Single-key block ciphers are divided into 3 groups:

Permutation ciphers

Substitution ciphers

Composite ciphers.

When using permutation ciphers, which are designed to eliminate the meaning of a message by changing the alternation order of its symbols, the signs plaintext are rearranged according to a certain rule (key) within a given block. As a result of this, the normal order of their occurrence and the very meaning of the information message are disrupted. In this case, a distinction is made between simple and complex permutation ciphers.

A simple permutation cipher rearranges a group of letters of text in a regular manner according to a chosen permutation key (rule). There are many examples from history of the use of such ciphers for manual encryption. In this case, special tables were often used, which provided simple encryption procedures (keys), according to which the letters in the message were rearranged. The key for such tables was the size of the table, a phrase specifying a permutation or other special features of the table.

An example of the simplest permutation cipher is shown in Fig. 5.5.

Rice. 5.5. The simplest cipher permutations.

As can be seen from Fig. 5.5, in order to encrypt the message “YUSTACE ALEX MEET YOUR CONNECTED MAN”, the latter must be written in the form of a table consisting, for example, of 5 rows and 6 columns. The message text is written in columns, excluding spaces. If the last column is incomplete, it is filled randomly with any letters. To obtain an encrypted message, the original text is read line by line (from left to right) and written in groups, for example, 5 digits. Last

the procedure does not relate to the encryption process and is done only to make it more convenient to write down text that is devoid of any meaning. To decrypt such text, you need to know the key, namely the number of rows and columns in the table or, in other words, its size.

A more practical encryption method, very similar to the previous one, is described below. It differs only in that the table columns are rearranged according to a keyword, phrase or set of numbers the length of a table line.

When encrypting by simple permutation, the ciphertext is written in successive lines under the keyword symbols, which should not be repeated. To simplify the remembering of the key, a keyword is used, the letters of which, numbered in the order of their location in the alphabet, set the permutation rule. 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. The encryption process using a simple permutation cipher is illustrated in Fig. 5.6. Suppose you need to encrypt an information message

“THE MEETING WILL BE HELD TOMORROW JUSTACE.”

To encrypt this plaintext, we write it without spaces (the participation of the latter in the encryption procedure, due to their high frequency repetition, significantly weakens the cryptographic strength of the cipher) and choose an encryption key, for example, 245 136. According to this key, consisting of 6 digits, we will divide the entire information message into blocks, each of which will contain 6 letters of text. After dividing into blocks, we got 4 blocks containing 6 letters each, and 1 block containing 5 letters. In such cases, the last group of letters of the original message is randomly supplemented with various symbols until a complete block is obtained. In our case, only one letter is missing, so we select any letter, for example Ъ, and add it at the end of the fifth block.

Rice. 5.6. Simple permutation cipher

Next, using the key 245 136, the letters of the original plaintext are rearranged. For example, the first digit of the key is 2, indicating that in the new block the first letter of the ciphertext will be the second letter of the plaintext block, the second digit of the key is 4, indicating that the second letter of the ciphertext is the fourth letter in the plaintext block, etc. d.

Ultimately, after permutations in all blocks, we obtain ciphertext. Having read it, we see that it is completely devoid of any semantic content.

To make the key easier to remember, a keyword is usually used. IN in this case- this is the word “ROOT”. In it, number 1 of the key corresponds to the letter E, since it is the first of all letters of this word found in our alphabet, number 2 - the letter K (for the same reason), etc.

The same message can be encrypted using a table consisting of, for example, 5 rows and 6 columns (the length of the keyword). The source text is written in columns and forms a table (Fig. 5.7). The keyword specifies a rule for rearranging columns. If the same letters appear in a keyword, they are numbered in order from left to right. The resulting second ciphertext, as can be seen from Fig. 5.7 is completely different from the first one.

Rice. 5.7. Encryption using a table

The main disadvantage of this cipher is its low cryptographic strength. By factoring the ciphertext (there aren't many options), you can easily determine the likely length of the codeword that was used during encryption.

To increase the cryptographic strength of the ciphertext obtained above, you can try to encrypt it again. This encryption method is known as double permutation. The essence of this method is as follows. The text obtained after the first encryption is encrypted a second time using a table with a different dimension (the lengths of the rows and columns are selected differently). In addition, you can rearrange rows in one table and columns in another. You can fill the table with source text different ways: zigzag, snake, spiral, etc.

A simple permutation cipher using table properties called magic squares (Figure 5.8) has been used since the Middle Ages. Magic squares are equilateral tables, all the cells of which are filled with natural numbers, starting from 1. Moreover, these numbers in sum give the same number for each column, each row and diagonals of the magic square (in our case, this is the number 34). Source text - WAITING TO MEET YOU JUSTACE, when filling out the magic square, it is entered in the order of the natural numbers, for example, the number 1 was replaced by 1 letter source text(G), number 12 - 12 letter of the message (C), etc. After writing the plaintext, the contents of the table are read line by line, resulting in a ciphertext with a permutation of letters.

Rice. 5.8. Magic square

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 left top 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:

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 last line 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.

Story

Exact time the appearance of the permutation cipher is not known. It is quite possible that scribes in ancient times rearranged the letters in the name of their king in order to hide his true name or for ritual purposes.

One of the oldest encryption devices known to us is Scytala. It is undoubtedly known that the wanderer was used in the war of Sparta against Athens at the end of the 5th century BC. e.

The ancestor of the anagram is considered to be the poet and grammarian Lycophron, who lived in Ancient Greece in the 3rd century BC e. As the Byzantine author John Tsets reported, from the name of King Ptolemy he composed the first anagram known to us: Ptolemaios - Aro Melitos, which translated means “from honey”, and from the name of Queen Arsinoe - as “ Ion Eras"(violet of Hera).

Simple permutation ciphers

Typically, when encrypting and decrypting a simple permutation cipher, a permutation table is used:

The first line is the position of the character in the plaintext, the second line is the position in the ciphergram. Thus, with message length n (\displaystyle n) characters exist exactly n! (\displaystyle n!\ ) keys.

Route permutation ciphers

The so-called route permutations using some geometric figure(flat or volumetric). The transformations consist in the fact that a segment of plaintext is written into such a figure along a certain trajectory, and written out along a different trajectory. An example of this cipher is the Scytala cipher.

Table routing permutation cipher

The most widespread routing codes permutations based on rectangles (tables). For example, you can write a message in a rectangular table along the route: horizontally, starting from the upper left corner, alternately from left to right. We will copy the message along the route: vertically, starting from the upper right corner, alternately from top to bottom.

CRYPTOGRAM: yesoeomrnniateairmuptkprrysv

Reversing the steps described will not present any difficulty in deciphering.

Vertical permutation cipher

A type of route permutation - vertical permutation - has become widespread. This cipher also uses a rectangular table in which the message is written in rows from left to right. The ciphergram is written vertically, with the columns selected in the order determined by the key.

CLEAR TEXT: example of route permutation

KEY: (3, 1, 4, 2, 5)

CRYPTOGRAM: rmuptkmrnrnrnprrysviateaeshoeo

It is not advisable to fill the last row of the table with “non-working” letters, since the cryptanalyst who received this cryptogram receives information about the length of the numeric key.

Code "rotary grid"

In 1550, the Italian mathematician Gerolamo Cardano (1501-1576) proposed in his book On Subtleties new technology message encryption - lattice.

Initially, the Cardano lattice was a stencil with holes into which letters, syllables or words of a message were written. Then the stencil was removed, and free place filled with more or less meaningful text. This method of hiding information refers to steganography.

Later, the “rotating lattice” cipher was proposed - the first transpositional (geometric) cipher. Even though there is a big difference Between Cardano's original proposal and the rotating lattice cipher, stencil-based encryption methods are commonly called "Cardano lattice".

To encrypt and decrypt using this cipher, a stencil with cut out cells is made. When applying a stencil to a table of the same size with four possible ways, its cuts must completely cover all the cells of the table exactly once.

When encrypting, a stencil is placed on the table. Letters of plaintext are written into visible cells along a certain route. Next, the stencil is turned over three times, each time performing the filling operation.

The ciphergram is written out from the resulting table along a specific route. The key is the stencil, the route of inscription and the order of turns.

This method encryption was used for transmission classified information Dutch rulers in the 1740s. During World War I, Kaiser Wilhelm's army used the "rotating grid" cipher. The Germans used bars different sizes, however, for a very short time (four months), to the great disappointment of the French cryptanalysts, who had just begun to select the keys to them. For grids of different sizes, the French came up with their own code names: Anna (25 letters), Bertha (36 letters), Dora (64 letters) and Emile (81 letters).

In permutation encryption, the characters of the encrypted text are rearranged according to certain rules within the encrypted block of this text.

Simple rearrangement

An encryption block size of n columns and m rows and a key sequence are selected, which is formed from a natural series of numbers 1,2,...,n by random permutation.

Encryption is carried out in the following order:

The encrypted text is written in successive lines under the key sequence numbers, forming an encryption block of size n*m.

The ciphertext is written out in columns in ascending order of column numbers specified by the key sequence.

Filled out new block etc.

For example, let's encrypt the text

LOAD_ORANGES_IN BARRELS

block size 8*3 and key 5-8-1-3-7-4-6-2.

A simple permutation table will look like:

Encrypted message:

WEB_NHZLOESLGAYEIAICHRP_

Decryption is performed in the following order:

A block of characters of size n*m ​​is extracted from the ciphertext.

This block is divided into n groups of m characters.

Symbols are written to those columns of the permutation table whose numbers coincide with the group numbers in the block. The decrypted text is read according to the rows of the permutation table.

A new block of characters is allocated, etc.

Permutation complicated according to the table

When permutation across tables becomes more complex, unused cells of the table are introduced into the permutation table to increase the strength of the cipher. The number and location of unused elements is an additional encryption key.

When encrypting text, text characters are not written into unused elements, and no characters from them are written into the encrypted text - they are simply skipped. When decrypting, ciphertext characters are also not included in unused elements.

To further increase the cryptographic strength of the cipher, during the encryption process you can change the keys, the size of the permutation table, the number and location of unused elements according to some algorithm, and this algorithm becomes an additional cipher key.

Permutation complicated by routes

High encryption strength can be achieved by complicating permutations along Hamiltonian-type routes. 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 of a three-dimensional hypercube is shown in Figure 6.

Figure 6. Three-dimensional hypercube

The numbers of the cube's vertices determine the sequence in which it is filled with ciphertext symbols when forming a block. In general, an n-dimensional hypercube has n 2 vertices.

Figure 7. Hamilton routes

The sequence of symbol permutations in the encrypted block for the first scheme is 5-6-2-1-3-4-8-7, and for the second it is 5-1-3-4-2-6-8-7. Similarly, you can obtain a sequence of permutations for other routes: 5-7-3-1-2-6-8-4, 5-6-8-7-3-1-2-4, 5-1-2-4-3 -7-8-6, etc.

The dimension of the hypercube and the number of types of selected Hamilton routes constitute the secret key of the method.

The stability of a simple permutation is uniquely determined by the size of the permutation matrix used. For example, when using a 16*16 matrix, the number of possible permutations reaches 1.4E26. It is impossible to sort through such a number of options even using a computer. The stability of complicated permutations is even higher. However, it should be borne in mind that when encrypting by permutation, the probabilistic characteristics of the source text are completely preserved, which facilitates cryptanalysis.

Encryption using the magic square method.

Magic squares are square tables with consecutive natural numbers inscribed in their cells, starting from 1, which add up to the same number for each column, row and diagonal.

When encrypting, the letters of the plaintext must be entered into the magic square in accordance with the numbering of its cells. To obtain the ciphertext, read the contents of the completed table row by row.

Let's encrypt the phrase “MAGIC POWER” using a 4x4 magic square. To do this, we will choose one of 880 options for magic squares of a given size (Figure 8a). Then we enter each letter of the message into a separate cell of the table with a number corresponding to the serial number of the letter in the original phrase (Figure 8b). When reading the filled table row by row, we get the ciphertext: “_GAIAESSCHYA_KIALM”.

Figure 8. Example of encryption using magic squares

A cipher from which transformations only change the order of the characters in the 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 upper left 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 a 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 paper of the same size in four 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 a predetermined order.

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 route permutation cipher is called a vertical permutation cipher (VPC). 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 the case where it is not recommended to write down the ballscrew key, 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 keyword will The letter A present in it receives 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 implementation features of the cipher, 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. He 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.