Simplest private key encryption methods. Replacement codes - educational and scientific activities of anisimov vladimir viktorovich

In his work " The Mathematical Theory of Secret Communication "Claude Shannon summarized the experience accumulated before him in the development of ciphers.

It turned out that even in complex ciphers, typical components can be distinguishedreplacement ciphers, permutation ciphers or combinations thereof.

14.1 Replacement code

The most famous and commonly used ciphers are replacement ciphers ... They are characterized by the fact that separate parts of the message(letters, words, ...) are replaced with any other letters, numbers, symbols etc. In this case, the replacement is carried out so that later, using the encrypted message, it is possible to unambiguously restore the transmitted message.

When encrypting substitution (substitution) the characters of the encrypted text are replaced by characters of the same or a different alphabet with a predetermined replacement rule. In a simple substitution cipher, each character source text is replaced by symbols of the same alphabet in the same way throughout the text.

The replacement cipher is the simplest, most popular cipher. Examples are:Caesar cipher , « digital alphabet "Peter the Great and "dancing men "A. Conan-Doyle .

Replacement cipher carries out the conversion of replacing letters or other "parts" plain text into similar "parts" cipher text .

By enlarging the alphabets, i.e. declaring "parts" in letters, any replacement cipher can be reduced to the replacement of letters.

Let's givemathematical description replacement cipher .

Let be: X – alphabetopen text andY- alphabetencrypted about the text, consistingof the same number of characters .

Let also: g: X  Y – one-to-one display X in Y . Each letter x alphabet X a uniquely defined letter at alphabet Y , which we denote by the symbol g (x), moreover different letters are associated with different letters .

Then replacement cipher acts like this: plaintext x 1 x 2 ... x n converted to cipher text g(x 1 ) g (x 2 ) ... g (x n ).

There are 4 types of substitutions considered in cryptography :

mono-alphabetic;

homophonic;

polyalphabetic;

polygram.

Mono-alphabetic replacement

With this method, each character of the plaintext alphabet is associated with one character of the ciphertext (from the same alphabet).

The general formula for mono-alphabetic substitution is as follows:

y i = (k 1 x i + k 2 ) mod n,

An example of this method is a cipher called Atbash.

The encryption rule is to replace i- oh letters of the alphabet with a letter with a number n = i + 1 where n- the number of letters in the alphabet. An example for the Latin alphabet looks like this:

Original text: abcdefghijklmnopqrstuvwxyz

Encrypted text: ZYXWVUTSRQPONMLKJIHGFEDCBA

Homophonic replacement

The peculiarity of this method is that matches several ciphertext characters to one plaintext character , which allows you to get away from the statistical relationship.

An example of this cipher is a book cipher- a type of cipher in which each element of the plaintext (each letter or word) is replaced by a pointer (for example, page, row and column numbers) of a similar element in an additional key text.

Polygram replacement

IN polygram ciphers substitutions plain text letters are replaced not one at a time, but in groups ... The first advantage of this method is that the frequency distribution of groups of letters is much more uniform than that of individual characters. Second, productive frequency analysis requires larger size ciphertext, since the number of different groups of letters is much more than just the alphabet.

Polyalphabetic Substitutions

To increase the strength of the cipher, so-called polyalphabetic substitutions are used, which several alphabets of the ciphertext are used for replacement.

Several varieties of polyalphabetic substitution are known, the most famous of which are:

single-circuit (ordinary and monophonic)

and multi-circuit.

When polyalphabetic single-line ordinary substitution Several alphabets are used to replace characters in the original text, and the alphabets are changed sequentially and cyclically, i.e. the first character is replaced with the corresponding character of the first alphabet, the second with the character of the second alphabet, and so on until all selected alphabets have been used. After that, the use of the alphabets is repeated.

The encryption process itself is carried out as follows:

Key letters are written under each letter of the encrypted test. The key is repeated the required number of times;

