Diffie-Hellman key exchange

Diffie-Hellman key exchange method — allows two or more parties to negotiate a secret encryption key without transferring it, or any data that might lead to it, over the network.

In this article the data transferred over the network is in blue color, the secret data that never leaves the party is in red.

First, parties MUST agree on a pair of public keys, typically abbreviated as and .

— stands for Prime and MUST be a prime number.
— goes for Generator and MUST be a Primitive root modulo .

Then each party generates its own random private secret number which must be greater than and less than .

— formula used to hash private secret and exchanges the hash with the other party(s). The same formula is used to calculate the shared secret where other party’s hash is used as generator ().

There are no way to reverse calculate the value of from the formula result. The fact that is primary root modulo means that for any value from till put in place of the formula will yield different result, what means that it would take an eavesdropper (the spying party) up to attempts to brute-force the secret value. Whereas nowadays (January 2020) the recommended size of is — 2048 bits, a number that in decimal representation could take up to 617 digits. For a comparison the number to describe a total number of atoms of the entire universe would fit in 83 digits according to universetoday.com.

At the end the entire exchange method, assuming there are two parties and their private keys abbreviated as and be , looks like this:

The practical example

As a practical example let’s assume there is Alice and Bob who need to negotiate a shared secret key, and there is Eve who’s spying to their conversation. Obviously, for the sake of simplicity we are not going to use 617 digits long .

  • Alice and Bob agree to use public keys and
  • Alice generates random private secret number
    and sends to Bob a hash
  • Bob generates random private secret number
    and sends Alice a hash
  • Alice calculates shared secret
    Bob calculates shared secret

As result

  • Alice knows: , , , , ,

  • Bob knows: , , , , ,

  • Eve knows: , , ,

Both parties never shared a private secret numbers and ended up with the same shared secret key. The data that Eve got, gives her no clue about the shared secret, except that it can be any value greater than and less than .

About key size

Various resources talk about key size, however the term itself is not explicitly mentioned in official RFC. The best clarification I found was by Xian Mu. He describes two key sizes in DH:

  • discrete log group size — goes for .
  • discrete log key size — goes for private secrets, like and .

Actual key size recommendations for today can be found at keylength.com

Real world use

Since its publication in 1976 till nowadays it grew up to de facto standard in a shared key negotiation. The most popular protocols such as SSH2 and TLS are using DH to negotiate symmetric encryption key, whereas asymmetric encryption (SSH keys and X.509 certificates) is used for server identity verification.

In august 2018 — TLS 1.3 was released, where the RSA key exchange was kicked out in favor of DH.

In March 2016 — Whitfield Diffie and Martin Hellman received ACM A.M. Turing Award for revolutionizing internet security and becoming a real pain in the ass for NSA.

© 2020 Dennis Tretyakov