10.2 Computing Discrete Logs – Introduction to Cryptography with Coding Theory, 3rd Edition

10.2 Computing Discrete Logs

In this section, we present some methods for computing discrete logarithms. A method based on the birthday attack is discussed in Subsection 12.1.1.

For simplicity, take α to be a primitive root mod p, so p1 is the smallest positive exponent n such that αn1 (mod p). This implies that

αm1αm2(mod p)m1m2(mod p1).

Assume that

βαx, 0x<p1.

We want to find x.

First, it’s easy to determine x (mod 2). Note that

(α(p1)/2)2αp11(mod p), 

so α(p1)/2±1 (mod p) (see Exercise 15 in Chapter 3). However, p1 is assumed to be the smallest exponent to yield +1, so we must have

α(p1)/21(mod p).

Starting with βαx (mod p), raise both sides to the (p1)/2 power to obtain

β(p1)/2αx(p1)/2(1)x(mod p).

Therefore, if β(p1)/2+1, then x is even; otherwise, x is odd.

Example

Suppose we want to solve 2x9 (mod 11). Since

β(p1)/2951(mod 11), 

we must have x even. In fact, x=6, as we saw previously.

10.2.1 The Pohlig-Hellman Algorithm

The preceding idea was extended by Pohlig and Hellman to give an algorithm to compute discrete logs when p1 has only small prime factors. Suppose

p1=iqiri

is the factorization of p1 into primes. Let qr be one of the factors. We’ll compute Lα(β) (mod qr). If this can be done for each qiri, the answers can be recombined using the Chinese remainder theorem to find the discrete logarithm.

Write

x=x0+x1q+x2q2+ with 0xiq1.

We’ll determine the coefficients x0, x1, xr1 successively, and thus obtain x mod qr. Note that

xp1q=x0p1q+(p1)(x1+x2q+x3q2+)=x0p1q+(p1)n, 

where n is an integer. Starting with βαx, raise both sides to the (p1)/q power to obtain

β(p1)/qαx(p1)/qαx0(p1)/q(αp1)nαx0(p1)/q(mod p).

The last congruence is a consequence of Fermat’s theorem: αp11 (mod p). To find x0, simply look at the powers

αk(p1)/q(mod p), k=0, 1, 2, , q1, 

until one of them yields β(p1)/q. Then x0=k. Note that since αm1αm2m1m2 (mod p1), and since the exponents k(p1)/q are distinct mod p1, there is a unique k that yields the answer.

An extension of this idea yields the remaining coefficients. Assume that q2|p1. Let

β1βαx0αq(x1+x2q+)(mod p).

Raise both sides to the (p1)/q2 power to obtain

β1(p1)/q2α(p1)(x1+x2q+)/qαx1(p1)/q(αp1)x2+x3q+αx1(p1)/q(mod p).

The last congruence follows by applying Fermat’s theorem. We couldn’t calculate β1(p1)/q2 as (β1p1)1/q2 since fractional exponents cause problems. Note that every exponent we have used is an integer.

To find x1, simply look at the powers

αk(p1)/q(mod p), k=0, 1, 2, , q1, 

until one of them yields β1(p1)/q2. Then x1=k.

If q3|p1, let β2β1αx1q and raise both sides to the (p1)/q3 power to obtain x2. In this way, we can continue until we find that qr+1 doesn’t divide p1. Since we cannot use fractional exponents, we must stop. But we have determined x0, x1, , xr1, so we know x modqr.

Repeat the procedure for all the prime factors of p1. This yields x mod qiri for all i. The Chinese remainder theorem allows us to combine these into a congruence for x mod p1. Since 0x<p1, this determines x.

Example

Let p=41, α=7, and β=12. We want to solve

7x12(mod 41).

Note that

411=235.

First, let q=2 and let’s find x mod23. Write xx0+2x1+4x2 (mod 8).

To start,

β(p1)/21220401(mod 41), 

and

α(p1)/27201(mod 41).

Since

