Diffie-Hellman Key Exchange

The Key Exchange Problem

Secure communication requires two parties to share secret information. In classical symmetric cryptography, both parties must already possess the same secret key before communication begins.

This raises a practical problem:

how can two people agree on a secret key over an insecure channel?

The Diffie-Hellman key exchange solves this problem. It allows two parties to create a shared secret even when an attacker can observe all public messages.

Its security rests on the difficulty of the discrete logarithm problem.

Cyclic Groups

Diffie-Hellman takes place in a cyclic group.

Let

G=\langle g\rangle

be a finite cyclic group generated by an element $g$ . Every element of $G$ has the form

g^n

for some integer $n$ .

Common choices include:

(\mathbb{Z}/p\mathbb{Z})^\times

for a large prime $p$ , or the group of points on an elliptic curve over a finite field.

The group operation is public. The security depends on exponentiation being easy while reversing exponentiation is hard.

The Discrete Logarithm Problem

Given

g

and

g^a,

the discrete logarithm problem asks for the exponent

a.

In suitable groups, computing

g^a

is efficient, but recovering $a$ from $g^a$ is believed to be difficult.

This asymmetry is the mathematical foundation of Diffie-Hellman.

Basic Protocol

Suppose Alice and Bob agree publicly on a finite cyclic group

G

and a generator

g.

Alice chooses a secret integer

a.

Bob chooses a secret integer

b.

Alice sends

A=g^a

to Bob.

Bob sends

B=g^b

to Alice.

Alice computes

B^a=(g^b)^a=g^{ab}.

Bob computes

A^b=(g^a)^b=g^{ab}.

Both obtain the same shared secret:

g^{ab}.

An eavesdropper sees only

g,\quad g^a,\quad g^b,

but must compute

g^{ab}.

This is known as the computational Diffie-Hellman problem.

Example in a Small Group

Small examples are insecure, but they illustrate the arithmetic.

Let

p=23, \qquad g=5.

Alice chooses

a=6,

so she sends

A=5^6\equiv8\pmod{23}.

Bob chooses

b=15,

so he sends

B=5^{15}\equiv19\pmod{23}.

Alice computes

B^a=19^6\equiv2\pmod{23}.

Bob computes

A^b=8^{15}\equiv2\pmod{23}.

Their shared secret is

2.

Real systems use much larger groups.

Why the Protocol Works

The correctness follows from associativity of exponentiation:

(g^a)^b=g^{ab}=(g^b)^a.

The public values reveal group elements, not exponents. If the discrete logarithm problem is hard in $G$ , then recovering the secret exponents is computationally infeasible.

Thus Diffie-Hellman separates public computation from private inversion.

Finite-Field Diffie-Hellman

The classical version uses the multiplicative group

(\mathbb{Z}/p\mathbb{Z})^\times.

This group has order

p-1.

One usually selects a subgroup of large prime order to avoid small-subgroup attacks.

Finite-field Diffie-Hellman requires careful parameter selection. The prime $p$ , subgroup order, and generator must be chosen so that known discrete logarithm algorithms are ineffective.

Elliptic Curve Diffie-Hellman

Elliptic curve Diffie-Hellman replaces modular exponentiation with scalar multiplication on an elliptic curve.

Let

P

be a public point on an elliptic curve.

Alice sends

A=[a]P.

Bob sends

B=[b]P.

Alice computes

[a]B=[ab]P.

Bob computes

[b]A=[ab]P.

The shared secret is derived from the point

[ab]P.

Elliptic curve groups provide comparable security with smaller key sizes than finite-field groups.

Man-in-the-Middle Attack

Unauthenticated Diffie-Hellman is vulnerable to a man-in-the-middle attack.

An attacker can intercept Alice’s message, substitute their own value, and do the same to Bob. Alice and Bob then establish separate secrets with the attacker instead of with each other.

Therefore Diffie-Hellman by itself provides key agreement, not authentication.

Practical protocols combine Diffie-Hellman with:

digital signatures,
certificates,
password authentication,
pre-shared keys.

Ephemeral Diffie-Hellman

In ephemeral Diffie-Hellman, new secret exponents are generated for each session.

This provides forward secrecy.

If a long-term private key is compromised later, past session keys remain protected, provided the ephemeral exponents were erased.

Forward secrecy is one of the main reasons Diffie-Hellman remains central in modern secure communication protocols.

Security Assumptions

Several related hardness assumptions appear in the theory.

The discrete logarithm problem asks for $a$ from

g^a.

The computational Diffie-Hellman problem asks for

g^{ab}

from

g^a \quad\text{and}\quad g^b.

The decisional Diffie-Hellman problem asks whether a given triple

(g^a,g^b,g^c)

satisfies

c=ab.

Different cryptographic constructions require different assumptions.

Known Attacks

Security depends strongly on the group.

For finite fields, index calculus algorithms can solve discrete logarithms faster than generic methods. This forces larger parameter sizes.

For elliptic curves, no comparable general index calculus method is known for properly chosen curves. Generic attacks such as Pollard rho require roughly square-root time in the group order.

Weak groups, small subgroups, poor randomness, and invalid public keys can all break implementations.

Quantum Threat

Diffie-Hellman is vulnerable to Shor’s algorithm.

A sufficiently large fault-tolerant quantum computer could solve discrete logarithms efficiently in both finite-field and elliptic curve groups.

This is one reason post-quantum key exchange protocols are being developed and deployed.

Role in Modern Protocols

Diffie-Hellman ideas appear throughout secure communication.

Examples include:

Protocol Context	Role
TLS	Session key agreement
SSH	Secure channel establishment
Signal protocol	Ratcheted key agreement
VPN protocols	Secure tunnel setup
Messaging systems	Forward secrecy

Modern systems usually use authenticated ephemeral elliptic curve Diffie-Hellman or post-quantum alternatives.

Conceptual Importance

Diffie-Hellman is one of the foundational discoveries of public-key cryptography.

Its mathematical core is simple: exponentiation in a suitable group is easy, while reversing it is hard.

From this asymmetry, two parties can create a shared secret across an insecure channel.

The protocol introduced a new way to think about cryptography. Security could arise not from prior shared secrets, but from computational hardness in algebraic structures.