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?


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

  • $\begingroup$ I find that $r^s=6^{19} \equiv 18$ and $g^{h(m)} y^{-r}=5^4 \cdot 20^{-6} \equiv 6$, so again the verification is not satisfied. Or am I doing something wrong? $\endgroup$
    – Evinda
    May 10, 2017 at 16:04
  • $\begingroup$ I checked this, because in my notes the verification step is this: $$r^s= g^{h(m)} y^{f(r)}$$ In my notes, there is an example... I will add it at my initial post. $\endgroup$
    – Evinda
    May 10, 2017 at 18:55
  • $\begingroup$ Did you see my edited post? Do we have to find in our case for $g$ an element in $\mathbb{Z}_{23}^{\ast}$ of order $11$ ? If so, how can we find such element? $\endgroup$
    – Evinda
    May 10, 2017 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.