How the ElGamal cryptosystem works

The ElGamal cryptosystem is making use of the discrete logarithm problem to make it secure, therefore it's fundamental to know what that is about.

The discrete logarithm problem

The discrete logarithm problem is a numerical procedure that is hard to evaluate on one way and easy another. In the congruence $y\equiv x^e (mod\: p)$ , p is a large prime number and e is a primitive root mod p, or e at least has a high order. To find y when you know x, e, and p is easy. To find the exponent e when you know x, y and p is hard.

ElGamal Cryptosystem

For the public key in the ElGamal cryptosystem, you choose a large prime number $p_1$ and a primitive root $g_1\: mod \: p_1$ , and a secret number $a_1$ between 1 and $p_1 -1$ . Then you calculate $h_1=g_1^{a_1}\: (mod\: p_1)$ , and your public key consists of the integers $p_1,g_1$ and $h_1$ . If someone wants to use your public key to send you an encrypted message m they first have to choose a number k between 1 and $p_1 -1$ , and then compute $g_1^k \: (mod \: p_1)$ and $mh_1^k\: (mod \: p_1)$ . The ciphertext consists of the numbers $g_1^k$ and $mh_1^k$ .

Since $h_1^k\equiv (g_1^k)^{a_1}\equiv (g_1^a)^{k_1}\: (mod\: p_1)$ , you can find the message m by using Euclid’s algorithm to find the inverse of $h_1^k$ , and then compute $h_1^k \cdot m[h_1^k]^{-1}\: (mod\: p_1)=m\: (mod\: p_1)$ .

ElGamal signature

To make sure the message is coming from the person you’re expecting it to come from, the other person can sign it. Suppose that the other persons public key depend on the numbers $p_2$ , $g_2$ and $h_2$ , where $h_2=g_2^{a_2}$ . The random number k should be chosen such that $gcd(k, p_2 - 1)=1$ so the inverse I of $k \: (mod\: p_2-1)$ can be computed. The signed message consists of m, $z_1=g_2^k\: (mod\: p_2)$ , and $z_2=(m-a_2z_2)I\: (mod\: p_2-1)$ . These three numbers are encrypted with your public key. When you have decrypted the ciphertext, you can check if the signed message is valid by checking if the congruence $h_2^{z_1}z_1^{z_2}\equiv g_2^m\: (mod \: p_2)$ holds.

How the ElGamal cryptosystem works