We have as a given: $gcd(j, p − 1) = 1$.

$$γ = \alpha^i \beta^j \bmod p $$ $$ \delta = −\gamma j^{-1} \bmod (p−1) $$ $$m = i \delta \bmod (p − 1)$$

I want to show that $(\gamma; \delta)$ is an ElGamal signature for message $m$.

In this book, they show an example: formula

How can I take the proof that $(\gamma, \delta)$ signs $m$?

  • $\begingroup$ The image you posted is actually the proof! Did you want help walking through it? $\endgroup$
    – user47922
    Commented Jun 12, 2017 at 0:02
  • $\begingroup$ I'm editing the post because the original formula provided for $m$ is incorrect. $\endgroup$
    – user47922
    Commented Jun 12, 2017 at 14:40

1 Answer 1


A valid ElGamal signature satisfies, in the notation from the book you posted:

$$\beta^\gamma \gamma^\delta = \alpha^m \bmod p$$

That's just the definition of an ElGamal signature. The snippet you posted is not an example, but precisely the proof that $(\gamma, \delta)$ is a valid signature of $m = i \delta \bmod (p-1)$. On page 68 of the book, it says

($\gamma, \delta$) este o semnatura valida pentru x. Intr-adevar, se verifica...

(In English: "$(\gamma,\delta)$ is a valid signature for $x$. Indeed, one verifies...")

So let's step through the proof. Everything is $\bmod p$:

$$\beta^\gamma \gamma^\delta = \beta^{\alpha^i \beta^j } (\alpha^i \beta^j)^{-\alpha^i \beta^j j^{-1} }$$

(Substitution of values)

$$... = \beta^{\alpha^i \beta^j } \alpha^{-i j^{-1} \alpha^i \beta^j } \beta^{-\alpha^i \beta^j}$$

(Just distribute the exponent across $\alpha^i$ and $\beta^j$. In the $\beta$ exponent, you get a $j j^{-1} = 1$)

$$...= \alpha^{-i j^{-1} \alpha^i \beta^j }$$

(The $\beta$ terms cancel out)

$$...= \alpha^{-\gamma i j^{-1} }$$

(definition of $\gamma$)

$$...= \alpha^m$$

(definition of $m$)

Here, $i$ and $j$ are such that $0 \leq i,j \leq p-2$. The proof you are showing is that this scheme is existentially forgeable (see page 381, Theorem 16). This is a two-parameter forgery (the $(i,j)$).

  • $\begingroup$ Thanks, yes. But if $$m=−iδmod(p−1)$$ than $α^m = α^-m$. Is that ok? What should we do with that minus? $\endgroup$
    – Tina Ch
    Commented Jun 12, 2017 at 13:51
  • $\begingroup$ That formula is wrong; the confusion is happening because: $$\delta = -\gamma j^{-1} \mod (p-1)$$ and $$m = -\gamma i j^{-1} \bmod (p-1) = i \delta \mod (p-1)$$. The minus sign is "in the $\delta$". Example 3.5 shows this in the link you provided. $\endgroup$
    – user47922
    Commented Jun 12, 2017 at 14:35
  • $\begingroup$ Also, $-x \bmod p \equiv (p-x) \bmod p$. Again, from Example 3.5, $$-117 \cdot 151 \bmod 466 \equiv (466 - 117) \cdot 151 \mod 466 \equiv 52699 \bmod 466 \equiv 41 \bmod 466$$ So negative numbers aren't a problem either, mod $p$. $\endgroup$
    – user47922
    Commented Jun 12, 2017 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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