Editing ElGamal encryption (section)

== The algorithm   ==
The algorithm can be described as first performing a Diffie–Hellman key exchange to establish a shared secret <math>s</math>, then using this as a [[one-time pad]] for encrypting the message. ElGamal encryption is performed in three phases: the key generation, the encryption, and the decryption. The first is purely key exchange, whereas the latter two mix key exchange computations with message computations.

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

* Generate an efficient description of a [[cyclic group]] <math>G\,</math> of [[order (group theory)|order]] <math>q\,</math> with [[generating set of a group|generator]] <math>g</math>.  Let <math>e</math> represent the identity element of <math>G</math>.
*: It is not necessary to come up with a group and generator for each new key. Indeed, one may expect a specific implementation of ElGamal to be hardcoded to use a specific group, or a group from a specific suite. The choice of group is mostly about how large keys you want to use.
* Choose an integer <math>x</math> randomly from <math>\{1, \ldots, q-1\}</math>.
* Compute <math>h := g^x</math>.
* The '''[[public key]]''' consists of the values <math>(G,q,g,h)</math>. Alice publishes this public key and retains <math>x</math> as her '''private key''', which must be kept secret.

=== Encryption ===
A second party, Bob, encrypts a message <math>M</math> to Alice under her public key <math>(G,q,g,h)</math> as follows:

* Map the message <math>M</math> to an element <math>m</math> of <math>G</math> using a reversible mapping function.
* Choose an integer <math>y</math> randomly from <math>\{1, \ldots, q-1\}</math>.
* Compute <math>s := h^y</math>. This is called the ''shared secret''.
* Compute <math>c_1 := g^y</math>.
* Compute <math>c_2 := m \cdot s</math>.
* Bob sends the ciphertext <math>(c_1,c_2)</math> to Alice.

Note that if one knows both the ciphertext <math>(c_1,c_2)</math> and the plaintext <math>m</math>, one can easily find the shared secret <math>s</math>, since <math>c_2 \cdot m^{-1} = s</math>. Therefore, a new <math>y</math> and hence a new <math>s</math> is generated for every message to improve security. For this reason, <math>y</math> is also called an [[ephemeral key]].

=== Decryption ===
Alice decrypts a ciphertext <math>(c_1, c_2)</math> with her private key <math>x</math> as follows:
* Compute <math>s := c_1^x</math>. Since <math>c_1 = g^y</math>, <math>c_1^x = g^{xy} = h^y</math>, and thus it is the same shared secret that was used by Bob in encryption.
* Compute <math>s^{-1}</math>, the inverse of <math>s</math> in the group <math>G</math>. This can be computed in one of several ways. If <math>G</math> is a subgroup of a multiplicative group of integers modulo&nbsp;<math>n</math>, where <math>n</math> is prime, the [[modular multiplicative inverse]] can be computed using the [[extended Euclidean algorithm]]. An alternative is to compute <math>s^{-1}</math> as <math>c_1^{q-x}</math>. This is the inverse of <math>s</math> because of [[Lagrange's theorem (group theory)|Lagrange's theorem]], since <math>s \cdot c_1^{q-x} = g^{xy} \cdot g^{(q-x)y} = (g^{q})^y = e^y = e</math>.
* Compute <math>m := c_2 \cdot s^{-1}</math>. This calculation produces the original message <math>m</math>, because <math> c_2 = m \cdot s</math>; hence <math>c_2 \cdot s^{-1} = (m \cdot s) \cdot s^{-1} = m \cdot e = m</math>.
* Map <math>m</math> back to the plaintext message <math>M</math>.

=== Practical use ===

Like most public key systems, the ElGamal cryptosystem is usually used as part of a [[hybrid cryptosystem]], where the message itself is encrypted using a symmetric cryptosystem, and ElGamal is then used to encrypt only the symmetric key. This is because asymmetric cryptosystems like ElGamal are usually slower than symmetric ones for the same [[level of security]], so it is faster to encrypt the message, which can be arbitrarily large, with a symmetric cipher, and then use ElGamal only to encrypt the symmetric key, which usually is quite small compared to the size of the message.