Im trying to figure out why $\delta$ in the signature part of ElGamal has mod $p-1$ when $\gamma$ has mod $p$?
$\gamma = \alpha^k \mod p$
$\delta = (x-a\gamma)k^{-1} \mod p-1$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Basically because of Fermat's little theorem: if $a$ is not divisible by $p$ then $a^{p-1} = 1$ $mod$ $p$. A part of the expression for $\delta$ appears as a power of $a$ in the ElGamal signature verification equation, which "happens" to work because it is reduced modulo $p-1$ so Fermat's little theorem applies.
-
$\begingroup$ Why can you when proving the verification, raise gamma when it is mod $p$? $\alpha^x = \beta^\gamma \gamma \delta \mod p$ $\endgroup$– BecktorCommented May 19, 2014 at 16:53
-
$\begingroup$ What's really going on is that $\beta$ and $\gamma$ are both themselves powers of $\alpha$. You need to expand them to see what's going on. $\endgroup$– otusCommented May 19, 2014 at 17:07
-
1$\begingroup$ Yea I $a^x=\beta^\gamma \gamma^\delta$ and get: $\alpha^{a\gamma}\alpha^{k(x-a\gamma)k^{-1}}$ which gives $\alpha^{a\gamma}\alpha^{x}\alpha^{-a\gamma}$, So since $\alpha^{a\gamma}$ and $\alpha^{-a\gamma}$ cancels each other we can do this? $\endgroup$– BecktorCommented May 19, 2014 at 17:15
-
$\begingroup$ That's it, basically. You need the $mod$ $p-1$ so that the power is "off" by a multiple a $p-1$ (which by F.l.t. means the power is one). Otherwise you couldn't cancel the $k$'s. $\endgroup$– otusCommented May 19, 2014 at 17:19