Day 28：Diffie–Hellman演算法

一路到了铁人赛最後阶段，最後写两个完全不同但都蛮有趣的演算法。

我们之前写到SHA家族演算法可以用来为资料加密，今天的演算法也跟加密有关，不过并不是直接用来改变资料内容，而是让通信的双方可以安全地交换金钥(key)。

想像如果A, B两个人要交换机密讯息，他们可以将讯息加密再传递，对方收到再以金钥解开(就像以钥匙开锁)，来得到真正的内容。例如双方可以约定金钥为5，当一人收到讯息"d gjqa tjp."，他可以将字母转为数字後加上5，就可以知道真正的讯息是"I love you."

姑且先不论这个金钥是否太简单，A, B双方总要以某种方式先同意金钥为何，但不管是用信件、e-mail、电话、甚至当面用讲的，金钥都还是有被窃取的风险。

上述的方法在加密和解密都是用同一个金钥，所以双方必须沟通决定，而Diffie Hellman演算法中，双方则是各有一组公开金钥(public key)和私人金钥(private key)，如此一来可以在没有任何事先资讯的情况下建立密码。它的作法是：

整个过程中，除了各自的私人金钥a, b之外，一开始约定的数字和中间交换的数字都是可以公开的，也就是以不安全的管道传递也没关系。因为运算的特性，双方最後会得到一样的结果，也就是不需要任何形式的沟通约定，就有共同秘密数字可以作为金钥使用。

数字选择合适的话(关於数字挑选细节可以参考百科)，攻击者很难用公开的部分资讯来得出私人金钥以及最终的密码，也就保障了密码系统的安全性。

Diffie Hellman是最早出现的一种公开金钥方式，它的一个缺点是过程并没有身分验证机制，也就是攻击者可以在中间与双方进行假的金钥交换来窃取讯息。不过後续以Diffie Hellman演算法为基础，也出现了许多身分验证的解决方案。

下图是以颜色表达演算法的流程，可以作为参考。过程中两人各自加入了两次只有自己知道的secret colours(用私人金钥作两次运算)，最後得到同样的颜色(共同密码)。