/* Written by Edward

* BEng, CSE, Faculty of Engineering, CUHK

* 本人本科小菜鸟一个，如有遗漏，欢迎指出，互相学习，谢谢

*/

Diffie-Hellman Key exchange可以说是Public Key Infrastructure的开山始祖，虽说没有涉及到具体详细的算法，但是提供了一个非常好的方向，可以说ElGamal Encryption基本上完全就是直接套用了Diffle-Hellman的核心思想，更然后才有了RSA算法，更多的介绍您可以移步百度百科或者WIKI(WIKI上的介绍更详尽)。

简而言之，人们在通信时想要加密自己的信息，然而收信方往往需要预先与发信方有一个提前商量好的加密/解密方法，以及其相对应的密钥(key)，但是在他们商量好加密/解密方法之前，他们的信息又是未加密的，怎么通过未加密的信息来传递关于加密/解密方法的信息（通常是协商确定key），避免在正式通信开始前就被敌方破解（知道key的值）呢? 这就是Diffie-Hellman Key Exchange解决的问题。

在这里小记一下自己对Diffie-Hellman Key exchange的理解

Pre-requisites:

1. 对群(group)有基本认知 （WIKI一下啦，反正我是自学的，上课时教授几页PPT就讲完了，不明觉厉啊）

2. 对Modular Arithmetic模运算有一定的认知（上课时教授几页PPT都没用就讲完了，完全不能支撑接下来的学习，于是我又WIKI了）

3. 对Diffille-Hellman Problem有一定认知

4. 对Discrete Logarithm Problem有一定的认知

那么接下来我大概简介一下3跟4、什么是Diffille-Hellman Problem，什么又是Discrete Logarithm Problem。

Diffile-Hellman Problem

这个问题说的是，如果你知道g的值、N的值、(g^x) mod N的值和(g^y) mod N的值，怎么算出(g^xy) mod N的值呢？

这被认为是一个很难解决的问题，您可以思考一下。

由于直接从(g^x) mod N和(g^y) mod N是很难算出(g^xy) mod N的值的，那么就有人开始考虑，是否可以先分别算出其中x跟y的值，然后直接去算出(g^xy) mod N的值呢？这就引申出了下面这个Discrete Logarithm Problem

Discrete Logarithm Problem

什么是Discrete Logarithm Problem呢？简单来说，就是你已知数字g、N和(g^x) mod N分别的值，但是你无法求出x的值。 

当然以上的解释是很不数学严谨的，但是直观上来讲大概就是这样的意思。这是由取模操作的特点造成的，我也无法给出具体的数学证明（毕竟数学差），但是我可以举几个例子

例如说，g = 3, N = 5, (g^x) mod N = 4

当然，你第一时间会想到x = 2啊！（3 ^ 2 = 9, 9 mod 5 = 4）

但是，很不幸的是，x = 5也行哦，x = 9也行哦，x = 13也行哦，晕了吧？往大一点，x = 28也行哦。

只要以上两个问题解决不了Diffie-Hellman Key Exchange就是不容易给攻破的（当然还有别的方法攻破）

Diffie-Hellman Key Exchange Procedure

Diffie-Hellman Key Exchange具体是怎么工作的呢？如下，设有两者A与B要进行KEY EXCHANGE

1. A选择一个g,一个N，一个x (A的secret key), 计算出X = (g^x) mod N，然后发送(g, N, X)给B

2. B收到(g, N, X)，选择一个y (B的secret key)，计算出Y = (g^y) mod N，并且把X^y = (g^x)^y mod N = (g^xy) mod N作为key,然后发送(Y)给A

3. A收到Y，计算Y^x = (g^y)^x mod N = (g^yx) mod N = (g^xy) mod N作为key，至此，A与B的key是相同的(g^xy) mod N。

就是以上三步那么简单。至此，A和B都共享同一个key = (g^xy) mod N可以用作今后通信的加密。

如果中间有一个黑客C，他窃听到了(g,N,X)和(Y),那么他可不可能知道key呢？

答案是否定的，基于Diffie-Hellman Problem跟Discrete Logarithm Problem，他既无法直接用X,Y算出key，也无法知道A与B分别的secret key x跟y，所以最后无法算出key的值。

总的来说，这种Key Exchange Protocol是安全的，但是也有许多局限性。

Man-in-the-Middle Attack （中间人攻击）

当然，由于A与B都没有验证信息(g,N,X)或者(Y)的来源，那么如果黑客C不仅仅可以窃听，还可以分别伪装成A和B跟另一方进行通信，那么这种Key Exchange就会被攻破了。

其他攻击

百度百科上还写道说此Key Exchange还容易受到重演攻击Replay Attack跟阻塞攻击(Congestion Attack? 私以为是一种Denial of Service)，具体是什么情况我还得另外了解了解……

Reference:

[1]Bruce Schneier, Applied Crptography

[2]各种维基百科