Each letter of the encrypted text is replaced by the submatrix with letters located at the intersection of the lines connecting the letters of the encrypted text in the first line of the submatrix and the key letters below them;

The resulting text can be divided into groups of several characters.

A particular case of the considered polyalphabetic substitution is the so-called monaural replacement .

Encryption is carried out in the same way as with a simple replacement, with the only difference that after encrypting each character, the corresponding column of alphabets is cyclically shifted up one position.

Polyalphabetic Multiple Loop Replacement lies in the fact that several sets (contours) of alphabets used cyclically are used for encryption, and each contour in the general case has its own individual period of application. This period, as a rule, is calculated by the number of characters, after encryption of which the outline of the alphabets changes. A special case of multi-loop polyalphabetic substitution is substitution according to the Viginer table if several keys are used for encryption, each of which has its own period of application.

Replacement cipher

Substitute code replaces each plaintext character with some other. In classical cryptography, four types of substitution ciphers are distinguished:

• One-alphabetic substitution cipher (simple substitution cipher)- a cipher in which each plaintext character is replaced by some character of the same alphabet, fixed for a given key.
• Monophonic Substitution Cipher is similar to mono-alphabetic except that the plaintext character can be replaced with one of several possible characters.
• Polygram substitution cipher replaces not one character, but a whole group. Examples: Playfair cipher, Hill cipher.
• Multi-alphabetic substitution cipher consists of several simple replacement ciphers. Examples: Vigenere cipher, Beaufort cipher, one-time pad.

Simple replacement ciphers

Examples of simple replacement ciphers

Atbash cipher

A simple replacement cipher used for the Hebrew alphabet and deriving its name from there. Encryption occurs by replacing the first letter of the alphabet with the last, the second with the penultimate ( aleph(first letter) is replaced with tav(last), bet(second) is replaced by tire(penultimate); the cipher got its name from these combinations). Atbash cipher for the English alphabet:

Replacement alphabet: Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

Cipher using a codeword

A cipher using a codeword is one of the easiest to implement and decrypt. The idea is that the code word is selected, which is written in front, then the rest of the letters of the alphabet are written out in their order. Cipher using the code word WORD.

Original alphabet: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Replacement alphabet: W O R D A B C E F G H I J K L M N P Q S T U V X Y Z

As we can see, when using a short code word, we get a very, very simple replacement... Also, we cannot use words with repeated letters as a code word, since this will lead to ambiguity in decoding, that is, the same letter of the cipher text will correspond to two different letters of the original alphabet.

Replacement ciphers also include well-known ciphers used by the authors of many well-known books. Such as "Dancing Men" by A. Conan Doyle, or "The Golden Beetle" by E. Poe, as well as a cipher from the novel by J. Verne "Journey to the Center of the Earth".

Easy replacement cipher security

The main disadvantage of this encryption method is that the last letters of the alphabet (which have low coefficients in frequency analysis) tend to stay at the end. A more secure way to construct a replacement alphabet is to perform column movement (column movement) in the alphabet using a keyword, but this is not often done. Despite the fact that the number of possible keys is very large (26! = 2 ^ 88.4), this kind of cipher can be easily broken. According to distance of uniqueness of English language, 27.6 letters from the ciphertext should be enough to break the simple substitution cipher. In practice, about 50 characters are usually enough to crack, although some ciphertexts can be cracked with fewer characters if any non-standard structures are found. But with an even distribution of characters in the text, much longer ciphertexts may be required to crack.

• distance of uniqueness- a term used in cryptography, referring to the length of the original ciphertext, which must be sufficient to break the cipher.

Omophonic replacement

