Diffie-Hellman Key Exchange

The Diffie-Hellman key exchange is a mathematical/cryptographic protocol allowing 2 people (who may have never met) to agree on a secret number (a shared secret key), without disclosing it during their exchanges (i.e. say that a person who could monitor the exchanges could not deduce the secret number). This number can then be used as an encryption key to encrypt and decrypt messages/information between the two interlocutors

Two people Alice and Bob come into contact and choose 2 numbers, a prime number $ P $ and a number $ G $ (with $ P > G $). This choice can be communicated in plain text and made public.

Alice chooses a number $ a $ at random, called the private key (kept secret), and performs the calculation $ A = G^a \mod P $ whose value $ A $ is called Alice's public key, qu he sends to Bob publicly.

Similarly, Bob chooses a random number $ b $, called the private key (also kept secret), and performs the calculation $ B = G^b \mod P $ whose value $ B $ is called the public key from Bob, which he sends to Alice publicly.

Alice received the value $ B $ and can then calculate the value $ S = B^a \mod P $

Similarly, Bob who received the value $ A $ can calculate the value $ S = A^b \mod P $

Thanks to math (and modular arithmetic), the $ S $ value is the same for Alice and Bob, it's their shared secret key. They can then communicate by encrypting their messages with this key.

The publicly exchanged values ($ P $, $ G $, $ A $ and $ B $) do not allow to calculate $ S $ as long as the 2 private keys $ a $ and $ b $ remain hidden and protected by their owners.

The main advantage of DH is to allow secure key exchange over an insecure channel.

The second advantage is the simplicity of the implementation of the algorithm.

The DHKE (Diffie-Hellman Key Exchange) protocol is vulnerable to several types of attacks:

— Man-in-the-middle attacks: an attacker intercepts the communication of the 2 parties and pretends to be the other party.

— Attack by reflection: an attacker sends a fake message asking to perform a new key exchange with himself, authentication of the parties is therefore preferable.

— Attack by precalculation/factorization: private keys are generally less than 1024 bits, precalculation of combinations with low values is possible but very costly in time and resources.

When P is a prime number, mathematical calculations are more secure. The group of integers modulo P has better properties if P is prime.

However, it is possible to use a non-prime P, but in this case, a person knowing the factorization will be able to break Diffie-Hellman.

As their name suggests, the keys are private, they are never shared publicly.

Knowing the public key does not allow calculating the private key, this is a famous mathematical problem (known as the discrete logarithm problem).

Numbers/keys can be created with a random number generator.

It is preferable to change the private key with each new communication.

Whitfield Diffie and Martin Hellman presented their method in 1976