Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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)$).
