I want to construct an Elgamal signature scheme with the group $\mathbb{Z}_{23}^{\star}$ and then to compute the signature for the message $m$ with $h(m)=4$, where $h$ is the hash function that we are using. I want to describe also the verification of the signature.
The algorithm to sign a message $m$ is the following:
Choose a $k \in_{R} \mathbb{Z}_q^{\ast}$ ($1 \leq k \leq q-1 $).
Compute $r=g^k $.
Compute $ s=k^{-1} (h(m)+f(r)x) \pmod{q} $.
$f: G \to \mathbb{Z}_q $
Signature for $m$: $(r,s)$.
The verification is $r^s=g^{h(m)}\cdot y^{f(r)}$.
I have done the following:
A generator of $\mathbb{Z}_{23}^{\star}$ is $5$, $\mathbb{Z}_{23}^{\star}=\langle 5\rangle$.
To construct an Elgamal signature scheme we have to determine the private key $x$ and the function $f(r)$.
Let $x=5\in \mathbb{Z}_{23}$ and $f(r)=r$.
The public key is therefore $y=g^x=5^5\equiv 20\pmod {23}$.
We apply the algorithm for the signature and we get the following:
Let $k=18\in \mathbb{Z}_{23}^{\star}$.
We have that $r=g^k=5^{18}\equiv 6\pmod {23} $.
We have that \begin{align*} s&= k^{-1} (h(m)+rx) \pmod{23} \\ & =18^{-1}\cdot (4+6\cdot 5)\pmod {23} \\ & =9\cdot 34\pmod {23} \\ & = 9\cdot 11\pmod {23} \\ & = 7\pmod {23}\end{align*}
The signature for the message $m$ with $h(m)=4$ is $(r,s)=(6,7)$.
For the verification we have to check if it holds that $r^s=g^{h(m)}\cdot y^r$.
We have that $r^s=6^7\equiv 3\pmod {23}$ and $g^{h(m)}\cdot y^r=5^4\cdot 20^6\equiv 4\cdot 16\pmod {23}\equiv 18\pmod {23}$.
The verification is therefore not satisfied. What have I done wrong?
Example: We consider the group $\mathbb{F}_{47}^{\times}$.
The order of the group is $47-1=2\cdot 23$.
We find that the element $g=2$ has order $q=23$.
Suppose that the private key is $a=14$, so we compute the public key $y=2^{14}\pmod {47}=28$.
We want to sign the message $m=32$. We choose $k=8$ and we compute $r=2^8\pmod {47}=21$.
We suppose that $h(m)=h(32)=20$.
We compute $s=k^{-1}(h(m)+ar)\pmod q=3\cdot (20+14\cdot 21)\pmod {23}=22$.
So, the signature for the message $m=32$ is $(s,r)=(22,21)$.
To verify the signature we compute $r^s=21^{22}\pmod {47}=9$, $g^{h(m)}=2^{20}\pmod {47}=6$ and $y^r=28^{21}\pmod {47}=25$ and check that $9\equiv 6\cdot 25\pmod {47}$.
So in order to use the function $f(r)$ we have to compute the signature modulo $p$ where $q-1=2p$, and $q$ is the order of the group we are considering, right?