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?

  • $\begingroup$ 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? $\endgroup$ – ddddavidee Nov 24 '14 at 8:35

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$


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.