Decrypting ElGamal messages

Question

You're Eve. Bob has made it public that he is using ElGamal, p = 29, g = 2, and his public key is 28. You intercept the following message: (9, 5), (16, 12), (28, 5), (1, 13), (20, 5), (23, 14), (20, 20), (1, 1), (13, 18), (22, 25). Decrypt the message by hand. Did you get Bob's private key (to get the best solution, you don't have to!)? Hints: Why 29? Also, what $c_1^α$ are possible? So far, I've only been able to tell that Bob (I think) is the one receiving the messages since he has a public and private key, as opposed to the sender who would only have one private (ephemeral) key.

Answer 1

I assume the encoding is $a=1,b=2$ etc. (only invertible elements (so non-zero) of $\Bbb Z_p$ are allowed).

Note that the public key $g^s=28$ is just $-1$ modulo $29$ ! A message letter $m$ is encrypted as the pair $c=(g^r, g^{rs}m)$ for some random $r \in \Bbb Z_p$. Note that $g^{rs}=(g^s)^r = (-1)^r$, so the multiplication factor in the $c_2$ is either $1$ or $-1$.

So the pairs are $$(9, 5), (16, 12), (28, 5), (1, 13), (20, 5), (23, 14), (20, 20), (1, 1), (13, 18), (22, 25)$$ which have second components

$$5,12,5,13,5,14,20,1,18,25 = e,l,e,m,e,n,t,a,r,y$$

in my supposed encoding. It seems that all factors were 1.

Of course, the public key is awful here (the private key is $\frac{p-1}{2}=14$ if you want to know, but we don't really need it). This whole system is just a bad substitution cipher: you're better off just encoding a random permutation of the alphabet somehow. For real life El-Gamal you need a huge prime (1024 bits or more is recommended) and a good generator, and then you encrypt a symmetric key with it, say and use AES for actual messages. IMHO these kind of exercises on PK-cryptography don't really teach you anything...