We first recall ElGamal encryption. The setting is Zp for a large prime p where p – 1 has a prime…

We first recall ElGamal encryption. The setting is Zp for a large prime p where p – 1 has a prime divisor q. Further, g is a generator for a subgroup of order q of Z * p . A community of users share parameters p, q and g. Typically, p is a 1024 bit number, while q has only 160 bits. Each user has a private key x < q and a public key X = g x (mod p). To encrypt a message m for this user, the sender chooses a random number y < q and encrypts the message as (c1, c2) = (g y , m · Xy ) (mod p). Because of the random choice of y for each message, different encryptions of the same message will be different. However, there is another quantity involving only m and q that can be computed from the ciphertext. This gives the basis for attacks on this textbook version of ElGamal. a) Show how to compute mq given the encryption of m. Solution Since the second part involves m we need to do something with c2 = m · Xy . If we raise c2 to the power of q we have that c q 2 = (m · (g x ) y ) q = mq · (g q ) xy = mq since g q = 1 (g is a generator of a group of order q). b) Given two messages m1 and m2 in Z * p with m q 1 = m q 2 , can one conclude that m1 = m2 (motivate your answer)? Hint: The probability that a random element in Z * p has order q is very small