Modern encryption methods. Encryption algorithms

The state encryption standard in Russia is an algorithm registered as GOST 28147-89. It is a block cipher, meaning it encrypts 64-bit blocks rather than individual characters. The algorithm provides 32 data conversion cycles with a 256-bit key, making it very reliable (has high cryptographic strength). On modern computers, breaking this cipher by brute force would take at least hundreds of years, making such an attack pointless. The US uses a similar block cipher, AES.

The RSA algorithm is popular on the Internet, named after the initial letters of the last names of its authors - R. Rivest, A. Shamir and L. Adleman. It is a public key algorithm whose strength is based on the properties of prime numbers. To crack it, you need to factor a very large number into simple factors. This problem can now be solved only by enumerating options. Since the number of options is huge, it takes many years of modern computers to crack the cipher.

To apply the algorithmRSA is required to construct public and private keys as follows.

1. Choose two large prime numbers, p and q.
2. Find their product n = p * q and the value f = (p - 1) (q - 1)
3. Choose the number e (1< e < k), которое не имеет общих делителей с f.
4. Find the number d that satisfies the condition d e = k f + 1 for some integer k
5. The value pair (e, n) is the RSA public key (it can be freely published) and the value pair (d, n) is the private key.

The transmitted message must first be presented as a sequence of numbers in the range from 0 to n - 1. For encryption, use the formula y = x e mod n, where x is the number of the original message, (e, n) is the public key, y is the number of the encrypted message , and the notation x e mod n denotes the remainder when x is divided by n. The message is decrypted using the formula x = y d mod n.
This means that anyone can encrypt a message (the public key is publicly known), but only someone who knows the secret exponent d can read it.
For better understanding, we will show the working of RSA algorithm with a simple example. EXAMPLE: Let's take p = 3 and q = 7, then we find n = p q = 21 and f = (p - 1) (q - 1) = 12. Let's choose e = 5, then the equality d e = kf + 1 holds, for example, for d = 17 (and k = 7). Thus, we received a public key (5, 21) and a private key (17, 21).

Let's encrypt the message “123” using the public key (5,21). We get

1 → 1 5 mod 21 = 1,
2 → 2 5 mod21 = 11 ,

3 → 3 5 mod 21 = 12,
that is, the encrypted message consists of numbers 1 ,11 and 12. Knowing the secret key (17, 21), you can decrypt it:

1 → 1 17 mod 21 = 1 ,

11 → 11 17 mod 21 = 2 ,
12 → 12 17 mod 21 = 3 .

We have received the original message.

Of course, you noticed that when encrypting and decrypting you have to calculate the remainder when dividing very large numbers (for example, 12 17) by n. It turns out that the number 12 17 itself does not need to be found in this case. It is enough to write one into a regular integer variable, for example x, and then perform the transformation x = 12*x mod 21 17 times. After this, the variable x will have the value 12 17 mod 21 = 3. Try to prove the correctness of this algorithm.
In order to decrypt a message, you need to know the secret exponent d. And for this, in turn, you need to find the factors p and q, such that n = p q. If n is large, this is a very difficult problem; solving it by searching through options on a modern computer will take hundreds of years. In 2009, a group of scientists from different countries, as a result of months of calculations on hundreds of computers, was able to decrypt a message encrypted with the RSA algorithm with a 768-bit key. Therefore, keys with a length of 1024 bits or more are now considered reliable. If a working quantum computer is built, breaking the RSA algorithm will be possible in a very short time.
When using symmetric ciphers, a problem always arises: how to transmit the key if the communication channel is unreliable? After all, having received the key, the enemy will be able to decrypt all further messages. For the RSA algorithm, this problem does not exist; the parties only need to exchange public keys, which can be shown to everyone.
The RSA algorithm has another advantage: it can be used to digitally sign messages. It serves to prove the authorship of documents, protect messages from forgery and intentional changes.

A digital signature is a set of characters that is obtained by encrypting a message using the sender's personal secret code.

