Cryptography lessons. Modern block ciphers. Modern encryption algorithms

As you remember, the shift, substitution, permutation cipher and Vernam cipher apply an operation to each specific character of the text. We need to shift - we shift the symbol, apply the key - apply it to the symbol, then to the next symbol and so on until we encrypt all the symbols plaintext. This encryption method is called stream encryption - we encrypt each character separately. Another approach is to split the original plaintext into groups of several characters (blocks) and perform encryption operations on each block. This is a block encryption method.

To make the difference between block and stream ciphers clearer, let's give an example: simple cipher replacements.

Stream encryption

Let's encrypt the word CIPHER with a replacement stream cipher:

We encrypted each character and obtained a ciphertext. As easy as pie.

BLOCK ENCRYPTION

Let's encrypt the word AVADAKEDAVRA. Since the cipher is a block one, we will divide the plaintext into blocks of four characters: AVAD | AKED | AVRA (in practice, text blocks consist of 64-256 bits). For each block we will come up with our own replacement table:

Now we encrypt each of the blocks with the corresponding alphabet:
It turned out a little better than with the in-line approach, if we talk about durability. After all, we learned to decipher the usual substitution cipher with one left hand. And with such a block approach, the attacker will have to rack his brains before he can select the block length and then apply cryptanalysis for replacement ciphers for each block.

FEISTEL NETWORK

Now we are ready to move on to a very important topic that opens the door to a vast world modern systems encryption. The Feistel network is a block encryption method developed by Horst Feistel at the IBM laboratory in 1971. Today the Feistel network underlies large quantity cryptographic protocols. Let’s try to figure out “on the fingers” what it is.

The Feistel network operates on blocks of plaintext, so we will look at the mechanism of its operation on one of the blocks. The actions for the remaining blocks will be similar.

• The block is divided into two equal parts - left (L) and right (R).
• After partitioning, the left subblock is modified by a function f using the key K: x = f(L, K). As a function, you can imagine any transformation you like - for example, the good old shift cipher with key K.
• The resulting subblock is added modulo 2 with the right subblock R, which was not used before: x=x+R
• Next, the resulting parts are swapped and glued together.

As you can see, everything is quite simple. To understand how this works, look at the diagram:

This arrangement is called a Feistel cell. The Feistel network itself consists of several cells. The subblocks obtained at the output of the first cell go to the input of the second cell, the resulting subblocks from the second cell go to the input of the third cell, and so on, depending on the number of rounds of the Feistel network. In each such round, a predetermined round key is used. Most often, round keys are derived from the main key secret key K. When all the rounds have been completed, the subblocks of text are glued together, and a normal ciphertext is obtained.

Now let's look at the operation of the Feistel network using an example. Let's take the word AVADAKEDAVRA and divide it into two blocks of six characters - AVADAK | EDAVRA. For the function we take the shift cipher by the number of positions determined by the round key. Let the secret key K = . As round keys, we take K = 1, K = 2. For addition modulo 2, we convert the text into binary code according to the telegraph alphabet, which hardly anyone else uses at all.

Here's what happened:

Now let’s run the first block through the Feistel network in two rounds:

Try to encrypt the second block yourself, I got MOSSTR.

Decryption is carried out in exactly the same way: the ciphertext is divided into blocks and then subblocks, the left subblock enters the function, is added modulo 2 with the right one, and then the subblocks are swapped. The difference is that round keys are supplied in reverse order, that is, in our case, in the first round we will use the key K = 2, and then in the second round K = 1.

Research on the Feistel network has shown that with independent round keys and a crypto-resistant pseudo-random function f, three rounds of the Feistel network will be enough for the ciphertext to be pseudo-random. This suggests that ciphers based on the Feistel network are currently quite secure.

GOST 28147-89 (MAGMA)

Almost everything is already in the arsenal necessary concepts, so we are ready to move on to the first important topic of domestic cryptography - GOST 28147-89. It is worth saying that only the lazy have not written about this standard, so I will try for the millionth and first time to briefly and without a cloud of formulas outline the essence of the encryption modes of the great and terrible Magma. If you decide to read the standard itself, then you should stock up on time, energy, patience and food, because, as you know, writing standards in human language is strictly prohibited.

Main characteristics: key 256 bits, block 64 bits.

