ElGamal encryption

related topics
{math, number, function}
{system, computer, user}
{war, force, army}

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 1984.[1] ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of PGP, and other cryptosystems. The Digital Signature Algorithm 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 G. Its security depends upon the difficulty of a certain problem in G related to computing discrete logarithms (see below).


The algorithm

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

Key generation

The key generator works as follows:

  • Alice generates an efficient description of a multiplicative cyclic group G\, of order q\, with generator g\,. See below for a discussion on the required properties of this group.
  • Alice chooses a random x\, from \{0, \ldots, q-1\}.
  • Alice computes h = g^x\,.
  • Alice publishes h\,, along with the description of G, q, g\,, as her public key. Alice retains x\, as her private key which must be kept secret.

Full article ▸

related documents
Burali-Forti paradox
Gaussian integer
Principal ideal
Möbius inversion formula
Connected space
Fuzzy set
Discrete space
Twin prime
Initial and terminal objects
Torsion subgroup
Floor and ceiling functions
Triangle inequality
Linear classifier
Euclidean domain
Harmonic series (mathematics)
Enriched category
Transfinite induction
Infinite product
Fermat's little theorem
Bounded set
String searching algorithm
Pre-Abelian category
Dimension (vector space)
Standard Generalized Markup Language