The sender can send along with the original message the same message encrypted using his secret key (this is a digital signature). The recipient decrypts the digital signature using the public key. If it matches an unencrypted message, you can be sure that it was sent by the person who knows the secret code. If the message was modified during transmission, it will not match the decrypted digital signature. Since the message can be very long, to reduce the amount of data transmitted, most often not the entire message is encrypted, but only its hash code.
Many modern programs have the ability to encrypt data with a password. For example, office suites OpenOffice.org And Microsoft Office allow you to encrypt all created documents (you need to enter a password to view and/or change them). When creating an archive (for example, in archivers 7Zip, WinRAR, WinZip) you can also set a password, without which it is impossible to extract files.
For simple file encryption tasks, you can use a free program Encryptor(http://www.familytree.ru/ru/cipher.htm), versions of which exist for Linux And Windows. Programs TnieCrypt(http://www.truecrypt.org/), BestCrypt(www.jetico.com) and FreeOTFE(freeotfe.org) create logical container drives, the information on which is encrypted. Free software DiskCrypto r (diskcryptor.net) allows you to encrypt hard drive partitions and even create encrypted flash drives and CD/DVDs.
Program GnuPG(gnupg.org) is also free software. It supports symmetric and asymmetric ciphers, as well as various electronic digital signature algorithms.

Steganography

YouTube Video

When transmitting messages, you can not only use encryption, but also hide the very fact of transmitting the message.

Steganography is the science of covert transmission of information by hiding the very fact of transmitting information.

The ancient Greek historian Herodotus described, for example, this method: a message was written on the shaved head of a slave, and when his hair grew back, he went to the recipient, who shaved his head and read the message.
The classic method of steganography is sympathetic (invisible) ink, which appears only under certain conditions (heating, lighting, chemical developer). For example, text written in milk can be read when heated.
Now steganography deals with hiding information in text, graphic, sound and video files using software “injection” of the necessary messages into them.
The simplest way is to replace the least significant bits of the file in which the image is encoded. Moreover, this must be done in such a way that the difference between the original and the resulting drawings is imperceptible to humans. For example, if in a black and white picture (256 shades of gray), the brightness of each pixel is encoded with 8 bits. If you change 1-2 low-order bits of this code by “embedding” a text message there, a photograph that has no clear boundaries will hardly change. When replacing 1 bit, each byte of the original text message is stored in the least significant bits of the 8 pixel codes. For example, let the first 8 pixels of the picture have the following codes:

10101101	10010100	00101010	01010010
10101010	10101010	10101011	10101111

To encode the code of the letter “I” (110010002) in them, you need to change the low-order bits of the codes:

1010110 1	1001010 1	0010101 0	0101001 0
1010101 1	1010101 0	1010101 0	1010111 0

The recipient needs to take these low-order bits and “assemble” them together into one byte.
For sounds, other steganography methods are used, based on adding short conditional signals to the recording, which indicate 1 and 0 and are not perceived are concerned

a person by ear. It is also possible to replace one sound fragment with another.
To confirm authorship and protect copyright for images, videos and sound files, digital watermarks are used - information about the author embedded in the file. They get their name from old watermarks on money and documents. In order to establish the authorship of a photograph, it is enough to decipher the hidden information recorded using a watermark.
Sometimes digital watermarks are made visible (text or a company logo on a photo or on each frame of a video). Many sites that sell digital photos place visible watermarks on preview photos.

Control questions:

1. What encryption algorithm is adopted in Russia as a state standard?
2. What is a block encryption algorithm?
3. What type of RSA algorithm is it? What is its cryptographic strength based on?
4. What is a digital signature?
5. How can you use the RSA algorithm for a digital signature?
6. What is steganography?
7. What methods of steganography existed before the invention of computers?
8. How can I add text to an encoded image?
9. What are the methods of steganography for audio and video data based on?
10. What are digital watermarks? Why are they used?

Exercise:

1.View the lecture material and answer the test questions.
2. Follow the links and get acquainted with programs for encrypting files.
3. Encrypt any document in any office suite OpenOffice.org or Microsoft Office and send me .

Encryption algorithms are used to change sensitive information so that it cannot be read by unauthorized persons.

The first ciphers were used during the times of Ancient Rome, Ancient Egypt and Ancient Greece. One of the famous ciphers is Caesar cipher. This algorithm worked as follows: each letter has its own serial number in the alphabet, which shifted $3$ values ​​to the left. Today, such an algorithm does not provide the protection that it provided at the time of its use.

Today, a large number of encryption algorithms have been developed, including standard ones, which provide reliable protection of confidential information.

Encryption algorithms are divided into symmetrical(these include AES, CAST, GOST, DES, Blowfish) and asymmetrical(RSA, El-Gamal).

Symmetric algorithms

Note 1

Symmetric encryption algorithms use the same key to encrypt and decrypt information.

When transmitting encrypted information, you must also transmit the decryption key. The weak point of this method is the data transmission channel. If it is unprotected or can be tapped, the decryption key may become available to an attacker.

Asymmetric Algorithms

Note 2

Asymmetric algorithms use two keys—one for encryption and one for decryption.

Each user must have a pair of keys - a public key and a private key.

Encryption key

Definition 1

Encryption key is a random or specially created sequence of bits, which is a variable parameter of the encryption algorithm.

When encrypting the same data with the same algorithm, but using different keys, the results are different.

Encryption programs (WinRAR, Rohos, etc.) create a key from a password specified by the user.

The encryption key can be of different lengths, measured in bits. As the key length increases, the theoretical strength of the cipher increases. In practice this is not always the case.

Encryption algorithm strength

Note 3

The encryption algorithm is considered strong until proven otherwise.

Encryption algorithms

AES algorithm (Rijndael) is currently the US federal encryption standard. It was approved as a standard by the Ministry of Commerce in 2001. The standard is considered to be a cipher version with a block size of $128$ bits. Developed in $1997 in Belgium. Possible key sizes are $128, $192, and $256 bit keys.

Algorithm GOST 28147-8 is a Russian Federation standard for data encryption and data protection. Became an official standard in $1989. Developed in the $1970s. in the Main Directorate of the KGB of the USSR. Uses a key size of $256$ bits.

Blowfish algorithm uses a complex key generation scheme, which makes it much more difficult to attack the algorithm by brute force. Not suitable for use in systems where the key is frequently changed and when encrypting small data volumes. The algorithm is best used for systems in which there is a need to encrypt large amounts of data. Developed in $1993. Used key sizes from $32$ to $448$ bits.

DES algorithm was the US Federal encryption standard from 1977 to 2001. The federal standard was adopted in $1977, after the introduction of a new standard in $2001, it lost its status as a standard. Developed in $1972–1975. research laboratory of IBM Corporation. Uses a $56$ bit key.

CAST algorithm is in some way an analogue of the DES algorithm. Uses $128$ and $256$ bit keys.

Data encryption is extremely important to protect privacy. In this article, I will discuss the different types and methods of encryption that are used to protect data today.

Did you know?
Back in Roman times, encryption was used by Julius Caesar to make letters and messages unreadable to the enemy. It played an important role as a military tactic, especially during wars.

As the capabilities of the Internet continue to grow, more and more of our businesses are being conducted online. Among these, the most important are Internet banking, online payment, emails, exchange of private and official messages, etc., which involve the exchange of confidential data and information. If this data falls into the wrong hands, it can harm not only the individual user, but also the entire online business system.

To prevent this from happening, several network security measures have been taken to protect the transmission of personal data. Chief among these are the processes of encrypting and decrypting data, which is known as cryptography. There are three main encryption methods used in most systems today: hashing, symmetric and asymmetric encryption. In the following lines, I will talk about each of these encryption types in more detail.

Encryption types

Symmetric encryption

In symmetric encryption, normal readable data, known as plain text, is encrypted so that it becomes unreadable. This data scrambling is done using a key. Once the data is encrypted, it can be sent securely to the receiver. At the recipient, the encrypted data is decoded using the same key that was used for encoding.

Thus, it is clear that the key is the most important part of symmetric encryption. It must be hidden from outsiders, since anyone who has access to it will be able to decrypt private data. This is why this type of encryption is also known as a "secret key".

In modern systems, the key is usually a string of data that is derived from a strong password, or from a completely random source. It is fed into symmetric encryption software, which uses it to keep the input data secret. Data scrambling is achieved using a symmetric encryption algorithm, such as Data Encryption Standard (DES), Advanced Encryption Standard (AES), or International Data Encryption Algorithm (IDEA).

Restrictions

The weakest link in this type of encryption is the security of the key, both in terms of storage and transmission to the authenticated user. If a hacker is able to obtain this key, he can easily decrypt the encrypted data, defeating the entire purpose of encryption.

Another disadvantage is that the software that processes the data cannot work with encrypted data. Therefore, to be able to use this software, the data must first be decoded. If the software itself is compromised, then an attacker can easily obtain the data.

Asymmetric encryption

Asymmetric key encryption works similar to symmetric key in that it uses a key to encrypt the messages being transmitted. However, instead of using the same key, he uses a completely different one to decrypt this message.

The key used for encoding is available to any and all network users. As such it is known as a "public" key. On the other hand, the key used for decryption is kept secret and is intended for private use by the user himself. Hence, it is known as the "private" key. Asymmetric encryption is also known as public key encryption.

Since, with this method, the secret key needed to decrypt the message does not have to be transmitted every time, and it is usually known only to the user (receiver), the likelihood that a hacker will be able to decrypt the message is much lower.

Diffie-Hellman and RSA are examples of algorithms that use public key encryption.

Restrictions

Many hackers use man-in-the-middle as a form of attack to bypass this type of encryption. In asymmetric encryption, you are given a public key that is used to securely exchange data with another person or service. However, hackers use network deception to trick you into communicating with them while you are led to believe that you are on a secure line.

To better understand this type of hacking, consider two interacting parties, Sasha and Natasha, and a hacker, Sergei, with the intent to intercept their conversation. First, Sasha sends a message over the network intended for Natasha, asking for her public key. Sergei intercepts this message and obtains the public key associated with her and uses it to encrypt and send a false message to Natasha containing his public key instead of Sasha's.

Natasha, thinking that this message came from Sasha, now encrypts it with Sergei's public key, and sends it back. This message was again intercepted by Sergei, decrypted, modified (if desired), encrypted again using the public key that Sasha originally sent, and sent back to Sasha.

Thus, when Sasha receives this message, he has been led to believe that it came from Natasha and remains unaware of foul play.

Hashing

The hashing technique uses an algorithm known as a hash function to generate a special string from the given data, known as a hash. This hash has the following properties:

• the same data always produces the same hash.
• It is not possible to generate raw data from a hash alone.
• It is not practical to try different combinations of inputs to try to generate the same hash.

Thus, the main difference between hashing and the other two forms of data encryption is that once the data is encrypted (hashed), it cannot be retrieved back in its original form (decrypted). This fact ensures that even if a hacker gets his hands on the hash, it will be of no use to him, since he will not be able to decrypt the contents of the message.

Message Digest 5 (MD5) and Secure Hashing Algorithm (SHA) are two widely used hashing algorithms.

Restrictions

As mentioned earlier, it is almost impossible to decrypt data from a given hash. However, this is only true if strong hashing is implemented. In the case of a weak implementation of the hashing technique, using enough resources and brute force attacks, a persistent hacker can find data that matches the hash.

Combination of encryption methods

As discussed above, each of these three encryption methods suffers from some disadvantages. However, when a combination of these methods is used, they form a secure and highly effective encryption system.

Most often, private and public key techniques are combined and used together. The private key method allows for quick decryption, while the public key method offers a safer and more convenient way to transmit the secret key. This combination of methods is known as the "digital envelope". PGP email encryption software is based on the "digital envelope" technique.

Hashing is used as a means of checking the strength of a password. If the system stores a hash of the password instead of the password itself, it will be more secure, since even if a hacker gets his hands on this hash, he will not be able to understand (read) it. During verification, the system will check the hash of the incoming password, and see if the result matches what is stored. This way, the actual password will only be visible during brief moments when it needs to be changed or verified, greatly reducing the likelihood of it falling into the wrong hands.

Hashing is also used to authenticate data using a secret key. A hash is generated using the data and this key. Therefore, only the data and hash are visible, and the key itself is not transmitted. This way, if changes are made to either the data or the hash, they will be easily detected.

In conclusion, these techniques can be used to efficiently encode data into an unreadable format that can ensure that it remains secure. Most modern systems typically use a combination of these encryption methods along with strong algorithm implementations to improve security. In addition to security, these systems also provide many additional benefits, such as verifying the user's identity and ensuring that the data received cannot be tampered with.

Typically, new encryption algorithms are published for public consumption and studied in specialized research centers. The results of such studies are also published for public consumption.

Symmetric algorithms
Encryption algorithms are divided into two large classes: symmetric (AES, GOST, Blowfish, CAST, DES) and asymmetric (RSA, El-Gamal). Symmetric encryption algorithms use the same key to encrypt information and to decrypt it, while asymmetric algorithms use two keys - one for encryption and the other for decryption.

If encrypted information needs to be transferred to another location, then the decryption key must also be transferred. The weak point here is the data transmission channel - if it is not secure or is tapped, then the decryption key can fall into the hands of an attacker. Systems based on asymmetric algorithms do not have this drawback. Since each participant in such a system has a pair of keys: a Public and a Secret Key.

Encryption key
This is a random or specially created sequence of bits from a password, which is a variable parameter of the encryption algorithm.
If you encrypt the same data with the same algorithm, but with different keys, the results will also be different.

Typically, in encryption programs (WinRAR, Rohos, etc.), the key is created from a password specified by the user.

The encryption key comes in different lengths, which are usually measured in bits. As the key length increases, the theoretical strength of the cipher increases. In practice this is not always true.

In cryptography, the encryption mechanism is considered to be an unclassified quantity, and an attacker can have the full source code of the encryption algorithm as well as the ciphertext (Kerkhoff's rule). Another assumption that may occur is that an attacker may know part of the unencrypted (plain) text.

Strength of the encryption algorithm.
The encryption algorithm is considered strong until proven otherwise. Thus, if an encryption algorithm has been published, has existed for more than 5 years, and no serious vulnerabilities have been found for it, we can assume that its strength is suitable for protecting classified information.

Theoretical and practical durability.
In 1949 K.E. Shannon published the article "The Theory of Communications in Secret Systems." Shannon considered the strength of cryptographic systems as Practical and Theoretical. The conclusion regarding theoretical strength is still pessimistic: the length of the key should be equal to the length of the plaintext.
Therefore, Shannon also considered the issue of the practical strength of cryptographic systems. Is the system reliable if the attacker has limited time and computing resources to analyze the intercepted messages?

Typically, vulnerabilities are found in programs that encrypt data using some algorithm. In this case, programmers make an error in the program logic or in the cryptographic protocol, due to which, by studying how the program works (at a low level), they can ultimately gain access to secret information.

Hacking the encryption algorithm
A cryptosystem is considered to be compromised if the attacker can calculate the secret key and also perform a conversion algorithm equivalent to the original cryptoalgorithm. And so that this algorithm can be executed in real time.

Cryptology has a subsection - cryptanalysis, which studies the issues of hacking or forging encrypted messages. There are many ways and methods of cryptanalysis. The most popular is the method of directly searching through all possible values ​​of the encryption key (the so-called “brute force” method). The essence of this method is to search through all possible values ​​of the encryption key until the desired key is selected.

In practice, this means that the attacker must:

• Have at your disposal a cryptosystem (i.e. a program) and examples of encrypted messages.
• Understand the cryptographic protocol. In other words, how the program encrypts data.
• Develop and implement a Key search algorithm for this cryptosystem.

How to determine if the key is correct or not?
It all depends on the specific program and the implementation of the encryption protocol. Usually, if after decryption you get “garbage”, then this is an incorrect Key. And if the text is more or less meaningful (this can be checked), then the Key is correct.

Encryption algorithms
AES (Rijndael). Currently the US federal encryption standard. Approved as a standard by the Department of Commerce on December 4, 2001. The decision came into force from the moment of publication in the Federal Register (12/06/01). A cipher version with only a block size of 128 bits has been adopted as a standard.

GOST 28147-8. Russian Federation standard for data encryption and imitation protection. Initially it had a rating (OB or SS - it is not known exactly), then the rating was successively lowered, and by the time the algorithm was officially carried out through the USSR State Standard in 1989, it was removed. The algorithm remains chipboard (as you know, chipboard is not considered a fingerboard). In 1989 it became the official standard of the USSR, and later, after the collapse of the USSR, the federal standard of the Russian Federation.

Blowfish The complex scheme for generating key elements significantly complicates a brute-force attack on the algorithm, but makes it unsuitable for use in systems where the key changes frequently and small amounts of data are encrypted on each key. The algorithm is best suited for systems in which large amounts of data are encrypted using the same key.

DES US Federal Encryption Standard 1977-2001. Adopted as a US federal standard in 1977. In December 2001, it lost its status due to the introduction of a new standard.

CAST In a sense, an analogue of DES.

Solving the problem of determining a key by simply trying all possible options is generally impractical, except by using a very short key. Therefore, if a cryptanalyst wants to have a real chance of breaking a cipher, he must abandon brute force methods and use a different strategy. Statistical analysis using the frequency of occurrence of individual characters or combinations of characters can be used to solve many encryption schemes. To complicate the solution of the problem of breaking a cipher using statistical analysis, K. Shannon proposed two encryption concepts, called mixing (confusion) And diffusion (diffusion). Mixing is the use of substitution in which the relationship between the key and the ciphertext becomes as complex as possible. The application of this concept complicates the use of statistical analysis, which narrows the search area for the key, and decryption of even a very short cryptogram sequence requires searching through a large number of keys. In turn, diffusion is the application of such transformations that smooth out statistical differences between symbols and their combinations. As a result, the cryptanalyst's use of statistical analysis can lead to a positive result only if a sufficiently large segment of the ciphertext is intercepted.

The implementation of the goals proclaimed by these concepts is achieved through the repeated use of elementary encryption methods such as the method of substitution, permutation and scrambling.

10.4.1. Substitution method.

The simplest and longest-history is the substitution method, the essence of which is that a character in the source text is replaced by another, selected from this or another alphabet according to the rule specified by the encryption key. The location of the character in the text does not change. One of the earliest examples of the use of the staging method is Caesar cipher, which was used by Gaius Julius Caesar during his Gallic campaigns. In it, each letter of the plaintext was replaced by another, taken from the same alphabet, but cyclically shifted by a certain number of characters. The application of this encryption method is illustrated by the example presented in Fig. 10.3, in which the encryption transformation is based on the use of an alphabet with a cyclic shift of five positions.

Rice. 10.3, A )

Original text

Cryptogram

Rice. 10.3, b )

