## Introduction#

In secure communication and cryptography, the **Diffie-Hellman**^{1} (DH) key exchange is a method of securely exchanging cryptographic keys over a public channel.
It is named after **Whitfield Diffie** and **Martin Hellman**.
The protocol allows **two parties to share a secret key over an insecure channel**, without sending the secret key directly.
Instead messages are exchanged in such a way that the secret key can be derived.

## Background#

Let’s begin with explaining some fundamental concepts used when calculating keys in the protocol.

### Modular Arithmetic#

Initially we need to understand the basics of **modular arithmetic**^{2}.
It is a system of arithmetic for integers, where numbers **“wrap around”** upon reaching a certain value (the modulus) and **start over from zero**.
This is often taught in **discrete mathematics** and **number theory courses**.
It is a **fundamental concept in cryptography**.

Thus all values in a modular system are bound to lie within the range $0$ to $p-1$ for a modulus $p$.
This range is denoted as $\mathbb{Z}_p = \{ 0, 1, \cdots, p-1 \}$ and called the **residue class modulo $p$**.^{3}
However the **multiplicative group of integers modulo ^{4} $p$**, $\mathbb{Z}_p^* = \{ 1, 2, \cdots, p-1 \}$,

**is the one most relevant in the DH protocol**. $0$ is excluded from $\mathbb{Z}_p^*$ because does not have a multiplicative inverse.

Note

$\mathbb{Z}_p^*$ has anorder(aka, total number of elements)of $|\mathbb{Z}_p^*| = p - 1$.

### Modular Exponentiation#

The *algorithm* in the DH protocol uses **modular exponentiation**^{5} to compute its keys.
It is a type of exponentiation performed over a modulus of $p$ with values in $\mathbb{Z}_p$.
Exponentiation in modular arithmetic involves computing the remainder when a number is raised to a power and divided by a modulus:

$$ \begin{align*} a^n \mod p = & \newline a \times \cdots \times a \mod p = & \newline (a \mod p) \times \cdots \times (a \mod p) \mod p = & \newline \end{align*} $$

We can try to “optimize” the multiplications by taking the remainder after each repeated multiplication to **keep the numbers small during the entire calculation**.
This results in *faster and more memory-efficient* computation.
However, due to **$O(n^2)$ time complexity** of multiplication^{6} and the fact that the number of iterations will still be $O(n)$, which for large numbers of roughly $2048$ bits, is *a lot of multiplications* and is **computationally expensive**.**But there is a way to solve this!**

#### Square-and-multiply#

This optimized algorithm computes the modular exponentiation by squaring^{7}, in **logarithmic time complexity** of $O(\log n)$, *where $n$ is the size of the exponent*.
It takes advantage of the **binary representation** of the exponent and moves from the **least significant bit (LSB)** to the **most significant bit (MSB)**, also known as the **Right-to-Left Binary Method**^{5}^{7}.

```
def mod_exp(b, e, m):
result = 1
x = b % m
while e > 0:
if e % 2 == 1:
result = (result * x) % m
x = (x * x) % m
e = e >> 1
return result
```

#### Example#

We can easily calculate, $5^{23} \mod 97 \equiv 82$, using the **SaM RTL method** above, where $e = 23_{10} = 10111_2$.

## Step-by-step calculation

- $r \gets 1$ and $x \gets 5 \mod 97 = 5$.
Initialize the $result$ and the base number $x$.

- $[e = 23_{10} = 10111_2] > 0$:
- $10111_2 \mod 2 \equiv 1 \implies r \gets (1 \times 5) \mod 97 = 5$.
Check if the last significant bit (LSB) of $e$ in base 2 is $1$. Then multiply the result with $x$ in modulo $m = 97$.

- $x \gets 5^2 \mod 97 = 25$ and $e \gets \lfloor\frac{10111_2}{2}\rfloor = 1011_2$.
Square $x$ and shift the bits of $e$ to the right.

- $10111_2 \mod 2 \equiv 1 \implies r \gets (1 \times 5) \mod 97 = 5$.
- $[e = 11_{10} = 1011_2] > 0$:
- $1011_2 \mod 2 \equiv 1 \implies r \gets (5 \times 25) \mod 97 = 28$.
LSB is $1$, so update the result again with the new $x$.

