What is wrong with my Elgamal signature example? 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&amp;= k^{-1} (h(m)+rx) \pmod{23} \\ &amp; =18^{-1}\cdot (4+6\cdot 5)\pmod {23} \\ &amp; =9\cdot 34\pmod {23} \\ &amp; = 9\cdot 11\pmod {23} \\ &amp; = 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?
Main problem is: in the question, a generator $g$ of order $q$ is used in the computation of [2.]. Thus if that computation and verification is in $\mathbb Z_{23}^*$ as in the attempted computations, then the modulus to use in [3.] is not $q=23$, but $q=22$ (if we use $g=5$), or rather $q=11$ (if we use another $g$ of prime order, which seems to be the intent: in [1.] it is considered that $\mathbb Z_q^*$ is the set of $k$ with $1\le k\le q-1$, which implies that $q$ is prime, as in the example).
Alternatively, we could use $q=23$ and $p=47$ as in the example (thus using modulo $47$ in the computation of step [2.] and signature verification); but then $g=5$ is unsuitable.

Further, the question misuse notations:


equivalence modulo, where $r\equiv a\pmod n$ means that $n$ divides $a-r$.
the operator $\bmod$, uniquely defining $r\,=\,a\bmod n$ such that $0\le r&lt;n$ and $n$ divides $a-r$.
residue class modulo, where $R=a\pmod n$ means that $R$ is the set of all $r$ such that $n$ divides $a-r$ (this notation is less common, and should not be used without a notice and a good reason; its use in [3.] is accidental and unwelcome).


Note: the question does not follow the standard definition of ElGamal signature, which would use $s\gets k^{-1}\,(h(m)-r\,x)\bmod q$ and verify that $g^{h(m)}\equiv r^s\,y^r\pmod p$.