The Diffie-Hellman Key Exchange

Historical Background

Before 1976 only symmetric cryptography existed: sender and receiver used the same key to encrypt and decrypt. The fundamental problem was: how to share the secret key securely when the communication channel is public?

In 1976 Whitfield Diffie and Martin Hellman published their landmark paper “New Directions in Cryptography” (IEEE Transactions on Information Theory). The core idea: allow two parties to establish a shared secret key over an insecure channel, without having communicated before. This is the birth of public-key (asymmetric) cryptography.

Mathematical Foundations

Modular Arithmetic

Modular arithmetic is the arithmetic of remainders after division. The most intuitive example is a clock: if it is 10 o’clock and 5 hours pass, the result is 3, not 15.

$$10 + 5 = 15 \equiv 3 \pmod{12}$$

In general, $a \equiv b \pmod{n}$ means that $a$ and $b$ have the same remainder when divided by $n$.

The main operations are:

• Addition: $(a + b) \pmod{n}$
• Multiplication: $(a \cdot b) \pmod{n}$
• Exponentiation: $a^b \pmod{n}$ — computable efficiently even with huge numbers thanks to the modular exponentiation algorithm

Example — computing $3^5 \pmod{7}$ step by step:

$$3^2 = 9 \equiv 2 \pmod{7}$$ $$3^4 = (3^2)^2 \equiv 2^2 = 4 \pmod{7}$$ $$3^5 = 3^4 \cdot 3 \equiv 4 \cdot 3 = 12 \equiv 5 \pmod{7}$$

The Discrete Logarithm Problem

In ordinary arithmetic, if $b^x = y$ then $x = \log_b y$. The inverse operation is straightforward.

In the modular world, the discrete logarithm poses the question: given $g$, $y$ and a prime $p$, find $x$ such that

$$g^x \equiv y \pmod{p}$$

Computing $g^x \pmod{p}$ given $x$ is fast (modular exponentiation).
Finding $x$ given the result is computationally intractable for a sufficiently large $p$.

This asymmetry — easy in one direction, impossible in reverse — is the mathematical foundation of Diffie-Hellman security.

The Algorithm: Key Exchange

Communication Diagram

Alice sends her public value; Bob replies with his. Each then raises the received value to their own secret exponent, arriving at the same shared key.

Numerical Example (p = 23, g = 5)

Agreed public parameters: $p = 23$, $g = 5$

Both arrive at $K = 2$ without the value ever travelling in plaintext over the channel.

Why is it secure? An attacker who intercepts $A = 8$, $B = 19$, $p = 23$, $g = 5$ would need to solve the discrete logarithm to find $a$ or $b$, and from there derive $K$. With real numbers in the thousands-of-bits range, this is computationally infeasible with current techniques.

Diffie-Hellman with Elliptic Curves (ECDH)

The Problem with the Classic Version

To guarantee adequate security, the classic version requires very long keys (2048–4096 bits), resulting in high computational cost.

Elliptic Curves

An elliptic curve is defined by an equation of the form:

$$y^2 = x^3 + ax + b$$

    y
  2 │    ·       ·
    │  ·           ·
  1 │ ·             ·
    │·               ·
  0 ┼─────────────────── x
    │·               ·
 -1 │ ·             ·
    │  ·           ·
 -2 │    ·       ·
         y² = x³ − x + 1

In cryptography, curves are defined over finite fields $\mathbb{F}_p$ (not over $\mathbb{R}$). An “addition” operation between points on the curve is defined, with algebraic properties analogous to modular arithmetic.

Why Elliptic Curves Are Better

The “discrete logarithm” on elliptic curves (finding $k$ given $P$ and $kP$) is even harder to solve than in the classic version. This allows much shorter keys for equivalent security:

ECDH Diagram

Public parameters: curve $E$ and base point $G$ on it.

By the properties of elliptic curves, $a(bG) = b(aG)$: both obtain the same point, from which they derive the shared key.

Conclusions

Diffie-Hellman is one of the foundational algorithms of modern cryptography. The key points:

• It enables secure key exchange over a completely public channel.
• Its security rests on the hardness of the discrete logarithm.
• The ECDH variant delivers equivalent security with much shorter keys and is the default choice in modern implementations.
• Real-world applications: HTTPS (TLS 1.3 uses ECDH by default), SSH, VPN, encrypted messaging protocols (Signal), cryptocurrencies.

References

• Whitfield Diffie, Martin E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, 1976.
• Neal Koblitz. Elliptic Curve Cryptosystems. Mathematics of Computation, 1987.
• Victor S. Miller. Use of Elliptic Curves in Cryptography. CRYPTO, 1985.
• William Stallings. Cryptography and Network Security: Principles and Practice. Pearson, 6th ed., 2013.
• A. J. Menezes, P. C. van Oorschot, S. A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.