Obviously, the cipher key is the cyclic shift value. If you select a different key than the one shown in the example, the cipher will change.

Another example of a classic substitution scheme is an encryption system called Polybius square. In relation to the Russian alphabet, this scheme can be described as follows. Initially, the letters E and E are combined into one; I, J and b, b, the true meaning of which in the decrypted text is easily restored from the context. Then 30 characters of the alphabet are placed in a table of size 65, an example of filling which is shown in Fig. 10.4.

Rice. 10.4.

Encryption of any plaintext letter is carried out by specifying its address (i.e. row and column number or vice versa) in the table provided. So, for example, the word CAESAR is encrypted using a Polybius square as 52 21 23 11 41 61. It is absolutely clear that the code can be changed as a result of rearrangements of letters in the table. It should also be noted that those who attended a tour of the casemates of the Peter and Paul Fortress should remember the words of the guide about how the prisoners knocked among themselves. Obviously, their method of communication is completely covered by this encryption method.

An example of a polyalphabetic cipher is a scheme based on the so-called. progressive key of Trithemius. The basis of this encryption method is the table shown in Fig. 10.5, the lines of which are copies of the original alphabet cyclically shifted by one position. So, the first line has a zero shift, the second is cyclically shifted one position to the left, the third is two positions relative to the first line, etc.

