# Show that the decryption transformation for the El Gamal cryptosystem works.

Want to show that, if $P$ is the original plaintext block and $(\gamma^a)'$ is the inverse of $\gamma^a$ modulo $p$, then $$(\gamma^a)'\delta \equiv P \pmod p$$

So, we have:

• $\gamma = \alpha^k \pmod p$
• $\delta = P(\alpha^a)^k mod p$
• $C = (\gamma, \delta)$

Plugging the values above to $(\gamma^a)'\delta$ $$(\gamma^a)'\delta = ((\alpha^k)^a)' P(\alpha^a)^k \equiv P \pmod p$$ $$((\alpha^k)^a)' P(\alpha^a)^k \equiv ((\alpha^k)^a)' (\alpha^a)^k \equiv 1 \pmod p$$

Not sure if I'm doing this correctly...

-
Ok. What have you tried? – mixedmath Apr 17 '13 at 0:32

Hint: We want to show that if $(\gamma^a)'$ is the inverse of $\gamma^a$ modulo $p$, then $(\gamma^a)'\delta \equiv P \pmod p$.

We have:

• $\gamma = \alpha^k \pmod p$

• $\delta = P(\alpha^a)^k \pmod p$

• $C = (\gamma, \delta)$

So, we need to find: $(\gamma^a)'\delta$

Plug in the above values and what do end up with?

$$(\gamma^a)'\delta = ((\alpha^k)^a)' P(\alpha^a)^k \equiv \alpha^{-ak} \cdot \alpha^{ak} P \equiv P \pmod p$$

What allows me to swap and cancel those values?

-
...nice job here, too! – amWhy Apr 17 '13 at 1:06
Thanks for responding, but still unsure about how to proceed. I've update the post with what you've suggested but I'm not sure if I'm going in the right direction. – Tejen Shrestha Apr 17 '13 at 2:11
@Amzoti Ok, so can you divide both sides by $\alpha^{-ak}$?. If so, it seems like I end up with $1 \equiv 1 \pmod p$. – Tejen Shrestha Apr 17 '13 at 2:25
@icanc: Huh? the RHS is our final result and is P. Why are you dividing anything from the left of that? Maybe just a slip up? Regards – Amzoti Apr 17 '13 at 2:28