Diffie–Hellman Key Exchange and ElGamal Encryption

Diffie-Hellman Key Exchange (DHKE) Protocol

Problem. Suppose Alice and Bob are communicating over a public channel and wish to securely exchange a secret number, called the symmetric key, such that only they can know it.

Protocol

The protocol is illustrated in the figure below. We assume that $p$ is a publicly known prime, $\mathbb{F}_p$ is the finite field of order $p$, and $g$ is a generator of the multiplicative group $\mathbb{F}_p^* = \{1, 2, \ldots, p - 1\}$. The final encryption step may use another algorithm such as AES, with $S$ (or some bits of $S$) serving as the key.

Correctness

The correctness of the protocol follows directly from the commutativity of the multiplicative group $\mathbb{F}_p^*$:

Security Guarantee

The security of the protocol relies on the computational hardness of the following problem:

Diffie-Hellman Problem (DHP). Given $(p, g, A, B)$ observed by a passive adversary, the problem asks whether the adversary can compute $S = g^{ab}$.

It is clear that DHP can be solved if the following problem is solvable:

Discrete Logarithm Problem (DLP) in $\mathbb{Z}_p^*$. Given the finite cyclic group $\mathbb{Z}_p^*$ of order $p - 1$, a generator $g$, and an element $A \in \mathbb{Z}_p^*$, the problem asks for $a \in [p - 1]$ such that

$$g^a \equiv A \pmod{p}.$$

However, it is not known whether solving DLP is the only way to solve DHP.

Computation

1. $A$ and $B$ can be efficiently computed using fast exponentiation.
2. $S^{-1}$ can be computed as follows:
   • By Fermat's Little Theorem: $S^{p - 1} \equiv 1 \pmod{p}$.
   • Hence, $S^{-1} \equiv S^{p - 2} \pmod{p}$, which can also be computed via fast exponentiation.

Generalization

The protocol can be generalized to other cyclic groups beyond $\mathbb{Z}_p^*$, such as elliptic curve groups. In that case, the security relies on the hardness of the following problem:

Generalized Diffie-Hellman Problem (DHP). Given a finite cyclic group $G$ of order $n$, a generator $g \in G$, and two elements $A = g^a$, $B = g^b$, the problem is to compute $g^{ab}$.

This problem can be solved if the following is easy:

Generalized Discrete Logarithm Problem (DLP). Given a finite cyclic group $G$ with operation $\circ$ and order $n$, a generator $g \in G$, and an element $A \in G$, the problem asks for $a \in [n]$ such that

$$g^a = \underbrace{g \circ \cdots \circ g}_{a \,\text{times}} = A.$$

It is worth noting that the discrete logarithm problem is not hard in all cyclic groups; hardness depends on the choice of group.

ElGamal Encryption

Problem. Suppose Alice and Bob are communicating over a public channel. Alice wants to publish a public key so that Bob can encrypt a message for her, while only Alice can decrypt it using her secret key.

Protocol

The protocol is illustrated in the figure below. It can be seen as a reordering of the steps in the Diffie-Hellman key exchange protocol.
Its correctness and security guarantees follow directly from the DHKE framework.

Additional Remark. Each time Bob encrypts a message, a fresh masking key is generated. Thus, even if the same message is sent multiple times, the ciphertexts will differ. This property is known as probabilistic encryption.

Reference

[1] C. Paar, J. Pelzl, and T. Güneysu, "Understanding Cryptography: From Established Symmetric and Asymmetric Ciphers to Post-Quantum Algorithms." Berlin, Heidelberg: Springer Berlin Heidelberg, 2024. doi: 10.1007/978-3-662-69007-9.