ECDH算法介绍

1.1、椭圆曲线介绍

ECC（Elliptic Curves Cryptography，椭圆曲线加密）是一种公开密钥算法。1985年，Neal Koblitz和Victor Miller分别独立提出了ECC。基本形状可以参考如下图：

图3：椭圆曲线示例

1.2、图解椭圆曲线

椭圆曲线有两个特点：

如果你在上方随便画一个点，那么下方也一定有一个对称的点，上下方距离水平线X轴是相同的。随便在图形上画两个点，让这两个点连成线然后延长会经过第三个点，当然除了垂直线以外。

图4：曲线A点到E点步骤

根据这两个特点我们就可以做文章了。如果有A，B两个点，延长以后会经过第三个点，而这第三个点以X轴为中心是会有一个点与其对称，我们就把这个对称的点先称为C点。这里头就像是运算过程，A和B得出C，在这里我就把运算过程称为 “点运算”，A点B得到C，这个 “点运算”其实就是椭园曲线上的加法运算，但为了让你们不与传统加法运算弄混，这里先使用“点运算”的说法。

现在我们把A和C进行连线，同样经过了第三个点，第三个点也有一个对称的点，这里称为D点，也就是A点C得到D，我们再把A和D连线，也经过了第三个点，第三个点也有一个对称的点，这里称为E点，也就是A点D得到E。

问题：已知起点是A，终点是E，请问起点A经过多少次点运算得到E？我们很难知道经过了多少次，这就很符合我们前面说的公钥加密的特点：正向简单，逆向困难

图5：加密容易，解密困难

我们还要考虑一种特殊情況，如果我们取一个点，命名为P，然后画一条直线，结果发现这条直线只能与椭圆曲线相交于一个点，而不是刚刚所说的一共有三个点，这种情況怎么定义运算呢？

首先解释一下这是一条切线，如果不记得什么是切线，那就想象这里有一个圆，而切线是垂直于经过切点的半径，还不明白也没关系，现在点P身处的这条直线相交椭圆曲线后，也有一个对称的点，这里先命名为Q点， 现在重点来了！因为点P初始没有和其他点连成线，不是刚刚那种开始就有两个点来连线，因此这里就认为是P点P的运算，也就是自己点自己，所以Q就是P点P的运算结果，也就是两介P得到Q，我们就把点Q称为2P，因为是两个P得出的点，你也可以理解为P+P=2P。

图6：曲线中的切线

现在P与2P连线，也经过了第三个点，第三个点也有一个对称的点，P+2P就等于3P，这个点就是3P，那么这个过程可以一直延续下去，我们是可以得到6P这个点的，6P这个点就很有灵性了，比如3P点3P，两次的话可以得到6P，也就是3P乘以2得到6P，那2P点2P，三次的话也可以得到6P，也就是2P乘以3得到6P，其实就是简单的乘法问题，只不过是椭园曲线上的，不要小看这简单的表示方法，等会你可能就会对着屏幕说“握草”。

图7：6P的生成

1.3、笛福赫尔曼(Diffie-Hellman)算法

DH 算法又称“Diffie–Hellman 算法”，像往常的算法名字一样，这是用俩个数学牛人的名字来命名的算法，实现安全的密钥交换，通讯双方在完全没有对方任何预先信息的条件下通过不安全信道创建起一个密钥。

如下图示例：首先两个要沟通的对象需要确定两个参数，参数P和参数G，参数P，故名意思是一个质数，因为P是Prime的缩写，而参数G是Generator的缩写，这里就不详细解释G的缘由了，因为涉及到一些数学的知识。这里我选一个简单的质数23，因为23乘以1等于23，没有其它整数相乘可以得到23了，而参数G这里选择5，这两个参数是可以公开的，所以黑客知道也没关系。

图8：DH算法示例

现在就可以套用公式1了，5的随机数次方除以23来求余数，这个公式也是公开的，黑客知道也没毛病，现在两边要各自生成一个随机数，蒜老大生成了6，油大叔生成了15，各自生成的随机数套入这个公开的公式，也就是蒜老大进行5的6次方要除以23得到余数8，油大叔进行5的15次方要除以23得到余数19，各自把生成的余数发送给对方。

对方收到后套用公式2，各自收到的余数的随机数次方除以参数P求出新的余数，对于蒜老大，就是用收到的19进行6次方运算再除以23得到余数2，这里的数字6就是蒜大哥自己生成的随机数，23就是前面定义好的参数P，对于油大叔来说，就是用收到的8进行15次方运算再除以23得到余数2，这里的数字15就是油大叔自己生成的随机数，23也是前面定义好的参数P，现在大家可以看到两边得到的余数都是一样的，都是数字2，两边就可以用这个数字2来对后续的对话进行加密了，没人知道原来他们用这个2来加密后续的对话，当然了实际上的随机数和质数其实并没有这么简单，通常都建议质数至少要有2048比特的长度，就是为了防止破解。

1.4、ECDH算法

ECDH是Elliptic Curve Diffie-Hellman，它一种基于ECC的密钥协商算法。ECDH是笛福赫尔曼(Diffie-Hellman)算法的变种，它是一种密钥协商协议，定义了密钥怎么样在通信双方之间生成和交换。其思路过程与笛福赫尔曼密钥协商算法基本相同，只是在具体的协商计算中使用ECC。

如下图示例：Alice需要生成一个私钥小a，然后再确定椭圆曲线上的一个点：G，这个G点是公开的，是大家都可以有的G点，接着Alice需要生成公钥大A，公钥就利用前面说到的椭圆曲线来运算，也就是公钥大A等于小a点G，这里的意思就是G这个点进行点运算，次数是a，也就是G点G点G点…一共a次，得到了椭圆曲线上的点大A，现在Alice把大A和G发送给Bob，也就是大A和G是公开的，有同学可能就在想，别人知道大A和G，那小a不就很容易算出来吗？其实前面已经说了，一定不容易，知道起点和终点，但是中间经历多少次是非常难知道的，这就是把椭园曲线加进来的奥义。

图9：ECDH算法示例

Bob收到后，也生成了一个私钥小b，然后生成椭园曲线上的一个新点(大B），这个大B就是G点进行小b次运算得到的，也就是G点G点G点…一共b次，现在Bob把生成的大B发送给Alice，别人知道大B和大G两个点也很难得到小b，还是那句话：中间经历多少次很难知道。现在Alice用私钥小a和收到的大B进行运算得到新的密钥，Bob用私钥小b和收到的大A进行运算也得到了新的密钥，这个新的密钥就只有他们知道，也就是会话密钥，而且这个密钥必须是相同的。相信你对于这个运算还有点懵，你们看Alice这边，大B其实就等于小b点G，直接从Bob那边把等式代入就明白了，而在Bob这边，大A其实就等于小a点G，直接从Alice那边把等式代入就明白了，这样一看就知道密钥是相同的，只不过小a和小b互换了位置。如果你还看不出，假设a等于3，b等于2，不管是2乘以3，还是3乘以2，其实就等于6G了，也就是前面提及到的运算方法，这个密钥交换过程也就是ECDHE的原理，ECDHE就是椭园曲线和DH混合起来的密钥交换算法。