Static Pages

Diffie-Hellman key exchange

November 8, 2021

In the last weeks I got involved a lot of times with HTTPS and SSL/TLS, most of the time because of website certificates or trusted connections.

That got me interested in the name popping up over and over again: The Diffie-Hellman key exchange.

I started reading about it and got really intrigued: Establishing a secure connection over an insecure channel - What? How is that even possible? Everybody can see everything that's exchanged, and you still can set up a secure connection? That seems totally counter-intuitive.

There's a really good StackOverflow answer here, I recommend you go and read it. To cite:

You're not sharing information during the key exchange, you're creating a key together.

How it works

image source

  1. Alice comes up with two prime numbers g and p. Alice then picks a secret number (a) and computes g^a mod p.
  2. Alice sends the result to Bob. We'll call this A since it was calculated from a. (The primes g and p are also sent to Bob.)
  3. Bob does the same thing - he chooses his secret number b and computes the number B, which is g^b mod p.
  4. Bob sends Alice the result (called B)
  5. Now, Alice takes the number Bob sent her and does the exact same operation with it, and this is where the magic happens - B^a mod p creates K, the key which they will use from now on for communicating securely. Bob does the same operation with A which he got from Alice: A^b mod p, which will also return K.

The whole thing works because there is no efficient way to solve the discrete logarithm problem, but the parameters have to be chosen carfully (there are RFCs containing safe primes suitable for Diffie-Hellman).

Demo

Grab a friend (or open a second browser tab) and try it yourself!

Obviously, this is for demonstration only, as the numbers are far, far too small. Also, never use something you find on a random blog post for cryptographic purposes.

Step 0: Who are you?

Who are you?

You are: {{ctrl.me}}

Step 1: Alice generates p, g, b and calculates A

  • p: {{ctrl._p}}
  • g: {{ctrl._g}}
  • A: {{ctrl.A}}
  • Secret a: {{ctrl._a}} (do not share this!)

Alice is generating primes and her secret number. Nothing to do for Bob here, please continue to next step.

Step 2: First exchange

Please share p = {{ctrl._p}}, g = {{ctrl._g}} and A = {{ctrl.A}} with your friend Bob and wait for his response.

Wait for Alice to send you p, g and A and enter them here:




Step 3: Bob generates b & calculates B

Bob is generating his secret number. Nothing to do for Alice here, please continue to next step.

  • B: {{ctrl.B}}
  • Secret b: {{ctrl._b}} (do not share this!)

Step 4: Second exchange

Please enter B you get from Bob:

Please share your calculated B = {{ctrl.B}} with Alice.

Final step 5: Calculation of the key

As Alice, we can now compute the key as follows:

 B^a mod p = K 
{{ctrl.B}}^{{ctrl._a}} mod {{ctrl._p}} = {{ctrl.K}}

As Bob, we can now compute the key as follows:

 A^b mod p = K 
{{ctrl.A}}^{{ctrl._b}} mod {{ctrl._p}} = {{ctrl.K}}

The key K should now be the same for both Alice and Bob.

Exchange "secured" messages

You can now exchange messages with your new key K!

Try for example this simple XOR encryption (not secure, but still unreadable), enter a message, transmit it:


Result: {{ctrl.encrypted}}

Code

Full code is also on Github.

Further reading:

Thanks for reading!