Early attempts to increase the difficulty of decoding by frequency analysis of replacement ciphers was to mask the actual frequencies of the characters in plain text using homophony. In these ciphers, the letters of the original alphabet correspond to more than one character from the replacement alphabet. Typically, the highest frequency characters in the original text are given more equivalents than the rarer characters. Thus, the frequency distribution becomes more uniform, making frequency analysis very difficult. Since the replacement alphabet required more than 26 characters, there has been a need for extended alphabets. One of the simplest solutions is to replace the alphabet with numbers. Another method consists of simple changes to the existing alphabet: uppercase letters, lower case, inverted characters, etc. More artistic, although not necessarily more reliable, would be homophonic ciphers, which use completely invented (fictional) alphabets. (for example, "The Dancing Men" by A. Conan Doyle, or "The Golden Beetle" by E. Poe, or "The Voynich Manuscript").

Examples of homophonic ciphers

Nomenclator

A cipher issued by a medieval official, which is a small book with large homophonic replacement tables. Initially, the cipher was limited to names important people that time, hence the name of the cipher; in later editions this cipher was supplemented large quantity common words and geographical names... On the basis of this "nomenclator", the Great Rossignel Cipher was compiled, used by the King of France, Louis XIV. Indeed, after this cipher ceased to be used, the French archives were closed for several hundred years. "Nomenclators" were the standard for diplomatic correspondence, espionage messages, and were the main means of anti-political conspiracy from the early fifteenth century to the late eighteenth century. Although government cryptanalysts were systematically hacking into the "nomenklators" by the middle of the sixteenth century. The usual way out of this situation was to increase the size of the tables. But by the end of the eighteenth century, when the system was beginning to die out, some "nomenclators" were up to 50,000 characters. However, not all "nomenklators" were broken.

Grand Cipher Rossignell

Antoni Rossignel and his son Bonaventure Rossignel invented a cipher that used 587 different numbers. The cipher was so strong that for many centuries no one could crack it, until Commander Ptignier Bazarier did it in 1893, who realized that each number stood for a French syllable, and not one letter, as was previously believed. He suggested that a specific sequence of repeated numbers, 124-22-125-46-345, encodes the word "les ennemis" (enemies) and based on this information he was able to unravel the entire cipher.

Book cipher

Book cipher - a cipher in which the key is a book or a small piece of text. The basic requirement will be that both correspondents not only have the same book, but the same edition and issue. Traditionally book ciphers work by replacing words in the original text with the location of those same words in the book. This will work until a word is encountered that is not in the book, then the message cannot be encoded. An alternative approach The one that gets around this problem is to replace individual characters rather than words. However, this method has by-effect: the ciphertext becomes very big size... (usually 4 to 6 digits are used to encrypt each character or syllable).

This is the way shown at the beginning of the film Seventeen Moments of Spring.

Cryptanalysis

The simple substitution cipher is easily broken by frequency analysis, since it does not change the frequency of the use of symbols in the message.

Monophonic ciphers are more difficult to break, although they do not hide all the statistical properties of the text.

Multi-alphabetic ciphers encrypt each character with some one-alphabetic cipher. The strength of such a cipher is highly dependent on the number of simple replacement ciphers used. But when using a computer, the cryptanalyst will have no difficulty in opening it.

see also

Literature

• Bruce Schneier "Applied Cryptography, Second Edition", ISBN 0-471-12845-7
• "Introduction to Cryptography" ed. V.V. Yashchenko - M .: MCNMO-CheRo, 2000, ISBN 5-900916-40-5

Wikimedia Foundation. 2010.

The simplest replacement cipher is mono-alphabetic pedestal, also called cipher simple replacement.

The key of such a cipher is a one-to-one mapping ( substitution) F plain text alphabet (X) in ciphertext (Y): F: X Y. Let us fix the numbering of symbols in the alphabets X and Y: X= { ,, … }, Y= { , , … }.

Then the mapping F is actually given by permutation of the order n= | X| = | Y|: when encrypting a character xi plaintext is replaced with the character ciphertext.

This permutation can be specified either by a table or using a formula. When specified using a formula, the value is represented as an expression depending on i.

