Selecting a prime p and generator of Z*p
In cryptographic applications for which a generator of Z* is required, one usually has the flexibility of selecting the prime p. To guard against the Pohlig-Hellman algorithm for computing discrete logarithms (Algorithm 3.63), a security requirement is that p— 1 should contain a “large” prime factor q. In this context, “large” means that the quantity ^/q represents an infeasible amount of computation; for example, q > 21G0. This suggests the following algorithm for selecting appropriate parameters (p. a).
4.84 Algorithm Selecting a k-b'ti primep and a generator» of Щ,
INPUT: the required bitlength к of the prime and a security parameter t.
OUTPUT: a А-bit prime p such that p — 1 has a prime factor > t, and a generator a of Z*.
- 1. Repeat the following:
- 1.1 Select a random fc-bit prime p (for example, using Algorithm 4.44).
- 1.2 Factor p - 1.
Until p — 1 has a prime factor > t.
- 2. Use Algorithm 4.80 with G = Z* and n = p - 1 to find a generator a of Z*.
- 3. Return(p,a).
Algorithm 4.84 is relatively inefficient as it requires the use of an integer factorization algorithm in step 1.2. An alternative approach is to generate the prime p by first choosing a large prime q and then selecting relatively small integers R at random until p = 2Rq + 1 is prime. Since p — 1 = 2Rq, the factorization of p - 1 can be obtained by factoring R. A particularly convenient situation occurs by imposing the condition R = 1. In this case the factorization of p - 1 is simply 2q. Furthermore, since ф(р - 1) = ф(2q) = >(2)
4.85 Definition A safe prime p is a prime of the form p = 2q + 1 where q is prime.
Algorithm 4.86 generates a safe (probable) prime p and a generator of Z*.
4.86 Algorithm Selecting a A>bit safe prime p and a generator a of Z*
INPUT: the required bitlength к of the prime.
OUTPUT: а А-bit safe prime p and a generator q of Z*.
- 1. Do the following:
- 1.1 Select a random (k - l)-bit prime q (for example, using Algorithm 4.44).
- 1.2 Compute p<^2q + 1, and test whether p is prime (for example, using trial division by small primes and Algorithm 4.24).
Until p is prime.
- 2. Use Algorithm 4.80 to find a generator a of Z*.
- 3. Return(p,a).