weaknesses in ElGamal with public key of small order Suppose $p=29$, $\alpha = 2 \in F_p^*$ is a generator of $F_p^*$. Bob picks $d \in \{2,...,27\}$ such that $\beta = \alpha ^d=28 \pmod{29}$. He then sends his $(p,\alpha ,\beta)$ to Alice who herself picks one $i_j \in \{2,...,27\}$ for eleven different plaintext values $m_j$, $0\leq j\leq 10$ and encrypts these by $c_j=m_j*28^{i_j} \pmod{29}$.
Since $|28|=2$, the only possibilities for the masking key $k_M = 28^{i_j} \pmod{29}$ are $1$ and $28$.

Alice sends the following ciphertext-key pairs in the form $({k_E}_j, c_j)$:
$$(3,15),(19,14),(6,15),(1,24),(22,13),(4,7),(13,24),(3,21),(18,12),(26,5),(7,12)$$
where $a=0, ..., z=25, ä=26, ö=27, ü=28$. We thus have the ciphertext
$$p,o,p,y,n,r,y,v,m,f,m$$
The task is to decrypt the message without computing Bob's private key, by "looking at the ciphertext and using the fact that there are only very few masking keys and a bit of guesswork". Since the only possibilities for $k_M$ are $1$ and $28$, the plaintext corresponding to $c_j$ is either $c_j$ itself or $c_j*28^{-1} \pmod{29}$. This yields two possibilities per $c_j$:
$$p,o,p,y,n,r,y,v,m,f,m$$
$$o,p,o,f,q,m,f,i,r,y,r$$
I could not make sense out of the two, so I computed Bob's private key anyways to check the result. It turns out Bob's private key is $14$ ($2^{14}=28 \pmod{29}$). Computing ${k_M}_j = {k_E}_j^{14}$, the result turned out to be 
$$o,p,p,y,n,r,y,i,r,y,m$$which still does not make any sense to me.

So my question is: did I mix something up along the way? If not, where is the "guessing" supposed to happen? Also I have not used the fact that $\alpha = 2$.

EDIT

I seem to have been unclear before. I am asking this because this belongs to an exercise (decrypting the given ciphertext without calculating Bob's private key), and I believe I missed something. The actual result, calculated by using that not allowed key, seems random. So I don't know how guessing should be of any use, or how to decide which is the correct sequence without using the private key.

EDIT2

As suggested in the comments I'll quote the complete exercise here:

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 $\mathbb{Z}_{29}^*$ with the primitive element $\alpha = 2$. His public key is $\beta = 28$.

i) What is the order of the public key?

ii) Which masking keys $k_M$ are possible?

iii) Alice encrypts a text message. Every character is encoded according to the simple rule $a=0,...,z=25$. There are three additional ciphertext symbols: $ä=26, ö=27, ü=28$. She transmits the following 11 ciphertexts $(k_E,y):$
(see the 11 pairs above)

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.

Thank you
Well, your problem is that you choose a specific bad private key ("-1"), which only generates a group with two elements. However, this is a very specific weak case, and the chance to select the according private key is negligible.

But in general, there are a couple of problems with choosing a generator for the whole group $\mathbb{Z}_p^*$, because it is leaking some information. For example, if $\beta$ is a quadratic residue, but $c=m\cdot \beta^i$ is not a quadratic residue, then $m$ is a quadratic non-residue.

The general solution is to use Schnorr groups, where the generator only generates a part of the multiplicative group, but has a large prime order itself (which is also the order of all elements except the neutral element).