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

-
As different masing keys are used for the ciphertexts it may be helpful to additionally follow tylos quadratic residuosity hint ;) –  DrLecter May 23 '14 at 22:07
@DrLecter "your public key to the power of the masking key"? To my understanding, the masking key $k_M$ is computed as $\beta ^i$ where $i\in \{2,...,27\}$ is chosen randomly by Alice, and is then used to encrypt ("mask") the plaintext $c=m*k_M$. That means that the masking key $k_M$ as a power of Bob's public key $\beta$ can only be $1$ or $28$. That is in line with what the exercise itself hints at: "use the fact that there are only very few masking keys". I'll look at the quadratic residue. –  foaly May 24 '14 at 3:27

Firstly, in ElGamal encryption the ciphertext is of the form $(c_1,c_2)=(\alpha^k,m\cdot \beta^k)$ and in your description it is $(c_1,c_2)=(\beta^k,m\cdot \beta^k)$ (which is not how ElGamal works). But I assume that this is just a bug in your writeup.

Then, as you observe for your second component $c_2$ the value masking the message $m$ can either be $1$ or $\beta$ (as $\beta$ has order 2 in $Z_{29}^*$).

So given all your second components of your ciphertexts you know that they can be either of the form $m\cdot 1$ or $m\cdot \beta$, i.e., either you already have the message itself or you have the message masked with the value of the public key. Consequently, if your given tuples of ciphertext are correct (in particular, the order of the elements in the tuples), then your findings are correct. You will have two possibilites for every ciphertext, which are for masking value $1$ and $\beta$ respectively: $$p,o,p,y,n,r,y,v,m,f,m$$ $$o,p,o,f,q,m,f,i,r,y,r$$

Now since guesswork will (as far as I can see it) give you no meaningful plaintext, what you can do is to use information about quadratic residuosity to determine the plaintext. As this is homework, I do not fill in all the details.

You can quickly, determine that your element $\alpha$ is a quadratic non-residue (using Eluers criterion - a generator of $Z_p^*$ will always be a quadratic non-residue btw.). Observe that every first element of your ciphertext tuples by construction have the form $c_{1}=\alpha^k$ for some unknown $k$.

Now you can easily test your $c_1$ components for quadratic residuosity and if the first element of the ciphertext $c_{1}$ is a quadratic residue you can derive that $k$ has to be even. Consequently, for the second element of the ciphertext you have that $c_{2}=m\cdot 1$. On the other hand, if the element $c_{1}$ is a quadratic non-residue, then your $k$ has to be an odd integer and consequently, for the second element of the ciphertext you have that $c_{2}=m\cdot 28$ (why this is the case is left open as an exercise).

Now, you can use this fact to figure out the plaintext without decryption and you will find that the plaintext must be $$o,p,p,y,n,r,y,i,r,y,m$$ which is the result that you have obtained after breaking the scheme and decrypting the ciphertexts.

-
Note that I wrote $k_E$, not $k_M$, wich $k_E=\alpha^i$, $i$ being chosen by Alice. So yes, that was just a misunderstanding. Thank you for your answer! –  foaly May 26 '14 at 1:49
I hadn't thought about using quadratic residues this way ("if the first element of the ciphertext $c_1$ is a quadratic residue you can derive that $k$ has to be even"). –  foaly May 26 '14 at 1:52

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

-
thanks for your answer. 28 (-1) is the given public key. Given that calculated the private key to be 14. But I know that it's specifically weak because of 28's order. What I was asking about, though, is what I did not get about the mentioned "task" to decrypt the given ciphertext without computing Bob's private key, by "using the fact that there are only very few masking keys" (2 in fact) "and a bit of guesswork". I do not know what is meant with the guesswork. Since the result I calculated with the private key (not allowed) seems random, I don't how I should otherwise know the correct result. –  foaly May 23 '14 at 11:07
I hope you understand what I mean. It's related to an exercise, and I believe I missed something. –  foaly May 23 '14 at 11:08
Well, you might want to tag the question with homework then, and actually quote the exercise precisely. There might be something missing here, but from what I can see: Your approach might be correct, but I can't say for sure. It could also be something along the lines of the quadratic residue example I gave. (If that was the actual solution, I would just have given tips instead) –  tylo May 23 '14 at 11:44
Thank you. I updated the question with the complete exercise quote. –  foaly May 23 '14 at 15:42
sadly in this case most of the time when $c$ is a quadratic non-residue, so are both of the possible $m$. So it only helps deciding between the two at a few instances. Also quadratic residues have not been mentioned before, so I believe the answer must be something else. Probably something simple I have overlooked. –  foaly May 25 '14 at 2:31