Data Encryption Methods - Web Programmer's Blog. Asymmetric encryption. How it works

Encryption is the most widely used cryptographic method of keeping information confidential; it protects data from unauthorized acquaintance with it. To begin with, we will consider the main methods of cryptographic information protection. In a word, cryptography - the science of information security using mathematical methods. There is also a science opposite to cryptography and devoted to methods of opening protected information - cryptanalysis... The combination of cryptography and cryptanalysis is usually called cryptology... Cryptographic methods can be classified in various ways, but most often they are subdivided depending on the number of keys used in the corresponding cryptoalgorithms (see Fig. 1):

1. Keyless, which do not use any keys.
2. Single-key - they use some additional key parameter - usually a secret key.
3. Two-key, using two keys in their calculations: a secret and a public.

Figure: 1. Cryptoalgorithms

Overview of cryptographic techniques

Encryption is the primary protection method; we will consider it in detail below.

It is worth saying a few words about the rest of the cryptographic methods:

1. An electronic signature is used to confirm the integrity and authorship of data. Data integrity means that the data has not been accidentally or intentionally altered during storage or transmission.
   Algorithms electronic signature use two kinds of keys:
   • the secret key is used to compute the electronic signature;
   • the public key is used to verify it.
   When using a cryptographically strong electronic signature algorithm and with proper storage and use of the secret key (that is, if the key cannot be used by anyone other than its owner), no one else is able to calculate the correct electronic signature of any electronic document.
2. Authentication allows you to verify that the user (or remote computer) really is who he claims to be. The simplest scheme authentication is password-based - as a secret element, it uses a password that is presented by the user when checking it. Such a scheme is proven to be weak unless special administrative and technical measures are taken to strengthen it. And based on encryption or hashing (see below), you can build really strong user authentication schemes.
3. There are various methods of cryptographic checksum:
   • key and keyless hashing;
   • calculation of prefixes;
   • use of message authentication codes.
   In fact, all these methods, in various ways, from data of arbitrary size, using or without a secret key, calculate a certain checksum of a fixed size that uniquely corresponds to the original data.
   This cryptographic checksum is widely used in different methods information protection, for example:
   • to confirm the integrity of any data in cases where the use of an electronic signature is impossible (for example, due to high resource consumption) or is excessive;
   • in the electronic signature schemes themselves, the hash of the data is usually "signed", and not all the data in its entirety;
   • in different schemes user authentication.
4. Random and pseudo generators random numbers allow you to create sequences of random numbers that are widely used in cryptography, in particular:
   • random numbers are needed to generate secret keys, which, ideally, should be completely random;
   • random numbers are used in many electronic signature algorithms;
   • random numbers are used in many authentication schemes.
   It is not always possible to obtain completely random numbers - this requires high-quality hardware generators. However, based on symmetric encryption algorithms, you can build high-quality pseudo-random number generators.

Encryption information is the transformation of open information into encrypted information (which is most often called ciphertext or cryptogram), and vice versa. The first part of this process is called encryption, the second is decryption.

You can imagine encryption in the form of the following formula:

С \u003d E k1 (M),

where:
M (message) - open information,
FROM (cipher text) - the ciphertext obtained as a result of encryption,
E (encryption) - an encryption function that performs cryptographic transformations on M,
k1 (key) - function parameter Ecalled key encryption.

In the GOST 28147-89 standard (the standard defines the domestic symmetric encryption algorithm) the concept key is defined as follows: "The specific secret state of some parameters of the cryptographic transformation algorithm, which ensures the selection of one transformation from a set of all possible ones for of this algorithm transformations ".

The key can belong to a specific user or group of users and be unique for them. Information encrypted using a specific key can only be decrypted using only the same key or a key associated with it in a certain ratio.

Decryption can be presented in a similar way:

M "\u003d D k2 (C),

where:
M "- the message received as a result of decryption,
D (decryption) - decryption function; as well as the encryption function, it performs cryptographic transformations on the ciphertext,
k2 - decryption key.

