Discrete logarithm

In mathematics, a discrete logarithm is an integer k exponent solving the equation b^k = g, where b and g are elements of a finite group. Discrete logarithms are thus the finite group-theoretic analogue of ordinary logarithms, which solve the same equation for real numbers b and g, where b is the base of the logarithm and g is the value whose logarithm is being taken.

No efficient general method for computing discrete logarithms on conventional computers is known. Several important algorithms in public-key cryptography base their security on the assumption that the discrete logarithm problem over carefully chosen groups has no efficient solution.

Examples

Powers of 10

The powers of 10 form an infinite subset G = {..., 0.001, 0.01, 0.1, 1, 10, 100, 1000, ...} of the rational numbers. This set G is a cyclic group under multiplication, and 10 is a generator. For any element g of the group, one can compute log₁₀ g. For example, log₁₀ 10000 = 4, and log₁₀ 0.001 = -3. These are instances of the discrete logarithm problem.

Other base-10 logarithms in the real numbers are not instances of the discrete logarithm problem, because they involve non-integer exponents. For example, the equation log₁₀ 53 = 1.724276... means that 10^1.724276... = 53. While integer exponents can be defined in any group using products and inverses, non-integer exponents in the real numbers arise through quite a different mechanism — the exponential function.

Modular arithmetic

One of the simplest settings for discrete logarithms is the group (Z_p)^×. This is the group of multiplication modulo the prime p. Its elements are 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. Regardless of the specific algorithm used, this operation is called modular exponentiation. For example, consider (Z₁₇)^×. To compute 3⁴ in this group, compute 3⁴ = 81, and then divide 81 by 17, obtaining a remainder of 13. Thus 3⁴ = 13 in the group (Z₁₇)^×.

The discrete logarithm is just the inverse operation. For example, consider the equation 3^k ≡ 13 (mod 17) for k. From the example above, one solution is k = 4, but it is not the only solution. Since 3¹⁶ ≡ 1 (mod 17)—as follows from Fermat's little theorem—it also follows that if n is an integer then 3⁴⁺¹⁶ⁿ ≡ 3⁴ × (3¹⁶)ⁿ ≡ 13 × 1ⁿ ≡ 13 (mod 17). Hence the equation has infinitely many solutions of the form 4 + 16n. Moreover, since 16 is the smallest positive integer m satisfying 3^m ≡ 1 (mod 17), i.e. 16 is the order of 3 in (Z₁₇)^×, these are the only solutions. Equivalently, the set of all possible solutions can be expressed by the constraint that k ≡ 4 (mod 16).

Definition

In general, let G be any group, with its group operation denoted by multiplication. Let b and g be any elements of G. Then any integer k that solves b^k = g is termed a discrete logarithm (or simply logarithm, in this context) of g to the base b. We write k = log_b g. Depending on b and g, it is possible that no discrete logarithm exists, or that more than one discrete logarithm exists. Let H be the subgroup of G generated by b. Then H is a cyclic group, and integral log_b g exists for all g in H. If H is infinite, then log_b g is also unique, and the discrete logarithm amounts to a group isomorphism

$\log _{b}\colon H\rightarrow \mathbf {Z} .$

On the other hand, if H is finite of size n, then log_b g is unique only up to congruence modulo n, and the discrete logarithm amounts to a group isomorphism

$\log _{b}\colon H\rightarrow \mathbf {Z} _{n},$

where Z_n denotes the ring of integers modulo n. The familiar base change formula for ordinary logarithms remains valid: If c is another generator of H, then

$\log _{c}(g)=\log _{c}(b)\cdot \log _{b}(g).$

Algorithms

Unsolved problem in computer science: Can the discrete logarithm be computed in polynomial time on a classical computer? (more unsolved problems in computer science)

The discrete logarithm problem is considered to be computationally intractable. That is, no efficient classical algorithm is known for computing discrete logarithms in general.

Efficient algorithms exist in certain special cases. For example, let G = Z_p be the integers modulo p under addition. The abstract equation b^k = g then amounts to

${\displaystyle bk\equiv g{\pmod {p}}}$

in ordinary arithmetic notation. The extended Euclidean algorithm finds k quickly.

A general algorithm for computing log_b g is to raise b to higher and higher powers k until the desired g is found. This algorithm is sometimes called trial multiplication. It requires running time linear in the size of the group G and thus exponential in the number of digits in the size of the group. Therefore it is an exponential-time algorithm, practical only for small groups G.

More sophisticated algorithms exist, usually inspired by similar algorithms for integer factorization. These algorithms run faster than the naïve algorithm, some of them linear in the square root of the size of the group, and thus exponential in half the number of digits in the size of the group. However none of them run in polynomial time (in the number of digits in the size of the group).

• Baby-step giant-step
• Function field sieve
• Index calculus algorithm
• Number field sieve
• Pohlig–Hellman algorithm
• Pollard's rho algorithm for logarithms
• Pollard's kangaroo algorithm (aka Pollard's lambda algorithm)

There is an efficient quantum algorithm due to Peter Shor.^[1]

Comparison with integer factorization

While computing discrete logarithms and factoring integers are distinct problems, they share some properties:

• both problems are difficult (no efficient algorithms are known for non-quantum computers),
• for both problems efficient algorithms on quantum computers are known,
• algorithms from one problem are often adapted to the other, and
• the difficulty of both problems has been used to construct various cryptographic systems.

Cryptography

There exist groups for which computing discrete logarithms is apparently difficult. In some cases (e.g. large prime order subgroups of groups (Z_p)^×) there is not only no efficient algorithm known for the worst case, but the average-case complexity can be shown to be about as hard as the worst case using random self-reducibility.

At the same time, the inverse problem of discrete exponentiation is not difficult (it can be computed efficiently using exponentiation by squaring, for example). This asymmetry is analogous to the one between integer factorization and integer multiplication. Both asymmetries have been exploited in the construction of cryptographic systems.

Popular choices for the group G in discrete logarithm cryptography are the cyclic groups (Z_p)^× (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).

While there is no publicly known algorithm for solving the discrete logarithm problem in general, the first three steps of the number field sieve algorithm only depend on the group G, not on the specific elements of G whose finite log is desired. By precomputing these three steps for a specific group, one need only carry out the last step, which is much less computationally expensive than the first three, to obtain a specific logarithm in that group.^[2]

It turns out that much Internet traffic uses one of a handful of groups that are of order 1024-bits or less, e.g. cyclic groups with order of the Oakley primes specified in RFC 2409. 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.^[2]

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). The Logjam authors speculate that precomputation against widely reused 1024 DH primes is behind claims in leaked NSA documents that NSA is able to break much of current crypto.^[2]

References

1. Shor, Peter (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/s0097539795293172. MR 1471990.
2. Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex; Heninger, Nadia; Springall, Drew; Thomé, Emmanuel; Valenta, Luke; VanderSloot, Benjamin; Wustrow, Eric; Zanella-Béguelin, Santiago; Zimmermann, Paul (October 2015). "Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice" (PDF).

Further reading

• Richard Crandall; Carl Pomerance. Chapter 5, Prime Numbers: A computational perspective, 2nd ed., Springer.
• Stinson, Douglas Robert (2006), Cryptography: Theory and Practice (3rd ed.), London: CRC Press, ISBN 978-1-58488-508-5