Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$

share|improve this question
up vote 3 down vote accepted

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.

share|improve this answer
Why can you when proving the verification, raise gamma when it is mod $p$? $\alpha^x = \beta^\gamma \gamma \delta \mod p$ – Becktor May 19 '14 at 16:53
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. – otus May 19 '14 at 17:07
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? – Becktor May 19 '14 at 17:15
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. – otus May 19 '14 at 17:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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