weaknesses in ElGamal with public key of small order

Question

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

Answer 1

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.

Answer 2

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