Before analyzing Magma, you need to learn a new concept - substitution tables, or S-boxes. This is the same type of table as the table in the substitution cipher. Designed to replace subblock symbols with symbols recorded in the table. Don't think that the S-box is random numbers generated by the rand() function. S-boxes are the result of thoughtfully generated sequences, because the cryptographic strength of the entire cipher rests on them.

GOST 28147 describes its replacement tables very sparingly. It only says that they are an additional secret element (along with the secret key) and “are supplied in in the prescribed manner" Nothing else. Since the adoption of GOST 28147, the scientific and technical uncertainty associated with the choice of S-boxes has given rise to rumors and speculation. There was talk about secret criteria known only to the developers of GOST. Naturally, this uncertainty reduced confidence in the cryptosystem.

This shortcoming provided excellent grounds for criticism of the standard. French cryptographer Nicolas Courtois published several articles containing a number of controversial provisions regarding the strength of GOST. Courtois believes that the Russian standard is easy to attack and cannot be considered international. However, Courtois performs his analysis for S-boxes other than the actual ones, so you should not rely on his opinion.

Now let's see what they came up with within the walls of the gloomy Lubyanka.

Easy replacement mode

In simple replacement mode for 32 rounds, according to the standard, we need 32 round keys. To generate round keys, the original 256-bit key is divided into eight 32-bit blocks: K1...K8. Keys K9...K24 are a cyclic repetition of keys K1...K8. Keys K25…K32 are keys K8…K1.

1. Each 64-bit block is divided into two subblocks - Ai and Bi.
2. The left subblock Ai is added modulo 232 with the round key K1: Ai+1 = Ai + Ki mod 232.
3. The left subblock passes through the S-box.
4. The bits of the left subblock are shifted by 11 positions (cyclic shift).
5. The left subblock adds up to the right one modulo 2: A = A ⊕ B . iii
6. The right subblock accepts original meaning left subblock: Bi+1 = Ai.
7. The subblocks are swapped.

Just an example of one round. Key 256 bits:

Then the round keys

How to use this S-box? Very simple! If the input of the S-box is 0, then the output will be 1 (take the 0th symbol of the S-box), if 4, then the output will be 5 (take the 4th symbol), if the input is 7, then the output will be 4, and so on.

Plain text:

Divided into two 32-bit blocks of high and low bits:

The example, of course, turned out to be wild, because GOST is still not such a standard that everyone can go through it with their own hands.

The simple replacement mode is too simple and has significant disadvantages:

• one error in an encrypted block corrupts all the bits of that block;
• when encrypting identical blocks of plaintext, one gets identical blocks ciphertext, which can provide certain information to a cryptanalyst.

Thus, it is advisable to use GOST 28147-89 in simple replacement mode only for encrypting key data.

GAMING MODE

This mode does not have the disadvantages of the simple replacement mode. The gamma mode is so called because it uses gamma, a pseudo-random sequence that is added modulo 2 to the plaintext in each round. Gamma is formed from the synchronization message S - a pseudo-random sequence that changes with each iteration and is encrypted in the simple replacement mode, after which it turns into gamma and is superimposed on the plaintext.

And now everything is in order.

Steps 3–5 are repeated for each block. All these manipulations can be seen in the diagram.

Decryption is performed in the same way; instead of a plaintext block, a ciphertext block is supplied.

Gamma mode with feedback

Let's get more complicated. The algorithm is similar to the gamma mode, but the gamma is formed based on the previous block of encrypted data, so the result of encrypting the current block also depends on the previous blocks. 1. Synchronization message S - 64-bit pseudo-random sequence.

2. S is encrypted in simple replacement mode.
3. The plaintext is added modulo 2 to the resulting gamma.
4. The resulting ciphertext is sent as a synchronization message for the next block, and is also sent to the output. You can see what it looks like in the diagram.

Simulated insert mode

In this mode, a simulated insert is generated - an additional block of a fixed length, depending on the source text and keys. Such a small block is needed to confirm that no distortions were accidentally or intentionally introduced into the ciphertext - that is, to check the integrity. This mode works like this:

1. A block of plaintext goes through 16 rounds in simple replacement mode.
2. Another plaintext block is added to the resulting block modulo 2.
3. The sum goes through another 16 rounds in simple replacement mode.
4. The next block of plaintext is added and again easy replacement and so on until there are no more plaintext blocks.

