The length of the encryption key. Public and private key: what are they used for? Generation of random and pseudo-random sequences

Many modern public-key encryption algorithms are based on the unidirectional factorization function of a number that is the product of two large prime numbers. These algorithms can also be subjected to an attack similar to the brute-force attack used against secret-key ciphers, with one difference: you don't need to try every key, you just need to be able to factor a large number.

Of course, factoring a large number into factors is a difficult task. However, a reasonable question immediately arises, how difficult. Unfortunately for cryptographers, the difficulty of solving it is decreasing. And to make matters worse, this difficulty is dropping at a much faster rate than previously expected. For example, in the mid-1970s, it was believed that it would take tens of quadrillions of years to factor a number of 125 digits. And just two decades later, using computers connected to the Internet, it was possible to factor out a number of 129 digits. This breakthrough became possible due to the fact that over the past 20 years not only new, faster methods of factoring large numbers have been proposed, but also the productivity of the computers used has increased.

Therefore, a qualified cryptographer must exercise very great care and discretion when it comes to the length of the public key. It is necessary to consider how valuable the information classified with its help is and how long it should remain secret to outsiders.

And why, one asks, not to take a 10,000-bit key? After all, then all questions related to the stability of an asymmetric encryption algorithm with a public key, based on the decomposition of a large number into factors, will disappear. But the fact is that ensuring sufficient strength of the cipher is not the only concern of the cryptographer. There are additional considerations that affect the choice of key length, and among them are issues related to the practical feasibility of the encryption algorithm for the chosen key length.

To estimate the length of the public key, we will measure the computing power available to the cryptanalyst in the so-called pug-yo, i.e., the number of operations that a computer capable of running at a speed of 1 million operations per second performs in a year. Let's say that a hacker has access to computer resources with a total computing power of 10,000 pug-years, a large corporation - 10 7 pug-years, the government - 10 7 pug-years. These are quite realistic numbers, given that the 129-digit decomposition project mentioned above used only 0.03% of the computing power of the Internet, and to achieve this, they did not need to take any extraordinary measures or go beyond the law.

Let us also assume that computing power increases 10 times every 5 years, and the method that is used to factorize large numbers allows this to be done with the complexity indicated in Table 1. 6.3.

Table 6.3. The complexity of factoring large numbers.

The assumptions made make it possible to estimate the length of a strong public key depending on the period during which it is necessary to keep the data encrypted with it in secret (Table 6.4). It must be remembered that public key cryptographic algorithms are often used to protect very valuable information for a very long period of time. For example, in electronic payment systems or when notarizing an electronic signature. The idea of spending several months factoring out a large number might seem very appealing to someone if they end up being able to pay for their purchases with your credit card. Also, I don't think you'd be happy to be called into a probate court 20 years from now and defend the impossibility of forging your grandfather's electronic signature he used to make a will in your favor.

Year	Hacker	large corporation	Government
2000	1024	1280	1536
2005	1280	1536	2048
2010	1280	1536	2048
2015	1536	2048	2048

With given in table. 6.4 not all reputable cryptographers agree with the data. Some of them flatly refuse to make any long-term forecasts, considering it a useless undertaking. Others, for example, specialists from the NSA, are overly optimistic, recommending a public key length of only 512-1024 bits for digital signature systems, which, in the light of the data from Table. 6.4 is completely insufficient to provide adequate long-term protection.

public key, noted that this requirement denies the whole essence of cryptography, namely the ability to maintain universal secrecy in communications.

The second task is the need to create such mechanisms, using which it would be impossible to replace any of the participants, i.e. need digital signature. When using communications for a wide range of purposes, such as commercial and private purposes, electronic messages and documents must have the equivalent of a signature contained in paper documents. It is necessary to create a method by which all participants will be convinced that the e-mail was sent by a particular participant. This is a stronger requirement than authentication.

Diffie and Hellman achieved significant results by proposing a way to solve both problems that is radically different from all previous approaches to encryption.

Let's look at the common features first. encryption algorithms with a public key and requirements for these algorithms. Let us define the requirements to be met by an algorithm that uses one key for encryption and another key for decryption, and it is computationally impossible to determine the decryption key if only the encryption algorithm and the encryption key are known.

In addition, some algorithms, such as RSA, have the following characteristic: each of the two keys can be used for both encryption and decryption.

We will first consider algorithms that have both properties, and then move on to public-key algorithms that do not have the second property.

When describing symmetric encryption and public key encryption, we will use the following terminology. key used in symmetric encryption, we will call secret key. The two keys used in public key encryption will be called public key And private key. The private key is kept secret, but we will refer to it as private key rather than secret to avoid confusion with the key used in symmetric encryption. The private key will be denoted KR , the public key - KU .

We will assume that all participants have access to each other's public keys, and private keys are created locally by each participant and, therefore, should not be distributed.

At any time, a participant may change its private key and publish the public key that makes up the pair, replacing the old public key with it.