β(p1)/2(α(p1)/2)x0(mod 41), 

we have x0=1. Next,

β1βαx0127131(mod 41).

Also,

β1(p1)/2231101(mod 41).

Since

β1(p1)/22(α(p1)/2)x1(mod 41), 

we have x1=0. Continuing, we have

β2β1α2x1317031(mod 41), 

and

β2(p1)/q33151(α(p1)/2)x2(mod 41).

Therefore, x2=1. We have obtained

xx0+2x1+4x21+45(mod 8).

Now, let q=5 and let’s find x mod 5. We have

β(p1)/512818(mod 41)

and

α(p1)/q7837(mod 41).

Trying the possible values of k yields

3701, 37137, 37216, 37318, 37410(mod 41).

Therefore, 373 gives the desired answer, so x3 (mod 5).

Since x5 (mod 8) and x3 (mod 5), we combine these to obtain x13 (mod 40), so x=13. A quick calculation checks that 71312 (mod 41), as desired.

As long as the primes q involved in the preceding algorithm are reasonably small, the calculations can be done quickly. However, when q is large, calculating the numbers αk(p1)/q for k=0, 1, 2, , q1 becomes infeasible, so the algorithm no longer is practical. This means that if we want a discrete logarithm to be hard, we should make sure that p1 has a large prime factor.

Note that even if p1=tq has a large prime factor q, the algorithm can determine discrete logs mod t if t is composed of small prime factors. For this reason, often β is chosen to be a power of αt. Then the discrete log is automatically 0 mod t, so the discrete log hides only mod q information, which the algorithm cannot find. If the discrete log x represents a secret (or better, t times a secret), this means that an attacker does not obtain partial information by determining x mod t, since there is no information hidden this way. This idea is used in the Digital Signature Algorithm, which we discuss in Chapter 13.

10.2.2 Baby Step, Giant Step

Eve wants to find x such that αxβ (mod p). She does the following. First, she chooses an integer N with N2p1, for example N=p1 (where x means round x up to the nearest integer). Then she makes two lists:

  1. αj (mod p) for 0j<N

  2. βαNk (mod p) for 0k<N

She looks for a match between the two lists. If she finds one, then

αjβαNk, 

so αj+Nkβ. Therefore, x=j+Nk solves the discrete log problem.

Why should there be a match? Since 0x<p1N2, we can write x in base N as x=x0+Nx1 with 0x0, x1<N. In fact, x1=[x/N] and x0=xNx1. Therefore,

j=x0, k=x1

gives the desired match.

The list αj for j=0, 1, 2,  is the set of “Baby Steps” since the elements of the list are obtained by multiplying by α, while the “Giant Steps” are obtained in the second list by multiplying by αN. It is, of course, not necessary to compute all of the second list. Each element, as it is computed, can be compared with the first list. As soon as a match is found, the computation stops.

The number of steps in this algorithm is proportional to Np and it requires storing approximately N numbers. Therefore, the method works for primes p up to 1020, or even slightly larger, but is impractical for very large p.

For an example, see Example 35 in the Computer Appendices.

10.2.3 The Index Calculus

The idea is similar to the method of factoring in Subsection 9.4.1 . Again, we are trying to solve βαx (mod p), where p is a large prime and α is a primitive root.

First, there is a precomputation step. Let B be a bound and let p1, p2, , pm,  be the primes less than B. This set of primes is called our factor base. Compute αk (mod p) for several values of k. For each such number, try to write it as a product of the primes less than B. If this is not the case, discard αk. However, if αkpiai (mod p), then

kaiLα(pi)(mod p1).

When we obtain enough such relations, we can solve for Lα(pi) for each i.

Now, for random integers r, compute βαr (mod p). For each such number, try to write it as a product of primes less than B. If we succeed, we have βαrpibi (mod p), which means

Lα(β)r+biLα(pi)(mod p1).

This algorithm is effective if p is of moderate size. This means that p should be chosen to have at least 200 digits, maybe more, if the discrete log problem is to be hard.

