2
$\begingroup$

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

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

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

| improve this answer | |
$\endgroup$
  • $\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 Jun 12 '17 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 Jun 12 '17 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 Jun 12 '17 at 15:45

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.