Answer Happy

1. (a) The ElGamal public key encryption algorithm works as follows. Alice generates a large prime number p and finds a generator g of GF(p). She then selects a random x, such that I susp-2 and computes X = g mod p. Now, Alice's private key is .x, and her public key is (p.9.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 r € 12.p-2), such that it is relatively prime to (P-1). She then computes S, - mod p and S= (M - XS r and sends her signature S - IS, S, to Bob. Bob can verify this signature using Alice's public key by checking, whether X$i$="mod p. (1) Suppose, in the calculation of signature Mand rare interchanged, i.e. for the same S; = 1.S, is now computed as S, -r-+S) What would now be the formula to verify the signature SS.S,)? 16 marks (ii) Does the signature algorithm suggested in part (1) have any security problems? If yes, then find one and explain what the problem is. If not, then explain why 16 marks) not