2.5.2. Asymmetric encryption algorithms

Historically, the first public key system was the Diffie-Hellman method of exponential key exchange , developed in 1976. The method is designed to transmit the secret key of symmetric encryption. Two participants A and B are involved in the exchange. At first they choose large prime numbers n   and g < n   (these numbers are not secret). Then participant A chooses a large integer x, calculates X = g ^x mod n   and passes X to participant B. B in turn chooses a large integer y , computes Y = g ^y mod n   and transfers Y to participant A. B calculates K ^' = X ^y mod n , A calculates K ^{' '} = Y ^x mod n . It is easy to notice that

K ^' = K ^{' '} = g ^xy mod n , and both participants can use this value as the key of symmetric encryption. The cryptographic stability of this method is determined by the complexity of calculating the discrete logarithm in a finite field. Indeed, an attacker can find out such algorithm parameters as n , g , X , Y , but calculate the x values ​​from them   or y - a task that requires very large computing power and time. The method can easily be generalized to the case of a key exchange of a larger number of participants. Using the Diffie - Hellman method in practice should be accompanied by certification of "public" keys X and Y. Otherwise, the attacker can conduct an attack, which is known as the “man in the middle” (man-in-the-middle), when the messages transmitted by participants A and B are intercepted by the attacker and replaced with messages X ^' and Y ^' , calculated based on his private key. As a result, two connections will be established: “A is the evil owner” and “B is the attacker”, and A and B will be sure that they are exchanging messages with each other. It should also be noted that the Diffie - Hellman algorithm is not an asymmetric encryption algorithm; when using it, it is necessary to perform encryption using a symmetric cipher. An example of a truly asymmetric encryption algorithm based on the discrete logarithm problem is the El Gemal algorithm, developed in 1985. A sequence of actions for key generation, encryption and decryption is presented in Fig. 2.14.

Fig.2.14. Al Gemal algorithm encryption scheme

It is necessary to clarify the decryption procedure. Since a ^x º g ^kx mod p , we have:

Thus, the encoded message M is divided into parts, each of which m is interpreted as a number in the range [0 .. p -1], and an encryption operation is performed according to the scheme in Fig. 2.14. In practice, when using this algorithm, it is recommended to choose keys of 768, 1024 and 1536 bits in size.

The very first, really asymmetric algorithm was the RSA algorithm, named after the first letters of the names of its developers. The algorithm was developed in 1978. RSA cryptographic strength is based on the task of factoring (factoring) large (more than 200 binary digits) integers.

The key generation, encryption, and decryption procedures for this algorithm are presented in Fig. 2.15.

Fig.2.15. RSA encryption scheme

At the key generation stage, a pair of keys is formed: a closed d and an open e . Data encryption should begin with its division into blocks m of size k = [log ₂ ( n )] bits each, so that block m can be considered as an integer in the range [0 .. n- 1]. The reversibility of encryption and decryption RSA requires proof. From the Euler theorem it is known that for two integers n   and x, such that ( n , x ) = 1,   performed:

x ^{j ( n )} º1 mod n , (2.2)

where j ( n ) is the Euler function whose value is equal to the number of numbers less than n   and mutually simple with it. For n = p × q from the RSA algorithm, where p   and q are prime numbers, you can write j ( n ) = ( p - 1) ( q - 1).

Then (2.2) can be rewritten in the form:

x ^{( p-1 ) ( q-1 )} º1 mod n (2.3)

Let us raise both sides of (2.3) to the power –y:

x ^{( -y ) ( p-1 ) ( q-1 )} º 1 ^{( -y )} mod n º 1 mod n (2.4)

Multiply both sides of (2.4) by x :

           x ^{( -y ) ( p-1 ) ( q-1 ) +1} mod n = x (2.5)

But when generating keys, we got e and d such that ed º 1 mod ( p -1) ( q -1), which means that in (2.5) you can replace 1 -y ( p-1 ) ( q-1 ) to ed:

           x ^ed   mod n = x

Then, if we build a ciphertext c = m ^e mod n   to degree d   modulo n , as we do when decrypting, we get:

( c ^d   ) mod n = ( m ^e mod n ) ^d mod n = m ^ed mod n = m

Obviously, the main task of a cryptanalyst in breaking this cipher is to find out the private key d . To do this, it must perform the same actions as the recipient when generating the key — solve the integer equation in integers   + y ( p -1) ( q -1) = 1 relative to d   and   y . However, if the recipient knows the parameters in the equation p   and q , the cryptanalyst knows only the number n - the product of p   and q . Therefore, he needs to factor the number n , that is, factor it. To solve the factorization problem, a number of algorithms have been developed to date: a quadratic sieve, a generalized numerical sieve, and an elliptic curve method. But for large numbers it is a very time consuming task. Its complexity can be confirmed by the following figures [11]: to factorize the number 100D (the number with 100 decimal places) required computational power 7MY (1 MY - the value equal to the annual computer performance, performing one million integer instructions per second), for 130D - 500MY , for the number 140D - 2000 MY. Modern cryptography to secure encryption keys RSA refers keys with a length of 768, 1024, 2048 bits.