Rice. 10.5.

One method of encryption using such a table is to use, instead of the first plaintext character, a character from the first cyclic shift of the original alphabet, located under the encrypted symbol, the second plaintext character from the string corresponding to the second cyclic shift, etc. An example of encrypting a message in a similar way is presented below (Fig. 10.6).

Plain text

Cipher text

Rice. 10.6.

Several interesting variants of ciphers based on the progressive Trithemius key are known. In one of them, called Viginère key method, a keyword is applied that specifies the lines to encrypt and decrypt each subsequent plaintext character: the first letter of the key specifies the row of the table in Fig. 10.5, with which the first character of the message is encrypted, the second letter of the key determines the table row that encrypts the second character of the plaintext, etc. Let the word “THROMB” be chosen as the key, then the message encrypted using the Viginère key can be presented as follows (Fig. 10.7). It is obvious that the key can be opened on the basis of statistical analysis of the ciphergram.

Plain text

Cipher text

Rice. 10.7.

A variation of this method is the so-called. automatic method (open) key Viginera, in which as forming key a single letter or word is used. This key provides the starting string or strings for encrypting the first or first few characters of the plaintext, similar to the example previously discussed. The plaintext characters are then used as the key to select the encryption string. In the example below, the letter “I” is used as the forming key (Fig. 10.8):