Diffie and Hellman describe the requirements that encryption algorithm with a public key.

It is computationally easy to create a pair (KU public key, KR private key).
It is computationally easy, given the public key and the unencrypted message M, to create the corresponding encrypted message:
It is computationally easy to decrypt a message using the private key:
M = D KR [C] = D KR ]
It is computationally impossible, knowing the public key KU , to determine the private key KR .
It is computationally impossible, knowing the public key KU and the encrypted message C , to recover the original message M .
A sixth requirement can be added, although it does not hold for all public key algorithms:
Encryption and decryption functions can be applied in any order:
M = E ku]

These are strong enough requirements that introduce the notion of . One way function such a function is called, in which each argument has a unique inverse value, while it is easy to calculate the function itself, but it is difficult to calculate the inverse function.

Usually "easy" means that the problem can be solved in polynomial time of the length of the input. Thus, if the length of the input is n bits, then the calculation time of the function is proportional to n a , where a is a fixed constant. Thus, the algorithm is said to belong to the class of polynomial algorithms P. The term "hard" means a more complicated concept. In the general case, we will assume that the problem cannot be solved if the effort to solve it is greater than the polynomial time of the input value. For example, if the length of the input is n bits, and the evaluation time of the function is proportional to 2 n , then this is considered a computationally impossible task. Unfortunately, it is difficult to determine whether a particular algorithm exhibits such complexity. Moreover, traditional notions of computational complexity focus on the worst-case or average-case complexity of an algorithm. This is unacceptable for cryptography, where it is required that the function cannot be inverted for all or almost all values of the inputs.

Back to definition unilateral function with sunroof, which, like one way function, is easy to compute in one direction and difficult to compute in the opposite direction until some additional information is available. With this additional information, the inversion can be computed in polynomial time. Thus, one way function with sunroof family owned one-way functions f k such that

We see that the development of a particular public key algorithm depends on the discovery of the corresponding unilateral function with sunroof.

Cryptanalysis of public key algorithms

As in the case symmetric encryption, encryption algorithm with a public key is vulnerable to frontal attack. The countermeasure is standard: use large keys.

A public key cryptosystem uses certain non-invertible mathematical functions. The complexity of computing such functions is not linear in the number of key bits, but increases faster than the key. Thus, the key size must be large enough to make a frontal attack impractical, and small enough to allow practical encryption. In practice, the key size is made such that a brute-force attack is impractical, but as a result, the encryption speed is slow enough for the algorithm to be used for general purposes. Therefore, public key encryption is currently mainly limited to key management and signature applications that require encryption of a small block of data.

Another form of attack is to find a way to compute the private key given the public key. There is no way to mathematically prove that a given form of attack is out of the question for a particular public key algorithm. Thus, any algorithm, including the widely used RSA algorithm, is suspicious.

Finally, there is a form of attack that is specific to how public key systems are used. This is an attack on a likely message. Suppose, for example, that the message being sent consists solely of a 56-bit session key for a symmetric encryption algorithm. An adversary can encrypt all possible keys using the public key, and can decrypt any message that matches the ciphertext being transmitted. Thus, regardless of the key size of the public key scheme, the attack is reduced to a brute-force attack on a 56-bit symmetric key. Protection against such an attack consists in adding a certain number of random bits to simple messages.

Basic Uses for Public Key Algorithms

The main uses of public key algorithms are encryption/decryption, signature creation and verification, and key exchange.

Encryption with a public key consists of the following steps:

Rice. 7.1.

User B creates a pair of keys KU b and KR b used to encrypt and decrypt the transmitted messages.
User B makes available his encryption key in some secure way, i.e. public key KU b . The paired private key KR b is kept secret.
If A wants to send a message to B, he encrypts the message using B's public key KU b .
When B receives the message, he decrypts it using his private key KR b . No one else can decrypt the message, since only B knows this private key.

If the user (end system) securely stores his private key, no one will be able to spy on the messages being transmitted.

Creating and verifying a signature consists of the following steps:

Rice. 7.2.

User A generates a pair of keys KR A and KU A , used to create and verify the signature of transmitted messages.
User A makes available his verification key in some secure way, i.e.

Cryptographic keys can differ from each other in their length, which, consequently, in the strength of a given key. The longer the key, the more possible combinations of selection. For example, if you use a key with a length of 128 bits, then the key will be one of 2128 possible options. The kidnapper is more likely to win the lottery than pick up a possible key. On a standard home PC, for a 40-bit key, you need to spend 6 hours to sort through all possible ones. However, even keys with a length of 128 bits can be vulnerable, and professionals can crack them.

The reliability of the symmetric directly depends on the strength of the key length and the encryption algorithm. If, for example, that the algorithm is ideal, then it can be decrypted only by enumeration of all keys. To implement this method, you need some ciphertext, and plaintext. For example, if the key length is 128 bits, then the supercomputer will need 1025 years to enumerate all the keys. The question immediately arises why not use a key length of over9999, or 4000 bytes.
At the same time, cryptography is a very subtle science, where we want to increase reliability, we can, on the contrary, lower it with minimal changes in the algorithm. When checking the strength of an encryption algorithm, they check the conditions under which an attacker can receive a sufficient amount of plaintext or ciphertext. Fortunately, in reality there are very few people who are really highly qualified to implement successful attacks to decrypt data.

