What is wrong with my Elgamal signature example?

Question

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:

1. Choose a $k \in_{R} \mathbb{Z}_q^{\ast}$ ($1 \leq k \leq q-1 $).

2. Compute $r=g^k $.

3. 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:

1. Let $k=18\in \mathbb{Z}_{23}^{\star}$.

2. We have that $r=g^k=5^{18}\equiv 6\pmod {23} $.

3. 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?

Answer 1

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<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$.