In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985.[1] ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of PGP, and other cryptosystems. The Digital Signature Algorithm (DSA) is a variant of the ElGamal signature scheme, which should not be confused with ElGamal encryption.

ElGamal encryption can be defined over any cyclic group

, like multiplicative group of integers modulo n. Its security depends upon the difficulty of a certain problem in

related to computing discrete logarithms.

. . . ElGamal encryption . . .

ElGamal encryption consists of three components: the key generator, the encryption algorithm, and the decryption algorithm.

The first party, Alice, generates a key pair as follows:

• Generate an efficient description of a cyclic group
  ${displaystyle G,}$

  of order

  ${displaystyle q,}$

  with generator

  ${displaystyle g}$

  . Let

  ${displaystyle e}$

  represent the unit element of

  ${displaystyle G}$

  .

• Choose an integer
  ${displaystyle x}$

  randomly from

  ${displaystyle {1,ldots ,q-1}}$

  .

• Compute
  ${displaystyle h:=g^{x}}$

  .

• The public key consists of the values
  ${displaystyle (G,q,g,h)}$

  . Alice publishes this public key and retains

  ${displaystyle x}$

  as her private key, which must be kept secret.

. . . ElGamal encryption . . .

. . . ElGamal encryption . . .