It works as follows:

KEY GENERATION. Choose a large prime *p*, such that the discrete logarithm problem in the cyclic group (**Z**_{p})^{×} (consisting of the congruence classes of 1, 2, ..., *p*-1 under multiplication modulo *p*) is intractable. Choose a
primitive root modulo *p* and call it *g*; then *g* generates the group (**Z**_{p})^{×}. Choose a random *k* with 1 < *k* < *p*-1. Calculate *h* = *g*^{k} mod *p* (with exponentiating by squaring). Then the public key is (*p*, *g*, *h*), and the private key is (*p*, *g*, *k*).

ENCRYPTION. To encrypt a message using the public key (*p*, *g*, *h*), first encode the message as a number *m* with 1 ≤ *m* ≤ *p* - 1 using a known reversible protocol. Then pick a random *s* with 1 < *s* < *p*-1 and calculate *c*_{1} = *g*^{s} mod *p* and *c*_{2} = *m***h*^{s} mod *p*. The cryptogram is then (*c*_{1}, *c*_{2}).

DECRYPTION. To recover the original message *m* from (*c*_{1}, *c*_{2}) using the private key (*p*, *g*, *k*), calculate *c*_{1}^{-k}**c*_{2} mod p. This works because *c*_{1}^{-k}**c*_{2} = (*g*^{s})^{-k} * *m***h*^{s} = (*g*^{k})^{-s} * *m***h*^{s} = *h*^{-s} * *m***h*^{s} = *m* mod *p*.

Elgamal can also be used to implement digital signatures, as follows:

KEY GENERATION. Same as for the encryption system above.

SIGNING. To sign the message *m* with the secret key (*p*, *g*, *k*) choose a random *s* with 1 < *s* < *p*-1 and *s* coprime to *p*-1 (in order that *s* has a multiplicative inverse modulo *p*-1). Calculate *s*_{1} = *g*^{s} mod *p* and *s*_{2} = (*m* - *ks*_{1})*s*^{-1} mod (*p*-1). The signature is (*s*_{1}, *s*_{2}).

VERIFICATION. To verify the signature (*s*_{1}, *s*_{2}) of the message *m* with the public key (*p*, *g*, *h*), verify that the following congruence holds: *h*^{s1} * *s*_{1}^{s2} = *g*^{m} (mod *p*).