Example

Let p=131 and α=2. Let B=10, so we are working with the primes 2,3,5,7. A calculation yields the following:

212(mod131)2853(mod131)21257(mod131)21432(mod131)234352(mod131).

Therefore,

1L2(2)(mod 130)83L2(5)(mod 130)12L2(5)+L2(7)(mod 130)142L2(3)(mod 130)34L2(3)+2L2(5)(mod 130).

The second congruence yields L2(5)46 (mod 130). Substituting this into the third congruence yields L2(7)3496 (mod 130). The fourth congruence yields only the value of L2(3) (mod 65) since gcd(2, 130) = 1. This gives two choices for L2(3) (mod 130). Of course, we could try them and see which works. Or we could use the fifth congruence to obtain L2(3)72 (mod 130). This finishes the precomputation step.

Suppose now that we want to find L2(37). Trying a few randomly chosen exponents yields 37243357 (mod 131), so

L2(37)43+L2(3)+L2(5)+L2(7)41(mod 130).

Therefore, L2(37)=41.

Of course, once the precomputation has been done, it can be reused for computing several discrete logs for the same prime p.

10.2.4 Computing Discrete Logs Mod 4

When p1 (mod 4), the Pohlig-Hellman algorithm computes discrete logs mod 4 quite quickly. What happens when p3 (mod 4)? The Pohlig-Hellman algorithm won’t work, since it would require us to raise numbers to the (p1)/4 power, which would yield the ambiguity of a fractional exponent. The surprising fact is that if we have an algorithm that quickly computes discrete logs mod 4 for a prime p3 (mod 4), then we can use it to compute discrete logs mod p quickly. Therefore, it is unlikely that such an algorithm exists.

There is a philosophical reason that we should not expect such an algorithm. A natural point of view is that the discrete log should be regarded as a number mod p1. Therefore, we should be able to obtain information on the discrete log only modulo the power of 2 that appears in p1. When p3 (mod 4), this means that asking questions about discrete logs mod 4 is somewhat unnatural. The question is possible only because we normalized the discrete log to be an integer between 0 and p2. For example, 262169 (mod 11). We defined L2(9) to be 6 in this case; if we had allowed it also to be 16, we would have two values for L2(9), namely 6 and 16, that are not congruent mod 4. Therefore, from this point of view, we shouldn’t even be asking about L2(9) mod4.

We need the following lemma, which is similar to the method for computing square roots mod a prime p3 (mod 4) (see Section 3.9).

Lemma

Let p3 (mod 4) be prime, let r2, and let y be an integer. Suppose α and γ are two nonzero numbers mod p such that γα2ry (mod p). Then

γ(p+1)/4α2r1y(mod p).

Proof.

γ(p+1)/4α(p+1)2r2yα2r1y(αp1)2r2yα2r1y(mod p).

The final congruence is because of Fermat’s theorem.

Fix the prime p3 (mod 4) and let α be a primitive root. Assume we have a machine that, given an input β, gives the output Lα(β) mod4. As we saw previously, it is easy to compute Lα(β) mod2. So the new information supplied by the machine is really only the second bit of the discrete log.

Now assume αxβ (mod p). Let x=x0+2x1+4x2++2nxn be the binary expansion of x. Using the Lα(β) (mod 4) machine, we determine x0 and x1. Suppose we have determined x0, x1, , xr1 with r2. Let

βrβα(x0++2r1xr1)α2r(xr+2xr+1+).

Using the lemma r1 times, we find

βr((p+1)/4)r1α2(xr+2xr+1+)(mod p).

Applying the Lα (mod 4) machine to this equation yields the value of xr. Proceeding inductively, we obtain all the values x0, x1, , xn. This determines x, as desired.

It is possible to make this algorithm more efficient. See, for example, [Stinson1, page 175].

In conclusion, if we believe that finding discrete logs for p3 (mod 4) is hard, then so is computing such discrete logs mod 4.