Consider the problem of creating domain parameters for DSA. Suppose we have already found primes \(p\) and \(q\) such that \(q \mid(p-1)\). Now we need to find \(g \in \mathbf{Z}_{p}\) with \(g\) of order \(q \bmod p\). Consider the following two algorithms:

a. Prove that the value returned by Algorithm 1 has order \(q\).

b. Prove that the value returned by Algorithm 2 has order \(q\).

c. Suppose \(p=40193\) and \(q=157\). How many loop iterations do you expect Algorithm 1 to make before it finds a generator?

d. If \(p\) is 1024 bits and \(q\) is 160 bits, would you recommend using Algorithm 1 to find \(g\) ? Explain.

e. Suppose \(p=40193\) and \(q=157\). What is the probability that Algorithm 2 computes a generator in its very first loop iteration? (If it is helpful, you may use the fact that \(\sum_{d \mid n} \varphi(d)=n\) when answering this question.)

Transcribed Image Text:

repeat Algorithm 1 select g Zp hg mod p until (h= 1 and g = 1) return g Algorithm 2 repeat select h E Zp g-hP-P mod p until (g # 1) return g