Plain text

Cipher text

Rice. 10.8.

As the example shows, the choice of encryption strings is completely determined by the content of the plaintext, i.e. Plaintext feedback is introduced into the encryption process.

Another variation of the Viginère method is automatic method (encrypted) Viginère key. It, like public key encryption, also uses a formative key and feedback. The difference is that after encryption using the generating key, each subsequent key symbol in the sequence is taken not from the plaintext, but from the resulting cryptogram. Below is an example explaining the principle of using this encryption method, in which, as before, the letter “I” is used as the forming key (Fig. 10.9):

Plain text

Cipher text

Rice. 10.9.

As can be seen from the above example, although each subsequent key symbol is determined by the preceding cryptogram symbol, it functionally depends on all previous symbols of the open message and the forming key. Consequently, there is an effect of dispersion of the statistical properties of the source text, which makes it difficult for a cryptanalyst to apply statistical analysis. The weak point of this method is that the ciphertext contains key characters.

By current standards, Viginère encryption is not considered secure, but its main contribution is the discovery that non-repeating key sequences can be generated using either the messages themselves or functions of the messages.

An option for implementing substitution technology that sufficiently implements the concept of mixing is the following example, based on a nonlinear transformation. The stream of information bits is pre-divided into blocks of length m, with each block represented by one of different symbols. Then a lot of
symbols is shuffled so that each symbol is replaced by another symbol from this set. After the shuffle operation, the symbol again turns into m–bit block. A device that implements the described algorithm when
, shown in Fig. 10.10, where the table specifies the rule for mixing the symbols of a set of
elements.