Many public key encryption algorithms implement factorization functions for a number that is the product of two large primes. in the 70s, it took tens of quadrillions of years to decompose a number of 125 digits. Today it does not consist of much time. Above, the question was asked why not use overr9999 long keys, because then the question of durability and reliability will not arise. It is necessary to take into account not only the reliability and secrecy, but also the time of value of information and the time spent on the implementation of such encryption. For example, information will lose its value in 10 years, and we spent financial resources that will pay off only after 20 years, where is the logic?

To evaluate a public key, one must measure the cryptanalytic computational power in pug-years. This is the number of operations per second that are performed in a year. For example, corporations have 107 pug-years, and governments have 109 pug-years. In Fig.1. you can see how long it takes to decompose numbers of different lengths. Often, all the same, valuable information is encrypted for a long time. The idea of spending a couple of months factoring a large number in order to be able to shop with someone else's credit card is attractive. The recommended length of public keys is shown in Figure 2.

Picture 1

Drawing - 2

A cryptanalytic attack against encryption algorithms is traditionally aimed at the thinnest or weakest point of the algorithm. Typically, enterprises use hybrid systems, these are systems using a public and private key. The strength of each algorithm must correspond to sufficient reliability. In Fig.3. key length pairs for non-symmetric and symmetric algorithms are shown.

To estimate the length of a public key, we will measure the computing power available to a cryptanalyst in so-called pug-years, that is, the number of operations that a computer capable of operating at a speed of 1 million operations per second performs in a year. Let's say that a hacker has access to computer resources with a total computing power of 10,000 pug-years, a large corporation - 107 pug-years, the government - 109 pug-years. These are quite realistic numbers when you consider that the 129-digit decomposition project mentioned above used only 0.03% of the computing power of the Internet, and to achieve this, they did not need to take any extraordinary measures or go beyond law.

Let us also assume that computing power increases 10 times every 5 years, and the method that is used to factorize large numbers allows this to be done with the complexity indicated in Table 1. 6.3.

Table 6.3. The complexity of factoring large numbers

The main purpose of using SSL certificates is to encrypt data transmitted to the server from the client and to the client from the server. To ensure the security of such a connection, modern browsers use the TLS algorithm based on X.509 certificates. This algorithm uses asymmetric encryption to generate a session key for symmetric encryption. The latter is used directly for data transfer after a secure connection has been established.

What is a key in cryptography?

A key in cryptography is secret information that is used in cryptography to encrypt and decode messages, to digitally sign and verify it, to calculate message authentication codes, and so on. How reliable a key is is determined by the so-called key length, which is measured in bits. The standard key length for SSL certificates is 128 or 256 bits. The key length of the root certificate authority (root certificate) must not be less than 4096 bits. All certificate authorities with which we cooperate provide SSL certificates with a key that fully complies with modern standards:

Public and private key in asymmetric encryption

Asymmetric encryption uses pair of keys: open (Public key) And closed, also called secret (private key). The public and private keys in this case allow the cryptographic algorithm to encrypt and decrypt the message. Messages encrypted with the public key can only be decrypted with the private key. The public key is published in the owner's certificate and is available to the connecting client, while the private key is stored by the certificate owner. The public and private keys are interconnected by mathematical dependencies, so it is impossible to pick up a public or private key in a short time (validity period of the certificate). That is why the maximum validity period of SSL certificates of a higher level of protection is always lower. So, you can order a maximum of 2 years. At the same time, when ordering a new SSL certificate or renewing an old one, it is important to generate a new CSR request, since your private key is tied to it, and it is better to update it when a new SSL certificate is issued. The client interacts with the server in the following way:

the browser encrypts the request based on the public key and sends it to the server;
the server, using the private key, decrypts the received message;
the server encrypts its digital identifier with a private key and transmits it to the client;
the client checks the server ID and sends its own;
after mutual authentication, the client encrypts the key of the future session with the public key and transmits it to the server;
all subsequent messages that are sent between the client and the server are signed with the session key and encrypted using the public and private keys.

This provides several security points:

the possibility of information leakage is excluded - when intercepted, it cannot be decrypted;
the server confirms its address and identifier, the possibility of redirecting to another site is cut off (phishing);
the client is assigned an individual session, which makes it possible to distinguish it from other clients more reliably;
once a secure session is established, all messages are encrypted using the client's identity, and cannot be intercepted or altered unnoticed.

In the general case, encryption with a public and private key can be considered as a case for which two keys are used: one can only be closed, the other can be opened. If the case was closed with the first key, only the second one can open it, if it was closed with the second key, the first one will be required to open it. You can clearly see this in the diagram above.