The Practical Importance of the Discrete Logarithm Problem
The basic practical implication of the Discrete Logarithm Problem (DLP) is the fact that no classical approach can compute discrete logarithms, which makes them secure and safe. It is important to note that both Diffie-Hellman key exchange (DHKE) and Elgamal encryption scheme (EES) are based on the DLP concept. Key exchange using the Diffie-Hellman protocol is a method of securely exchanging cryptographic keys over a public channel. These are key protocols that were originally conceptualized by Ralph Merkle and named after Martin Hellman and Whitfield Diffie. DHKE is one of the first practical examples of public key exchange.
Today, DHKE is used for many applications, such as, for example, Proton Mail, SSH, and GPG. In simple terms, the protocol operates by integrating a 1-way function, where the key is partially transferred to the beneficiary in order to avoid the capturing by an outside party. The one-way function for party A is A = ga mod p, and the function makes it impossible to decode in the reverse order. In order to create a secret key unknown to anyone else, both subscribers generate large random numbers: the first subscriber – the number a, the second subscriber – the number b. Then the first subscriber calculates the value of A and sends it to the second, and the second calculates B and passes it to the first.
It is assumed that an attacker can obtain both of these values, but not modify them, that is, he does not have the opportunity to intervene in the transfer process. At the second stage, the first subscriber calculates the value from B based on his a and received through the network B, and the second subscriber calculates the value from A based on his b and received through the network A. The cryptographic strength of the Diffie-Hellman algorithm is based on the assumed complexity of the discrete logarithm problem. However, although the ability to solve the problem of discrete logarithms will allow a person to crack the Diffie-Hellman algorithm, the converse is still an open question.
It is important to note the fact that the Diffie-Hellman algorithm works only on communication lines that are reliably protected from modification. If it were applicable on any open channels, it would have long removed the problem of key distribution and, possibly, replaced all asymmetric cryptography. However, in cases where data modification is possible in the channel, there is an obvious possibility of wedging an intermediary attacker into the key generation process according to the same scheme as for asymmetric cryptography. EES can be considered as a small extension of DHKE protocol, where it allows to send the encrypted message in a direct manner.
However, the basic principle is the fact that both use discrete logarithms to encrypt data. The cryptographic strength of the protocol is based on the notion that it highly difficult to solve problems, such as the identification of the element of polynomial-time of decomposition of multiplicative sections into primary factors. In addition, it is challenging to define if the finite field system can be determined by discrete logarithms operations. Then it is possible to find discrete logarithms with comparable laboriousness, for example, by algorithms, and the potential cracker does not have such a decomposition. In the presence of large simple divisors in the decomposition, the required database becomes very large, which significantly slows down the operation of the algorithm.