To verify, the recipient, after decrypting the text, carries out a procedure similar to that described. If the result does not match the transmitted imitative insert, all corresponding M blocks are considered false.

GOST 34.12-2015 (GRASSHOPPER)

Many consider GOST 28147-89 to be obsolete and not robust enough compared to foreign algorithms. To replace it, domestic cryptographers released a new encryption standard. They say that this happened either due to the large number of attacks on the old GOST, or because this block length is already outdated and too small for modern data sets. The real reasons no one advertises. Of course, there were some changes to the main characteristics.

Main characteristics: key 256 bits, block 128 bits.

It’s also worth saying that in the new standard, S-boxes are fixed and thoughtful, so there’s no need to invent your own miraculous random substitutions. The new GOST has many more encryption modes:
simple replacement mode (Electronic Codebook, ECB);
gamma mode (Counter, CTR);
gamma mode with output feedback (Output Feedback, OFB);
simple replacement mode with engagement (Cipher Block Chaining, SBC);
gamma mode with ciphertext feedback (Cipher Feedback, CFB);
simulation insert generation mode (Message Authentication Code algorithm).

Let's look at the new modes.

Easy replacement mode with engagement

As was seen in the previous standard, the simple replacement mode is the weakest of the modes, so in the new standard it now protrudes with engagement and has become not so simple at all.

1. An initialization vector sounds scary, but in reality it's just a sequence of bits entering the input.
2. The vector is split into two parts - L and R, one of which is added modulo 2 with the plaintext, and the other becomes half of the initialization vector for the next block.
3. The sum of the plaintext and a piece of the initialization vector is passed through a simple substitution cipher.
4. The resulting ciphertext blocks are glued together.

Once you look at the diagram, everything immediately becomes clear.

Of course, the initialization vector is not that simple: it goes through a series of linear transformations (using a linear shift register) before it begins encrypting a new block. But to get acquainted with the cipher, it is enough to imagine such a scheme. Decryption in this mode is also not entirely obvious, so it’s better to look at the diagram.

For the pros - Encryptions. Among domestic developments is the cryptoprovider CryptoPro CSP.

A few words about the strength of encryption modes. Many foreign cryptographers have tried to raise their hand against our standard, but at the moment there is not a single attack known that can be implemented at the current technological level of development. Among programmers this standard for a long time was not very popular, since it is difficult to understand the operating algorithm from its text, and there are not enough clearer descriptions. But now there are already plenty of implementations in many programming languages. So now the use of GOST is quite possible, and in many respects it surpasses foreign standards. In the end, where is the patriotism?!

Data encryption is extremely important to protect privacy. In this article I will talk about various types and encryption methods 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 could cause harm not only individual user, but also all online system business.

To prevent this from happening, some network measures security 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 following lines, I'll 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.

So it is clear that the key is the most important part 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 encrypt input data. Data scrambling is achieved using symmetric algorithm encryption, 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 similarly symmetric key, is that it uses a key to encode transmitted messages. 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's not worth trying different combinations input data 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 sufficient resources and attacks brute force, a persistent hacker may be able to 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 reliable and highly effective system encryption.

Most often, private and public key techniques are combined and used together. The private key method allows for faster decryption, while the public key method offers a more secure and more convenient way to transfer the secret key. This combination of methods is known as the "digital envelope". Encryption program Email PGP 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 implementation algorithms 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.

Sergey Panasenko,
Head of the software development department at Ankad,
[email protected]

Basic Concepts

The process of converting open data into encrypted data and vice versa is usually called encryption, and the two components of this process are called encryption and decryption, respectively. Mathematically, this transformation is represented by the following dependencies that describe actions with the original information:

C = Ek1(M)

M" = Dk2(C),

where M (message) - open information(in the literature on information security it is often called " original text");
C (cipher text) - the ciphertext (or cryptogram) obtained as a result of encryption;
E (encryption) - an encryption function that performs cryptographic transformations on the source text;
k1 (key) - parameter of function E, called the encryption key;
M" - information obtained as a result of decryption;
D (decryption) - decryption function that performs inverse cryptographic transformations on the ciphertext;
k2 is the key used to decrypt information.

