Because in the exercise $g$ is is not a generator of $\mathbb Z^*_p$, the exercise would indeed be incorrect in a context explicitly giving a definition of ElGamal encryption that both
- requires $g$ to be a generator of the group the message belongs to,
- and chooses the message in $\mathbb Z^*_p$, here as an integer in range $[1,22]$.
Otherwise, the exercise and it's (now reformatted) correction are OK.
A common definition of ElGamal encryption (note: $h$ is used where the question uses $y$) has the message (representative) $m'$ in a finite cyclic group $G$ with generator $g$. In the question's examples, the message would be restricted to $G=\{1,2,3,4,6,8,9,12,13,16,18\}$. That makes the exercise fine.
Note: We do not need to rewrite that set as $\mathbb Z^*_{11}$, and cannot do this while keeping the same multiplication law as in $\mathbb Z^*_{23}$.
Another possible definition of ElGamal encryption makes no such restriction on $m'$, allows it to take any value in any finite commutative group (including $\mathbb Z^*_p$, possibly without restriction to prime $p$), and picks an element $g$ in that group that needs not be a generator of the full group (but needs to generate a large cyclic subgroup in which the discrete logarithm is hard, and other properties often associated). That still allows decryption of any message in the base group. In that definition, the question's message could be any integer in range $[1,22]$. That also makes the exercise consistent.
However, in that second definition, security suffers somewhat. When as in the question the base group is $\mathbb Z^*_p$ with $p$ prime, and $g$ generates a subgroup $G$ of prime order $(p-1)/2$, it is possible to test if the message $m'$ belongs to the subgroup $G$ generated by $g$. That's because ElGamal's ciphertext includes $c_2=m'\cdot g^z\bmod p$ for some integer $z$, therefore $m'$ belongs to $G$ if and only if $c_2$ does, and we can test that by checking if $c_2^{(p-1)/2}\bmod p\,=1$. That's a one-bit information leak about a message $m'$ picked randomly in $[1,22]$. Such information leak is against modern definitions of a cipher's security. We can:
- Ignore that issue. That's reasonable in the example, since it has a much worse security issue: $p$ is small enough that finding the private key $x$ from public key $g^x\bmod p$ is easy, thus deciphering is easy. $p$ would need hundreds of decimal digits for true security.
- Restrict to messages $m'$ that belong to $G$. When the order of $|G|$ is prime $(p-1)/2$ as in the example, that's easy. We can test if $m'$ belongs to $G$ by checking if $m'^{(p-1)/2}\bmod p\,=1$, and if it does not use $\tilde m'=p-m'$ (which does) instead of $m'$. We can get back to $m'$ after decryption (e.g. by requiring $m'<p/2$ which allows recognition of if decryption yielded $m'$ or $\tilde m'$).
- Have the sender make $m'$ a random element of $\mathbb Z^*_p$, then hash it (which makes the leak immaterial) to obtain the key of a symmetric cipher used to encrypt the true message. That's hybrid encryption.
- Have the sender choose a random $r\in\{1,\dots,|G|\}$, then compute $m'=g^r\bmod p$, which is a random member of subgroup $G$ (but we can not chose $m'$ directly representing a long message to send, thus typically that's still used with hybrid encryption).
It is common (and desirable for security to some degree, for at least the reason above) to use $g$ such that $G$ is a group of prime order. When using $\mathbb Z^*_p$ as the base group, it is typical to use a Schnorr group, perhaps with $p$ 2048-bit and $|G|$ 256-bit, both prime.
