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)
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.