The discrete logarithm problem

The security of many cryptographic techniques depends on the intractability of the discrete logarithm problem. A partial list of these includes Diffie-Hellman key agreement and its derivatives (§12.6), ElGamal encryption (§8.4), and the ElGamal signature scheme and its variants (§11.5). This section summarizes the current knowledge regarding algorithms for solving the discrete logarithm problem.

Unless otherwise specified, algorithms in this section are described in the general setting of a (multiplicatively written) finite cyclic group G of order n with generator a (see Definition 2.167). For a more concrete approach, the reader may find it convenient to think of G as the multiplicative group Z* of order p — 1, where the group operation is simply multiplication modulo p.

  • 3.48 Definition Let G be a finite cyclic group of order n. Let q be a generator of G, and let (3G. The discrete logarithm of в to the base a, denoted loga 3, is the unique integer x, 0 < x < n — 1, such that 3 = ax.
  • 3.49 Example Let p = 97. Then Zg7 is a cyclic group of order n = 96. A generator of Zg7 is

a = 5. Since 532 = 35 (mod 97), log5 35 = 32 in Zg7. □

The following are some elementary' facts about logarithms.

3.50 Fact Let a be a generator of a cyclic group G of order n, and let 3, 7 € G. Let s be an integer. Then logft (,67) = (loga 3 + logQ 7) mod n and log„ (3s) = s loga /3 mod n.

The groups of most interest in cryptography are the multiplicative group F* of the finite field F(/ (§2.6), including the particular cases of the multiplicative group Z* of the integers modulo a prime p, and the multiplicative group F^m of the finite field F2"« of characteristic two. Also of interest are the group of units Z* where n is a composite mteger, the group of points on an elliptic curve defined over a finite field, and the jacobian of a hyperelliptic curve defined over a finite field.

3.51 Definition The discrete logarithm problem (DLP) is the following: given a prime p, a generator a of Z*, and an element 3 e Z*, find the integer x, 0 < x < p - 2, such that

ax = (3 (mod p).

3.52 Definition The generalized discrete logarithm problem (GDLP) is the following: given a finite cyclic group G of order n, a generator a of G, and an element 3 e G, find the mteger

x, 0 < x < n - 1, such that ax = (3.

The discrete logarithm problem in elliptic curve groups and in the jacobians of hyperelliptic curves are not explicitly considered in this section. The discrete logarithm problem in Z* is discussed further in §3.8.

3.53 Note (difficultу of the GDLP is independent of generator) Let a and 7 be two generators of a cyclic group G of order n, and let 3 e G. Let x = logQ (3,y = log7,3, and г = logQ 7. Then ax = f3 = -yy = (az)y. Consequently x = zy mod n, and

This means that any algorithm which computes logarithms to the base a can be used to compute logarithms to any other base 7 that is also a generator of G.

  • 3.54 Note (generalization ofGDLP) A more general formulation of the GDLP is the following: given a finite group G and elements a,f3G, find an integer x such that ax = (3, provided that such an integer exists. In this formulation, it is not required that G be a cyclic group, and, even if it is, it is not required that a be a generator of G. This problem may be harder to solve, in general, than GDLP. However, in the case where G is a cyclic group (for example if G is the multiplicative group of a finite field) and the order of a is known, it can be easily recognized whether an integer x satisfying ax = (3 exists. This is because of the following fact: if G is a cyclic group, a is an element of order n in G, and (3 e G, then there exists an integer x such that ax = (3 if and only if (3n = 1.
  • 3.55 Note (solving the DLP in a cyclic group G of order n is in essence computing an isomorphism between G and Z„) Even though any two cyclic groups of the same order are isomorphic (that is, they have the same structure although the elements may be written in different representations), an efficient algorithm for computing logarithms in one group does not necessarily imply an efficient algorithm for the other group. To see this, consider that every cyclic group of order n is isomorphic to the additive cyclic group Zn, i.e., the set of integers {0.1,2,... , n — 1} where the group operation is addition modulo n. Moreover, the discrete logarithm problem in the latter group, namely, the problem of finding an integer x such that ax = b (mod n) given a,b e Z„, is easy as shown in the following. First note that there does not exist a solution x if d = gcd(a, n) does not divide b (Fact 2.119). Otherwise, if d divides 6, the extended Euclidean algorithm (Algorithm 2.107) can be used to find integers s and t such that as + nt = d, Multiplying both sides of this equation by the integer b/d gives a(sb/d) + n(tb/d) = b. Reducing this equation modulo n yields a(sb/d) = b (mod n) and hence x = (sb/d) mod n is the desired (and easily obtainable) solution.

The known algorithms for the DLP can be categorized as follows:

  • 1. algorithms which work in arbitrary groups, e.g., exhaustive search (§3.6.1), the baby- step giant-step algorithm (§3.6.2), Pollard’s rho algorithm (§3.6.3);
  • 2. algorithms which work in arbitrary groups but are especially efficient if the order of the group has only small prime factors, e.g., Pohlig-Hellman algorithm (§3.6.4); and
  • 3. the index-calculus algorithms (§3.6.5) which are efficient only in certain groups.
 
Source
< Prev   CONTENTS   Source   Next >