It should be noted that the uniqueness of the method of recovering m by c and e was not proved mathematically.   decomposition of n   by factors. Cryptanalysts do not exclude that a completely different method of RSA cryptanalysis can be discovered, and then the algorithm will become completely unsuitable for practical use.

Another problem is the generation of large primes for the algorithm. Strict proof of the simplicity of the generated random number requires solving the same factorization problem, therefore most of the commonly accepted tests establish the simplicity of a number with a certain probability. What happens if p or q turns out to be composite? Then the module n will have three or more divisors. Accordingly, some dividers will be less than the recommended value, which, in turn, opens up opportunities for an attack by factoring the module.

Some attacks exploit the RSA protocol utilization vulnerability [12]. It is important to understand that the use of RSA by itself does not provide the required level of system security. Consider some possible attacks on the RSA encryption protocol.

If the attacker managed to intercept the message c , encrypted using the public RSA-key of user A, then for disclosing m = c ^d, he first chooses the first random number r , less than n , and then using the public key A e , calculates

x = r ^e mod n,

y = xc mod n ,

t = r ^-1 mod n .

If x = r ^e mod n , then r = x ^d mod n

Further, the attacker in some way forces A to encode the message y   on   his secret key . A sends an attacker

u = y ^d mod n

Now the attacker reveals m , calculating

tu mod n = r ^-1 y ^d mod n = r ^-1 x ^d c ^d mod n = c ^d mod n = m

Another known attack is an attack based on a common RSA module.

If we distribute the same module n to all crypto network subscribers, but each has its own values ​​of the exponents ( e 1, d 1), ( e 2, d 2), then when encrypting the same message with different exponents (with a fixed module), provided such that e 1 and   e 2 - mutually simple numbers, the plaintext can be revealed even with unknown decryption keys. Let there be given: m - plaintext, e ₁ and e ₂ - two encryption keys, n - a common module. The ciphertexts of the message are:

c ₁ = m ^e1 mod n ,

c ₂ = m ^e2 mod n ,

A cryptanalyst knows n , e ₁ , e ₂ , c ₁ and c ₂ . Since e ₁ and e ₂ are mutually prime numbers, using the advanced Euclidean algorithm, one can find such numbers r and s that

re ₁ + se ₂ = 1.

Assuming r is negative (either r or s must be negative), you can again use the Euclidean extended algorithm to calculate c ₁ ^-1 . Then

( c ₁ ^-1 ) ^{- r} c ₂ ^s = ( m ^e1 mod n ) ^r ( m ^e2 mod n ) ^s = m ^{e1r + e2s} mod n = m mod n .

Thus, the use of the parameter n common for the user group may adversely affect the security level of the crypto network.

Another requirement for cryptographic protocols arises from the possibility of an attack of "encrypting short messages." It is known that the RSA cryptosystem has a low cryptographic strength with a short message encrypted on a small e . Indeed, with c = m ^e < n, the plaintext m can be recovered from ciphertext c using the root extraction procedure. However, countermeasures are also obvious - either the public key e must be large enough or the open text must not be short. The choice of small e is due to considerations of the computational efficiency of encryption and signature verification. Thus, a reasonable approach is to artificially build up short open texts (“stuffing”).

For the practical cryptographic strength of the RSA algorithm, it is necessary to observe a number of restrictions: the secret key d should not be too small, the numbers p and q   must very closely match in order of length, the numbers ( p +1) and ( q +1) should contain in their decomposition large prime dividers. These restrictions take into account a number of possible attacks on RSA that are not covered in this manual.

Consider another asymmetric coding algorithm - the Rabin scheme .

This algorithm is similar to RSA coding, but instead of building a message to the power of e , encryption uses the operation of building a message block in a square, which favorably affects the speed of the algorithm without sacrificing cryptographic strength (Figure 2.16).

Fig.2.16. Rabin algorithm encryption scheme

Compared to RSA, Rabin's scheme has a smaller public key n and provides less encryption time. The disadvantage of the scheme is that as a result of decryption, 4 different values ​​are obtained, only one of which coincides with the original message. To resolve this situation, it is necessary to add some label to the encoded message, which will uniquely distinguish it on the receiving side.

The list of asymmetric encryption algorithms on this, of course, is not exhausted; a more complete list of them is given in [12]. In conclusion, I would like to mention two more algorithms that are based on other difficult-to-calculate tasks. McAlees' cryptosystem is based on the methods of the noise-resistant coding theory. This cryptosystem uses error-correcting code decoding and uses the fact that the linear code generally does not have a polynomial decoding algorithm. A cryptosystem based on elliptic curves uses the properties of an elliptic curve (EC), which is a set of points on the plane that satisfy the equation:

y ² = x ³ + ax + b mod p,

The cryptographic stability of EC is based on the difficulty of solving the discrete logarithm problem in a group of points of an elliptic curve over a finite field. The cryptosystems on elliptic curves will be discussed in more detail in Chapter 4.