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, ..., p1 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 < p1. 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 < p1 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 < p1 and s coprime to p1 (in order that s has a multiplicative inverse modulo p1). Calculate s_{1} = g^{s} mod p and s_{2} = (m  ks_{1})s^{1} mod (p1). 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).
Breaking ElGamal is believed to be, by most informed observers, generally as difficult as solving the discrete logarithm problem. If the discrete logarithm problem could be solved efficiently, then ElGamal could be broken. However, it remains possible that there may be some way to break ElGamal without having to solve that problem.
NB: When signing a message using the ElGamal algorithm, the per message random value s used may never be made public. Nor may the same s value be used to sign two different messages; doing so will enable an opponent to easily recover the secret key. (Proof left as exercise to reader.)
Search Encyclopedia

Featured Article