Example. A typical example of a replacement cipher is Caesar cipher... This cipher implements the following transformation of a text written using the Latin alphabet: each plaintext letter is replaced by a letter three positions later in the alphabet (in this case, the alphabet is considered written in a circle, that is, after the letter 'z' is the letter 'a') ...

The plaintext ‘secret’ will be converted to ‘vhfuhw’. The key for the Caesar cipher can be specified in the form of the following table (Fig. 3). The first line contains the plaintext letters, the second contains the corresponding ciphertext letters.

Caesar's cipher can also be described in the form of a formula. To do this, we number the letters of the Latin alphabet with numbers from 0 to 25: a = 0, b = 1, …, z= 25. Then the replacement rule can be described as follows: the letter with the number i i + 3(mod 26 ), where the operation 'mod 26' means calculating the remainder of division by 26.

A generalized version of the Caesar cipher is possible, in which the letter with the number i is replaced by a letter with a number i+k(mod 26). In this case, the cipher key is the number k.

Generalizing this method even more, we come to the family affine ciphers... For the alphabet from n characters { ,, ...,) an affine cipher is a procedure that replaces the input symbol per symbol where j= k· i+l(mod n).

Simple replacement ciphers are not currently used because their strength is low. Methods for breaking such ciphers are based on analyzing the frequency of individual characters and their combinations. The fact is that in any language, various letters and combinations of two, three or more letters have characteristic repetition rates in texts. For example, in texts in Russian, the letter 'O' is most often encountered, then, in decreasing order of frequency, there are letters 'E' (assuming that 'E' and 'E' are the same letter), 'A', 'And',

‘T’, etc. For the English language, the same sequence of the most frequent letters: ‘E’, ‘T’, ‘A’, ‘I’, ‘N’. The most common character in texts is, however, not a letter, but a space character.

It becomes clear that when using a simple substitution cipher, the repetition rate of the encrypted characters in the ciphertext coincides with the repetition rate of the corresponding original characters in the plaintext. This makes it quite easy to break such a cipher. More subtle characteristics (taking into account the compatibility of various letters) even allow you to automate the hacking process.

In order to increase the strength of replacement ciphers, use multi-alphabetic substitution.

The encryption procedure for multi-alphabetic replacement includes a set of substitutions (,, ...,) and a function - distributor(k, i), specifying the sequence for applying substitutions.

When encrypting the i-th plaintext character, a substitution with the number (k, i), Where k- encryption key.

The Vigenere cipher is a special case of a poly-alphabetic substitution. Formally, this cipher can be described as follows.

As an encryption key, we choose a set of m integers:

k= (, , …, ). Plaintext transformation procedure t= (,, ...) to ciphertext c= (,, ...) we construct on the basis of the generalized Caesar cipher:

= + (mod 26), = + (mod 26), etc. When will all be used m component of the key k, for encryption (m + 1) Let us take the th letter again, and so on. In fact, an infinite sequence is used as an encryption key, formed by periodic repetition of the original set:,, ..., , , , …, ,,, ... Such a sequence is usually called gamut.

Breaking a poly-alphabetic substitution cipher is slightly more difficult than simple substitution ciphers, but it is also quite easy. Such a cipher is actually a simultaneous application m simple replacement ciphers (generalized Caesar cipher), and the part of the original text consisting of letters , ,, ... are encrypted using the "key" ki (i = 1,…, m).

If the gamma period is known (i.e. the number m), then any of the simple replacement cipher breaking methods can be applied to each such part. If the gamma period is not known, then the problem becomes more complicated. But even for these cases, effective methods hacking. These methods make it possible to determine the gamma period with sufficient probability, after which the task is reduced to breaking the gamma cipher with a known period.

As mentioned above, the basis for attacks on substitution ciphers is the analysis of the frequency of occurrences of characters in the ciphertext. In order to make it difficult to crack the replacement cipher, one can try to hide the frequency properties of the original text. For it is necessary that the frequencies of the appearance of different characters in the text coincide.

