Question -We investigate the weaknesses that arise in Elgamal encryption if a public key of small order is used. We look at the following example. Assume 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 ciphertext symbols: ¨a?26, ¨o?27, ¨u?28.

She transmits the subsequent 11 ciphertexts (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.

I am not sure how to solve the question. Can anyone help me?