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.

I tried to find online for the correctness of El-Gamal, but I couldn't find any good resource that will teach me how to show the correctness of El-Gamal, could any body show me how is it done?

share|improve this question
It is quite easy and straightforward. Could you tell us more about the problem you encountered? Could you try to write down your computation to verify correctness and show us where you stop? –  ddddavidee Nov 24 '14 at 8:35

1 Answer 1

up vote 1 down vote accepted

Say that $y = g^k \pmod p$ is the public key ($g$ a generator of the group and $p$ a prime, $k$ a secret random integer known as the secret key).

To encrypt $M$ one chooses a random $r$ and compute $(c_1, c_2)$ as $c_1 = g^r \pmod p$ and $c_2 = M \cdot y^r \pmod p$.

You should show that the decryption works: $M = c_2 \cdot (c_1)^{-k}$.

$c_2 \cdot (c_1)^{-k} = M \cdot y^r \cdot (g^r)^{-k} = M \cdot g^{kr} \cdot g^{-kr} = M \pmod p$

share|improve this answer

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.