The concept of “key” in the GOST 28147-89 standard (symmetric encryption algorithm) is defined as follows: “a specific secret state of some parameters of the cryptographic transformation algorithm, ensuring the selection of one transformation from a set of possible ones for of this algorithm transformations". In other words, the key is a unique element with which you can change the results of the encryption algorithm: the same source text when used different keys will be encrypted differently.

In order for the decryption result to coincide with original message(i.e., for M" = M), two conditions must be simultaneously satisfied. First, the decryption function D must correspond to the encryption function E. Second, the decryption key k2 must correspond to the encryption key k1.

If a cryptographically strong encryption algorithm was used for encryption, then in the absence of the correct key k2 it is impossible to obtain M" = M. Cryptographic strength is the main characteristic of encryption algorithms and primarily indicates the degree of complexity of obtaining the original text from an encrypted text without a key k2.

Encryption algorithms can be divided into two categories: symmetric and asymmetric encryption. For the former, the ratio of encryption and decryption keys is defined as k1 = k2 = k (i.e., functions E and D use the same encryption key). With asymmetric encryption, the encryption key k1 is calculated from the key k2 in such a way that the reverse transformation is impossible, for example, using the formula k1 = ak2 mod p (a and p are the parameters of the algorithm used).

Symmetric encryption

Symmetric encryption algorithms date back to ancient times: it was this method of hiding information that was used by the Roman emperor Gaius Julius Caesar in the 1st century BC. e., and the algorithm he invented is known as the “Caesar cryptosystem.”

Currently, the best known symmetric encryption algorithm is DES (Data Encryption Standard), developed in 1977. Until recently, it was a "US standard" because the government of that country recommended its use for implementation various systems data encryption. Despite the fact that DES was originally planned to be used for no more than 10-15 years, attempts to replace it began only in 1997.

We will not cover DES in detail (almost all books on the list of additional materials have it detailed description), and let's turn to more modern encryption algorithms. It is only worth noting that the main reason for changing the encryption standard is its relatively weak cryptographic strength, the reason for which is that the DES key length is only 56 significant bits. It is known that any crypto-strong algorithm can be cracked by trying all possible encryption keys (the so-called brute force method - brute force attack). It is easy to calculate that a cluster of 1 million processors, each of which calculates 1 million keys per second, will check 256 variants of DES keys in almost 20 hours. And since, by today’s standards, such computing power are quite real, it is clear that the 56-bit key is too short and DES algorithm needs to be replaced with a stronger one.

Today, two modern strong encryption algorithms are increasingly used: the domestic standard GOST 28147-89 and the new US crypto standard - AES (Advanced Encryption Standard).

Standard GOST 28147-89

The algorithm defined by GOST 28147-89 (Fig. 1) has an encryption key length of 256 bits. It encrypts information in blocks of 64 bits (such algorithms are called block algorithms), which are then divided into two subblocks of 32 bits (N1 and N2). Subblock N1 is being processed in a certain way, after which its value is added to the value of subblock N2 (the addition is performed modulo 2, i.e. the logical operation XOR is applied - “exclusive or”), and then the subblocks are swapped. This transformation is performed a certain number of times (“rounds”): 16 or 32, depending on the mode of operation of the algorithm. In each round, two operations are performed.

The first is keying. The contents of subblock N1 are added modulo 2 with the 32-bit part of the key Kx. Full key encryption is represented as a concatenation of 32-bit subkeys: K0, K1, K2, K3, K4, K5, K6, K7. During the encryption process, one of these subkeys is used, depending on the round number and the operating mode of the algorithm.

The second operation is table replacement. After keying, subblock N1 is divided into 8 parts of 4 bits, the value of each of which is replaced in accordance with the replacement table for this part of the subblock. The subblock is then bit-rotated to the left by 11 bits.

Table substitutions(Substitution box - S-box) are often used in modern encryption algorithms, so it is worth explaining how such an operation is organized. The output values ​​of the blocks are recorded in the table. A data block of a certain dimension (in our case - 4-bit) has its own numerical representation

, which specifies the number of the output value. For example, if the S-box looks like 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 and the 4-bit block “0100” came to the input (value 4), then, according to the table, the output value will be 15, i.e. “1111” (0 a 4, 1 a 11, 2 a 2 ...). The algorithm, defined by GOST 28147-89, provides four operating modes: simple replacement, gamming, gamming with feedback

and generation of imitation prefixes. They use the same encryption transformation described above, but since the purpose of the modes is different, this transformation is carried out differently in each of them. In mode easy replacement

To encrypt each 64-bit block of information, the 32 rounds described above are performed. In this case, 32-bit subkeys are used in the following sequence:

K7, K6, K5, K4, K3, K2, K1, K0 - in rounds 25 to 32.

Decoding in this mode is carried out in exactly the same way, but with a slightly different sequence of using subkeys:

K0, K1, K2, K3, K4, K5, K6, K7 - in rounds 1 to 8;

K7, K6, K5, K4, K3, K2, K1, K0, K7, K6, etc. - in rounds 9 to 32.

All blocks are encrypted independently of each other, i.e., the encryption result of each block depends only on its contents (the corresponding block of the original text). If there are several identical blocks of original (plain) text, the corresponding ciphertext blocks will also be identical, which gives additional useful information for a cryptanalyst trying to break a cipher. Therefore, this mode is used mainly for encrypting the encryption keys themselves (multi-key schemes are very often implemented, in which, for a number of reasons, the keys are encrypted on each other). Two other operating modes are intended for encrypting the information itself - gamma and gamma with feedback.

IN gamma mode Each plaintext block is added bit by bit modulo 2 to a 64-bit cipher gamma block. The gamma cipher is a special sequence that is obtained as a result of certain operations with registers N1 and N2 (see Fig. 1).

1. Their initial filling is written to registers N1 and N2 - a 64-bit value called a synchronization message.

2. The contents of registers N1 and N2 are encrypted (in in this case- sync messages) in simple replacement mode.

3. The contents of register N1 are added modulo (232 - 1) with the constant C1 = 224 + 216 + 28 + 24, and the result of the addition is written to register N1.

4. The contents of register N2 are added modulo 232 with the constant C2 = 224 + 216 + 28 + 1, and the result of the addition is written to register N2.

5. The contents of registers N1 and N2 are output as a 64-bit gamma block of the cipher (in this case, N1 and N2 form the first gamma block).

If the next gamma block is needed (i.e., encryption or decryption needs to continue), it returns to step 2.

For decryption, gamma is generated in a similar manner, and then the ciphertext and gamma bits are again XORed. Since this operation is reversible, in the case of a correctly developed scale, the original text (table) is obtained.

Encryption and decryption in gamma mode

To develop the cipher needed to decrypt the gamma, the user decrypting the cryptogram must have the same key and the same value of the synchronization message that were used when encrypting the information. Otherwise, it will not be possible to obtain the original text from the encrypted one.

In most implementations of the GOST 28147-89 algorithm, the synchronization message is not secret, however, there are systems where the synchronization message is the same secret element as the encryption key. For such systems, the effective key length of the algorithm (256 bits) is increased by another 64 bits of the secret synchronization message, which can also be considered as a key element.

In the feedback gamma mode, to fill the N1 and N2 registers, starting from the 2nd block, it is not the previous gamma block that is used, but the result of encrypting the previous plaintext block (Fig. 2). The first block in this mode is generated completely similarly to the previous one.

Rice. 2. Development of a cipher gamma in the gamma mode with feedback.

Considering the mode generation of imitation prefixes, the concept of the subject of generation should be defined. Imitation prefix is ​​a cryptographic check sum, calculated using the encryption key and designed to verify the integrity of messages. When generating imitation prefixes, the following are performed: following operations: the first 64-bit block of information for which the imitation prefix is ​​calculated is written to registers N1 and N2 and encrypted in the reduced simple replacement mode (the first 16 rounds out of 32 are performed). The resulting result is summed modulo 2 with the next block of information and the result is stored in N1 and N2.

The cycle repeats until last block information. The resulting 64-bit contents of the N1 and N2 registers or part of them as a result of these transformations is called the imitation prefix. The size of the imitation prefix is ​​selected based on the required reliability of messages: with the length of the imitation prefix r bits, the probability that a change in the message will go unnoticed is equal to 2-r. Most often, a 32-bit imitation prefix is ​​used, i.e., half the contents of the registers. This is enough, since, like any checksum, the imitation attachment is intended primarily to protect against accidental distortion of information. To protect against intentional modification of data, other cryptographic methods- primarily an electronic digital signature.

When exchanging information, the imitation prefix serves as a kind of additional means control. It is calculated for the plaintext when any information is encrypted and is sent along with the ciphertext. After decryption, a new value of the imitation prefix is ​​calculated and compared with the sent one. If the values ​​do not match, it means that the ciphertext was corrupted during transmission or incorrect keys were used during decryption. The imitation prefix is ​​especially useful for checking the correctness of decryption key information when using multi-key schemes.

The GOST 28147-89 algorithm is considered a very strong algorithm - currently no more has been proposed for its disclosure effective methods than the "brute force" method mentioned above. Its high security is achieved primarily due to the large key length - 256 bits. When using a secret sync message, the effective key length increases to 320 bits, and encrypting the replacement table adds additional bits. In addition, cryptographic strength depends on the number of transformation rounds, which according to GOST 28147-89 should be 32 (the full effect of input data dispersion is achieved after 8 rounds).

AES standard

Unlike the GOST 28147-89 algorithm, which remained secret for a long time, American standard AES encryption, intended to replace DES, was selected through an open competition where all interested organizations and individuals could study and comment on the candidate algorithms.

A competition to replace DES was announced in 1997. National Institute US standards and technologies (NIST - National Institute of Standards and Technology). 15 candidate algorithms were submitted to the competition, developed by both well-known organizations in the field of cryptography (RSA Security, Counterpane, etc.) and individuals. The results of the competition were announced in October 2000: the winner was the Rijndael algorithm, developed by two cryptographers from Belgium, Vincent Rijmen and Joan Daemen.

The Rijndael algorithm is not similar to most known symmetric encryption algorithms, the structure of which is called the “Feistel network” and is similar to the Russian GOST 28147-89. The peculiarity of the Feistel network is that the input value is divided into two or more subblocks, part of which in each round is processed according to a certain law, after which it is superimposed on unprocessed subblocks (see Fig. 1).

Unlike the domestic encryption standard, the Rijndael algorithm represents a data block in the form of a two-dimensional byte array of size 4X4, 4X6 or 4X8 (the use of several fixed sizes of the encrypted block of information is allowed). All operations are performed on individual bytes of the array, as well as on independent columns and rows.

The Rijndael algorithm performs four transformations: BS (ByteSub) - table replacement of each byte of the array (Fig. 3); SR (ShiftRow) - shift of array rows (Fig. 4). With this operation, the first line remains unchanged, and the rest are cyclically shifted byte-by-byte to the left by a fixed number of bytes, depending on the size of the array. For example, for a 4X4 array, lines 2, 3 and 4 are shifted by 1, 2 and 3 bytes respectively. Next comes MC (MixColumn) - an operation on independent array columns (Fig. 5), when each column is multiplied by a fixed matrix c(x) according to a certain rule. And finally, AK (AddRoundKey) - adding a key. Each bit of the array is added modulo 2 with the corresponding bit of the round key, which, in turn, is calculated in a certain way from the encryption key (Fig. 6).

Rice. 3. Operation BS.

Rice. 4. Operation SR.

Rice. 5. Operation MC.

The number of encryption rounds (R) in the Rijndael algorithm is variable (10, 12 or 14 rounds) and depends on the block size and the encryption key (there are also several fixed sizes for the key).

Decryption is performed using the following reverse operations. A table inversion and table replacement are performed on an inverse table (relative to the one used during encryption). The inverse operation to SR is to rotate rows to the right rather than to the left. The inverse operation for MC is multiplication using the same rules by another matrix d(x) satisfying the condition: c(x) * d(x) = 1. Adding the key AK is the inverse of itself, since it only uses the XOR operation. These reverse operations are used during decryption in the reverse sequence to that used during encryption.

Rijndael has become the new standard for data encryption due to a number of advantages over other algorithms. First of all, it provides high speed encryption on all platforms: both in software and hardware implementation. It is distinguished incomparably best opportunities parallelization of calculations in comparison with other algorithms submitted to the competition. In addition, the resource requirements for its operation are minimal, which is important when used in devices with limited computing capabilities.

The only disadvantage of the algorithm can be considered its inherent unconventional scheme. The fact is that the properties of algorithms based on the Feistel network have been well researched, and Rijndael, in contrast, may contain hidden vulnerabilities that can only be discovered after some time has passed since its widespread use began.

Asymmetric encryption

Asymmetric encryption algorithms, as already noted, use two keys: k1 - the encryption key, or public, and k2 - the decryption key, or secret. Public key calculated from the secret: k1 = f(k2).

Asymmetric encryption algorithms are based on the use of one-way functions. According to the definition, a function y = f(x) is unidirectional if: it is easy to calculate for all possible options x and for most possible values ​​of y, it is quite difficult to calculate a value of x for which y = f(x).

An example of a one-way function is the multiplication of two large numbers: N = P*Q. In itself, such multiplication is a simple operation. However, the inverse function (decomposition of N into two large factors), called factorization, according to modern time estimates, is quite complex math problem. For example, factorization N with a dimension of 664 bits at P ? Q will require approximately 1023 operations, and to inversely calculate x for the modular exponent y = ax mod p with known a, p and y (with the same dimensions of a and p) you need to perform approximately 1026 operations. The last example given is called the Discrete Logarithm Problem (DLP), and this kind of function is often used in asymmetric encryption algorithms, as well as in algorithms used to create an electronic digital signature.

Another important class of functions used in asymmetric encryption are one-way backdoor functions. Their definition states that a function is unidirectional with a backdoor if it is unidirectional and it can be computed efficiently inverse function x = f-1(y), i.e. if the “secret passage” is known (a certain secret number, in application to asymmetric encryption algorithms - the value of the secret key).

One-way backdoor functions are used in the widely used asymmetric encryption algorithm RSA.

RSA algorithm

Developed in 1978 by three authors (Rivest, Shamir, Adleman), it got its name from the first letters of the developers' last names. The reliability of the algorithm is based on the difficulty of factoring large numbers and calculating discrete logarithms. Main parameter RSA algorithm- module of the system N, according to which all calculations in the system are carried out, and N = P*Q (P and Q are secret random simple big numbers, usually the same size).

The secret key k2 is selected randomly and must meet the following conditions:

1

where GCD is the greatest common divisor, i.e. k1 must be coprime to the value of the Euler function F(N), the latter being equal to the number of positive integers in the range from 1 to N coprime to N, and is calculated as F(N) = (P - 1)*(Q - 1).

The public key k1 is calculated from the relation (k2*k1) = 1 mod F(N), and for this purpose the generalized Euclidean algorithm (algorithm for calculating the greatest common divisor) is used. Encryption of data block M using the RSA algorithm is performed as follows: C=M [to the power k1] mod N. Note that since in a real cryptosystem using RSA the number k1 is very large (currently its dimension can reach up to 2048 bits), direct calculation of M [to the power k1] unreal. To obtain it, a combination of repeated squaring of M and multiplication of the results is used.

Inversion of this function for large dimensions is not feasible; in other words, it is impossible to find M given the known C, N and k1. However, having a secret key k2, using simple transformations you can calculate M = Ck2 mod N. Obviously, in addition to the secret key itself, it is necessary to ensure the secrecy of the parameters P and Q. If an attacker obtains their values, he will be able to calculate the secret key k2.

Which encryption is better?

The main disadvantage of symmetric encryption is the need to transfer keys “from hand to hand”. This drawback is very serious, since it makes it impossible to use symmetric encryption in systems with an unlimited number of participants. However, otherwise, symmetric encryption has some advantages that are clearly visible against the background of the serious disadvantages of asymmetric encryption.

The first of them is the low speed of encryption and decryption operations, due to the presence of resource-intensive operations. Another “theoretical” disadvantage is that the cryptographic strength of asymmetric encryption algorithms has not been mathematically proven. This is primarily due to the problem of the discrete logarithm - it has not yet been proven that its solution in an acceptable time is impossible. Unnecessary difficulties are also created by the need to protect public keys from substitution - by replacing the public key of a legal user, an attacker will be able to encrypt an important message with his public key and subsequently easily decrypt it with his private key.

However, these shortcomings do not prevent the widespread use of asymmetric encryption algorithms. Today there are cryptosystems that support certification of public keys, as well as combining symmetric and asymmetric encryption algorithms. But this is a topic for a separate article.

RSA algorithm: http://www.rsasecurity.com/rsalabs/pkcs/pkcs-1.

In the 21st century, cryptography plays a serious role in the digital lives of modern people. Let's briefly look at ways to encrypt information.

Cryptography is not just some computer thing

Most likely, you have already encountered basic cryptography and perhaps know some encryption methods. For example, the Caesar Cipher is often used in educational children's games.

ROT13 is another common type of message encryption. In it, each letter of the alphabet is shifted by 13 positions, as shown in the figure:

Today we talk about cryptography most often in the context of some technology. How is personal and financial information transmitted securely when we make an online purchase or view bank accounts? How can you store data securely so that no one can just open up your computer, pull out the hard drive, and have full access to all the information on it? We will answer these and other questions in this article.

Cybersecurity Definitions and Quick Start Guide

In cybersecurity, there are a number of things that worry users when it comes to any data. These include confidentiality, integrity and availability of information.

Confidentiality– data cannot be received or read by unauthorized users.

Information integrity– confidence that the information will remain 100% intact and will not be changed by an attacker.

Availability of information– gaining access to data when necessary.

This article will also look at the different forms of digital cryptography and how they can help achieve the goals listed above.

Basic encryption methods:

• Symmetrical
• Asymmetrical
• Hashing
• Digital signature

Symmetric encryption

Before we get into the subject, let's answer a simple question: what exactly is meant by "encryption"? Encryption is the transformation of information to hide it from unauthorized persons, while at the same time allowing authorized users access to it.

To properly encrypt and decrypt data, you need two things: the data and the decryption key. When using symmetric encryption, the key for encrypting and decrypting data is the same. Let's take a string and encrypt it using Ruby and OpenSSL:

Ruby

require "openssl" require "pry" data_to_encrypt = "now you can read me!" cipher = OpenSSL::Cipher.new("aes256") cipher.encrypt key = cipher.random_key iv = cipher.random_iv data_to_encrypt = cipher.update(data_to_encrypt) + cipher.final binding.pry true

This is what the program will output:

Please note that the variable data_to_encrypt, which was originally the line “now you can read me!” is now a bunch of incomprehensible characters. Let's reverse the process using the key that was originally stored in a variable key.

After using the same key that we set for encryption, we decrypt the message and get the original string.

Let's look at other encryption methods.

Asymmetric encryption

The problem with symmetric encryption is this: suppose you need to send some data over the Internet. If the same key is required to encrypt and decrypt data, then the key must be sent first. This means that the key will need to be sent over an insecure connection. But this way the key can be intercepted and used by a third party. To avoid this outcome, asymmetric encryption was invented.

To use asymmetric encryption, you need to generate two mathematically related keys. One is a private key that only you have access to. The second is open, which is publicly available.

Let's look at an example of communication using asymmetric encryption. In it, the server and the user will send messages to each other. Each of them has two keys: private and public. It was said earlier that the keys are connected. Those. A message encrypted with a private key can only be decrypted using an adjacent public key. Therefore, to start communication, you need to exchange public keys.

But how can you understand that the server’s public key belongs to this particular server? There are several ways to solve this problem. The most common method (and the one used on the Internet) is the use of a public key infrastructure (PKI). In the case of websites, there is a Certificate Authority, which has a directory of all the sites to which certificates and public keys have been issued. When you connect to a website, its public key is first verified by a certificate authority.

Let's create a pair of public and private keys:

Ruby

require "openssl" require "pry" data_to_encrypt = "now you can read me!" key = OpenSSL::PKey::RSA.new(2048) binding.pry true

It will turn out:

Note that the private key and public key are separate entities with different identifiers. Using #private_encrypt, you can encrypt a string using a private key, and using #public_decrypt– decrypt the message:

Hashing information

Hashing, unlike symmetric and asymmetric encryption, is a one-way function. It is possible to create a hash from some data, but there is no way to reverse the process. This makes hashing not a very convenient way to store data, but it is suitable for checking the integrity of some data.

The function takes some information as input and outputs a seemingly random string that will always be the same length. An ideal hashing function produces unique values ​​for different inputs. The same input will always produce the same hash. Therefore, hashing can be used to verify data integrity.