x ← (x + F (β )) mod q, β ← H(β )

i←i+1

if i < q then

output (x ’ x )i’1 mod q

else

output “fail”

To analyze this algorithm, let us de¬ne β1 , β2 , . . . , as follows: β1 := ± and

for i > 1, βi := H(βi’1 ).

Exercise 11.5. Show that each time the main loop of the algorithm is

entered, we have β = βi = γ x ±i , and β = β2i = γ x ±2i .

Exercise 11.6. Show that if the loop terminates with i < q, the value

output is equal to logγ ±.

Exercise 11.7. Let j be the smallest index such that βj = βk for some

index k < j. Show that j ¤ q + 1 and that the loop terminates with i < j

(and in particular, i ¤ q).

Exercise 11.8. Assume that F is a random function, meaning that it is cho-

sen at random, uniformly from among all functions from G into {0, . . . , q’1}.

Show that this implies that H is a random function, meaning that it is uni-

formly distributed over all functions from G into G.

Exercise 11.9. Assuming that F is a random function as in the previous

exercise, apply the result of Exercise 6.27 to conclude that the expected run-

ning time of the algorithm is O(q 1/2 len(q) len(p)2 ), and that the probability

that the algorithm fails is exponentially small in q.

11.3 The Di¬e“Hellman key establishment protocol

One of the main motivations for studying algorithms for computing discrete

logarithms is the relation between this problem and the problem of break-

Finding generators and discrete logarithms in Z—

276 p

ing a protocol called the Di¬e“Hellman key establishment protocol,

named after its inventors.

In this protocol, Alice and Bob need never to have talked to each other

before, but nevertheless, can establish a shared secret key that nobody else

can easily compute. To use this protocol, a third party must provide a

“telephone book,” which contains the following information:

• p, q, and γ, where p and q are primes with q | (p ’ 1), and γ is an

element generating a subgroup G of Z— of order q;

p

• an entry for each user, such as Alice or Bob, that contains the user™s

name, along with a “public key” for that user, which is an element

of the group G.

To use this system, Alice posts her public key in the telephone book,

which is of the form ± = γ x , where x ∈ {0, . . . , q ’ 1} is chosen by Alice at

random. The value of x is Alice™s “secret key,” which Alice never divulges

to anybody. Likewise, Bob posts his public key, which is of the form β = γ y ,

where y ∈ {0, . . . , q ’ 1} is chosen by Bob at random, and is his secret key.

To establish a shared key known only between them, Alice retrieves Bob™s

public key β from the telephone book, and computes κA := β x . Likewise,

Bob retrieves Alice™s public key ±, and computes κB := ±y . It is easy to see

that

κA = β x = (γ y )x = γ xy = (γ x )y = ±y = κB ,

and hence Alice and Bob share the same secret key κ := κA = κB .

Using this shared secret key, they can then use standard methods for

encryption and message authentication to hold a secure conversation. We

shall not go any further into how this is done; rather, we brie¬‚y (and only

super¬cially) discuss some aspects of the security of the key establishment

protocol itself. Clearly, if an attacker obtains ± and β from the telephone

book, and computes x = logγ ±, then he can compute Alice and Bob™s shared

key as κ = β x ” in fact, given x, an attacker can e¬ciently compute any

key shared between Alice and another user.

Thus, if this system is to be secure, it should be very di¬cult to com-

pute discrete logarithms. However, the assumption that computing discrete

logarithms is hard is not enough to guarantee security. Indeed, it is not

entirely inconceivable that the discrete logarithm problem is hard, and yet

the problem of computing κ from ± and β is easy. The latter problem ”

computing κ from ± and β ”is called the Di¬e“Hellman problem.

As in the discussion of the RSA cryptosystem in §7.8, the reader is warned

that the above discussion about security is a bit of an oversimpli¬cation. A

11.3 The Di¬e“Hellman key establishment protocol 277

complete discussion of all the security issues related to the above protocol

is beyond the scope of this text.

Note that in our presentation of the Di¬e“Hellman protocol, we work with

a generator of a subgroup G of Z— of prime order, rather than a generator

p

— . There are several reasons for doing this: one is that there are no

for Zp

known discrete logarithm algorithms that are any more practical in G than

in Z— , provided the order q of G is su¬ciently large; another is that by

p

working in G, the protocol becomes substantially more e¬cient. In typical

implementations, p is 1024 bits long, so as to protect against subexponential-

time algorithms such as those discussed later in §16.2, while q is 160 bits long,

which is enough to protect against the square-root-time algorithms discussed

in §11.2.2 and §11.2.5. The modular exponentiations in the protocol will run

several times faster using “short,” 160-bit exponents rather than “long,”

1024-bit exponents.

For the following exercise, we need the following notions from complexity

theory.

• We say problem A is deterministic poly-time reducible to prob-

lem B if there exists a deterministic algorithm R for solving problem

A that makes calls to a subroutine for problem B, where the running

time of R (not including the running time for the subroutine for B)

is polynomial in the input length.

• We say that A and B are deterministic poly-time equivalent if

A is deterministic poly-time reducible to B and B is deterministic

poly-time reducible to A.

Exercise 11.10. Consider the following problems.

(a) Given a prime p, a prime q that divides p ’ 1, an element γ ∈ Z— p

— of order q, and two elements ±, β ∈ G,

generating a subgroup G of Zp

compute γ xy , where x := logγ ± and y := logγ β. (This is just the

Di¬e“Hellman problem.)

(b) Given a prime p, a prime q that divides p ’ 1, an element γ ∈ Z—p

— of order q, and an element ± ∈ G,

generating a subgroup G of Zp

2

compute γ x , where x := logγ ±.

(c) Given a prime p, a prime q that divides p ’ 1, an element γ ∈ Z— p

— of order q, and two elements ±, β ∈ G,

generating a subgroup G of Zp

with β = 1, compute γ xy , where x := logγ ±, y := y ’1 mod q, and

y := logγ β.

(d) Given a prime p, a prime q that divides p ’ 1, an element γ ∈ Z—

p

Finding generators and discrete logarithms in Z—

278 p

generating a subgroup G of Z— of order q, and an element ± ∈ G,

p

x , where x := x’1 mod q and x := log ±.

with ± = 1, compute γ γ

Show that these problems are deterministic poly-time equivalent. Moreover,

your reductions should preserve the values of p, q, and γ; that is, if the

algorithm that reduces one problem to another takes as input an instance of

the former problem of the form (p, q, γ, . . .), it should invoke the subroutine

for the latter problem with inputs of the form (p, q, γ, . . .).

Exercise 11.11. Suppose there is a probabilistic algorithm A that takes

as input a prime p, a prime q that divides p ’ 1, and an element γ ∈ Z— p

— of order q. The algorithm also takes as input

generating a subgroup G of Zp

± ∈ G. It outputs either “failure,” or logγ ±. Furthermore, assume that

A runs in strict polynomial time, and that for all p, q, and γ of the above

form, and for randomly chosen ± ∈ G, A succeeds in computing logγ ± with

probability (p, q, γ). Here, the probability is taken over the random choice

of ±, as well as the random choices made during the execution of A. Show

how to use A to construct another probabilistic algorithm A that takes as

input p, q, and γ as above, as well as ± ∈ G, runs in expected polynomial

time, and that satis¬es the following property:

if (p, q, γ) ≥ 0.001, then for all ± ∈ G, A computes logγ ±

with probability at least 0.999.

The algorithm A in the previous exercise is another example of a random

self-reduction (see discussion following Exercise 7.27).