logoZK Academy

02. Diffie-Hellman Key Exchange

How to keep secrets in a public space

Encrypting messages

Let's imagine we want to have a secret conversation with a friend over the internet. You can agree on a shared key, that you will use to encode your messages. To exchange the private key, you can meet privately. You will share the key, return each to your homes, and text each other using encoded messages

In some sense, that's how we did cryptography for centuries - exchange a shared key privately, and use it to encode the messages. When a message is encrypted, you and your friend are the only ones who can decipher it. You can send a postman with your encoded message, and if a postman will get curious and read it - they won't be able to decrypt it. You can even broadcast your message over the radio - nobody else has a secret key to it, so they won't get the actual content

This approach is called symmetric-key cryptography — the same key locks and unlocks the message. The hard part was never the encryption itself, but getting that key to your friend without anyone else seeing it. Cryptographers call this the key distribution problem.

Key exchange, the old way
Meet in private, then talk in public
dark alleypublic channelJeffreyBill9#4∆7%3§8×5?

But can you agree on a shared key over the same unprotected channel you deliver the encrypted message over? Just to exclude the "meet at the alley privately" part. Sounds quite tough but it is possible, and already was done by your browser as you opened this page

Sharing secrets publicly

If you send unencrypted messages over the internet - you should consider it is unsafe operation. Your ISP can see whatever requests you made as it delivers them. A server that your message arrives at, is owned by some company. Owner can secretly listen to all incoming traffic, or being infected by spyware. Chances this happening over you asking your friend "how are you doing?", but if you send your bank card details, or discuss something extremely sensitive - someone can have incentive to capture it

So how can we agree on something secret, talking in a public space? We already got one ingredient of this magic - the modulo operator, and we need to upgrade it

Integers problems

Some problems are just suck to solve in integers. For example integer factorization. You can easily figure out that 13 multiply by 7 is 91. But how can you figure out what integers you need to multiply to get a given number? For example 119. There are no efficient way of doing so, you can make a couple of optimizations, but it's not half as easy as going the other way

RSA encryption actually based on hardness of integer factorization

Something similar happens with this set of operations:

g^x mod p

So it's - you take a number g (called "generator" since we produce from it) to a power of x (it's actually our secret number), and do modulo of p over the result.

What is actually hard about it? The incredible thing that - even if you know g, p and the result - you can't recover the secret number x

I set up a little interactive element showing how g^x gets broken down by modulo operation. You can try different variable values to see how it would affect the end result:

How remainder is produced
See how 34 breaks into groups of 7
3481
34 mod 74

You can actually notice that for some values, g^x is super big. But at the end we take only little green piece - remainder from modulo operation. In some sense that's the sauce.

You can recover an x from the g^x - you just divide the result by x in a loop unless you get 1 and count how many cycles it took you. But when you loose main chunk of the result value, which is the key to getting the original power - you can't divide it in a loop no more

I'd compare it to this - it's easy to solve a Rubick's Cube if you rotate it only by X axis. Similarly - it is easy to solve it if you rotate it only by Y axis. But try to rotate it in both and then actually torn it apart and try to restore it's original state from a piece - well good luck with it - and that's essentially what we did here.

We believe that we can't do the reverse of this operation as easy as doing it the straight way, but we actually have no prove. See P = NP problem. Nonetheless we base a lot of our cryptography believing that some operations are much harder to do one way then another

You also can notice that some combination of numbers just suck. For example try to do generator (g) equals to 5 and modulus (p) equals to 10. Look at modulo result - it is always 5, because they have a common factor. Now try to put some prime number into modulus (p), like 13 or 17 - and try different exponents (x). The sequence of modulo will be quite random, but will cover all possible remainder values from 0 to p - 1 (Remember how we explored this behavior in modulo chapter?)

To the actual cryptography

Mixing secrets in the open
No side channel anymore — step through the exchange
public channelg = 5p = 23BonnieClyde
Agree on public numbers

Bonnie and Clyde agree on a generator g and a modulus p — right over the open wire. Anyone listening learns both, and that is fine: these are meant to be public.

You are the eavesdropper now
You captured everything on the wire — recover the secret
g = 5p = 23JudyNickA = 6 →← B = 11a = ?
51 mod 23 — need A = 65guesses so far: 0
The real thing
Same exchange, but with numbers nobody can brute-force
public channelg = 2p = 617 digitsWalterJesse
Standardized public numbers

In practice nobody picks g and p by hand — protocols ship standardized groups. This one is RFC 3526 group 14: g = 2 and a 2048-bit prime p, 617 digits long.

On this page