- $x \gets 25^2 \mod 97 = 43$ and $e \gets \lfloor\frac{1011_2}{2}\rfloor = 101_2$.

- $1011_2 \mod 2 \equiv 1 \implies r \gets (5 \times 25) \mod 97 = 28$.
- $[e = 5_{10} = 101_2] > 0$:
- $101_2 \mod 2 \equiv 1 \implies r \gets (28 \times 43) \mod 97 = 40$.
- $x \gets 43^2 \mod 97 = 6$ and $e \gets \lfloor\frac{101_2}{2}\rfloor = 10_2$.

- $[e = 2_{10} = 10_2] > 0$:
- $10_2 \mod 2 \not\equiv 1 \implies$ do nothing.
The LSB is $0$, so no update is needed.

- $x \gets 6^2 \mod 97 = 36$ and $e \gets \lfloor\frac{10_2}{2}\rfloor = 1_2$.

- $10_2 \mod 2 \not\equiv 1 \implies$ do nothing.
- $[e = 1] > 0$:
- $1 \mod 2 \equiv 1 \implies r \gets (40 \times 36) \mod 97 = 82$.
LSB is $1$, so update the result one last time.

- $r = 82$.

- $1 \mod 2 \equiv 1 \implies r \gets (40 \times 36) \mod 97 = 82$.
- $[e = 0] \not> 0 \implies$ return the result $r = 82$.

In **$\approx 5$ steps** we managed to compute $5^{23} \mod 97 = 82$ using the **square-and-multiply method**, which using repeated multiplication would have taken **$22$ steps**. The algorithm took about the same amount of iterations as expected from $\log_2(23) = 4.52 \approx 5$, which takes about $\frac{\log_2(23)}{23} \approx \frac{5}{23} \approx 19\%$ of the steps compared to naive repeated multiplication.

If I were to ask you which power $e$ I started with to get to $82$, only knowing $b=5$, $p=97$.
You would have to **brute-force** it by trying different exponents until you find *the correct one* ($b = 23$).

This is the essence of the **discrete logarithm problem**.

### Discrete Logarithm Problem#

The **discrete logarithm problem**^{8} (DLP) is the basis for the security of the DH key exchange.
Finding the exponent $x$ in the equation $g^x = A \mod p$ is **computationally infeasible** for large numbers.
**No efficient classical algorithm is known** for computing discrete logarithms in general.
In fact, it is an exponential-time algorithm.^{8}
Given this, the set of all integers $a$ satisfying $A \equiv g^a \mod p$ can be expressed using the discrete logarithm:

$$ a \equiv \log_g A \mod \text{ord}_p(g) $$

The **multiplicative order** of $g$ modulo $p$, denoted as $\text{ord}_p(g)$, is the smallest positive integer $n$ such that $g^n \mod p \equiv 1$.
The order of $g$ is a divisor of $p - 1$, meaning that $\text{ord}_p(g) \mid |\mathbb{Z}_p^*|$.

Note

Theorder of the generator $g$, denoted as $\text{ord}_p(g)$, is adivisor of $p - 1$but not necessarily equal. This means that $\text{ord}_p(g) \mid |\mathbb{Z}_p^*| \iff \text{ord}_p(g) \mid p - 1$for all$g \in \mathbb{Z}_p^*$.

Further analysis **why the discrete logarithm problem is hard to solve** can be found in the Wikipedia article.

## Algorithm#

The algorithm is based on **DLP**.
As it is very hard to solve for large numbers, the algorithm is considered cryptographically secure if the parameters are chosen correctly.

A = g^a mod p Alice->>Bob: A Note left of Bob: b = random()

B = g^b mod p Bob->>Alice: B Note over Alice, Bob: K = B^a mod p and K = A^b mod p

*Short explanation of the steps above:*

**Setup**: Alice and Bob agree on a**prime number $p$**and a**generator $g$**.**Alice**: Alice randomly chooses a**secret number $a$**and computes $A = g^a \mod p$.**Bob**: Bob randomly chooses a**secret number $b$**and computes $B = g^b \mod p$.**Exchange**: Alice sends $A$ to Bob and Bob sends $B$ to Alice.**Key**: Alice computes $K = B^a \mod p$ and Bob computes $K = A^b \mod p$.

