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.
1. What is the order of the public key?
2. Which masking keys kM are possible?
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 following 11 ciphertexts (kE,y)
![1151_83c27560-f846-45c2-b89a-731efb171509.png](https://secure.tutorsglobe.com/CMSImages/1151_83c27560-f846-45c2-b89a-731efb171509.png)
Decrypt the message without computing Bob's private key. Just look at the ciphertext and use the fact that there are only very few masking keys and a bit of guesswork.