Classical permutation ciphers. Route permutations

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.

Vertical permutation cipher. It is a variation of the previous cipher. The features of the cipher include the following:

The number of columns in the table is fixed and determined by the key length;

The route of entry is strictly from left to right, top to bottom;

The ciphergram is written out in columns in accordance with their numbering (key).

Fig.5.5. An example of using a vertical permutation cipher

You can use a word or phrase as a key. Then the order in which the columns are written corresponds to the alphabetical order of the letters in the key. For example, if the keyword is “UNCLE”, then the letter present in it A gets number 1, D– 2, etc. If a letter appears several times in a word, its occurrences are numbered sequentially from left to right. In the example, the first letter D gets number 2, second D – 3.

When encrypting the message “ABRAMOV ILYA SERGEEVICH” the result will be “ОЯЭ_АВ_ЭРИИЛЧМГМГ_Б_СВ”.

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. Let's look at some of the most common varieties of this method that can be used in automated systems.

The simplest permutation is to write the original text backwards and at the same time break the ciphergram into five letters. For example, from the phrase:

LET IT BE THE WAY WE WANTED

you get the following ciphertext:

ILETO KHIMKA KKATT EDUB TSUP

The last group (five) is missing one letter. This means that before encrypting the original expression, it should be supplemented with an insignificant letter (for example, O) to a number that is a multiple of five:

LET-BE-TAKKA-KMYKHO-TELIO.

Then the ciphergram, despite such a minor change, will look different:

OILET OKHYMK AKKAT TEDUB LTSUP

It seems nothing complicated, but decryption will cause serious inconvenience.

During the American Civil War, the following code was used: the original phrase was written in several lines. For example, fifteen letters each (filling the last line with meaningless letters).

After this, the vertical columns were written in order into a line divided into five letters:

PKUMS YTHIO BTUED LEITK TLAMK NCOAP

A variant of this cipher: first write the original phrase in columns:

Then break the lines into five letters:

PSYUE TKAMH TLAVD UTBDT AKKYO EIBGE

If we shorten the lines and increase their number, we get rectangle lattice, into which you can write the source text. But here preliminary agreements are already required between the addressee and the sender of the messages, since the grid itself can be of different lengths and heights, you can write in it in rows, in columns, in a spiral there or in a spiral back, you can also write along diagonals, and for encryption You can also take different directions. In general, there are a lot of options.

For example, let's take a 6x6 grid (and the number of lines can increase or decrease depending on the length of the original message) and fill it line by line:

If you encrypt along the arrows (diagonals) from top to bottom from the upper left corner, you will end up with the following ciphergram:

P UU SDK TECH LTAOA BTKTBM AMEVL YLGK IDI EZ ZH

For final design, the ciphertext can be divided into groups of 6 characters:

PUUSDK TEKKHT AOABTK TBMAME VLYLGK IDIEZZH

Keyed permutations are often used. Then the rules for filling the grid and encrypting from it are simplified and become standard. The only thing you need to remember and know is the key, which can be any word, for example, RADIATOR. In accordance with the arrangement of letters in the alphabet, the letter A receives the number 1, the second letter A - 2, the next letter D in the alphabet - 3, then I - 4, O - 5; the first letter P is 6, the second P is 7 and the letter T is 8. Fill in the grid:

We write down the columns in accordance with the numbers of the key letters:

UTY BKT STH TAO UAL PEMO DKI BKE

Then the sequence is again divided into fives:

UTYK TSTHT AOUAL PEMOD KIBKE

This simple column rearrangement cipher was used by German secret agents during World War II. They used the first letters of the lines on a certain page of some ordinary book as a key.

A development of this cipher is a cipher for rearranging columns with gaps, which are located in the lattice also in accordance with the key (in our case, after 6-1-3-4-2-8-5-7 ... characters):

The encryption will be like this:

UDC b SEHL TTOM AEP PKI UKLR BTTO

From the examples considered, it is clear that all encryption and decryption procedures using the permutation method are quite formal and can be implemented algorithmically.

Aatbash, Scital cipher, Cardano lattice are well-known ways to hide information from prying eyes. In the classical sense, a permutation cipher is an anagram. Its essence lies in the fact that the letters of the plaintext change positions according to a certain rule. In other words, the cipher key is to change the order of characters in the open message. However, the dependence of the key on the length of the encrypted text has created many inconveniences for using this type of cipher. But smart heads have found interesting, cunning solutions that are described in the article.

Inverted groups

To get acquainted with encryption using the permutation method, we will mention one of the simplest examples. Its algorithm consists of dividing a message into n blocks, which are then turned backwards and swapped. Let's look at an example.

• "The day was passing, and the air was dark in the sky."

Let's divide this message into groups. In this case n = 6.

• "Denukh odili nebav ozd uhtemny."

Now let's expand the groups, writing each one from the end.

• "hunned vaben dzo methu yyn."

Let's rearrange them in a certain way.

• "ilido methu yyn huned vaben dzo."

To an ignorant person, in this form the message is nothing more than rubbish. But, of course, the one to whom the message is addressed is in charge of the decryption algorithm.

Middle insert

The algorithm for this encryption is a little more complicated than permutation:

1. Divide the message into groups with an even number of characters.
2. Insert additional letters in the middle of each group.

Let's look at an example.

"He led the creatures of the earth to sleep."

"Zemn yetv ariu vodi lkosnu."

"Zeamn yeabtv araiu voabdi lkoasnu."

