Discrete logarithm
In mathematics, for given real numbers a and b, the logarithm logb a is a number x such that bx = a. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that bk = a.Several important algorithms in public-key cryptography, such as ElGamal, base their security on the hardness assumption that the discrete logarithm problem (DLP) over carefully chosen groups has no efficient solution.The discrete logarithm log10 a is defined for any a in G. A similar example holds for any non-zero real number b.This is the group of multiplication modulo the prime p. Its elements are non-zero congruence classes modulo p, and the group product of two elements may be obtained by ordinary integer multiplication of the elements followed by reduction modulo p. The kth power of one of the numbers in this group may be computed by finding its kth power as an integer and then finding the remainder after division by p. When the numbers involved are large, it is more efficient to reduce modulo p multiple times during the computation.Conversely, logb a does not exist for a that are not in H. If H is infinite, then logb a is also unique, and the discrete logarithm amounts to a group isomorphism On the other hand, if H is finite of order n, then logb a is unique only up to congruence modulo n, and the discrete logarithm amounts to a group isomorphism where Zn denotes the additive group of integers modulo n. The familiar base change formula for ordinary logarithms remains valid: If c is another generator of H, then The discrete logarithm problem is considered to be computationally intractable.Both asymmetries (and other possibly one-way functions) have been exploited in the construction of cryptographic systems.Popular choices for the group G in discrete logarithm cryptography (DLC) are the cyclic groups Zp× (e.g. ElGamal encryption, Diffie–Hellman key exchange, and the Digital Signature Algorithm) and cyclic subgroups of elliptic curves over finite fields (see Elliptic curve cryptography).[6] The Logjam attack used this vulnerability to compromise a variety of internet services that allowed the use of groups whose order was a 512-bit prime number, so called export grade.[5] The authors of the Logjam attack estimate that the much more difficult precomputation needed to solve the discrete log problem for a 1024-bit prime would be within the budget of a large national intelligence agency such as the U.S. National Security Agency (NSA).