Such replacement ciphers are called homophonic.

The simplest variant of a homophonic cipher is as follows. Suppose we know the frequencies of occurrences of characters in the plaintext. Let be fi

• One-alphabetic substitution cipher (simple substitution cipher)- a cipher in which each plaintext character is replaced by some character of the same alphabet, fixed for a given key.
• Monophonic Substitution Cipher is similar to mono-alphabetic except that the plaintext character can be replaced with one of several possible characters.
• Polygram substitution cipher replaces not one character, but a whole group. Examples: Playfair cipher, Hill cipher.
• Polyalphabetic Substitution Cipher consists of several simple replacement ciphers. Examples: Vigenere cipher, Beaufort cipher, one-time pad.

Permutation ciphers can be considered as an alternative to substitution ciphers. In them, the elements of the text are rearranged in a different order from the original, and the elements themselves remain unchanged. On the contrary, in substitution ciphers, the elements of the text do not change their sequence, but change themselves.

History

The use of substitution ciphers dates back to Mesopotamia. In order to conceal information about the recipe for the production of glaze for pottery, the author replaced some of the words with numbers and cuneiform signs. The Roman emperor Gaius Julius Caesar, when writing secret messages, shifted each letter of the alphabet by 3 positions. This view substitution ciphers were later named after him, the Caesar cipher. Another equally well-known cipher of antiquity, Atbash, was used in the Bible to create hidden messages. Each letter of the word was replaced by its mirror image in the alphabet.

One of the first encryption devices is considered to be Aeneas's ruler, when using which a long thread was threaded through a slot, and then through holes made in the ruler. The letters corresponding to them were located next to the holes. A knot was tied on the thread where it passed through the hole. Thus, the text of the message was replaced by a sequence of distances between the nodes. This device was invented by the ancient Greek commander Aeneas the Tactician in the 4th century BC. e.

This shortcoming was deprived of polyalphabetic ciphers, the first of which was described by the German monk Johann Trithemius. According to the method described in his treatise "Polygraphy", the next letter was replaced by a symbol from its own cipher alphabet, while each next alphabet was obtained from the previous one using a shift by one letter. The polyalphabetic cipher described by Blaise de Vigenère in 1585 was especially popular. An arbitrary word was used as a key to the cipher. The corresponding this word the set of cipher alphabets was determined from the Vigenere table.

Simple replacement ciphers

Cipher using a codeword

A cipher using a codeword is one of the easiest to implement and decrypt. The idea is that the code word is selected, which is written in front, then the rest of the letters of the alphabet are written out in their order. Cipher using the code word WORD.

As we can see, when using a short codeword, we get a very, very simple replacement. We can use a word with repeated letters as a code word, but only if we remove extra letters from the code word, otherwise this will lead to ambiguity in decoding, that is, the same letter of the cipher text will correspond to two different letters of the original alphabet.

Cipher Text Writing Method

Traditionally, the ciphertext is written in blocks (another name for the “group”) of 5 characters each, without taking into account punctuation and spaces. This helps to avoid errors in the transmission of the encrypted message and allows you to hide word boundaries in the original text. The block contains 5 characters, as earlier it was convenient to transmit them by telegraph.

Easy replacement cipher security

The main disadvantage of this encryption method is that the last letters of the alphabet (which have low coefficients in frequency analysis) tend to stay at the end. A safer way to construct a replacement alphabet is to perform column movement (column movement) in the alphabet using a keyword, but this is rarely done. Despite the fact that the number of possible keys is very large (26! = 2 88.4), this kind of cipher can be easily broken. Provided that the message is of sufficient length (see below), a cryptanalyst can guess the meanings of some of the most common letters from an analysis of the frequency distribution of characters in the ciphertext. This makes it possible to form separate words that can be previously used for the subsequent obtaining of a more complete solution (see frequency analysis). According to distance of uniqueness English 27.6 letters from the ciphertext should be enough to break the simple substitution cipher. In practice, about 50 characters are usually enough to crack, although some ciphertexts can be cracked with fewer characters if any non-standard structures are found. But with an even distribution of characters in the text, much longer ciphertexts may be required to crack.

