2.6 The Pohlig-Hellman Algorithm

2.6 The Pohlig-Hellman Algorithm

In this section, a bit of further explanation concerning the workings of the Pohlig-Hellman

algorithm is provided. It is needed to be understood this algorithm because Pohlig-

Hellman attack is a serious attack which is based on mathematical views. The same

notation will be used as in the last section: p is prime, g is a primitive element in Z_p,

and h Є Z*_p. Our goal is to determine a = log_g h, where, without loss of generality,0≤a≤p-2.

From this,it is a simple matter to determine a_0.

The next step would be to compute a_1,a_2,... ,a_(e-1) (if e>1). These computations can

be done from a suitable generalization of Equation (2.1).

Corollary 2.5.2

Corollary 2.5.2 Suppose p and q are prime, and p =2q + 1. Suppose g Є Z*_p is not a

primitive element, and g ≠±1(mod p). Then (-g) is a primitive element.

This means that we have an efficient deterministic algorithm to find a primitive element

for when p and (p - 1)/2 are both prime.

It is not so easy to verify that elements are primitive if the factorization of p – 1 is

not known. For this reason, the designer of a cryptosystem will often construct p in such

a way that the factorization of p - 1 is known. For example, it is often desirable to

implement a cryptosystem in Z_p, where p =2q + 1 and p and q are both prime. One

reason why this might be done is that it ensures that the system will not be vulnerable

to a Pohlig-Hellman attack on the discrete logarithm problem. To find such a p, the

designer of the system will choose a random odd value q, and test both p and p =2q +1

for primality using one of the probablistic primality tests. If either of p or q is found

to be composite, then a new random value of q is chosen and the process is repeated.

As another example, several protocols are implemented in Z_p where p - 1 has a prime

divisor q of a specified size. A convenient realization of such a system would be to take

p =2qr + 1, where p, q and r are all primes. if q is to be a 160-bit prime and p is to be a

512-bit prime, then r will be a prime of approximately 352 bits. Here, the designer of the

system would begin by choosing random values q and r of the appropriate size, and then

define p =2qr + 1. The three integers p, q and r will all be tested for primality using a

probabilistic primality testing algorithm.