Visualizing Diffie-Hellman in Rust + WASM

The Diffie-Hellman equation was my first love in the world of cryptography and cybersecurity as a whole. So I think it fitting it be the first article for this new blog. Hopefully it won't be the only one.

I first came across it when a buddy of mine recommended I apply for a job at the company where he then worked. This company was heavily involved in the cryptography space, so in order to get ready for the interviews, I decided to read up on what was then a new-to-me concept. I checked out a copy of An Introduction to Mathematical Cryptography by Jeffrey Hoffstein from the library of the community college I was attending. I started reading it and working through some of the early exercises. Early on we get to a chapter on the Diffie-Hellman exchange. I stopped. I re-read the earlier sections. I read the proof again and walked through it myself step by step. I found it elegant, magnificent, and absolutely beautiful in the truest sense of that word. I learned it so well that when I went in for my interview I was able to even fully walk through the formal proof on a white board when asked a question about it. I did not get that job (hindsight 20/20, that's a good thing) but that was the first step that catapulted me into the career I enjoy today.

1. The problem: agreeing in public

The question Diffie-Hellman solves is actually pretty simple on the surface: how do you agree on a shared secret with another party whom you have never met and can only communicate with in a public setting? I promise that this shared secret being just a number will pay off big down the road (probably in a future post).

The answer as it turns out is math. Really cool math.

Our cast of characters are ones familiar to anyone that's read anything about cryptography. Alice, Bob, and Eve. Alice and Bob are our protagonists, Eve (short for Eavesdropper) is the antagonist.

Alice and Bob have never met and share no secret. Every byte they exchange is visible to Eve, who is recording everything. Somehow they need to end up holding the same secret number that Eve does not have.

That sounds impossible — and with more classic cryptographic techniques, it is. The trick is to pick an operation that's cheap to do and ludicrously expensive to undo.

2. The toy protocol

The Diffie-Hellman key exchange leans on the Discrete Logarithm Problem — easy to compute one way (powers mod p), painfully hard to reverse. Everything starts from two public numbers, agreed in the open:

p = prime modulus
g = generator   (a base whose powers cycle through the group)

Then each side rolls a private number and publishes one value:

Alice:  private a    public  A = g^a mod p
Bob:    private b    public  B = g^b mod p

They swap A and B over the open channel and each finishes locally:

Alice computes  s = B^a mod p
Bob computes    s = A^b mod p

With the textbook small values p = 23, g = 5, a = 6, b = 15:

A = 5^6  mod 23 = 8
B = 5^15 mod 23 = 19
s = 19^6 mod 23 = 2     (Alice)
s = 8^15 mod 23 = 2     (Bob)

Both land on 2. Eve saw p, g, A, B go past and still can't get there. Drag the sliders and watch it hold:

3. Why both sides get the same number

There's no magic here — just exponents that commute:

B^a = (g^b)^a = g^(b·a) mod p
A^b = (g^a)^b = g^(a·b) mod p

Since b·a = a·b, both sides land on the very same g^(ab) mod p. Alice and Bob arrive at the identical number from opposite directions — and notice what never crossed the wire: not a, not b, and not the secret s itself. That's the whole beautiful trick, in one line.

4. Why Eve loses

So where does all this leave Eve? She's been listening the whole time, so she has p, g, A, and B. To break in she needs to find a (or b) — some exponent where g^a mod p = A. And that, right there, is the discrete logarithm problem we ran into back in section 2.

Going forward — a → g^a mod p — is quick. Going backward — A → a — has no known efficient method when p is large and well chosen. Look at the right-hand plot in the lab and you can almost feel it: g^x mod p scatters everywhere with no usable structure. No slope to follow, no clever binary search, nothing to exploit but brute force — and brute force quietly loses the instant p grows to hundreds of digits.

The left-hand plot is where you can see why the choice of g matters so much. A true generator's orbit sweeps through every nonzero value mod p before it loops back around. Pick a g that isn't a primitive root, though, and that orbit collapses into a small subgroup — the lab will call this out for you — and all of a sudden Eve's search space is a lot smaller than it ought to be. Which is exactly where toy Diffie-Hellman starts to break. We'll pull on that thread in part two.

5. Under the hood: modular exponentiation in Rust

We've leaned on g^x mod p this whole post without once saying how you actually compute it. Strip everything else away and that's the only operation the protocol needs — done over and over. The naive way — compute the giant power and then take the remainder — falls apart fast, because that power gets astronomically large. So instead you reduce as you go, with square-and-multiply:

#[wasm_bindgen]
pub fn mod_exp(base: u64, mut exp: u64, modulus: u64) -> u64 {
    if modulus <= 1 {
        return 0;
    }
    let m = modulus as u128;
    let mut result: u128 = 1;
    let mut b = (base as u128) % m;
    while exp > 0 {
        if exp & 1 == 1 {
            result = result * b % m;
        }
        exp >>= 1;
        b = b * b % m;
    }
    result as u64
}

See that u128? It matters more than it looks. Stay in u64 — or worse, reach for saturating_mul to "handle overflow" — and you've built a primitive that's silently wrong the moment a factor climbs past 2^32, because b * b overflows before the % m ever runs. With the toy primes here you'd never catch it. In real code you'd have shipped a broken crypto primitive and been none the wiser. Widening the intermediate to u128 is the whole fix: cheap, boring, correct. (Past u64 you'd reach for a big-integer type instead.)

And here's the part I still find a little magical: this is the exact function the lab above runs, compiled straight to WebAssembly with wasm-bindgen. No JavaScript reimplementation, no hand-waving — the same Rust I'd write for a real implementation is what's executing in your browser right now.

Why it mattered

It's hard to overstate what Whitfield Diffie and Martin Hellman pulled off in 1976. Before their paper — "New Directions in Cryptography" — private communication meant somehow exchanging a key in secret first, a chicken-and-egg problem people had wrestled with for millennia. They showed that two strangers could agree on a secret in full view of their adversary. That's the whole idea we've been circling, and it quietly became part of the plumbing of the modern world: a direct ancestor of the key exchange behind nearly every HTTPS connection you make.

However this toy version we've been poking at is fragile. Tiny primes fall to brute force in microseconds. A badly chosen g leaks structure — you watched its orbit collapse into a handful of dots. More important, even with big, careful parameters, plain Diffie-Hellman doesn't know who it's talking to: unauthenticated, it's wide open to a man-in-the-middle who quietly runs the exchange with each side. This was actually a key thing I didn't call out in that interview all those years ago.

That gap — between this beautiful equation and what now holds up just about the entirety of private communications on the public networks we call the internet — is where we'll go next.