To get the correct plaintext as a result of decryption (that is, the one that was previously encrypted: M "\u003d M), the following conditions must be met simultaneously:

1. The decryption function must match the encryption function.
2. The decryption key must match the encryption key.

Without the correct key k2 get original message M " = M using the correct function D impossible. The word "impossible" in this case usually means the impossibility of calculating for real time with existing computing resources.

Encryption algorithms can be divided into two categories (see Figure 1):

1. Symmetric encryption algorithms.
2. Asymmetric encryption algorithms.

In algorithms symmetric encryption for decryption, the same key is usually used as for encryption, or a key associated with it by some simple relationship. The latter is much less common, especially in modern encryption algorithms. Such a key (common for encryption and decryption) is usually called simply encryption key.

IN asymmetric encryption encryption key k1 easily computed from the key k2 in such a way that the reverse calculation is impossible. For example, the key ratio might be:

k1 \u003d a k2 mod p,

where a and p are parameters of the encryption algorithm, which have a sufficiently large dimension.

This key ratio is also used in electronic signature algorithms.

The main characteristic of the encryption algorithm is cryptographic strength, which determines its resistance to disclosure by cryptanalysis methods. Typically, this characteristic is determined by the time interval required to break the cipher.

Symmetric encryption is less convenient due to the fact that when transmitting encrypted information, someone needs the addressee to receive a key in advance to decrypt the information. Asymmetric encryption does not have this problem (since the public key can be freely transmitted over the network), however, it has its own problems, in particular, the problem of substituting the public key and the slow encryption speed. Most often, asymmetric encryption is used in conjunction with symmetric - to transfer a symmetric encryption key, on which the bulk of the data is encrypted. However, schemes for storing and transferring keys are a topic for a separate article. Here I will dare to assert that symmetric encryption is used much more often than asymmetric, therefore the rest of the article will be devoted only to symmetric encryption.

There are two types of symmetric encryption:

• Block encryption - information is divided into blocks of fixed length (for example, 64 or 128 bits), after which these blocks are encrypted one by one. Moreover, in various encryption algorithms or even in different modes When the same algorithm works, blocks can be encrypted independently of each other or "with concatenation" - when the encryption result of the current data block depends on the value of the previous block or on the encryption result of the previous block.
• Stream encryption - it is necessary, first of all, in those cases when information cannot be divided into blocks - say, a certain data stream, each character of which must be encrypted and sent somewhere, without waiting for the rest of the data sufficient to form a block. Therefore, stream encryption algorithms encrypt data bit by bit or character by character. Although it should be said that some classifications do not separate block and stream encryption, considering that stream encryption is encryption of blocks of a single length.

Let's see how the block symmetric encryption algorithms look from the inside.

The vast majority of modern encryption algorithms work in a very similar way: a certain transformation is performed on the encrypted text with the participation of the encryption key, which is repeated a certain number of times (rounds). At the same time, according to the type of repeated transformation, encryption algorithms are usually divided into several categories. There are also various classifications here, I will give one of them. So, by their structure, encryption algorithms are classified as follows:

1. Algorithms based on the Feistel network.

   The Feistel network implies splitting the processed data block into several subblocks (most often two), one of which is processed by some function f () and superimposed on one or more other subunits. In fig. 2 shows the most common structure of algorithms based on the Feistel network.
   
   

   Figure: 2. The structure of algorithms based on the Feistel network.

   Optional function argument f (), indicated in Fig. 2 how Kiis called round key... The round key is the result of processing the encryption key by the key expansion procedure, the task of which is to obtain the required number of keys Ki from the original encryption key of a relatively small size (currently, 128 bits are considered sufficient for a symmetric encryption key). In the simplest cases, the key expansion procedure simply splits the key into several fragments, which are used in turn in the encryption rounds; much more often the key expansion procedure is rather complicated, and the keys Ki depend on the values \u200b\u200bof most of the bits of the original encryption key.

   The imposition of a processed subblock on an unprocessed subblock is most often done using the logical XOR operation (as shown in Figure 2). Quite often, instead of XOR, modulo addition is used here. 2 nwhere n - subblock size in bits. After imposition, the subblocks are swapped, that is, in the next round of the algorithm, another data subblock is processed.

   This structure of encryption algorithms got its name from Horst Feistel - one of the developers of the Lucifer encryption algorithm and the DES (Data Encryption Standard) algorithm developed on its basis - the former (but still widely used) US encryption standard. Both of these algorithms have a structure similar to that shown in Fig. 2. Among other algorithms based on the Feistel network, one can cite as an example the domestic encryption standard GOST 28147-89, as well as other very well-known algorithms: RC5, Blowfish, TEA, CAST-128, etc.

   Most modern encryption algorithms are based on the Feistel network - due to the many advantages of such a structure, among which the following are worth noting:

   • Algorithms based on the Feistel network can be designed in such a way that the same algorithm code can be used for encryption and decryption - the difference between these operations can only be in the order of using the Ki keys; this property of the algorithm is most useful for its hardware implementation or on platforms with limited resources; GOST 28147-89 is an example of such an algorithm.

Algorithms based on the Feistel network are the most studied - a huge number of cryptanalytic studies are devoted to such algorithms, which is an undoubted advantage both in the development of the algorithm and in its analysis.

There is also a more complex structure of the Feistel network, an example of which is shown in Fig. 3.



Figure: 3. The structure of the Feistel network.

This structure is called generalized or expanded the Feistel network and is used much less often than the traditional Feistel network. An example of such a Feistel network is the RC6 algorithm.

2. Algorithms based on permutation networks (SP network - Substitution-permutation network).

   Unlike the Feistel network, SP networks process the entire encrypted block in one round. Data processing comes down mainly to replacements (when, for example, a fragment of the input value is replaced by another fragment in accordance with the table of replacements, which may depend on the key value Ki) and permutations depending on the key Ki (a simplified diagram is shown in Fig. 4).
   
   

   Figure: 4. Substitution-permutation network.

   However, such operations are typical for other types of encryption algorithms, therefore, in my opinion, the name "substitution-permutation network" is rather arbitrary.

   SP-networks are much less common than Feistel networks; Serpent or SAFER + algorithms are examples of SP networks.

3. Algorithms with structure "square" (Square).

   The structure "square" is characterized by the representation of the encrypted data block in the form of a two-dimensional byte array. Cryptographic transformations can be performed on individual bytes of an array, as well as on its rows or columns.

   The structure of the algorithm gets its name from the Square algorithm, which was developed in 1996 by Vincent Rijmen and Joan Daemen - the future authors of the Rijndael algorithm, which became the new US encryption standard AES after winning an open competition. The Rijndael algorithm also has a Square-like structure; also examples are Shark (an earlier development by Ridgeman and Damen) and Crypton. The disadvantage of algorithms with the "square" structure is their insufficient knowledge, which did not prevent the Rijndael algorithm from becoming the new US standard.
   
   

   Figure: 5. Rijndael Algorithm.

   In fig. 5 shows an example of an operation on a data block performed by the Rijndael algorithm.

Algorithms with a non-standard structure, that is, those algorithms that cannot be assigned to any of the listed types. It is clear that ingenuity can be limitless, so it is difficult to classify all possible variants of encryption algorithms. As an example of an algorithm with a non-standard structure, one can cite the FROG algorithm, unique in its structure, in each round of which there are enough complex rules modification of two bytes of encrypted data is performed (see Fig. 6).



Figure: 6. Modification of two bytes of encrypted data.

There are no strict boundaries between the structures described above; therefore, algorithms that various experts rank as different types structures. For example, the CAST-256 algorithm refers by its author to the SP-network, and by many experts it is called the extended Feistel network. Another example is the HPC algorithm, called by its author the Feistel network, but attributed by experts to algorithms with a non-standard structure.

Sergey Panasenko,
head of development department software firm "Ankad",
[email protected]

Basic concepts

The process of converting open data into encrypted 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, which describe actions with the initial information:

С \u003d Ek1 (M)

M "\u003d Dk2 (C),

where M (message) is open information (in the information security literature it is often called "source 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 original text;
k1 (key) - parameter of the function E, called the encryption key;
M "- information obtained as a result of decryption;
D (decryption) - a decryption function that performs reverse encryption cryptographic transformations over 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, which ensures the selection of one transformation from a set of all possible transformations for this algorithm." In other words, the key is a unique element with which you can change the results of the encryption algorithm: the same source text will be encrypted in different ways when using different keys.

In order for the decryption result to coincide with the original message (that is, for M "\u003d M), two conditions must be met simultaneously. First, the decryption function D must correspond to the encryption function E. Second, the decryption key k2 must match 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 "\u003d M. Cryptographic strength is the main characteristic of encryption algorithms and indicates, first of all, the degree of difficulty in obtaining the original text from encrypted 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 \u003d k2 \u003d k (i.e., functions E and D use the same encryption key). In asymmetric encryption, the encryption key k1 is calculated using the key k2 in such a way that the reverse transformation is impossible, for example, by the formula k1 \u003d ak2 mod p (a and p are the parameters of the algorithm used).

Symmetric encryption

Symmetric encryption algorithms have their history since antiquity: this method of hiding information was used by the Roman emperor Gaius Julius Caesar in the 1st century BC. e., and the algorithm invented by him is known as "Caesar's cryptosystem".

Currently, the most famous is the symmetric encryption algorithm DES (Data Encryption Standard), developed in 1977. Until recently, it was the "US standard" because the government of that country recommended using it to implement different systems data encryption. Despite the fact that DES was originally planned to be used no more than 10-15 years, attempts to replace it began only in 1997.

We will not cover DES in detail (almost all books from the list of additional materials have it detailed description), and turn to more modern encryption algorithms. It should only be noted 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 cryptographically strong algorithm can be cracked by going through all possible variants of 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 DES keys in almost 20 hours. And since such computing power is quite real by today's standards, it is clear that a 56-bit key is too short and dES algorithm must be replaced with a stronger one.

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

GOST 28147-89 standard

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 split into two sub-blocks of 32 bits (N1 and N2). Subblock N1 is processed in a certain way, after which its value is added to the value of subblock N2 (addition is performed modulo 2, that is, the logical operation XOR - "exclusive or" is applied), and then the subblocks are swapped. This transformation it is executed a certain number of times ("rounds"): 16 or 32, depending on the mode of operation of the algorithm. Two operations are performed in each round.

The first is the key overlay. The content of the sub-block N1 is 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. In the encryption process, one of these subkeys is used, depending on the round number and the mode of operation of the algorithm.

The second operation is table replacement. After the key is applied, the N1 sub-block 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 sub-block. The sub-block is then bitwise shifted to the left by 11 bits.

Table replacements(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 \u200b\u200bof the blocks are written to the table. A data block of a certain dimension (in our case, 4-bit) has its own numerical representation, which determines 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 a 4-bit block "0100" arrived at the input (value 4), then, according to the table, the output value will be 15, that is, "1111" (0 a 4, 1 a 11, 2 a 2 ...).

The algorithm, defined by GOST 28147-89, provides for four modes of operation: simple replacement, gamming, gamming with feedback and generation of simulators. They use the same encryption transformation described above, but since the purpose of the modes is different, this transformation is carried out in each of them in different ways.

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

K0, K1, K2, K3, K4, K5, K6, K7, K0, K1, etc. - in rounds 1 to 24;

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

Decryption in this mode is carried out in 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, that is, the encryption result of each block depends only on its content (the corresponding block of the source text). If there are several identical blocks of the original (plain) text, the corresponding blocks of ciphertext will also be the same, which gives an additional useful information for a cryptanalyst trying to break the code. Therefore, this mode is mainly used to encrypt the encryption keys themselves (very often multi-key schemes are implemented, in which, for a number of reasons, the keys are encrypted on top of each other). To encrypt the information itself, there are two other modes of operation - gamma and feedback gamma.

IN gamma mode each block of plaintext is bitwise added modulo 2 with 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. In registers N1 and N2 their initial filling is written - a 64-bit value called sync burst.

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

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

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

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

If the next block of gamma is needed (that is, you need to continue encryption or decryption), you return to step 2.

For decryption, the gamma is generated in a similar way, and then the XOR operation is applied to the ciphertext and gamma bits again. Since this operation is reversible, in the case of a correctly worked out scale, the original text (table) is obtained.

Encryption and decryption in gamma mode

To generate the cipher gamut required for decryption, the user decrypting the cryptogram must have the same key and the same synchro-message value that were used to encrypt the information. Otherwise, it will not be possible to get the original text from the encrypted one.

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

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

Figure: 2. Generation of the cipher gamma in the feedback gamma mode.

Considering the mode generation of simulators, the concept of the subject of generation should be defined. A prefix is \u200b\u200ba cryptographic checksum calculated using an encryption key to verify the integrity of messages. When generating a prefix, the following operations are performed: the first 64-bit block of the information array, for which the prefix is \u200b\u200bcalculated, is written into registers N1 and N2 and encrypted in the reduced mode of simple replacement (the first 16 rounds out of 32 are performed). The resulting result is summed modulo 2 with the next block of information, storing the result in N1 and N2.

The cycle is repeated until the last block of information. The resulting 64-bit contents of registers N1 and N2, or part of it, obtained as a result of these conversions, is called a prefix. The size of the prefix is \u200b\u200bselected based on the required message reliability: with the length of the prefix r bits, the probability that the message change will go unnoticed is 2-r. Most often, a 32-bit prefix is \u200b\u200bused, i.e. half of the register contents. This is sufficient because, like any checksum, the simulator is designed primarily to protect against accidental distortion of information. To protect against deliberate modification of data, other cryptographic methods are used - first of all, an electronic digital signature.

When exchanging information, the simulator serves as a kind of additional means of control. It is calculated for the plaintext when some information is encrypted and sent along with the ciphertext. After decryption, a new prefix value is calculated, which is compared with the sent one. If the values \u200b\u200bdo not match, it means that the ciphertext was distorted during transmission or incorrect keys were used during decryption. The prefix is \u200b\u200bespecially 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 - at present, no more have been proposed for its disclosure. effective methodsthan 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 is increased to 320 bits, and the secrecy of the substitution table adds additional bits. In addition, cryptographic strength depends on the number of rounds of transformations, of which, according to GOST 28147-89, there should be 32 (the full effect of dispersion of the input data is achieved after 8 rounds).

AES standard

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

A competition to replace DES was announced in 1997 by the US National Institute of Standards and Technology (NIST). Fifteen candidate algorithms were presented for the competition, developed both by organizations well-known in the field of cryptography (RSA Security, Counterpane, etc.) and by 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 like most of the well-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, some of which are processed in each round according to a certain law, and then 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 4X4, 4X6, or 4X8 sizes (several fixed sizes of the encrypted information block are 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). During this operation, the first line remains unchanged, and the rest are cyclically byte shifted to the left by a fixed number of bytes, depending on the size of the array. For example, for a 4X4 array, rows 2, 3, and 4 are shifted by 1, 2, and 3 bytes, respectively. Next comes MC (MixColumn) - an operation on independent columns of an array (Fig. 5), when each column is multiplied according to a certain rule by a fixed matrix c (x). 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).

Figure: 3. Operation BS.

Figure: 4. Operation SR.

Figure: 5. Operation MC.

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

Decryption is performed using the following reverse operations. The table is inverted and the table replacement is performed on the inverse table (relative to that used for encryption). The inverse of SR is to cycle the rows to the right, not the left. The inverse operation for MC is multiplication according to the same rules by another matrix d (x) satisfying the condition: c (x) * d (x) \u003d 1. Adding the AK key is the inverse of itself, since it only uses the XOR operation. These reverse operations are applied during decryption in the reverse order to that used for 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 by incomparably better possibilities of parallelizing computations in comparison with other algorithms presented for the competition. In addition, the resource requirements for its operation are minimal, which is important when using it in devices with limited computing capabilities.

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

Asymmetric encryption

As already noted, asymmetric encryption algorithms use two keys: k1 is the encryption key, or public, and k2 is the decryption key, or secret. Public key calculated from the secret: k1 \u003d f (k2).

Asymmetric encryption algorithms are based on the use of one-way functions. By definition, a function y \u003d f (x) is unidirectional if: it is easy to compute for all possible options x and for most possible values \u200b\u200bof y it is rather difficult to calculate such a value of x for which y \u003d f (x).

An example of a one-way function is the multiplication of two large numbers: N \u003d P * Q. Such multiplication itself is a simple operation. However, the inverse function (decomposition of N into two large factors), called factorization, is, according to modern time estimates, a rather complicated mathematical problem. For example, factoring N of 664 bits at P? Q will require approximately 1023 operations, and to reverse x for the modular exponent y \u003d ax mod p with known a, p, and y (with the same dimensions of a and p), approximately 1026 operations will be required. The last of these examples is called the Discrete Logarithm Problem (DLP), and such functions are often used in asymmetric encryption algorithms, as well as in algorithms used to create digital signatures.

Another important class of functions used in asymmetric encryption are backdoor one-way functions. Their definition states that a function is unidirectional with a secret passage if it is unidirectional and it is possible to efficiently calculate the inverse function x \u003d f-1 (y), that is, if the "secret passage" is known (a certain secret number, as applied to for asymmetric encryption algorithms - the value of the secret key).

Backdoor unidirectional functions are used in the popular RSA asymmetric encryption algorithm.

RSA algorithm

Developed in 1978 by three authors (Rivest, Shamir, Adleman), it got its name from the first letters of the developers' surnames. The reliability of the algorithm is based on the complexity of factorizing large numbers and calculating discrete logarithms. The main parameter of the RSA algorithm is the system module N, according to which all calculations in the system are carried out, and N \u003d P * Q (P and Q are secret random prime numbers, usually of the same dimension).

The secret key k2 is chosen at random and must meet the following conditions:

1

where GCD is the greatest common divisor, i.e., k1 must be coprime with 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 with N, and is calculated as F (N) \u003d (P - 1) * (Q - 1).

The public key k1 is calculated from the relation (k2 * k1) \u003d 1 mod F (N), and for this the generalized Euclidean algorithm (algorithm for calculating the greatest common divisor) is used. Data block M is encrypted using the RSA algorithm as follows: C \u003d M [to the power of k1] mod N... Note that since in a real cryptosystem using RSA the number k1 is very large (at present its dimension can reach 2048 bits), direct computation of M [to the power of k1] unrealistic. To obtain it, a combination of multiple squaring M with multiplication of the results is used.

Inversion of this function is not feasible for large dimensions; in other words, it is impossible to find M from the known C, N, and k1. However, having the secret key k2, using simple transformations, we can calculate M \u003d 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, then he can 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 disadvantage is very serious, since it makes it impossible to use symmetric encryption in systems with an unlimited number of participants. However, the rest of the symmetric encryption has some advantages, which are clearly visible against the background of 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" drawback is that the cryptographic strength of asymmetric encryption algorithms has not been proven mathematically. This is primarily due to the discrete logarithm problem - so far it has not been possible to prove that its solution in a reasonable time is impossible. Unnecessary difficulties are also created by the need to protect public keys from substitution - by changing the public key of a legal user, an attacker will be able to encrypt an important message using his public key and subsequently easily decrypt it with his private key.

Nevertheless, these shortcomings do not prevent the widespread use of asymmetric encryption algorithms. Cryptosystems exist today that support public key certification, as well as a combination of symmetric and asymmetric encryption algorithms. But this is already a topic for a separate article.

Information lifetime

§ When intercepting an encrypted message for some types of encryption algorithms, you can calculate the frequency of occurrence of certain characters and compare them with the probabilities of occurrence of certain characters or their combinations (bigrams, trigrams, etc.). This, in turn, can lead to unambiguous decryption (disclosure) of individual sections of the encrypted message.

§ Presence of probable words. These are words or expressions that can be expected to appear in an intercepted message (for example, for English text - “and”, “the”, “are”, etc.).

§ There are methods to make encrypted messages practically unsuitable for statistical analysis and probable word analysis. These include the following.

§ Diffusion.The influence of one character in an open message extends to many characters in an encrypted message. This method, although it leads to an increase in the number of errors during decryption, however, it helps to hide the statistical structure of an open message.

§ Entanglement.Development of the scattering principle. In it, the influence of one key character extends to many characters of the encrypted

messages.

§ Mixing.It is based on the use of special transformations of the original message, as a result of which the probable sequences seem to be scattered throughout the space of possible open messages. The development of this method was the use of composite encryption algorithms, consisting of a sequence of simple operations of permutation and substitution.

Examples of the methods described are DES encryption standards and GOST 28147-89.

There are two main types of encryption algorithms:

§ symmetric encryption algorithms;

§ algorithms for asymmetric encryption.

Symmetric encryption.

Symmetric encryption algorithms are based on the fact that the same (shared) key is used to encrypt a message and to decrypt it (Fig. 1).

One of the main advantages of symmetric methods is the speed of encryption and decryption, and the main disadvantage is the need to transfer the secret key value to the recipient.

Inevitably, a problem arises: how to transfer the key and at the same time not allow intruders to intercept it.

Benefits of cryptography with symmetric keys:

· High performance.

· High durability.All other things being equal, the strength of a cryptographic algorithm is determined by the key length. With a key length of 256 bits, it is necessary to perform 10 77 iterations to determine it.

Disadvantages of cryptography with symmetric keys.

§ Key distribution problem.Since the same key is used for encryption and decryption, very reliable mechanisms are required for their distribution (transmission).

§ Scalability.Since both the sender and the recipient use a single key, the number of keys required increases exponentially depending on the number of participants in the communication. To exchange messages between 10 users, you need to have 45 keys, and for 1000 users - already 499,500.

§ Limited use.Cryptography with a secret key is used to encrypt data and restrict access to it, it is impossible to provide such properties of information as authenticity and

non-repudiation.

Asymmetric encryption

Asymmetric encryption algorithms (public-key cryptography) use two keys. The first key is open.It is distributed completely free, without any precautions. Second, closedthe key is kept secret.

Any message encrypted using one of these keys can only be decrypted using its paired key. Typically, the sender of a message uses the recipient's public key, and the recipient uses their private private key.

In an asymmetric scheme for the transmission of encrypted messages, both keys are derived from a single generating master key.When two keys are generated from one, they are mathematically dependent, however, due to computational complexity, neither of them can be calculated from the other. After both keys are generated (both public and private, private), the master key is destroyed, and thus any attempt to restore the values \u200b\u200bof the keys derived from it is suppressed.

The asymmetric scheme is ideally suited to the use of public messaging networks (eg the Internet). Any subscriber of the network can absolutely freely send the public key to his negotiating partner, and the latter, as the sender of the message, will use this key when encrypting the message being sent (Fig. 2). This message can only be decrypted with his private key by the recipient of the message who previously sent the corresponding public key. An attacker who intercepts such a key can only use it for the sole purpose of transmitting encrypted messages to the legitimate owner of the key.

The disadvantage of the asymmetric scheme is the large time required for encryption and decryption, which does not allow their use for the rapid exchange of lengthy messages in the dialogue mode. The implementation of asymmetric encryption methods is CPU-intensive. Therefore, in its pure form, public key cryptography is usually not used in world practice.

Figure: 2. Asymmetric encryption scheme

It is impossible to compare which is better, symmetric or asymmetric encryption algorithms. It is noted that symmetric cryptographic algorithms have a shorter key length and are faster.

Secret cryptography and public key cryptography are designed to solve very different problems. Symmetric algorithms are well suited for encrypting data, asymmetric algorithms are implemented in most network cryptographic protocols.

The most widespread methods are those that combine the advantages of both schemes. The principle of operation of combined schemes is that a symmetric (session) key is generated for the next messaging session. This key is then encrypted and sent using an asymmetric scheme. After the end of the current negotiation session, the symmetric key is destroyed.

The question often arises: what type of Wi-Fi encryption to choose for a home router. It would seem a trifle, but with incorrect parameters, problems may arise to the network, and even with the transfer of information via an Ethernet cable.

Therefore, here we will consider what types of data encryption are supported by modern WiFi routers, and how the aes encryption type differs from the popular wpa and wpa2.

Wireless encryption type: how to choose a security method?

So, there are 3 types of encryption in total:

1. 1. WEP encryption

The type of WEP encryption appeared back in the distant 90s and was the first option for protecting Wi-Fi networks: it was positioned as an analogue of encryption in wired networks and used the RC4 cipher. There were three common encryption algorithms for transmitted data - Neesus, Apple and MD5 - but each of them did not provide the required level of security. In 2004, the IEEE declared the standard obsolete due to the fact that it finally ceased to provide a secure connection to the network. At the moment, this type of encryption for wifi is not recommended, because it is not cryptographically secure.

1. 2. WPS is a non-use standard. To connect to the router, you just need to click on the corresponding button, which we discussed in detail in the article.

In theory, WPS allows you to connect to an access point using an eight-digit code, but in practice, often only four are enough.

This fact is calmly used by numerous hackers who quickly enough (in 3 - 15 hours) hack wifi networks, so using this connection is also not recommended.

1. 3. Encryption type WPA / WPA2

Things are much better with WPA encryption. Instead of the vulnerable RC4 cipher, AES encryption is used here, where the password length is an arbitrary value (8 - 63 bits). This type of encryption provides a normal level of security and is quite suitable for simple wifi routers. Moreover, there are two types of it:

PSK type (Pre-Shared Key) - connection to the access point is carried out using a predefined password.
- Enterprise — a password for each node is generated automatically with verification on RADIUS servers.

WPA2 is a continuation of WPA with security enhancements. This protocol uses RSN, which is based on AES encryption.

Like WPA encryption, WPA2 has two modes of operation: PSK and Enterprise.

Since 2006, the WPA2 encryption type is supported by all Wi-Fi equipment, the corresponding geo can be selected for any router.

Advantages of WPA2 encryption over WPA:

Encryption keys are generated during the connection to the router (instead of static ones);
- Using the Michael algorithm to control the integrity of transmitted messages
- Using an initialization vector of a substantially longer length.
In addition, the type of Wi-Fi encryption should be chosen depending on where your router is used:

WEP, TKIP and CKIP encryption shouldn't be used at all;

For a home access point, WPA / WPA2 PSK is fine;

For it is worth choosing WPA / WPA2 Enterprise.

Few people know exactly how asymmetric encryption works. For example, there are people who do not consider the https protocol to be any adequate protection of transmitted data. And as a rule, to an attempt to convince the opposite, they respond with something like “if we transmit encrypted data, then we must tell how to decrypt it, and this information can be intercepted and, therefore, decrypted the data”. And to arguments that this is not so and that asymmetric encryption is based on, the answer is “So what?”.

Okay, I understand that not everyone needs to know all the intricacies of implementing asymmetric encryption. But the general principle of operation, I believe, should be known to everyone who is in any way connected with computers.

I want to bring the essence of this post into this annotation: Remember, asymmetric encryption is safe, naturally under all conditions. And to prove this, I will try to describe the algorithm in an understandable language so that everyone can understand that it is safe. Meet Alice, Bob and Eve and the transmission of their secret message under the cut.

By the way, why Alice and Bob? There is a short article about this on Wikipedia: Alice, Bob and Eve. To make it clearer, Alice and Bob want to exchange messages, and Eve is trying to intercept and read these messages.

A bit of history

Cryptography of the past centuries had one huge problem - the problem of transferring keys. In those days, there were only so-called "symmetric" ciphers - ciphers in which data is encrypted and decrypted with the same key.

For example, Alice has encrypted some message and wants to send it to Bob. Naturally, for Bob to read it, he needs a key with which this message was encrypted. And then the problem arises of how to transfer the key so that no one can intercept it. Inquiring minds will offer - let them pass it on in person, and then communicate as much as they want. Yes, I do not argue, the way out. Now imagine for a second that your Internet mail, before you log into it, will require your trip to the physical location of the mail server. Conveniently? Perhaps not very much.

Of course, the key can be transmitted over another communication channel. But cryptography considers all unsecured communication channels to be insecure. That is, handing over the key to Bob over the phone, for example, is considered unsafe since nothing prevents Eve from listening to the phone as well.

Until the 70s, this problem became so common that it was considered an axiom that in order to transmit a message, it is necessary to transmit the key to which the message is encrypted (and some people still think that way). But in 76, Diffie and Hellman proposed their "exponential key exchange method." From these years the development of asymmetric cryptosystems began.

A little bit of real life

Before studying any algorithm, you need to imagine how it works. And the easiest way is to compare it with the work of something in reality.

Imagine that Alice and Bob live in a country where the entire postal system is completely immoral and postal workers read all unprotected mail. Alice, a girl not stupid, before sending a message to Bob, took an iron box and, putting a letter inside and closing it with her lock, sends this box to Bob.

Naturally, they cannot read this letter at the post office, but Bob himself cannot read it, since he does not have a key with which the lock is closed. Alice, of course, can take another iron box, put the key from the previous one in it, and send it to Bob, but Bob cannot open it either ...

The only way is to make a duplicate key and give it to Bob in person ...

And then it starts to seem that key exchange is an inevitable part of encryption - or is it not?

Let's imagine a different picture. I will write down step by step:

1. Alice puts her letter in an iron box and, locking it on the lock, sends it to Bob.
2. Upon receiving the box, Bob (attention!) Takes his lock and, additionally locking the box with it, sends it back.
3. Alice comes with a box with two locks (let me remind you with Alice's first lock from which she has a key, and with the second - Bob, from which only Bob has the key).
4. Alice unlocks her lock and sends the box back to Bob
5. Bob comes to a box with already one of his lock from which he has a key
6. Bob unlocks his remaining lock with his key and reads the message

The significance of this short story is enormous. It shows that two people can transmit a secret message without exchanging keys. Think about it! This story actually destroys all the axioms on which the then cryptography was built. Yes, we get some complication of the process (the box had to be sent three times), but the result ...

Back to cryptography

It would seem that a solution has been found. The sender and the receiver encrypt their message, and then the interlocutors take turns removing their cipher.


But the point is that there are no ciphers that would allow you to remove a cipher from a different cipher. That is, the stage where Alice removes her cipher is impossible:


Unfortunately, all available algorithms still require the removal of ciphers in the queue in which they were applied. I am afraid to call it an axiom (since history already knows cases when such axioms were crushed to smithereens), but this is still the case.

Back to math

The box idea I described above inspired Diffie and Hellman to look for a way to get the message across. Eventually they ended up using one-way functions.

What is a one way function? For example, there is a doubling function, i.e. double (4) \u003d 8, it is double-sided, because from result 8 it is easy to get the initial value 4. A one-way function is a function after which it is almost impossible to get the initial value. For example mixing yellow and blue paint is an example of a one-way function. Mix them easy, but to get back the original components - impossible... One such function in mathematics is modulo computation.

As a basis for the algorithm, Hellman proposed the function Y x (mod P)... The reverse conversion for such a function is very difficult, and we can say that, in fact, it consists in a complete enumeration of the original values.

For example, you were told that 5 x (mod 7) \u003d 2, try find x, a? Found it? Now imagine that Y and P are numbers of the order of 10,300.

By the way, to increase durability, the number P must be prime and Y - be an antiderivative root modulo P... But since we are still trying to understand the theory, I don't see any reason to bother with this.

Diffie-Hellman algorithm

Then one day it dawned on Hellman and he was able to develop a working key exchange algorithm. To work with this algorithm, you need to perform steps on both sides, so I will sketch this in the table:

Magic? I do not argue, it is not clear at first sight. But after reading and thinking about this table, it becomes clear how it works. However, if it is not clear, then scroll to the end of the chapter, there I posted an explanatory video.

Moreover, note that to get the key in the final formula, any person needs to have three values:

• The values a and P, and Bob's secret number B
• or values b and P, and Alice's secret number A

But the secret numbers are not transmitted over the channel! Eve will not be able to retrieve the key without someone's secret number. Why - I wrote above, this function is one-way. Try to solve the equation 4 x (mod 11) \u003d 2 y (mod 11) finding x and y.

To make it clearer how Hellman's scheme works, imagine a cipher that somehow uses color as a key:

Let's assume at the outset that everyone, including Alice, Bob, and Eve, has a three-liter jar with one liter of yellow paint poured into. If Alice and Bob want to agree on a secret key, they add one liter of their own secret paint to their cans.

Alice can add a purple hue, and Bob can add raspberry. After that, each of them sends their jar of mixed contents to the other.

Finally, Alice takes Bob's mixture and pours one liter of his secret paint into it, and Bob takes Alice's mixture and adds one liter of his secret paint to it. The paint in both cans will now be the same color, since each contains one liter of yellow, purple and crimson paint.

It is this color, obtained by adding twice to the paint cans, and will be used as a key. Alice has no idea what paint Bob added, and Bob also has no idea what paint Alice poured, but they both achieved the same result.

Meanwhile, Eve is furious. Even if she does manage to intercept the cans of intermediate, she will not be able to determine the final color, which will be the negotiated key. Eve can see the color of the paint obtained by mixing the yellow paint and Alice's secret paint in the jar sent to Bob, and she can see the paint color obtained by mixing the yellow paint and Bob's secret paint in the jar sent to Alice, but to find the key, she, in fact, you need to know the colors of Alice and Bob's original secret colors. However, looking at cans of mixed paints, Eve will not be able to identify Alice and Bob's secret colors. Even if she takes a sample of one of the mixed paints, she will not be able to separate it into the original paints in order to find the secret, since mixing the paint is a one-way function.

Still not clear? Then watch the video:

Well, I hope you realized that there is a very real way to securely exchange keys. But please note that it is not yet possible to call this algorithm an asymmetric cipher, since in fact it is just a key exchange algorithm.

Asymmetric encryption

the asymmetric algorithm assumes the presence of two keys - public and private. That is, the message is encrypted with a public key, and decrypted with a private one and nothing else. Actually, it was this concept that Diffie formulated.

In general, the essence of this algorithm is that the receiving party, before accepting the message, generates a key pair based on the modular arithmetic algorithm (the principle is the same as in the Diffie-Hellman algorithm), a private and public key. Before sending, the sender receives a public key and encrypts the message with this key, after which this message can be decrypted only with the private key, which is kept secret by the receiving party.


If we go back to the analogy with locks, then public key encryption can be imagined as follows:

Anyone can lock a lock by simply snapping it shut, but only someone with the key can unlock it. It is easy to lock the lock (encryption), almost everyone can do it, but only the owner of the key can open it (decryption). Understanding how to latch a lock so that it closes doesn't tell you how to unlock it.

A deeper analogy can also be drawn.

Imagine Alice designing a lock and key. She vigilantly guards the key, but at the same time makes thousands of duplicate locks and sends them to post offices around the world. If Bob wants to send a message, he puts it in a box, goes to the local post office, asks for "Alice's lock" and locks the box with it. Now he will not be able to open the box, but when Alice receives the box, she can open it with her only key.

A padlock and snapping it shut to close is equivalent to a shared encryption key, since everyone has access to the locks and everyone can use the lock to close the message in the box. The key to the lock is equivalent to the private decryption key, because only Alice has it, only she can open the lock, and only she can access the message in the box.

There are several algorithms that implement asymmetric encryption. The most famous of these is RSA. I don't see the point in writing it down, since I still won't be able to understand how it works on the fly, and I can't write better than what is written on Wikipedia.

Conclusion

Well, I hope that by understanding how asymmetric encryption works from the inside, you will begin to trust it more and, accordingly, use SSL more often \u003d)

Used materials from the book Singh Simon - The Book of Ciphers. By the way, the best book for those who want to understand at least a little bit of cryptography. I advise everyone to read.

1. tv

   The selection of such a key will take you a lot of time. Little more than the universe exists. Even on very powerful computers.

2. Igor

   What is this public key bullshit for? Symmetrical is more reliable.
   Good day!
   A good site, the material is clearly stated, many thanks to the author. I got here by accident in September when I was looking for information on practical encryption.
   I am writing because I want to ask: Are there people who want to know how to find numbers for symmetric encryption? I can teach on my fingers how to quickly check the number P for simplicity (without looking for the number g) - but this is unlikely to be interesting. The most interesting:
   Find a number P of any length and a number g to it. I don't use any 2 to the power n plus one (or minus one). Naturally, it's free. There is even a site where I posted my work.