Diffie Hellman example

The disclosure of the topic of public key cryptography must begin with the historical path of the problem. Whitfield Diffie and Martin Hellman were the first to ask about the open method of handing over keys. It happened in 1976. The publication made the first attempts to deal with the problem. Their solution was not without flaws, but laid the foundation for a completely different way of thinking in the field of encrypted data transmission.

Prerequisites for creating a Diffie-Hellman algorithm

Up to this point, authentication and encryption were possible only through a shared secret key. With the development of technology, the issue has become more acute. If 10 people need to transfer data among themselves over insecure channels, they will need to exchange passwords with each other. This task looks quite real. Even with the need to update them. After all, for 10 friends you will need only 45 secret keys. And if the contacts will be 100? It will take 4950 passwords. The situation is growing like a snowball.

The main achievement of Diffie and Hellman was the correct formulation of the question and the ingenious answer to it. They suggested that data could be encrypted in one way, and decrypted in another. That is, have 2 keys. The one used for encryption can be left open. Thus, any person will be able to encrypt the message, but only the owners of the second secret key can decrypt it. But how to implement the algorithm for the transfer of such a key? Scientists were able to partially and give an answer.

Short mathematics: groups

The Diffie-Hellman algorithm or protocol (further DH) works with the help of prime numbers. Let a be a sufficiently large number belonging to the set of primes. The algorithm involves the use of a number of 250-500 bytes. Let za- the multiplicative group of the residue ring modulo a, which will be used by the Diffie-Hellman encryption algorithm. It consists of a set of numbers 1, ..., a-1.

Take some element b from group Zaand consider the infinite sequence 1, b, b2, b3, b4... From the fact that the group Zaby definition, is a finite set; sooner or later, the considered sequence {b} will begin to repeat. Set bi= bj(i <j).

Now divide each part of the equality by bi(modulo a) and get bj-i= 1. This means that there is a number k = j-i for which b is truek= 1 (mod a). The smallest k for which this equality holds is called the order of b. To avoid confusion with other special literature, standard mathematical notation is used to explain the Diffie-Hellman system.

Math in DH algorithm

Thus, raising the number b, called the generating element, to a power, we get a sequence of numbers (a set) 1, ..., bk-1. The number of elements in this set is exactly k.

The multiplication property modulo a says that there is at least one number b generating all elements of the group Z *a. In other words, there is a number for which k = a - 1 is true. This property allows us to represent the numbers of the group Z *ain the form of 1, b, b2... ba-2. Such a number b is called a primitive number of a group.

In the sequel, it is easy to prove from the group signs that the set generated by the number b is also a group itself and inherits all the properties of the groups. In other words, operations within a generated group or subgroup can be performed in exactly the same way as in a group modulo a.

Consider the statement.For any element b, its order is a divisor of a-1. It is easy to show. Let a = 7. The number b = 3 is primitive, since 1, ..., b5= 1, 3, 2, 6, 4, 5. Then the number h = 2 will generate the subgroup 1, ..., h2= 1, 2, 4, since h3= 23mod 7 = 1. h = 6 generates a subgroup 1, 6. The sizes of the groups are 3 and 2, respectively. Obviously, they are divisors of the number a-1 = 6.

DH's first algorithm

In the original version, the algorithm worked as follows. A large number a is selected from the set of simple and primitive element b generating Z *a. Both numbers a and b are a public key, they are known to all, including the attackers. How, then, to hide messages?

Diffie-Hellman algorithm

It was at this point that Diffie and Hellman came up with a very ingenious move. Suppose we have two people who communicate with each other: A and B. First, A chooses a random number x from Z *athat is equivalent to choosing a number from {1, ..., a-1}. It then calculates the value using the formula (bxmod a) and sends it to B. In turn, B chooses a certain number y from the same set, calculates the value (bymod a) and sends the result back to A.

Diffie-Hellman basic algorithm

In such a tricky way, it turns out that the secret key looks like bxy. Due to the property of degrees, which says gxy= (gy)x, the source A can calculate the desired value and decrypt the information sent to him. And in the same way, this value is computed by the interlocutor B. Thus, both have the same secret key.

What problems does an intruder experience with this exchange of information? He can intercept numbers gxand gy. And even with the knowledge of public keys, the task of computing gxyis not trivial, since there is no effective algorithm for finding the desired value in the Diffie-Hellman key distribution. This problem is known as the problem of computing the discrete logarithm.

Mediator attack

One of the weaknesses of the Diffie-Hellman primary algorithm is its vulnerability against intermediary attacks. What does it mean? Interlocutor A knows that he communicates with a certain face, but specifically with whom - he has no idea. Thus, an attacker can penetrate into the transfer of information and imitate the interlocutor B when communicating with A, and vice versa. None of them will be able to suspect that something was wrong.

Attacker attack on the algorithm

There is only one area of ​​use in which attacks on the Diffie-Hellman algorithm are excluded. This is a telephone and video call.Here, the interlocutors are able to know each other, so the mediator will not be able to penetrate.

Underwater rocks

In addition to the mediator attack, the DH protocol harbors a host of other problems. For example, one of the drawbacks is the case when the role of the generator of the number a is not a primitive. Then it generates only a subgroup. Due to the narrowing of the number of possible options, the attacker opens the possibility of their search.

