Question - We investigate the weaknesses that arise in Elgamal encryption if a public key of small order is used. We look at the subsequent example.

Suppose Bob uses the group Z

29 with the primitive element ??= 2. His public key is ??= 28.

Part 1- What is the order of the public key?

Part 2- Which masking keys kM are possible?

Part 3- Alice encrypts a text message. Every character is encoded according to the simple rule a?0,. . ., z?25. There are three additional cipher text symbols: ¨a?26,

¨o?27, ¨u?28. She transmits the following 11 cipher texts (kE,y):

238 8 Public-Key Cryptosystems Based on the Discrete Logarithm Problem

(3,15), (19,14), (6,15), (1,24), (22,13), (4,7),

(13,24), (3,21), (18,12), (26,5), (7,12)

Decrypt the message without computing Bob's private key. Just look at the cipher text and use the fact that there are only very few masking keys and a bit of guesswork.

Please provide a detailed answer so that I can learn from it. Thank you!