Cryptology Problems

To be discussed Wednesday, April 29, 1998.

1. In the discussion of DSS on page 211 (I hope it’s the same page and says the same thing in the newer edition), it says that to find a qth root of 1 modulo p, one should begin with a primitive element α_{0} of Z_{p} and compute α_{0}^{(p−1)/q}.

a. Why is this correct? What subgroup does the result generate?

b. How long does it take to do this computation?

c. Is it necessary that α_{0} be a primitive element?

2. In the verification protocol for undeniable signatures, the verifier chooses randomly two values e_{1} and e_{2}. Why are there two values? Why not just let e_{2} = 0 always?