Annotation: This lecture has several goals. Show the difference between traditional and modern ciphers with a symmetric key. Bring modern block ciphers and discuss their characteristics. Explain why modern block ciphers should be designed as substitution ciphers. Introduce the components of block ciphers such as P-boxes and S-boxes. Discuss and show the difference between two classes of ciphers: Feistel ciphers and non-Feistel ciphers. Discuss two types of attacks specifically aimed at breaking modern block ciphers: differential and linear cryptanalysis. Introduce the concept of "stream ciphers" and show the difference between synchronous and non-synchronous ciphers. Discuss linear and non-linear feedback of shift registers for realizing stream ciphers.
Traditional ciphers with symmetric keythat we have studied so far are symbol-oriented. With the advent of the computer, bit-oriented ciphers became necessary. Because the information to be encrypted is not always just text; it can also consist of numbers, graphics, audio and video data. It is convenient to convert these data types to a bitstream in order to encrypt that stream, and then transmit the encrypted stream. In addition, when the text is processed at the bit level, each character is replaced by 8 (or 16) bits, which means that the number of characters becomes 8 (or 16) times more. Mixing more characters increases security.
This chapter provides the necessary foundation for learning modern block and stream ciphers, which are covered in the next three chapters. Most of this chapter is devoted to discussing the general ideas of modern block ciphers, and only a small part is devoted to the principles of modern stream ciphers.
7.1. Modern block ciphers
A modern symmetric key block cipher encrypts an n-bit block of the original text or decrypts an n-bit block of the ciphertext. The encryption or decryption algorithm uses a k-bit key. The decryption algorithm must be the inverse of the encryption algorithm, and both operate on the same encryption key so that Bob can recover the message Alice sent. Figure 7.1 shows the general idea of \u200b\u200bencryption and decryption in a modern block cipher.
Figure: 7.1.
If the message is less than n bits, padding must be added to create this n-bit block; if the message has more than n bits, it must be split into n-bit blocks and, if necessary, add padding to the last block. Common values \u200b\u200bfor n are usually 64, 128, 256, or 512 bits.
Example 7.1
How many extra bits do you need to add to a 100-character message if 8-bit ASCII is used for encoding and the block cipher accepts 64-bit blocks?
Decision
Encode 100 characters using 8-bit ASCII. This message contains 800 bits. The original text must be divisible by 64 without a remainder. If | M | and | Pad | - message length and filling length, then
| M | + | Pad | \u003d\u003d 0 mod 64 -\u003e | Pad | \u003d -800 mod 64 -\u003e 32 mod 64
This means that 32 bits of padding (eg zeros) must be added to the message. The text would then be 832 bits, or thirteen 64-bit blocks. Note that only the last block contains padding. The encryptor uses the encryption algorithm thirteen times to create thirteen ciphertext blocks.
Substitution, or transposition
A modern block cipher can be designed to act as a substitution cipher or as a transposition cipher. This is the same idea used in traditional ciphers, except that characters to be replaced or moved contain bits instead of characters.
If the cipher is designed as substitution cipher, bit values \u200b\u200b1 or 0 in the source text can be replaced with either 0 or 1. This means that the original text and the ciphertext can have a different number of units. A 64-bit block of original text, which contains 12 zeros and 52 ones, can be represented in ciphertext by 34 zeros and 30 ones. If the cipher is designed as permutation (transposition) cipher, the bits only change the order (move), keeping the same number of characters in the original and ciphertext. In any case, the number of possible n-bit sources or ciphers is 2 n, because each of the n bits used in a block can have one of two values \u200b\u200b- 0 or 1.2 64 blocks of 64 bits to find one that makes sense. If Eve could sample 1 billion blocks per second, then it would take her hundreds of years before this work could be successful.
b. In the second case (permutation), Eve knows that there are exactly 10 ones in the original text, because the transposition does not change the number of ones (or zeros) in the ciphertext. Eve can launch an exhaustive search attack using only those 64-bit blocks that are exactly 10 units. There is only (64!) / [(10!) (54!)] = 151 473 214 816 of 2 64 words of 64 bits, which are exactly 10 ones. Eve can test all of them in less than 3 minutes if she can do 1 billion tests per second.
Resistant to an exhaustive search attack, a modern block cipher must be designed as a substitution cipher.
Data encryption is extremely important to protect privacy. In this article, I will talk about different types and the encryption methods used to protect data today.
Did you know?
Back in the days of the Roman Empire, 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 possibilities of the Internet continue to grow, more and more of our businesses are being hired online. Among these, the most important are Internet banking, online payment, emails, exchange of private and official messages, etc., which provide for the exchange of confidential data and information. If this data falls into the wrong hands, it can harm not only the individual user, but also the entire online business system.
To prevent this from happening, some network security measures have been taken to protect the transmission of personal data. Chief among these are the data encryption and decryption processes known as cryptography. There are three main encryption methods used in most systems today: hashing, symmetric and asymmetric encryption. In the next lines, I will discuss each of these encryption types in more detail.
Encryption types
Symmetric encryption
With symmetric encryption, normal readable data, known as plain text, is encrypted (encrypted) so that it becomes unreadable. This data scrambling is done with a key. Once the data is encrypted, it can be safely transferred to the receiver. At the recipient, the encrypted data is decoded using the same key that was used for encryption.
Thus, it is clear that the key is the most important part of symmetric encryption. It should be hidden from strangers, since everyone 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 systemsah, the key is usually a string of data that comes from a strong password, or from a completely random source. It is fed into symmetric encryption softwarewhich uses it to classify the input. Data scrambling is achieved using symmetric encryption algorithms such as Data Encryption Standard (DES), Advanced Encryption Standard (AES), or International Data Encryption Algorithm (IDEA).
Limitations
The weakest link in this type of encryption is the security of the key, both in terms of storage and transmission of the authenticated user. If a hacker is able to get hold of this key, he can easily decrypt the encrypted data, destroying the whole point of encryption.
Another disadvantage is due to the fact 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
An asymmetric encryption key works similarly to a symmetric key in that it uses a key to encrypt the transmitted messages. However, instead of using the same key, it uses a completely different key to decrypt this message.
The key used for encryption is available to anyone and everyone on the network. As such, it is known as the "public" key. On the other hand, the key used for decryption is kept secret and intended to be used privately 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.
Limitations
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 trickery networks to trick you into communicating with them while they make you believe you are on a safe line.
To better understand this type of hacking, consider the two interacting parties Sasha and Natasha, and the hacker Sergey 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 receives the public key associated with it, and uses it to encrypt and transmit a false message, Natasha, containing his public key instead of Sasha.
Natasha, thinking that this message came from Sasha, now encrypts it using Sergey's public key, and sends it back. This message was again intercepted by Sergey, decrypted, changed (if desired), encrypted again using the public key that Sasha had originally sent, and sent back to Sasha.
Thus, when Sasha receives this message, he is made to believe that it came from Natasha, and continues to be unaware of foul play.
Hashing
The hashing technique uses an algorithm known as a hash function to generate special line from the given data known as the hash. This hash has the following properties:
- the same data always produces the same hash.
- it is impossible to generate raw data from the hash alone.
- It is impractical to try different combinations of inputs in order 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 received back in its original form (decrypted). This fact ensures that even if the hacker gets his hands on the hash, it will be useless 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.
Limitations
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 a sufficient amount of resources and brute force attacks, a persistent hacker can find data that matches the hash.
Combination of encryption methods
As discussed above, each of these three encryption methods suffers from some disadvantages. However, when a combination of these methods is used, they form a reliable and highly effective encryption system.
Most often, private and public key techniques are combined and used together. The private key method allows for quick decryption, while the public key method offers more secure and more convenient way to transfer the secret key. This combination of techniques 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 password strength. If the system stores the hash of the password, instead of the password itself, it will be more secure, since even if this hash falls into the hands of a hacker, 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. Thus, the actual password will be visible only in brief moments when it needs to be changed or verified, which will significantly reduce the likelihood of it falling into the wrong hands.
Hashing is also used to authenticate data with a secret key. The 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, it can be said that 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 techniques along with strong 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 of the "Ankad" company,
[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:
C \u003d Ek1 (M)
M "\u003d Dk2 (C),
where M (message) - open information (often referred to as "source code" in information security literature);
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 standard GOST 28147-89 (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 ones for of this algorithm transformations. "In other words, a 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, using 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 a "US standard" because the government of this 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 is performed 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 has been 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" came to the input (value 4), then, according to the table, the output value will be 15, ie "1111" (0 a 4, 1 a 11, 2 a 2 ...).
The algorithm, determined 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 performed in each of them differently.
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, i.e. 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, two other modes of operation are intended - gamming and gamming with feedback.
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 register N2 are added modulo 232 with the constant C2 \u003d 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 block of the cipher gamma (in this case, N1 and N2 form the first block of the gamma).
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 required cipher gamut 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 scale 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 a 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, storing the result in N1 and N2.
The cycle repeats 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 transformations, is called a prefix. The size of the prefix is \u200b\u200bchosen based on the required message reliability: with the length of the prefix r bits, the probability that the message change will remain 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 - primarily 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 value of the prefix is \u200b\u200bcalculated and compared with the one sent. If the values \u200b\u200bdo not match, it means that the ciphertext was corrupted 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). 15 algorithms-applicants 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 "Feistel's 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 uses only the XOR operation. These reverse operations are applied during decryption in the reverse order 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 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, 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 this kind of function is often used in asymmetric encryption algorithms, as well as in algorithms used to create electronic digital signatures.
Another important class of functions used in asymmetric encryption are backdoor one-way functions. Their definition says 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 computing 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), and the latter is 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 be up to 2048 bits), direct computation of M [to the power 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 the attacker obtains their values, he will be able to calculate the secret key k2. 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 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 performing 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. The need to protect public keys from substitution also creates unnecessary difficulties - by changing the public key of a legitimate user, an attacker will be able to encrypt an important message using his public key and subsequently easily decrypt it with his private key. However, these disadvantages 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. For those readers who are interested in encryption, the author recommends expanding their horizons with the help of the following books. A full description of encryption algorithms can be found in the following documents: Last time you met the great and terrible domestic ciphers. It was a very difficult lesson, because these cryptosystems guard state secrets. Tell me, how much more intricate? And here, please! In fact, do not be afraid, this time we will not dive so deeply into mathematics and consider encryption modes - you have already learned their principles (well, or have not learned them). Let's go through the most top foreign ciphers and see how they are used in practice. This is the fourth lesson in the Crypt Dive series. All lessons of the cycle in chronological order: So, we will be the first in a series of foreign ciphers to consider 3DES, or rather its closest relative DES (Data Encryption Standard), which, although it is no longer used as such, is the ancestor of 3DES. DES was developed by a team of mathematicians at the IBM Research Laboratory, which included the already familiar Feistel. The first version of the cipher was named "Lucifer", but then it was modified and as a result adopted as the official data encryption algorithm (DEA). It remained the global standard for over twenty years before being replaced by Triple DES. Let's look at how the DES encryption algorithm works. For this it is necessary to recall the work of the Feistel network. DES is a 16-round Feistel network with symmetric encryption keys. The text block length is 64 bits, the round key length is 48 bits. So, let's go through the main stages of DES encryption, leaving out the harsh mathematical side: The initial and final permutations have no meaning for DES cryptography. Both permutations are without keys, and tables for them are predefined. The reason why they are included in DES is unclear, and the designers of DES said nothing about it. It can be assumed that the algorithm was planned to be implemented in hardware (on chips) and that these two complex permutations should have made it difficult to simulate the encryption mechanism in software. Here's everything you need to know about DES. If you delve into how the function defined in the Feistel network works, then everything is fine in it. It performs both permutation and replacement (S-boxes, as you can remember from the previous article), and addition with a round key. But back to triple DES, or Triple DES. It became necessary, since the 56-bit DES key was vulnerable to brute force and with the growth of computing power this problem became more and more acute. Using the technology available today, one million keys can be verified per second. This means that it will take over two thousand years to brute-force decrypt DES using a computer with only one processor. But if we take a computer with one million processor cores that will process keys in parallel, we can check the entire set of keys in about 20 hours. When DES was introduced, the cost of such a computer was several million dollars, but it quickly declined. A special computer was created in 1998 - and found the key in 112 hours. To solve the problem of quickly finding a key, smart foreign cryptographers have proposed using two keys and using DES twice. However, double DES proved to be vulnerable to a meet-in-the-middle attack. To carry out this attack, an attacker needs to have a clear and corresponding ciphertext. The attacker encrypts the plaintext using all possible keys, writing the results to Table 1. Then he decrypts the ciphertext with all possible keys and writes the result to Table 2. Next, the attacker looks for matches in Tables 1 and 2. This type of attack consists of an enumeration of keys on the side of the cipher and plain text and requires about four times more computations than an enumeration of a regular DES key, and quite a lot of memory to store intermediate results. However, in practice, the attack is feasible, making the Double DES algorithm unusable. The situation is quite different with Triple DES. Using three keys and applying the algorithms in the sequence shown in the diagram extended the life of DES by several more years. So what's so great about DES? This encryption algorithm has been thoroughly analyzed. DES possessed two very important qualities of block ciphers - flooding and completeness. It's time to expand your cryptographic vocabulary! DES has been shown to have all the attributes of this property. Although the two blocks of source text do not match only by the rightmost bit, the ciphertext blocks differ by 29 bits. This means that a change in approximately 1.5% of the original text causes a change in approximately 45% of the ciphertext. The completeness effect is that each bit of the ciphertext must depend on many bits of the original text. As we have already found out, in DES, both permutations and replacements are used - all transformations establish the dependence of each bit of the ciphertext on several bits of the original text. Where is DES used? Almost everywhere, its implementation is present in most software libraries. However, who knows how secure DES is today? Although IBM claimed that the algorithm was the result of 17 man-years of intensive cryptanalysis, some people feared that the NSA had inserted a loophole into the algorithm that allows the agency to easily decrypt intercepted messages. The US Senate Intelligence Committee carefully studied this issue and, of course, found nothing, the charges against the NSA were dropped, the results of the study are nevertheless classified. In short, rumors and speculations were circulating in America for a long time about whether DES should be trusted or not. But, as I believe, the situation here is described by the saying "The clever will not say, the fool will not understand." In the end, the NSA admitted that it could not entrust IBM with such an important mission and made several adjustments, such as the S-box assignment. Throughout DES, it has been the target of various cryptanalysis methods. Cryptanalysts never stopped measuring the machines for cracking DES - how long will it take who can decrypt the text. In this regard, an uncountable number of different modifications of this algorithm have appeared, and 3DES is far from the most sophisticated of them.Which encryption is better?
Additional sources of information
Roadmap
3DES
Wonderful DES
The avalanche effect means that small changes in the source text (or key) can cause significant changes in the ciphertext.
