ElGamal signature - show that $(\gamma, \delta)$ signs $m$ 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:


How can I take the proof that $(\gamma, \delta)$ signs $m$?
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)$).