Algorithm problems

Problems due to this shortcoming can be avoided if each of the interlocutors checks that the numbers a and b are correct before starting the exchange of data. That is, a is a prime number and b is a primitive. However, when it comes to security through the implementation of certain monotonous optional steps, users often ignore them.

Another serious problem arises on the basis of subgroups modulo a. If the attacker decides to change gxby 1, in order to facilitate the process of eavesdropping, users can easily detect it by checking the number for compliance. However, if he replaces the key with a low order number, users will not be able to suspect anything.And since the number of elements in the set with a low order will be small, the attacker will need to sort out a small number of options for decoding.

Reliability of prime numbers

The DH algorithm uses a large and reliable number of many simple ones. How exactly to choose it? We analyze the steps.

  1. Select the numbers a and k by the formula a = 2k + 1 so that they are simple.
  2. From the set 1, ..., a-1, exclude 1 and a-1.
  3. Take a random number x from the set left after the second step and find the value b = x2(mod a).
  4. Make sure b is not equal to 1 or a-1. If b is equal to one of the forbidden values, you should choose another x. And repeat the operation.

The set (a, k, b) obtained in this way can be considered sufficient for use in the Diffie-Hellman key exchange algorithm. Accordingly, the recipient of the message also needs to check the value, which must be a power of b, and make sure (for example, a function of the Legendre symbol) that it falls into the set generated by the number b.

Using subgroups

The main disadvantage of the above algorithm is insufficient efficiency. Assuming that the length of the prime number a is n bits, then k is n − 1 bits. It turns out that all degrees will be n-1 long.Then the exponentiation operation will consist on average of 3n / 2 multiplications modulo a. This is quite a big process.

DH algorithm in subgroups

In order to cope with this problem, it was decided to use smaller subgroups. What is the performance gain in this case? If the number a consists of 2000 bits, then to calculate bx3000 multiplication operations are required. Through the use of subgroups, this number can be reduced to 400. This significant increase in the efficiency of the algorithm makes possible its full application. For example, the Diffie-Hellman algorithm with three or more participants.

What should be the length of a

Proper selection of the sizes of the parameters of the Diffie-Hellman algorithm is a rather complicated task. A common requirement in the world of cryptography is, for example, the condition that an attacker needs at least 2 to break into the system.128steps. If in the symmetric encryption algorithms to comply with such a requirement is quite easy, in public-key algorithms this is a real problem. If you comply with the above requirement, then the length a must consist of at least 850 bytes.

Prime length

In practice, this size creates big performance problems in the system, since public key operations take much longer than, for example, in symmetric encryption with 128 or 256 bit keys. Then what to do? The minimum length of a public key must start at 2048 bits. Although the longer the key, the higher the security level. Should be considered first and foremost, the performance of the system and its cost. If it allows you to use a key of 4096 bits, you need to do it.

How is the required security level assessed?

The key sizes in symmetric encryption remain unchanged (128, 256 bits) the entire life of the system, while the sizes of the public key are always a variable value. If you have to develop a system that must be used for 30 years and keep data secret for at least 20 years after the system is taken out of use, then the size of the symmetric encryption key must initially be large enough to protect the system for the next 50 years.

Due to obvious performance problems, due to the fact that the Diffie-Hellman algorithm encrypts a much larger number of operations, the requirements for public keys are different.It remains valid for one year and protects the data for the next 20 years, that is, a total of 21 years are used. Due to its variable size, the key can be changed every year and created increasingly longer to ensure the required level of security.

For example, the best estimates show that a key with a length of 256 bytes is capable of protecting data for 20 years, a length of 384 bytes is 35 years, and with a length of 512 bytes it is 47 years, etc. The number is 6800 bits, ensuring that an attacker need 2128Steps to hack it, derived from similar estimates. However, this is only a forecast that you need to trust with great care. You can fairly accurately predict the development of events for 10 years ahead, but at 50 - this is fantastic.

Practical recommendations

Here are some practical tips on using the DH protocol. Choose k as a prime number of 256 bits. This is the minimum that can provide at least some adequate level of security against attacks. For a, choose a number that would have the form Na + 1, where N is an integer. About the size of the number a was said earlier. After that, a random number b is selected and checked for several conditions. First, it cannot be a unit. Second, bk= 1.

In turn, any participant in communication should be convinced of the following:

  • a and k are prime numbers, the length of k is 256 bits, the length of p is quite large.
  • the number k is the divisor of a-1.
  • b is not equal to 1 and bk= 1.

These conditions should be verified even with unconditional trust in the source.

Conclusion

The DH algorithm is an ingenious solution to one of the serious problems and is still actively used in a modified form for modern security requirements in various protocols. The Diffie-Hellman algorithm, for example, is used in some parts of the IKE protocol implementation. However, its use should be methodical and careful due to the presence of obvious problems and serious pitfalls.

Related news

Diffie Hellman example image, picture, imagery


Diffie Hellman example 59


Diffie Hellman example 78


Diffie Hellman example 94


Diffie Hellman example 61


Diffie Hellman example 20


Diffie Hellman example 59


Diffie Hellman example 34


Diffie Hellman example 8


Diffie Hellman example 55


Diffie Hellman example 99