Naming

$p$ and $g$ arepublic parameters. Both $a$ and $b$ are kept secret, and are therefore calledprivate keys. The numbers $A$ and $B$ are calledpublic keys, as they get sent over the public channel`Internet`

.

**Alice and Bob now share the same secret key $K$ without anyone eavesdropping knowing it!**
The initial numbers **$p$ and $g$**, and the generated **$A$ and $B$** are **public** and can be shared over an insecure channel **without compromising the key $K$**.

## Multi-party#

It is possible to extend this protocol to more than two parties where each agrees on the same $p$ and $g$ and each party chooses a secret key and computes a public key.
Similar steps are followed as in the two-party case, but the **shared secret key** is computed with everyone’s public keys using **$ K = g^{a b c} \mod p $**^{1}, where $a$, $b$, and $c$ are the private keys of the parties.

## Drawbacks#

As to any technology, there are drawbacks and vulnerabilities to recognize.

### Man-in-the-Middle Attack#

Everything is fine until **Charles** comes into the picture.
He is **not only eavesdropping** but also **actively manipulating the messages**.
This is called a **Man-in-the-Middle**^{9} (MitM) attack.
The DH protocol is **vulnerable** to this because Charles can **generate his own keys**, and **forward the messages** to each of the other parties separately, without them knowing.
By doing so, he can **decrypt and read the messages**, **alter them**, and **re-encrypt** them before sending them on to the intended recipient, thereby compromising the encryption and the security of the communication.

Solution

The fundamental issue is that the partiescannot verify the authenticityof the public keys they receive. That is,Bob cannot be 100% surethat the public key he receives is actually from Alice.Both Alice and Bob need to agree to trust some

third partyto verify the authenticity of the public keys. This is done via adigital signature^{10}provided by acertificate authority^{11}(CA). Before Alice and Bob exchange their public keys, they send them to the CA to besigned by the CA’s private key. After receiving thesigned public keys, both Alice and Bob canverify their authenticityby checking the signature using theCA’s public keywhich everyone has access to. Only then will they trust each other’s public keys, and proceed with the key exchange.

**certificate pinning**or other forms of

**authentication**to verify authenticity.

### Pohlig-Hellman Algorithm#

The **Pohlig-Hellman algorithm**^{12} is a **discrete logarithm algorithm** that can be used to **efficiently solve DLP $\iff$ (if and only if) either** the

**or the**

*order of the group*$|\mathbb{Z}_p^*| = p - 1$**. Thus the private keys and the shared secret can be computed,**

*order of the generator*$\text{ord}_p(g)$ factors into small prime numbers**breaking the security**of the DH key exchange. The algorithm split the problem into smaller

**subgroups of order $q_i$**.

$$ n = \prod_{i=1}^k q_i^{e_i} = q_1^{e_1} \times q_2^{e_2} \times \cdots \times q_k^{e_k} $$

Where, $n = \text{ord}_p(g)$ * or* $n = p - 1$, and all

**$q_i$ are the prime factors of $n$**. This algorithm can be used to break the DH key exchange if the

**prime number $p$**is not chosen carefully.

Solution

Because of Pohlig-Hellman algorithm working efficiently when $p-1$ or $\text{ord}_p(g)$ factors into small primes, we can choose alarge prime number $p$such that$p - 1$ has at least one large prime factorto make the DLPharder to solve. This is why it is recommended to use2048-bit or 4096-bit prime numbersin practice.To select a sufficiently large prime number $p$, we can use

safe primes^{13}on the form $p = 2q + 1$, where both $p$ and $q$ are prime. Additionally, selecting agenerator $g$ with a large order$q = \text{ord}_p(g)$ ensures computations are performed within thislarge prime-order subgroup, further enhancing security. Safe primes ensure that $n$ has alargeprime factor,rendering the Pohlig-Hellman algorithm ineffective!

## Security#

Before summing up this post about Diffie-Hellman, let’s talk about the **security aspects** and what to think about when choosing the parameters or using the protocol in general.

