Devil's Night

From the AKE we can see that Alice and Bob established a secure channel in a unprotected environment through Diffie-Hellman Key Exchange system. We can see that Diffie-Hellman is a great method (also the first) to create a safe conversation from an unsafe environment.

Assume Alice and Bob try to talk secretly, but Eve can hear every word they say.

To avoid this monitoring, Alice and Bob could do the following steps

1. Alice and Bob agree on some prime number p, and a generator g for this prime number.
2. Alice picks a value a secretly, and sends Bob A = g^a mod p
3. Bob picks a value b secretly, and sends Alice B = g^b mod p
4. Alice receives B, and Computes A’ = B^a mod p
5. Bob receives A, and Computes B’ = A^b mop p

From step 1 to step 5, we can check what values do Alice Bob and Eve know

Alice: g, p, a, A, B, A’

Bob: g, p, b, B, A, B’

Eve: g, p, A, B

It turns out that A’ = g^ab mod p = g^ba mod p = B’, so even every word between Alice and Bob is under the monitoring of Eve, but they succeed in exchange a value without letting Eve know. The rest story is easy, They can use A’(B’) as a secret key to encrypt their conversation.

but there is still a small chance for Eve to break this crypto, If Eve can get a and b from g, p A and B, then she will know the secret key of Alice and Bob.

How to get a and b from g, p, A and B, it’s the famous math problem called discrete logarithm, So the safety of Diffie-Hellman Key Exchange is based on the difficulty of solving discrete log problem.