ElGamal encryption

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 identity element of ${\displaystyle G}$.

  It is not necessary to come up with a group and generator anew 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 ${\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.

A second party, Bob, encrypts a message ${\displaystyle M}$ to Alice under her public key ${\displaystyle (G,q,g,h)}$ as follows:

• Map the message ${\displaystyle M}$ to an element ${\displaystyle m}$ of ${\displaystyle G}$ using a reversible mapping function.
• Choose an integer ${\displaystyle y}$ randomly from ${\displaystyle \{1,\ldots ,q-1\}}$.
• Compute ${\displaystyle s:=h^{y}}$. This is called the shared secret.
• Compute ${\displaystyle c_{1}:=g^{y}}$.
• Compute ${\displaystyle c_{2}:=m\cdot s}$.
• Bob sends the ciphertext ${\displaystyle (c_{1},c_{2})}$ to Alice.

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

Alice decrypts a ciphertext ${\displaystyle (c_{1},c_{2})}$ with her private key ${\displaystyle x}$ as follows:

• Compute ${\displaystyle s:=c_{1}^{x}}$. Since ${\displaystyle c_{1}=g^{y}}$, ${\displaystyle c_{1}^{x}=g^{xy}=h^{y}}$, and thus it is the same shared secret that was used by Bob in encryption.
• Compute ${\displaystyle s^{-1}}$, the inverse of ${\displaystyle s}$ in the group ${\displaystyle G}$. This can be computed in one of several ways. If ${\displaystyle G}$ is a subgroup of a multiplicative group of integers modulo ${\displaystyle n}$, where ${\displaystyle n}$ is prime, the modular multiplicative inverse can be computed using the extended Euclidean algorithm. An alternative is to compute ${\displaystyle s^{-1}}$ as ${\displaystyle c_{1}^{q-x}}$. This is the inverse of ${\displaystyle s}$ because of Lagrange's theorem, since ${\displaystyle s\cdot c_{1}^{q-x}=g^{xy}\cdot g^{(q-x)y}=(g^{q})^{y}=e^{y}=e}$.
• Compute ${\displaystyle m:=c_{2}\cdot s^{-1}}$. This calculation produces the original message ${\displaystyle m}$, because ${\displaystyle c_{2}=m\cdot s}$; hence ${\displaystyle c_{2}\cdot s^{-1}=(m\cdot s)\cdot s^{-1}=m\cdot e=m}$.
• Map ${\displaystyle m}$ back to the plaintext message ${\displaystyle M}$.

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.