The security of the DH protocol relies on good choices of the **prime number $p$** and the **generator $g$** to make **DLP** hard to solve, which is crucial for maintaining the confidentiality of the shared secret.
Below is a list of **best practices** to keep in mind when using the DH protocol to ensure secure communications:

Guideline | Risk |
---|---|

Choose a Large Prime Number $p$Select a prime $p$ of at least 2048 bits. | Using a smaller prime makes it feasible for attackers to use brute-force methods to solve the DLP. |

Use Safe Primes^{13}Opt for $p = 2q + 1$ where $p, q$ are prime, ensuring $p - 1$ has a large prime factor. | If $\text{ord}_p(g)$ or $p - 1$ factors into small primes, attackers can use the Pohlig-Hellman^{12} algorithm to solve the DLP efficiently, compute the private keys and shared secret. |

Select an Appropriate Generator $g$Choose $g$ with a large prime-order subgroup $\text{ord}_p(g) = q$ of $\mathbb{Z}_p^*$ to operate within. | A generator with a small order allows attackers to exploit smaller subgroups where the DLP is easier to solve using Pohlig-Hellman^{12}. |

Avoid Deprecated ParametersAlways use the latest reccomended parameters from industry and trusted agencies. | Using standard parameters with known weaknesses may expose you to other attacks. Such as in RFC 5114 suggesting a group with 160-bit $q$ or $\text{ord}_p(g)$ value, too smallNOT RECOMMENDED^{14} and MUST NOT USE. New updated suggestions in RFC 3526, RFC 7296, RFC 4419 among others. |

Verify Public KeysUse certificate authorities^{11} (CA) and digital signatures^{10} or certificate pinning^{15} to authenticate public keys. | Without proper verification, attackers can perform MitM^{9} attacks and impersonate parties by substituting their own public keys, enabling them to intercept and decrypt communications. |

Careful selection of $p$ and $g$ significantly enhances the security of the DH protocol by maintaining the difficulty of the DLP, thereby safeguarding secure communications in cryptographic systems.

## Conclusion#

Diffie-Hellman (DH) is vastly used in many cryptographic protocols such as **TLS/SSL**, **SSH**, **IPsec**, and **PGP**.
The main benefit comes from the **forward secrecy** provided by the protocol, as new keys get generated for each unique session.
This makes it **more difficult** for an attacker to decrypt past sessions if the current key is compromised.
With the **right parameters** and **good practices**, the Diffie-Hellman key exchange is a **secure and efficient** way to establish a shared secret key over an insecure channel.

**want to show your support**, consider sponsoring me! I use donations to

**buy coffee ☕️**and

**write more articles**that you'll love. ❤️ Donate Now 🙏

Diffie-Hellman key exchange by Whitfield Diffie and Martin Hellman. ↩︎ ↩︎

Modular arithmetic is a system of arithmetic for integers, where numbers “wrap around” upon reaching a certain value. ↩︎

A residue class is a set of integers that are congruent modulo a given integer. ↩︎

The multiplicative group modulo $n$ is the set of integers relatively prime to $n$ under multiplication modulo $n$. ↩︎

Modular exponentiation is a type of exponentiation performed over a modulus. ↩︎ ↩︎

Multiplication Algorithm is a method to multiply two numbers using a series of additions and shifts. ↩︎

Exponentiation by squaring is a general method for fast computation of large positive integer powers of a number. ↩︎ ↩︎

The discrete logarithm problem (DLP) is the problem of finding the exponent $x$ in the equation $g^x = A \mod p$. ↩︎ ↩︎

A Man-in-the-Middle attack is an attack where the attacker secretly relays and possibly alters the communication between two parties. ↩︎ ↩︎

Digital signatures are used to verify the authenticity of a message or document. ↩︎ ↩︎

A certificate authority is an entity that issues digital certificates. ↩︎ ↩︎

The Pohlig-Hellman algorithm is a discrete logarithm algorithm that can be used to solve the discrete logarithm problem in a cyclic group. ↩︎ ↩︎ ↩︎

Safe and Sophie Germain primes are primes on the form $2p + 1$ where $p$ is also a prime. ↩︎ ↩︎

See discussion in https://support.checkpoint.com/results/sk/sk27054. ↩︎

Certificate pinning is a security mechanism that associates a host with its expected public key or keys. ↩︎