Rice. 10.10.

It is not difficult to show that there is
various substitutions or possible models associated with them. In connection with which, at large values m the cryptanalyst's task becomes computationally almost impossible. For example, when
the number of possible substitutions is defined as
, i.e. represents an astronomical number. Obviously, with such a value m this transformation using substitution block (substitution block, S-block) can be considered to have practical secrecy. However, its practical implementation is hardly possible, since it presupposes the existence
connections.

Let us now make sure that S– block shown in Fig. 10.10, indeed carries out a nonlinear transformation, for which we use the principle of superpositions: transformation
is linear if. Let's pretend that
, A
. Then, a, whence it follows that S– the block is nonlinear.

10.4.2. Rearrangement method.

At rearrangement(or transpositions) in accordance with the key, the order of the plaintext characters changes, but the meaning of the character is preserved. Permutation ciphers are block ciphers, i.e. the source text is first divided into blocks, in which the permutation specified by the key is carried out.

The simplest implementation of this encryption method can be the previously discussed interleaving algorithm, the essence of which is to split the stream of information symbols into blocks of length
, writing it row by row into a memory matrix of size lines and columns and reading by columns. This algorithm is illustrated by an example with
in Fig. 10.11, during which the phrase is recorded X= “Exam time will start soon.” Then the output of the permutation device will receive a cryptogram of the form

