Читать книгу Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen - Страница 76

Given a prime and , where is one of the numbers , find .

It is called the discrete log problem because when is chosen as the logarithmic base. A solution to the discrete log problem (i.e. finding an algorithm for calculating in a reasonable amount of time) would imply a solution to the Diffie–Hellman problem. The converse statement is not known to be true, although there is experimental evidence pointing in that direction.

We should point out that, for security, one wants to be well‐behaved meaning that has large factors. The ideal case is when , where itself is prime. For example, take so In the ideal case, has the greatest possible number of different generators (for its size) so that it is easy to find a generator. However, such primes , known as Sophie‐Germain primes, are conjectured to be rare. In any event, only a finite number are known to exist.

Using the Diffie–Hellman idea, it is possible to construct a public‐key cryptosystem called the El Gamal Cryptosystem.