(Answered): The Schnorr Signature schemes works as follows: Choose a prime number q and a generator of g Z_q ...

The Schnorr Signature schemes works as follows: Choose a prime number q and a generator of g Z_q of prime order q. Choose a Hash function H:{0, l}* rightarrow Z_q; H, q and g are publicly known. Let M={0, 1}* be the set of binary strings that need to be signed. To sign a message M, Alice chooses a private key x Z_q{0} (that is x Z_q but x notequalto 0) and a randomly chosen (say a per-message signing key) x Z_q{0}. 1. Compute r = g^k mod q. 2. Compute e = H(M||r) 3. Compute s =(k-xe) The message, signature pair consists of (M, (s, e)). Note that s, e Zq So the public parts are g, q, y, s, e and r. Private parts are k and x. To verily the signature on M, Bob computes the following: Compute r_v = g^sy^e Compute e_v =H(M|| r_v) If the computed value e_v = e, then the signature is valid. If the message size |M| = (q-l)/2, then given one hash r, what is the probability of finding another value r' such that H(M||r)=H(m||r') for a given message M?