Rice. 10.11.

The considered variant of the permutation method can be complicated by the introduction of keys
And
, which determine the order of writing rows and reading columns, respectively, as illustrated by the table in Fig. 10.12. The result of the transformation will look like this

Rice. 10.12.

In Fig. Figure 10.13 shows an example of a binary permutation of data (linear operation), from which it can be seen that the data is simply shuffled or rearranged. The transformation is carried out using a permutation block ( permutation block, P-block). The shuffling technology implemented by this block has one major drawback: it is vulnerable to fraudulent messages. The fraudulent message is shown in Fig. 10.13 and consists of submitting one single unit to the input with the rest being zeros, which allows one to detect one of the internal connections. If a cryptanalyst were to analyze such a scheme using a plaintext attack, he would send a sequence of similar decoy messages, shifting a single 1 by one position with each transmission. As a result of such an attack, all input and output connections will be established. This example demonstrates why the security of a circuit should not depend on its architecture.

10.4.3. Gamma method.

P Many modern telecommunication systems that use scrambling operations demonstrate attempts to approach perfect secrecy. Under scrambling refers to the process of superimposing codes of plaintext characters with codes of a random sequence of numbers, which is also called gamma (named after the letter  of the Greek alphabet, used in mathematical formulas to denote a random process). Gumming refers to stream encryption methods, when successive plaintext characters are sequentially converted into ciphergram characters, which increases the conversion speed. So, for example, a stream of information bits arrives at one input of the modulo 2 adder shown in Fig. 10.14, while on the second there is a scrambling binary sequence
. Ideally consistency
must be a random sequence with equally probable values ​​of zeros and ones. Then the output encrypted stream
will be statistically independent of the information sequence
, which means that the sufficient condition of perfect secrecy will be satisfied. It's actually a complete coincidence
is not necessary because otherwise the recipient would not be able to recover the plaintext. Indeed, restoration of the plaintext on the receiving side should be carried out according to the rule
, so that exactly the same scrambling sequence and with the same phase should be generated on the receiving side. However, due to absolute randomness
this procedure becomes impossible.

In practice, pseudo-random sequences (PRS) have found widespread use as scrambling sequences, which can be reproduced on the receiving side. In stream encryption technology, a generator based on linear shift register with feedback (linear feedback shift register(LFSR)). A typical structure of a PSP generator, shown in Fig. 10.15, includes a shift register, which consists of – private delay elements or bits having possible states and storing some field element
during a clock interval, a feedback circuit that includes multipliers of elements (states) stored in bits by constants , and adders. The formation of the PSP is described by a recurrent relation of the form

where are the coefficients
are fixed constants belonging to
, according to which each next element of the sequence is calculated based on n previous ones.

