ElGamal Encryption

I will elaborate a bit on why ElGamal public key encryption can be thought of as approximately equivalent to using an ephemeral Diffie-Hellman (DH) exchanged key as a one-time pad.

Prerequisite

Diffie-Hellman (DH) Key Exchange

1. Let $G$ be a cyclic group of prime order $q$ with generator $g$.
2. Party A:
   • Picks a secret key $a \in \mathbb{Z}_q$.
   • Computes the public key: $\textcolor{teal}{pk_A} = g^a$.
3. Party B:
   • Picks a secret key $b \in \mathbb{Z}_q$.
   • Computes the public key: $\textcolor{orange}{pk_B} = g^b$.
4. Both parties compute the shared key:
   • A computes: $(pk_B)^a = g^{ba}$.
   • B computes: $(pk_A)^b = g^{ab}$.

Both parties arrive at the same shared secret $\textcolor{#8B4513}{g^{ab}}$, which can be used for symmetric encryption.

See also: Ephemeral and/or static keys.

Original ElGamal Encryption

Let’s first recall the original ElGamal Encryption. Let $G$ be a cyclic group of prime order $q$ with generator $g$. An ElGamal Encryption is a tuple of 3 PPT algorithms:

1. KeyGen:

   • Choose a random secret key $sk \in \mathbb{Z}_q$.
   • Compute the public key $pk = g^{sk}$.
   • Output: $(pk, sk)$.

2. Encrypt(pk, m):

   • Choose a random $r \in \mathbb{Z}_q$.
   • Compute $c_1 = g^r$.
   • Compute $c_2 = m \cdot pk^r = m \cdot g^{r \cdot sk}$.
   • Output: ciphertext $c = (c_1, c_2)$.

3. Decrypt(sk, c):

   • Parse ciphertext $c = (c_1, c_2)$.
   • Compute shared secret $s = c_1^{sk} = g^{r \cdot sk}$.
   • Recover message: $m = c_2 \cdot s^{-1}$.

Suppose A wants to send a message to B and knows B’s ElGamal public key. In this scenario:

• B’s public key in ElGamal encryption is essentially a static DH key, written as $\textcolor{orange}{g^{sk_B}}$.
• When A encrypts a message using B’s public key, it effectively performs a DH key exchange:
  • A picks a random $r$ and computes $\textcolor{teal}{g^r}$, an ephemeral DH key.
  • A then computes a shared key $\textcolor{#8B4513}{g^{r \cdot sk_B}}$ and uses it to blind the message $m$.

• It’s not a pure One-Time Pad (OTP) because the encryption uses multiplication rather than XOR³.

1. This style of blog is inspired by Alin Tomescu’s post on Marlin. ↩

2. ElGamal encryption ↩

3. Hashed ElGamal emulates OTP by hashing the shared key $p = H(pk^r)$ and XORing it with the message. This avoids encoding/decoding messages into the group used by ElGamal. ↩