Diffie-Hellman key exchange

16 Jan, 2020

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 p and g.

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

Each party generates its own random private secret number n which must be greater than 1 and less than p.

Both sides calculate hash for public exchange using gⁿ mod p formula. The same formula is used to calculate the shared secret where other party’s hash is used as generator (g).

There are no way to reverse calculate the value of n from the formula result. The fact that g is primary root modulo p means that for any value from 1 till p - 1 put in place of n the formula will yield different result, what means that it would take an eavesdropper (the spying party) up to p attempts to brute-force the secret value. Whereas nowadays (January 2020) the recommended size of p 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 a and be b, looks like this:

(g^a mod p)^b mod p = (g^b mod p)^a mod p

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 p.

Alice and Bob agree to use public keys p = 23 and g = 5
Alice generates random private secret number a = 6, and sends to Bob a has of it A, which is g^a mod p, in this example 5⁶ mod 23 = 8
Bob generates random private secret number b = 13, and sends to Alice a has of it B, which is g^b mod p, in this example 5¹³ mod 23 = 21
Alice calculates shared secret s, which is s = B^a mod P, in this example 21⁶ mod 23 = 18
Bob calculates shared secret s, which is s = A^b mod P, in this example 8¹³ mod 23 = 18

As result

Alice knows: p = 23, g = 5, A = 8, B = 21, a = 6, s = 18
Bob knows: p = 23, g = 5, A = 8, B = 21, b = 13, s = 18
Eve knows: p = 23, g = 5, A = 8, B = 21,

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 1 and less than 23.

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 p.
discrete log key size — goes for private secrets, like a and b.

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.