# Diffie-Hellman(-Merkle) Key Exchange Protocol

[TOC]

>This is a method to **securely generate and exchange key pairs** and is universally used not only in the field of cryptography but also computer science.

When we were discussed about symmetric encryption, we assume that 2 parties share a same secret key to do encryptions and decryptions.

DHM allows these 2 parties to generate a **shared secret key** over an insecure channel, which can be used in a symmetric encryption and is also followed afterwards by [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)), the other way to exchange keys in asymmetric encryption.

## Math Explanation
DH key exchange protocol allows 2 party to share a secret key, but what do they do in the math?

There are 2 people, **Alice** and **Bob**, who want to exchange some msg by using the same secret to encrypt and decrypt.

In fact, the process is relatively quite simple:

Terms used below
- **g**: generator
- **p**: a prime
- **a**: the secret number held by Alice
- **b**: the secret number held by Bob

1. Set up a public numbers: $g$ & $p$.
2. Alice pick a secret number $a$ to generate $g^a \pmod{p}$, we would call it $pub_A$.
3. $pub_A$ can be public sent to the communication channel because the adversaries are not able to figure out what is $a$. (due to the [discrete log problem](https://www.doc.ic.ac.uk/~mrh/330tutor/ch06s02.html))
4. Then, Bob does the same calculation to generate $pub_B = g^b \pmod{p}$.
5. Now that Alice and Bob both knows the public information of each others. Alice and Bob are able to calculate a secret Key that only known by Alice and Bob:
$$
secretKey = g^{a} \pmod{p} * g^{b} \pmod{p} \equiv g^{ab} \pmod{p} \equiv g^{ba} \pmod{p}
$$
6. Afterward, Alic and Bob both get $secretKey$ to **encrypt their messages**, yet the adversaries on the communication channel can not build this key since they don't have $a$ or $b$.

> In 2006, Hellman shout out to Merkle (The one who invented [Merkle Tree](https://en.wikipedia.org/wiki/Merkle_tree)) to help people recognize Merkle's equal contribution to the invention of public key cryptography by a new name: **Diffie-Hellman-Merkle Key Exchange**.

If you feel this one too hard, [here's](https://www.youtube.com/watch?v=NmM9HA2MQGI&list=PLzH6n4zXuckpoaxDKOOV26yhgoY2S-xYg&index=1) another version of explanation in colors

## Security
Since this key exchange algorithm is based on the **hardness of discrete logarithm**, its security is also depends on this problem.

1. `p` needs to be big enough for that *dicrete log*** problem is hard enough for the adversaries to solve the secret key.
2. In the early stage of this exchange protocol, Bob and Alice still have to exchange their public key to generate their secret key. However, if one of the public key is **not provided by Alice but the Adversary**, and Bob does not know anything about this, then Bob would send his message to the adversary.