Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

1 Answer 1

up vote 2 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 at 16:53
    
Sorry, that was a rather short explanation. –  otus May 19 at 16:57
    
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 at 17:07
1  
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 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 at 17:19

Your Answer

 
discard

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.