Omophonic replacement

Early attempts to increase the complexity of the frequency analysis of ciphertexts were to mask the actual frequencies of the characters in plain text using homophony. In these ciphers, the letters of the original alphabet correspond to more than one character from the replacement alphabet. Typically, the characters in the source text with the highest frequency are given more equivalents than the rarer characters. Thus, the frequency distribution becomes more uniform, making frequency analysis very difficult. Since the replacement alphabet required more than 26 characters, there has been a need for extended alphabets. One of the simplest solutions is to replace the alphabet with numbers. Another method consists of simple modifications to the existing alphabet: uppercase letters, lowercase letters, inverted characters, etc. More artistic, although not necessarily more reliable, would be homophonic ciphers, which use completely invented (fictional) alphabets (such as the cipher in a book Poe's “Golden Beetle,” or “The Voynich Manuscript.” However, these ciphers are not examples of homophonic substitution).

Examples of homophonic ciphers

Nomenclator

A cipher issued by a medieval official, which is a small book with large homophonic replacement tables. Initially, the cipher was limited to the names of important people of that time, hence the name of the cipher; in later editions, this cipher was supplemented with a large number of common words and place names. On the basis of this "nomenclator", the Great Cipher of Rossignol was compiled, which was used by King Louis XIV of France. Indeed, after this cipher ceased to be used, the French archives were closed for several hundred years. "Nomenclators" were the standard for diplomatic correspondence, espionage messages, and were the primary means of anti-political conspiracy from the early fifteenth century to the late eighteenth century. Although government cryptanalysts were systematically hacking into the "nomenklators" by the middle of the sixteenth century. The usual way out of this situation was to increase the size of the tables. But by the end of the eighteenth century, when the system began to fall out of use, some "nomenclators" were up to 50,000 characters. However, not all "nomenclators" were broken.

Great Cipher of Rossignol

Polygram ciphers

In polygram substitution ciphers, plaintext letters are replaced not one at a time, but in groups. The first advantage of this method is that the frequency distribution of groups of letters is much more uniform than that of individual characters. Secondly, for productive frequency analysis, a larger ciphertext size is required, since the number of different groups of letters is much larger than just the alphabet.

Examples of polygram ciphers

Playfair cipher

Cryptanalysis

1. Adaptive plaintext attack

Cryptanalysis of one-sound substitution ciphers is carried out by counting the frequencies of occurrence of pairs and triplets of symbols.

Plaintext attacks

With a plaintext of sufficient length, breaking mono-alphabetic and mono-sound ciphers is trivial.

Gleaned plaintext attacks

All substitution ciphers with the exception of the one-time pad are vulnerable to an attack based on the selected plaintext.

In encryption machines

One of the first encryption devices was invented in the fifteenth century and replaced the Caesar cipher. Its author was the Italian architect Leon Battista Alberti, who made a tangible contribution to the development of substitution ciphers. This device consisted of two copper discs different sizes fastened with a needle. An alphabet was applied to the edges of each disc. Both discs could rotate independently of each other, thereby matching the letters of the plain and ciphertext. The Alberti disc has been in widespread use for five centuries, including during the American Civil War.

To obtain an encrypted signal, a hollow disk with contacts applied on both sides was used. The resulting encrypted text depended on the disk commutation and its angular position. This type of encryption device was later called rotary machines.

Rotary machines were used by various countries during the Second World War. The most famous of them were: the American SIGABA car, the German ENIGMA, the English TYPEX and the Japanese PURPLE.

Rotary encryption systems had two types of keys. Soldering between the rotor contacts set a constant key. To replace the permanent keys, it was necessary to modernize all the released encryption machines of this model, which is difficult to implement in practice. Variable keys were often changed every day and were determined by the set of rotors and their initial position.

Application in our time

Despite the suppression of substitution ciphers with block ciphers, disposable pads are still used at the state level in our time. They are used to provide top secret communication channels. According to rumors, the telephone line between the heads of the USSR and the United States was encrypted using a disposable pad and quite possibly still exists. Disposable pads are used by spies of various states to hide especially important information... Such messages cannot be decrypted in the absence of a key written in the notebook, regardless of the computing power of the computer.

The most famous and commonly used ciphers are replacement ciphers. They are characterized by the fact that individual parts of the message (letters, words, ...) are replaced with any other letters, numbers, symbols, etc. In this case, the replacement is carried out so that later, using the encrypted message, it would be possible to unambiguously restore the transmitted message ...

For example, suppose a message in Russian is encrypted and each letter of the message is subject to replacement. Formally, in this case, the replacement cipher can be described as follows. For each letter a of the original alphabet, a set of symbols is constructed so that the sets do not intersect in pairs for and that is, any two different sets do not contain

identical elements. The set is called the set of designations for the letter a.

is the key of the replacement cipher. Knowing it, it is possible to carry out both encryption and decryption.

When encrypting, each letter a of an open message, starting with the first, is replaced by any character from the set.If a message contains several letters of it, then each of them is replaced by any character from. Due to this, using one key (1), you can get different versions of the encrypted message for the same open message. For example, if the key is a table

then the message "I am familiar with replacement ciphers" can be encrypted, for example, in any of the following three ways:

Since the sets do not intersect in pairs, then for each symbol of the encrypted message it is possible to uniquely determine which set it belongs to, and, therefore, which letter of the open message it replaces. Therefore, decryption is possible and an open message is uniquely determined.

It often consists of one element. For example, in Verne's novel A Journey to the Center of the Earth, a parchment containing a manuscript of runic characters falls into the hands of Professor Liedenbrock. Each set consists of one element. An element of each set is selected from a set of symbols of the form

In A. Conan Doyle's story "Dancing Men", each symbol depicts a dancing man in a variety of poses

At first glance, it seems that the more cunning the symbols, the more difficult it is to crack the message without the key. This is certainly not the case. If each character is uniquely associated with a letter or number, then it is easy to go to an encrypted message of letters or numbers. In Verne's novel A Journey to the Center of the Earth, each rune sign was replaced with a corresponding letter German language, which made it easier to recover an open message. From the point of view of cryptographers, the use of various complex symbols does not complicate the cipher. However, if the encrypted message consists of letters or numbers, then it is more convenient to open such a message.

Let's consider some examples of replacement ciphers. Let each set consist of one letter. For example,

Such a cipher is called a simple one-letter substitution cipher. It is convenient to encrypt and decrypt using the key (4): during encryption, each letter of the plaintext is replaced by the corresponding letter from the second line (a by). When decrypting, on the contrary, it is replaced by a, etc. When encrypting and decrypting, remember the second line in (4), that is, the key.

It is difficult to remember the arbitrary order of letters of the alphabet. Therefore, we have always tried to come up with some kind of rule by which one can simply restore the second line in (4).

One of the first ciphers known from history was the so-called Caesar cipher, for which the second line in (4) is a sequence written in alphabetical order, but not starting with the letter a:

In one of the tasks (task 4.4), the Caesar cipher is used. In this case, remembering the key is simple - you need to know the first letter of the second line (4) (the sequence of letters in the alphabet is assumed to be known). However, such a cipher has a major drawback. The number of different keys is equal to the number of letters in the alphabet. After going through these options, you can

unambiguously restore an open message, since with the correct choice of the key, a "meaningful" text will be obtained. In other cases, it usually results in "unreadable" text. Task 4.4 is designed for this. Although the phrase used in Latin, which schoolchildren do not know, many participants of the Olympiad were able to indicate an open message.

Another example of a replacement cipher is a slogan cipher. Here the memorization of the key sequence is based on a slogan - an easily memorized word. For example, let's choose the slogan word "textbook" and fill in the second row of the table according to the following rule: first, write out the slogan word, and then write out in alphabetical order the letters of the alphabet that are not included in the slogan word. The second line in (4) takes the form

In this case, the number of key variants is significantly greater than the number of alphabet letters.

The considered ciphers have one weakness. If a letter is often encountered in an open message, then the corresponding character or letter will often appear in the encrypted message. Therefore, when opening the replacement cipher, they usually try to match the most common characters of the encrypted message with the letters of the open message with the highest expected frequency of occurrence. If the encrypted message is large enough, then this path leads to success, even if you do not know the key.

In addition to the frequency of occurrence of letters, other circumstances may be used to help uncover the message. For example, the breakdown into words can be known, as in task 4.2, and punctuation marks are placed. Considering a small number possible options substitutions for prepositions and conjunctions, one can try to define part of the key. This problem essentially uses which vowels or consonants can be doubled: "nn", "ee", "ui", etc.

When analyzing an encrypted message, one should proceed from the fact that the number different options for a portion of the designated key is not that big if you are on the right track. Otherwise, either you will get a contradiction, or the number of key options will increase dramatically. Usually, from some point on, it becomes a matter of technique to determine the open message. So, in task 4.2, if you have defined "day and night", then further definition of the plain text is not difficult.

Generally speaking, we can say that cracking replacement ciphers is an art and it is rather difficult to formalize this process.

Cryptograms popular among schoolchildren (of the type considered in Problem 1.5) are essentially a replacement cipher with a key

cipher substitutions in which each digit is assigned a letter. In this case, the rules of arithmetic must be observed. These rules make it much easier to identify the plaintext, just as the rules of syntax and spelling in task 4.2 make it easier to find V. Vysotsky's quatrains.

Any features of the text that may be known to you are your helpers. For example, in Problem 5.2 it is directly stated that the text contains the expressions "zpt", "pt", as is often the case in real telegrams. And this tip is the way to solve the problem.

Encryption of even relatively small texts on one key for the considered replacement ciphers creates conditions for opening open messages. Therefore, they tried to improve such ciphers. One of the directions is the construction of different-valued replacement ciphers, when one or two characters are assigned to each letter. (The simplest example is the cipher defined in Problem 4.2.) For example,

If the encrypted message is written without spaces between characters, then there is an additional difficulty in breaking the encrypted message into separate characters and words.

Another direction in the creation of replacement ciphers is that the sets of cipher values ​​contain more than one element. Such ciphers are called multivalued replacement ciphers. They allow you to hide the true frequency of the letters of an open message, which makes it much more difficult to break these ciphers. The main difficulty that arises when using such ciphers is remembering the key. It is necessary to remember not one line, but for each letter of the alphabet a - the set of its cipher symbols. As a rule, the elements of the sets are numbers. Of fiction and movies about scouts, you know that during the Second World War, so-called book ciphers were often used. The set of cipher symbols for each letter is determined by all five-digit sets of numbers, in each of which the first two digits indicate the page number, the third digit is the line number, the fourth and fifth digits are the position number of this letter in the specified

line. Therefore, when capturing a scout, they always tried to find a book that could be used by him as a key.

We do not dwell here on more sophisticated methods of constructing replacement ciphers. The given examples are enough to appreciate the variety of such ciphers. But they all have a serious drawback - one key cannot encrypt long enough messages. Therefore, as a rule, replacement ciphers are used in combination with other ciphers. Most often with permutation ciphers, which you will read about in the next section.

In conclusion, following the heroes of the famous literary works, let's break open some replacement ciphers. Pay attention to what unexpected circumstances are involved in this. Indeed, cracking ciphers is an art.