In this case, alternating letters “a” and “ab” were inserted into the middle of the groups. Inserts can be different, in different quantities and not repeated. In addition, you can expand each group, shuffle them, etc.

Cipher code "Sandwich"

Another fun and simple example of permutation encryption. To use it, you need to divide the plaintext into 2 halves and write one of them character by character between the letters of the other. Let's show it with an example.

• "From their labors; only I am alone, homeless."

Divide into halves with an equal number of letters.

• "I'm the only homeless person out of their labor."

Now let's write the first half of the message with a large space between letters.

• "About t i h t u d o v l i s h ."

And in these spaces we will place the letters of the second half.

• "Oyatoidhitnrbuedzodvolminshy."

Finally, let's group the letters into a kind of words (optional operation).

• "Oyatoi dhi tnrbue dzodvol minshyy."

It is very easy to encrypt text using this method. The resulting line of nonsense will have to take some time for the uninitiated to unravel.

Rearrangements along the "route"

This name was given to ciphers that were widely used in ancient times. The route in their construction was some geometric figure. The plaintext was written into such a figure according to a certain pattern, and retrieved according to its inverse. For example, one option might be to write plaintext into a table using the scheme: a snake crawls clockwise through the cells, and an encrypted message is composed by writing the columns into one row, from the first to the last. This is also permutation encryption.

Let's show with an example how to encrypt text. Try to determine the recording route and the encryption route yourself.

"I was preparing to endure the war."

We will write the message in a table with dimensions of 3x9 cells. The table size can be determined based on the message length, or some fixed table can be used several times.

We will compose the code starting from the upper right corner of the table.

• "Launlvosoyatovvygidtaerprzh."

Reversing the steps described is not difficult. It's enough to just do the opposite. This method is extremely convenient because it makes it easy to remember the encryption and decryption procedure. It is also interesting because any shape can be used for a cipher. For example, a spiral.

Vertical permutations

This type of cipher is also a variant of route permutation. It is interesting primarily because of the presence of a key. This method was widespread in the past and also used tables for encryption. The message is written into the table in the usual way - from top to bottom, and the ciphergram is written vertically, while maintaining the order specified by the key or password. Let's look at an example of such encryption.

"Both with a painful path and with compassion"

We use a table with dimensions of 4x8 cells and write our message in it in the usual way. And for encryption we use the key 85241673.

Now, using the key as an indication of the order, let's write the columns into a line.

• "Gusetmsntmayapoysaotmserinid."

It is important to note that with this encryption method, empty cells in the table should not be filled with random letters or symbols, hoping that this will complicate the ciphergram. In fact, on the contrary, such an action will give the enemies a hint. Because the key length will be equal to one of the message length divisors.

Reverse decoding of vertical permutation

Vertical permutation is interesting because decrypting a message is not simply following an algorithm in reverse. Anyone who knows the key knows how many columns there are in the table. To decrypt a message, you need to determine the number of long and short lines in the table. This will allow you to determine the beginning from where to start writing the ciphergram into the table in order to read the plaintext. To do this, divide the message length by the key length and get 30/8=3 and 6 as a remainder.

Thus, we learned that the table has 6 long columns and 2 short ones, not completely filled with letters. Looking at the key, we see that the encryption started at the 5th column and it should be long. So we find that the first 4 letters of the ciphergram correspond to the fifth column of the table. Now you can write down all the letters in their places and read the secret message.

This type belongs to the so-called stencil ciphers, but at its core is encryption by the method of symbol permutation. The key is a stencil in the shape of a table with holes cut in it. In fact, the stencil can be any shape, but most often a square or table is used.

The Cardano stencil is made according to the following principle: the cut cells, when rotated 90°, should not overlap each other. That is, after 4 rotations of the stencil around its axis, the slots in it should not coincide even once.

Let's use a simple Cardano lattice as an example (in the figure below).

Using this stencil, we will encrypt the phrase “O Muses, I will address you with an appeal.”

We fill the cells of the stencil with letters according to the rule: first from right to left, and then from top to bottom. When the cells run out, turn the stencil 90° clockwise. In this way we obtain the following table.

And the last turn.

After combining 4 tables into one, we get the final encrypted message.

Although the message may remain the same, it will be more convenient to receive a familiar-looking ciphergram for transmission. To do this, you can fill empty cells with random letters and write the columns in one line:

• "YAVGVGM OOZGVS MUAKG MBZGN GOSCHAGE SRYUAG"

In order to decrypt this message, the recipient must have an exact copy of the stencil that was used for encryption. This cipher was considered quite stable for a long time. It also has many variations. For example, using 4 Cardano grids at once, each of which rotates in its own way.

Analysis of permutation ciphers

All permutation ciphers are vulnerable to frequency analysis. Especially in cases where the message length is comparable to the key length. And this fact cannot be changed by repeated use of permutations, no matter how complex they may be. Therefore, in cryptography, only those ciphers that use several mechanisms at once, in addition to permutation, can be stable.

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) a keyword with non-repeating characters is selected;

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 use the digital key 5 – 8 – 1 – 3 – 7 – 4 – 6 – 2. In the source text, instead of spaces, the letter is used 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.

There are various methods for obtaining and storing a numeric key. 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.:

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 an additional encryption key. Encrypted text in blocks of m x n – s elements (m x n– dimensions of the table, s – number of unused elements) is recorded in the table. Further encryption is similar to simple permutation.

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 in 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 was further developed. An improved permutation scheme based on the Rubik's cube principle, in which, along with the plaintext, the functional elements of the encryption algorithm itself are also permuted, 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.