Encyclopedia > ElGamal discrete log cryptosystem

  Article Content

ElGamal discrete log cryptosystem

The ElGamal algorithm is an asymmetric key encryption algorithm[?] for public key cryptography which is based on discrete logarithms. The ElGamal algorithm is used in the free GNU Privacy Guard software, recent versions of PGP, and other crypto systems. It can be used for encryption/decryption, and also for digital signatures. NSA's Digital Signature Algorithm is based on ElGamal, and is very similar.

It works as follows:

KEY GENERATION. Choose a large prime p, such that the discrete logarithm problem in the cyclic group (Zp)× (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 (Zp)×. Choose a random k with 1 < k < p-1. Calculate h = gk 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 ≤ mp - 1 using a known reversible protocol. Then pick a random s with 1 < s < p-1 and calculate c1 = gs mod p and c2 = m*hs mod p. The cryptogram is then (c1, c2).

DECRYPTION. To recover the original message m from (c1, c2) using the private key (p, g, k), calculate c1-k*c2 mod p. This works because c1-k*c2 = (gs)-k * m*hs = (gk)-s * m*hs = h-s * m*hs = 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 s1 = gs mod p and s2 = (m - ks1)s-1 mod (p-1). The signature is (s1, s2).

VERIFICATION. To verify the signature (s1, s2) of the message m with the public key (p, g, h), verify that the following congruence holds: hs1 * s1s2 = gm (mod p).

Security

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.)



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
1228

... century - 13th century - 14th century Decades: 1170s 1180s 1190s 1200s 1210s - 1220s - 1230s 1240s 1250s 1260s 1270s Years: 1223 1224 1225 1226 1227 - 1228 - 1229 ...