1. (a) The ElGamal public key encryption algorithm works as follows. Alice generates a large prime number p and finds a generator 9 of GF(p). She then selects a random x, such that I sxs p-2 and computes X = g' mod p. Now, Alice's private key is x, and her public key is (p.g. X), which she sends to Bob. Alice wants to send Bob a signed message M. To produce a signature on this mes- sage, she generates a random integer re (2,p-2], such that it is relatively prime to (p-1). She then computes S = g' mod p and S = (M-xS), and sends her signature S [S1,S2] to Bob. Bob can verify this signature using Alice's public key by checking, whether XS S = g" mod p. (i) Suppose, in the calculation of signature, M and r are interchanged, i.e. for the same S =g'. S, is now computed as S2 = (r-xS)M. What would now be the formula to verify the signature S = [S.S.]? [6 marks] (ii) Does the signature algorithm suggested in part (i) have any security problems? If yes, then find one and explain what the problem is. If not, then explain why not. [6 marks]