Since the number of different register states is finite (at most ) a situation is inevitable when, after a certain number of cycles, the state repeats itself in the form of one of the previously occurring ones. However, starting with some initial loading, i.e. fixed state, diagram in Fig. 10.15 will form only a single sequence determined by the mentioned recursion. Consequently, repetition of the register state leads to repetition of all subsequent generated symbols, meaning that any PRP is periodic. Moreover, in the case of a zero state of the register (the presence of zeros in all bits), an infinite degenerate sequence will always be formed, consisting of only zeros. Obviously, such a case is absolutely hopeless, so the zero state of the register must be excluded. As a result, no more remains
permissible register states, which limits the maximum possible period of the sequence to a value not greater than
.

Example 10.4.1. In Fig. 10.16, a, the implementation of a generator based on a shift register with linear feedback is presented, generating a binary pseudo-random sequence of the period
. Note that in the case of binary PSP, multiplying by one is equivalent to simply connecting the bit output to the adder. Rice. 10.16, b, illustrates successive register contents (bit states), as well as the state of the feedback output (feedback point in the diagram) when clock pulses are applied. The sequence is read in the form of successive states of the extreme n equal rank. Reading the states of other bits results in copies of the same sequence, shifted by one or two clock cycles.

At first glance, it can be assumed that the use of long-term memory bandwidth can provide fairly high security. For example, in the cellular mobile communication system of the IS-95 standard, the PSP of the period is used as a scrambling
among elementary chips. At a chip speed of 1.228810 6 symbols/sec, its period is:

Therefore, it can be assumed that since the sequence is not repeated over such a long period, it can be considered random and provide perfect secrecy. However, there is a fundamental difference between a pseudo-random sequence and a truly random sequence: a pseudo-random sequence is formed according to some algorithm. Thus, if the algorithm is known, then the sequence itself will be known. As a result of this feature, an encryption scheme using a linear feedback shift register is vulnerable to a known plaintext attack.

To determine the feedback taps, the initial state of the register and the entire sequence, the cryptanalyst only needs to have
plaintext bits and their corresponding ciphertext. Obviously, the value 2 n significantly less than the PSP period, equal to
. Let's illustrate the mentioned vulnerability with an example.

Example 10.4.2. Let the period PSP be used as a scrambling
, generated using recursion of the form

at the initial state of the register 0001. As a result, the sequence will be generated. Let us assume that a cryptanalyst, who knows nothing about the feedback structure of the PRP generator, managed to obtain
bit of the cryptogram and its open equivalent:

Then, by adding both sequences modulo 2, the cryptanalyst has at his disposal a fragment of the scrambling sequence, which shows the state of the shift register at different times. So, for example, the first four bits of the key sequence correspond to the state of the register at some point in time . If we now shift the window that allocates the quadruple bits one position to the right, then the states of the shift register will be obtained at successive moments in time
. Considering the linear structure of the feedback circuit, we can write that

Where the PSP symbol, which is generated by the feedback circuit and supplied to the input of the first digit of the register, and
determines the absence or presence i-th connection between the output of the shift register bit and the adder, i.e. feedback circuit.

By analyzing the states of the shift register at four consecutive moments in time, we can create the following system of four equations with four unknowns:

Solving this system of equations gives the following coefficient values:

Thus, having determined the feedback connection diagram of the linear register and knowing its state at the moment of time , the cryptanalyst is able to reproduce the scrambling sequence at an arbitrary point in time, and therefore is able to decrypt the intercepted cryptogram.

Generalizing the considered example to the case of an arbitrary memory shift register n, the original equation can be represented as

,

and the system of equations is written in the following matrix form

,

Where
, A
.

It can be shown that the matrix columns are linearly independent and, therefore, there is an inverse matrix
. Hence

.

Matrix inversion requires order operations, so when
we have
, that for a computer with operating speed, one operation in 1 μs will require 1 second to invert the matrix. Obviously, the weakness of the shift register is due to the linearity of the feedback.

To make it more difficult for analysts to calculate PSP elements when comparing plaintext and ciphertext fragments, feedback on the output and ciphertext is used. In Fig. 10.17 explains the principle of introducing ciphertext feedback.

Rice. 10.17. Stream encryption with feedback.

First, a preamble is transmitted, which contains information about the parameters of the generated PSP, including the value of the initial phase Z 00. For each n the generated ciphergram symbols are calculated and a new phase value is set in the generator
. Feedback makes the gamma method sensitive to cryptogram distortions. Thus, due to interference in the communication channel, some received symbols may be distorted, which will lead to the calculation of an erroneous PRP phase value and complicate further decoding, but after receiving n correct ciphertext characters, the system is restored. At the same time, such distortion can be explained by an attempt by an attacker to impose false data.