For $p=23$, $g=2$, $q=11$ you are given the signature $(18,3)$ in the message $m=2$. Construct a signature in the message $m'=3$

Question

Alice uses an ElGamal signature in group $(Z/pZ)^{*}$ without using hash function. To sign the message $m \in (Z/pZ)^*$ calculates the signature $(r,s)$ as follows: choose random $k \in \{0, 1, \dots, q-1\}$ where $q/p-1$ is prime number and the order of the base $g$ and then calculates $r\equiv g^{k}\pmod p$ and $s\equiv k^{-1}(m+ar)\pmod q$ where $a$ is the private key of Alice.For $p=23$, $g=2$, $q=11$ you are given the signature $(18,3)$ in the message $m=2$. Construct a signature in the message $m'=3$ (without using the private key). The public key of Alice is $y=13$

Could someone give some hints on how to construct this signature in message $m'=3$?

Answer 1

Just read the original paper for ElGamal signatures. Especially one of the attacks in section IV. B should help you out. Alternatively, the Wikipedia article about ElGamals signatures also has a section about existential forgeries.

Since this is clearly homework, I'll leave the rest up to you. One last hint: Use q instead of p-1, since you're actually in a smaller multiplicative subgroup.